Cryptography Problems Being Solved at Sandia National Laboratories

Sandia Ulusal Laboratuvarları’nda Çözülen Kriptografi Problemleri

Syf. 25’ten devam

Matematiğin gözlem ve deneyle hiçbir ilgisi olmayan bir bilim olduğu yönündeki bazı seçkin bilim insanlarının iddialarına rağmen, Sayılar Kuramı’nın tarihi büyük ölçüde doğa bilimleri öğrencisinin yöntemlerine yakından bağlı yöntemleri izleyenler tarafından yazılmıştır.... Sayılar Kuramı’nda önem taşıyan herhangi bir teoremin, ilk etapta listelenmiş sonuçların gözlemiyle bulunmamış olması pek olası değildir.... Her araştırmacı, bir amaçla oluşturulmuş bir tablonun neredeyse her zaman araştırmanın kârlı biçimde yürütülebileceği başka yönler önerdiği gerçeğine aşinadır.

Sayılar Kuramı, 2000 yılı aşkın süredir araştırmacıları adeta mıknatıs gibi kendine çekmiştir. Öklid, Eratosthenes, Mersenne, Fermat, Gauss, Riemann, Lucas ve daha birçok ismin adı matematik tarihinde parıldar.

Belki de bunun nedeni, asal sayıların dağılımının, doğal sayıların kendisi gibi bitmeyen bir bilmece olmasıdır. Örneğin, burada dört asal sayı vardır: 22271, 22273, 22277, 22279; bunlar 11, 13, 17, 19’a benzer. Bu dörtlü kümeler ne kadar ileri gider? Kimse bilmiyor, ancak tahmin, sonsuza dek sürdükleri yönündedir.

Sandia Ulusal Laboratuvarlarında Çözülen Kriptografi Problemleri

Edmund C. Berkeley
Editör

"Kod geliştiricileri, yetkisiz kişiler tarafından çarpanlara ayrılması muhtemelen güvenli olan, ancak muhtemelen gerekenden daha uzun olmayan sayıları kullanmak ister."

Bu rapor, Sandia Ulusal Laboratuvarları, Albuquerque, NM 87185, Uygulamalı Matematik Bölümü Başkanı Dr. Gustavus J. Simmons'un ve oradaki diğer kişilerin bana sağladığı önemli ve büyük takdir edilen yardım olmadan mümkün olmazdı. Herhangi bir yanlış ifade veya hata ise tamamen bana aittir. — ECB

Asal Sayılar

Son zamanlarda, kriptografi, bilgisayar güvenliği ve parolalardaki modern uygulamalar nedeniyle, asal sayılarla ve iki büyük asal sayının çarpımı olan sayılarla ilgili yüzyıllık problemlere ilgi yeniden canlanmıştır.

Asal sayı, kendisi ve 1 dışında başka hiçbir tam sayıya tam bölünmeyen bir tam sayıdır. 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 sayıları ilk on asal sayıdır. Diğer sayılar olan 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25 ise ilk on beş bileşik sayıdır.

Her bileşik sayı asallara ayrılabilir (1 ve kendisi sayılmadan); örneğin, 18 = 2 × 3 × 3. 2, 3, 6, 9 sayıları 18'in çarpanlarıdır. 2'nin eş çarpanı 9'dur. 3'ün bir eş çarpanı 2'dir.

Çarpanlara Ayırma

Çarpanlara ayırma zor gibi görünmeyebilir ve küçük sayılar ile belirli tablolarda listelenmiş sayılar için zor değildir. 1913'te D. W. Lehmer, 1'den 10.006.721'e kadar olan tüm asal sayıları listeleyen 133 sayfalık bir tablo yayımladı; bu, bilgisayar öncesi dönemin anıtsal bir başarısıydı ve 1956'da yeniden basıldı.

Ancak, sonunda 37 sıfır bulunan 1 gibi (10'un 37. kuvveti) kolay bileşik sayılar — ki bu, dünya tamamen kumdan oluşsaydı yaklaşık kum tanesi sayısıdır — dışında, büyük sayıların çarpanlara ayrılması son derece zor olabilir.

Örneğin 11.111 gibi bir sayıyı çarpanlara ayırmak istiyorsanız ve Lehmer'in listesi gibi sıralı bir asal sayılar listeniz varsa, 103'e kadar listedeki her asal sayıyı birer birer bölen olarak deneyebilirsiniz (çünkü bir sonraki asal olan 107 ile 107'nin çarpımı 11.449 eder). Gerçekten de 41'e ulaştığınızda, 41'in 11.111'i tam olarak 271 verdiğini bulursunuz. Böylece 11.111'i çarpanlara ayırmış olursunuz.

Ancak açıkça görüldüğü gibi, çarpanlara ayırılacak sayı büyüdükçe, çok sayıda böleni art arda deneme işi muazzam ölçüde artar. Çarpanlara ayırmanın zorluğu, şifrelenmiş bir mesajı çözmenin zorluğuyla ilişkilendirilebilir.

Büyük Sayılar

50 ve daha fazla basamaklı büyük sayıların çarpanlara ayrılması, iki anahtarlı kodlama teknikleri denilen yöntemlerde kullanılmaları nedeniyle yeni bir ilgi alanıdır. Bunlar şu alanlarda kullanılır:

• elektronik fon transferleri;
• otomatik banka vezne makineleri;
• akıllı kredi kartları;
• uzak veritabanlarına erişim;
• doğrudan borçlandırmalı satış sistemleri;
• ve diğer yerlerde.

Kod geliştiricileri, yetkisiz kişiler tarafından çarpanlara ayrılması muhtemelen güvenli olacak kadar uzun, ancak gerekenden daha uzun olmayan sayıları kullanmak ister.

Günümüzde Sandia'daki ekip, 10¹² temel assembly dili işlemi kullanarak yaklaşık 75 ondalık basamaklı sayıları çarpanlara ayırabilmektedir: toplama, kaydırma, XOR (mantıksal maskeleme işlemi) vb. Büyük kuruluşların bir kısmı tarafından (Büyük Britanya, Japonya, ABD) benimsenen yaygın bir güvenlik ölçütü 10¹⁸ temel işlemdir. Günümüzde 10¹² işlem, Cray sınıfı bir bilgisayarda yaklaşık bir günlük zamana karşılık gelir. Bir kuruluş, 10²⁴ işlemin önümüzdeki on iki yıl boyunca güvenli bir engel olarak kalacağını düşünmektedir.

Dört Dünya Rekoru

Son derece hızlı ve yetenekli bir bilgisayardan (Cray 1-S) yararlanan yeni genel amaçlı çarpanlara ayırma yordamları, Sandia ekibinin dört yeni dünya rekoru kırmasını sağlamıştır.

1. 1983'te Dr. James A. Davis ve Diane B. Holdridge, genel amaçlı bir çarpanlara ayırma yordamı tarafından ayrılan en uzun sayı için yeni bir dünya rekoru kırdı: 63 ondalık basamak uzunluğunda bir sayı. Bu sayı, 11'in 93. kuvvetine artı 1'in "zor bileşik eş çarpanı" olarak yayımlanmıştı.

2. Ardından Aralık 1983'te, aynı iki kişi 67 basamaklı bir sayıyı çarpanlara ayırdı. Bu, 1164 rakamlarıyla başlayan ve belirli bir listede "9. sayı" olarak adlandırılan bir sayıdır.

3. Daha sonra Şubat 1984'te, 2'nin 251. kuvvetinden 1 çıkarılmasıyla elde edilen sayının "zor bileşik eş çarpanı" olan 69 basamaklı bir sayıyı çarpanlara ayırdılar. Diğer iki çarpan olan 503 ve 54.217, bir yüzyıldan uzun süredir bilinmektedir. 69 basamaklı sayının 21, 23 ve 26 basamak uzunluğunda üç asal çarpanı vardır.

4. Ardından Mart 1984'te, 71 adet birden oluşan ondalık sayının tam olarak iki asal çarpanını buldular:

5. 30 basamaklı bir çarpan: 24157 31423 93627 67357 69574 39049;

6. ve 41 basamaklı bir çarpan: 45994 81134 78868 46310 22172 88952 23034 301839.

Bazı Düşünceler

Şimdi, bu kısa raporun okuru olarak siz, birinci sayıyı ikinciyle çarpıp sürenizi ölçerseniz, 71 adet birden oluşan bir dizinin elde edildiğini göreceksiniz. Ardından, bu süreyi Los Alamos Ulusal Laboratuvarı'ndaki Cray X-MP bilgisayarıyla karşılaştırabilirsiniz; burada çarpma işlemi merkezi işlemcide yaklaşık 1/100 saniyede gerçekleştirilmiştir.

Hızlı düşünen bir muhasebeci zihni için oldukça kolay bir yöntem, birinci sayının 1'den 9'a kadar olan katlarını toplama yoluyla içeren bir tablo oluşturmak ve ardından kareli kâğıt kullanarak hizalamayı sağlayıp ikinci sayının rakamlarına göre kısmi çarpımları seçmek ve sonra sütunları (71 tanesini) toplayarak elde edilen elde taşımaları ayrı bir satırda not etmektir. Elbette bu, eğer program yazılım kütüphanesinde hazır değilse, çok hassas aritmetik çarpma için bir bilgisayar programı yazmaktan daha az zaman alacaktır.

Elbette, 71 adet birden oluşan sayının iki asal çarpanını en başta bulmak, 1953’te Everest Dağı’na tırmanmak gibi bir başarıydı; daha önce hiç yapılmamış bir şeydi. Ve 8 Mart 1984’te, Sandia grubunun işbirliğiyle Los Alamos Ulusal Laboratuvarı’ndaki Cray X-MP bilgisayarında 9,5 saat sürdü.

Güncellenmiş çarpanlara ayırma algoritmasının şu anda bir adı yok gibi görünüyor, ancak "yalınlaştırılmış vektör borulaması" olarak adlandırılabilir. Sir John Hunt, 1953 Everest seferinin lideri, şöyle demişti: "Uzun süre başkalarının beceri ve ısrarına direnmiş bir problemi çözmek, insan etkinliğinin her alanında karşı konulmaz bir mıknatıstır."

Sayılar Teorisi

Doğal sayılar dünyasında (Sayılar Teorisi olarak adlandırılır) büyük sayıların çarpanlara ayrılması için burada burada özel yöntemler vardır. Ancak, 70 adet birden veya 72 adet birden oluşan büyük sayının bir çarpanını bulmak kimseyi pek etkilemezdi: 11 sayısı her ikisini de çarpanlara ayırır. 69 adet birden veya 72 adet birden oluşan bir sayı durumunda ise, 111 = 3 × 37 sayısı her ikisini de çarpanlara ayırır.

Aşağıdaki çarpanlar, yalnızca birlerden oluşan birçok büyük sayı için geçerli olacaktır:

Soru: On bir adet birden oluşan sayının çarpanları nelerdir?

Kalanları vermeyen elde taşınabilir 8 haneli hesap makinemle bunu kolayca inceleyemiyorum. Ayrıca günümüzde, yanıtların bir dergide tablo halinde listelenmiş olabileceği iyi kütüphanelere erişimim yok. Ve mikro bilgisayarımın programlanması hakkında, 11 adet birden oluşan sayıyı çarpanlara ayırmak için kolayca bir program yapacak kadar henüz yeterince bilmiyorum. (1980’de bir güç dalgalanması nedeniyle 12 yaşında ölen DEC PDP-9’umu özlüyorum.)

Matematikte Gözlem ve Deney Yapma

D. W. Lehmer, 1’den 10.006.721’e kadar olan asal sayı tablosuna yazdığı girişin sonunda bazı çok ilginç yorumlar yaptı. (Lütfen sayfa 19’a bakınız.)