1024 bitlik asal sayı üretmenin zorluğu

 (glitchcomet.com)
4 puan yazan GN⁺ 2024-05-05 | 1 yorum | WhatsApp'ta paylaş
  • 2048 bitlik RSA anahtarı için gereken, yaklaşık 1024 bitlik iki asal sayıyı Rust ile doğrudan üretmeye yönelik; dış bağımlılık kullanmadan rastgele sayı üretiminden büyük tamsayı işlemlerine kadar her şeyi uygulayan bir deney
  • Basit trial division, 16 bitte yaklaşık 40 ms ile yeterliydi; ancak 64 bitte bile optimizasyondan sonra 6,4 saniye sürdü ve 1024 bite ölçeklenmesi zordu
  • Fermat testi hızlı olsa da pseudoprime sayıları eleyemeyebileceğinden, nihai kararda k=10 Miller-Rabin testi kullanıldı
  • Yerleşik tamsayı türlerinin sınırını aşmak için doğrudan BigInt yazıldı; bool dizisinden byte dizisine, ardından u64 chunk yapısına geçilerek 1024 bitlik asal üretim süresi 32 dakika seviyesinden 60-90 saniye düzeyine indirildi
  • Nihai uygulama; u64 chunk BigInt, hızlı bölme, küçük asallarla trial division, aday değeri +2 artırma ve 16 iş parçacıklı paralel çalıştırmayı birleştirerek ortalama yaklaşık 40 ms’de 1024 bitlik asal buldu; ancak doğrulanmış bir kripto kütüphanesi değildir

RSA için 1024 bitlik asalı doğrudan üretmek

  • Amaç, RSA anahtarı üretiminde kullanılabilecek bir asal sayıyı doğrudan üretmekti
    • 2048 bitlik RSA anahtarı iki asalın çarpımından oluşturulduğu için, her biri yaklaşık 1024 bit büyüklüğünde asallar gerekir
    • Zorluk doğal olarak 1024 bitlik asal üretimine daraldı
  • Deney için üç kısıt kondu
    • Kod sıfırdan yazılacak ve dış bağımlılık kullanılmayacaktı
    • Harici donanım veya bulut olmadan AMD Ryzen 7 CPU ve 16 GB RAM’e sahip bir dizüstü bilgisayar kullanılacaktı
    • Asal sayı “makul bir süre” içinde üretilecekti
  • Dil olarak o sıralar yeni öğrenilen Rust seçildi
    • Düşük seviyeli kavramlarla çalışmaya yeterince yakın, kod parçalarını anlamak içinse yeterince yüksek seviyeli olduğu düşünüldü

16 bit ve 64 bitte ortaya çıkan trial division sınırı

  • Temel akış, N bitlik rastgele sayıları tekrar tekrar üretip asallık testini geçince durmak şeklindeydi
  • Rastgele sayı, Rust’ın rand crate’i yerine Linux’taki /dev/urandom doğrudan okunarak üretildi
    • /dev/urandom, Linux çekirdeğinin CSPRNG’sine erişen sözde aygıt dosyasıdır
    • Çekirdek, kullanıcı ortamından entropi toplar ve ChaCha20 tabanlı deterministik akış şifresini periyodik olarak seed eder
  • 16 bitlik rastgele sayının ilk biti ve son biti 1 olarak ayarlandı
    • Son bit 1, tek sayı olmasını garanti etmek içindir
    • İlk bit 1, gereken bit aralığının tamamını kullanmak için bir düzenektir
  • 16 bitte 3’ten sqrt(num) değerine kadar bölmeyi deneyen trial division tek başına yaklaşık 40 ms’de asal bulmaya yetti
    • Örnek çalıştırmada Prime found: 44809, toplam süre yaklaşık 0,038 saniyeydi
  • 64 bite genişletilince basit trial division yaklaşık 30 saniye sürdü
    • Sonrasında yalnızca 6k±1 biçimindeki adayları kontrol etme ve önce küçük asal listesiyle bölmeyi deneme yöntemiyle iyileştirildi
    • İyileştirme sonrası 64 bitlik asal üretim süresi yaklaşık 6,414 saniyeydi
  • 64 bitte bile 6 saniye sürmesiyle, bu yöntemle 1024 bitlik asal üretimine ulaşmanın zor olduğu sınır açıkça görüldü

Olasılıksal asallık testine geçiş

  • Deterministik algoritmalar arasında APR-CL ve ECPP incelendi; ancak matematiksel olarak karmaşık ve erişilebilir açıklamaları az olduğundan uygulama hedefi yapmak zordu
  • OpenSSL kaynak kodu ve NIST önerileri incelendikten sonra, RSA dahil gerçek kullanım senaryolarında olasılıksal asallık testinin yaygın kullanıldığı doğrulandı
  • Bundan sonra algoritma, bir sayının “asal olduğunu kanıtlamak” yerine belirli bir doğrulukla probable prime olduğuna karar veren bir yaklaşıma dönüştü

  • Fermat testi

    • Fermat’nın küçük teoremi, p asal ve a, p’ye bölünmüyorsa a^(p-1) = 1 mod p ilişkisinin geçerli olmasını kullanır
    • Basit üs alma u128 üzerinde overflow oluşturduğu için modüler üs alma uygulandı
    • pow() üssü u32 olarak alır; u128 daha büyük bir üsse çıkarılırsa overflow oluşabilir
    • Çarpmanın kendisi de u128 aralığını aşabildiğinden, geçici olarak 64 bitlik sayıları u128 içinde saklama yöntemiyle ilerlendi
    • Fermat testi hızlıdır; ancak Fermat pseudoprime nedeniyle bileşik sayıları yanlışlıkla asal olarak değerlendirebilir
    • Bu tür bileşik sayılar nadir olsa da yeterince fazladır; yalnızca Fermat testine güvenmenin zor olduğu düşünüldü

  • Miller-Rabin testi

    • Miller-Rabin, Fermat testiyle aynı ilkeye dayanır; ancak daha güçlü bir olasılıksal asallık testi algoritması olarak kullanılır
    • Uygulama, n-1 = 2^s × d biçiminde 2’nin kuvvetlerini ayırdıktan sonra birkaç koşulu kontrol eder
    • a^d = 1 mod n
    • Veya herhangi bir 0 <= r < s için a^(2^r × d) = n - 1 mod n
    • 128 bitlik deneyde Fermat testine benzer şekilde yaklaşık 0,042 saniyede asal bulundu
    • Miller-Rabin’in en kötü hata sınırı 4^-k, büyük n için ortalamada ise 8^-k düzeyindedir
    • k=10 için ortalama hata olasılığı hesabı 0.000000000931323% idi
    • Bu, bir madeni parayı art arda 30 kez atıp hepsinin tura gelme olasılığı olan 2^-30 ile karşılaştırıldı
    • Gerçek kriptografik kullanımda rastgele base seçimi ve hasmane koşullara daha dikkatli yaklaşmak gerekir

Doğrudan BigInt yazmak

  • Rust’ın yerleşik tamsayı türleriyle 64 bitin ötesinde yeterince büyük sayılarla çalışmak zor olduğundan keyfi duyarlıklı tamsayı (BigInt) uygulaması gerekti
  • Dış bigint crate’i kullanmama kısıtı nedeniyle BigInt de doğrudan yazıldı

  • Deneme 1: rakam basamakları dizisi

    • İlk olarak büyük sayıyı ondalık rakam basamakları dizisi olarak saklama yöntemi denendi
    • Toplama ve çarpma, elle hesaplama yöntemine benzer şekilde uygulanabiliyordu; ancak bölme uygulamasında takılınca vazgeçildi

  • Deneme 2: bool tabanlı ikili dizi

    • İkinci yöntem, sayıyı 0 ve 1 dizisi olarak saklayan bir yapıydı
    • BigInt, [bool; 2048] dizisi kullanıyordu
    • 1024 bitlik sayılar birbirleriyle çarpıldığında en fazla 2048 bitlik alan gerektiği için 2048 bit ayrıldı
    • Toplama ve çıkarma full adder yöntemiyle uygulandı
    • Çarpma, ikili sayı özelliğinden yararlanılarak shift-and-add yöntemiyle işlendi
    • Bölme, ikili long division olarak uygulandı
    • Bu uygulamayla ilk 1024 bitlik asal bulunabildi; ancak çalışma süresi yaklaşık 32 dakika 44,90 saniyeydi
    • Teknik olarak hedefe ulaşılmıştı; fakat “makul süre” kısıtına uymuyordu

  • Deneme 3: byte chunk’ları

    • bool dizisindeki her bool değerinin 1 bit değil, 1 byte yer kapladığı doğrulandı
    • [bool; 2048], 2048 bit değil 2048 byte kullanıyordu
    • Sonrasında 2048 bit, 256 byte’lık bir dizide saklanacak şekilde değiştirildi
    • Toplama, çıkarma ve çarpma büyük değişiklik olmadan çalıştı; bölme ise byte chunk’larını bit listesi gibi ele alacak şekilde ayarlandı
    • Bu yöntemle 1024 bitlik asal üretim süresi 4 dakika 43 saniyeye kadar düştü

  • Deneme 4: u64 chunk’ları

    • Byte chunk yöntemi, aslında yüksek tabanlı basamaklar kullanan digit tabanlı bir BigInt idi
    • Bir sonraki aşamada 2048 bit, 32 adet u64 chunk’ında saklandı
    • Her chunk tek bir “basamak” gibi davranır
    • İki u64 chunk’ının çarpım sonucunu tutmak için u128 kullanıldı
    • Bu yapıda 1024 bitlik bir sayı, 309 ondalık basamak yerine 16 adet u64 chunk’ı ile ifade edilebilir
    • 1024 bitlik asal üretim süresi 60-90 saniyeye kadar iyileşti

Darboğaz optimizasyonu

  • Basit benchmark’ta binary uygulama ile u64 chunk uygulaması arasındaki fark belirgindi
    • a + b ve a - b: 5537.35ns → 123.57ns
    • a * b: 1292283.14ns → 842.32ns
    • a / b ve a % b: 733446.76ns → 44440.12ns
    • a < b ve a > b: 2506.02ns → 58.91ns
  • Sonraki optimizasyonlar ağırlıklı olarak bölme, çarpma, Miller-Rabin iç işlemleri ve aday üretim mantığına odaklandı

  • Bölme

    • En büyük darboğaz bölme idi
    • u64 chunk yapısında bile mevcut bölme hâlâ bit bit long division yapıyordu
    • Handbook of Applied Cryptography’nin 598. sayfasındaki algoritma referans alınarak radix tabanlı long division uygulandı
    • Dividend’in ilk 3 “basamağı” ve divisor’ın ilk 2 “basamağı” ile mevcut quotient “basamağını” tahmin eden bir yöntemdir
    • Bu uygulama, bölme başına yaklaşık 40.000 ns tasarruf sağladı
    • Divisor tek bir u64 chunk’ı ise u128 kullanarak daha doğrudan long division yapılacak şekilde özel işlem uygulandı
    • Miller-Rabin’de bu durum sıkça ortaya çıkar

  • Çarpma

    • Çarpma, ara sonuç saklamaya yarayan BigInt’i kaldıracak şekilde döngüleri yeniden düzenleyerek yaklaşık 2 kat hızlandı
    • Dolu chunk sayısı hesaplanıp yalnızca sıfır olmayan chunk’lar için döngü çalışacak şekilde değiştirildi
    • BigInt çoğunlukla 1024 bit ve altındaki sayıları sakladığından, 2048 bitlik alanın yarısı çoğu zaman boştur
    • Karatsuba veya FFT tabanlı çarpma da değerlendirildi; ancak doğrudan uygulamak karmaşıktı ve mevcut çarpmanın yeterince hızlandığı düşünüldü

  • Miller-Rabin iç optimizasyonları

    • Miller-Rabin uygulamasında maliyetli işlemleri azaltmaya odaklanıldı
    • x = mod_exp(x, 2, n) yerine doğrudan x = (x * x) % n yapıldı
    • İlk mod_exp(), fonksiyon çağrısı overhead’ini azaltmak için sadeleştirilmiş inline sürümle değiştirildi
    • Çift sayı kontrolüne num.is_even() eklenerek % 2 hesaplamasından kaçınıldı
    • d / 2, d >>= 1 olarak değiştirildi
    • += 1, -= 1 işlemleri increase() ve decrease() ile özel olarak işlendi
    • Özellikle is_even() ve d >>= 1 sırasıyla yaklaşık 70.000 ns kazanç sağladı
    • Nihai benchmark’ta u64 chunk optimize sürümü büyük ölçüde hızlandı
    • a * b: 842.32ns → 295.04ns
    • a / b ve a % b: 44440.12ns → 831.77ns
    • a / 2: 75121.58ns → 60.89ns
    • a % 2 == 0: 78400.87ns → 21.65ns
    • a - 1: 103.15ns → 67.54ns

Nihai 1024 bitlik asal üretici

  • Nihai fonksiyon önce /dev/urandom üzerinden 1024 bitlik rastgele sayı okur
    • En yüksek bit açılarak 1024 bitlik boyut garanti edilir
    • En düşük bit açılarak tek sayı olması garanti edilir
  • Ardından her seferinde yeni rastgele sayı okumak yerine, aday değere 2 eklenerek bir sonraki tek aday sayıya geçilir
    • increase_by_2() çoğu zaman yalnızca tek bir u64 chunk’ında toplama yapar
  • Miller-Rabin’den önce küçük asal listesiyle trial division uygulanır
    • Nihai kodda ilk 1000 küçük asal kullanılır
    • Küçük asallar tek bir u64 chunk’ına sığdığı için, hızlı tek chunk bölme özel işlemi kullanılabilir
  • Bu problem, paylaşılan bellek veya iş parçacıkları arası senkronizasyon gerektirmeyen embarrassingly parallel bir biçimde ele alınabilir
    • 16 CPU iş parçacığının her biri asal arar ve sonucu ilk gönderen iş parçacığının değeri kullanılır
  • Nihai çalıştırma örneği yaklaşık 0,086 saniye elapsed time kaydetti
    • CPU kullanımı %690 olarak gösterildi
  • 100 çalıştırma ortalaması 0.04109 ± 0.00307 saniyeydi
    • Ortalama olarak yaklaşık 40 ms içinde 1024 bitlik asal bulunur
    • Tekil prime_1024bit() çağrısı, rastgelelik nedeniyle yaklaşık 8 ms’den yaklaşık 800 ms’ye kadar değişebilir
    • Paralel çalıştırmayla en hızlı sonuç seçilerek dalgalanma azaltılır

Kod ve sınırlar

  • Tüm kod ve depo github’da yayımlandı
  • Tartışma bağlantıları hackernews ve reddit üzerinde bulunuyor
  • Bu uygulamanın gerçek anlamda kriptografik olarak güvenli olduğu söylenemez; amacı da kripto amaçlı bir kütüphane üretmekten çok öğrenme ve uygulama deneyidir

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-05
Hacker News yorumları

  • Büyük asal sayılar bulma işini iş ispatı fonksiyonunun parçası olarak kullanan birkaç kripto para vardı; yaklaşık 8 yıl önce yalnızca çok hızlı bir asallık testi uygulamasıyla bile epey para kazanılabiliyordu.
    Bir süre riecoin madencilik yazılımının yazarı ve bakımcısıydım; nedenini tam bilmiyorum, sanırım sadece asal sayıları sevdiğim içindi.
    Bu yazı, hızlı asallık testinin bir numaralı optimizasyonu olan Montgomery çarpımını atlamış: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
    Bu, pratik ve hızlı modüler üs alma uygulamalarının temelini oluşturur.
    O dönemde akademide olan, şimdi ise bildiğim kadarıyla Nvidia’da bulunan Niall Emmart, gerçekten inanılmaz hızlı bir GPU büyük tamsayı kütüphanesi olan CGBN’yi yayımladı: https://github.com/NVlabs/CGBN
    Hâlâ bildiğim en hızlı toplu modüler üs alma uygulaması; biraz geek’çe hayranlık edecek olursam, nefes kesici.
    Bir gün bunun sayesinde küçük bir kripto paranın üretimini yaklaşık 5 yıl boyunca nasıl domine ettiğimin hikâyesini yazmalıyım. Ayrıca Python’da pow(x, y, m) üç argümanlı biçimiyle x^y % m hesaplayan oldukça iyi bir modüler üs alma vardır.
    Bunu kullanarak, kendiniz uygulamak istediğinizde Fermat veya Miller-Rabin asallık testlerini çok kolayca yazabilirsiniz; oldukça da eğlencelidir. Kendiniz yapmak istemiyorsanız gmp kütüphanesindeki mpz_probab_prime() da iyidir. gmp doğal olarak daha hızlıdır ama büyük asal sayılarla oynarken iki satırlık Fermat testinin keyfini aşmak zordur.

    • Niall, hızlı çoklu skaler çarpma ile ilgili ZPrize kazanan gönderilerden birinde de yer aldı.
      Toplu modüler üs almaya yakındır; farkı, asal modül üzerinde değil eliptik eğriler üzerinde çalışmasıdır. Bunu CGBN çalışmasının devamı olarak görüyorum.
      Geçen yıl Stanford kriptografi öğle seminerinde iyi bir sunum yaptı; slaytlar ve kayıt da çevrimiçi.
      https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
      https://www.youtube.com/watch?v=KAWlySN7Hm8
    • Böyle kripto paraların neden bu kadar özel iş ispatı fonksiyonları kullandığını merak ediyorum.
      Kriptografinin bir şekilde asal sayılar kullandığına dair muğlak bir fikirleri olup bunların ne zaman ve neden kullanıldığını bilmedikleri için mi, yoksa daha derin bir sebep mi vardı, bilmek isterdim.
    • pow(x,e,mod) yüzünden Perl’den Python’a geçtim.

  • Verili bir maksimum sayı aralığı varsa Miller-Rabin’i fiilen deterministik yapmak basittir.
    O aralıktaki tüm sözde asalları birlikte elediği kanıtlanmış tabanları seçersiniz.
    Liste de uzun olmaz. Miller-Rabin gerçekten güçlüdür.

    • 1024 bitlik sayı aralığında bu tabanların ne olduğunu merak ediyorum.
      İnternette yanıtını bulamadım.
    • Üstelik sadece asal sayı arıyorsanız, asal gibi görünen bir adayı seçip deterministik test ile doğrulayabilirsiniz.

  • Bir satır inline assembly ile büyük tamsayılarda ilkokul usulü çarpma basitleşiyor: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
    Geçmişe dönüp C dilinde tek bir şeyi değiştirebilseydim genişletilmiş çarpma kavramını eklemek isterdim. Rust’ta da olmaması üzücü. Donanım desteği her yerde var. Cortex M0 bölme bile yapmaz ama genişletilmiş çarpması vardır.
    Bu, uzun zaman önce yazdığım çok çirkin bir oyuncak RSA uygulamasından gelen kod: https://github.com/jcalvinowens/toy-rsa
    Sadece Fermat testiyle idare edebilmesinin nedeni, asal sayılar gerçekten asal değilse algoritmanın çalışmamasıydı. Fermat testi hızlıdır; tek bir şifreleme/şifre çözme işlemi de ikisinden birinin Fermat yalancısı olmasına dair aşırı küçük olasılığı ortadan kaldırır.
    Ancak asal olmayan P/Q değerleriyle de bir mesajı başarıyla şifreleyip çözebilen RSA anahtar çiftlerinin var olmadığını kanıtlayabilir miyim bilmiyorum. Gerçek bir uygulamada elbette doğru yöntem bu olmazdı, ama bunun yanıtını hiç bulamadım.

    • İlginç biçimde C’de artık büyük tamsayılar var.
      C23’te _BitInt(N) tipi eklendi; örneğin 128 baytlık tip olarak _BitInt(1024) kullanılabiliyor.
      Ancak derleyici desteği sınırlı. Clang’de N değerinin 128’den büyük olmasına izin vermek için -fexperimental-max-bitint-width=N bayrağı verilebiliyor. N 128’den büyükken _BitInt(N) değerlerini bölerseniz derleyici düpedüz çöküyor, ama +, -, * beklendiği gibi çalışıyor.
    • Zig’de bu nispeten kolay.
      @mulWithOverflow yerleşik fonksiyonu var; sonuçla birlikte taşma bitini döndürüyor ve tamsayılar (u|i)65535 değerine kadar mevcut.
      Yaptığınız işe bağlı olarak taşmayı algıladıktan sonra daha büyük bir tipe yükseltebilir ya da önce yükseltip sonra isteğe bağlı olarak kırpabilirsiniz.
      Ayrıca ayrı operatörler olarak *| ile doygunluklu çarpmayı, *% ile sarmalı çarpmayı destekliyor. Bu tür semantiklere ihtiyaç olduğunda kullanılabilir. Diğer taşmalar güvenlik denetimine tabi tanımsız davranış sayılır; Debug ve ReleaseSafe derleme modlarında panic oluşur.
    • p ve q aralarında asal Carmichael sayıları ise RSA yine de mesajları başarıyla şifreleyip çözebilir.
      Ancak p*q daha küçük asal çarpanlara sahip olacağından çarpanlara ayırmak kolaylaşır ve bu yüzden güvenlik düşer.
    • Bildiğim kadarıyla çoğu C derleyicisinde ve Rust’ta, daha büyük bir tipe cast edip çarptığınızda tam olarak istediğiniz makine kodu komutu üretilir.
    • Philip Zimmermann’ın 1994 tarihli özgün Pretty Good Privacy(PGP) sürümü, bilinen tüm 16 bitlik asal sayılara bölme yapan yalnızca bir elek kullanıyordu; bu tablo da Eratosthenes eleğiyle oluşturulmuştu. Ardından Fermat testi uygulanıyordu.

  • Bu işin ne kadar sürdüğünü merak ediyorum
    Lisans araştırma projesi olarak büyük tamsayı çarpımı yapmıştım ve neredeyse iki dönem sürmüştü. Karatsuba, Toom-Cook, karmaşık FFT, birkaç NTT ve Schonhage-Strassen uygulamıştım
    Asallar neredeyse matematik büyüsü gibi. İlgilenenler için Silverman'ın A Friendly Introduction to Number Theory kitabı harika bir matematik kitabı
    Bu arada sayfadaki bağlantı 40250519 değil 4025051 olarak verilmiş

  • Güzel yazı. Ben de yakın zamanda [0]'ın ilk sürümü için biraz kendi büyük tamsayı kodumu yazdım; matematik makalelerindeki üst düzey açıklamaları gerçek işlemlere dönüştürmenin ne kadar sinir bozucu olduğunu hatırlıyorum
    Yalnız küçük bir itirazım var
    u64'ün tüm aralığını kullanıyorsanız sayı 2^64-1 tabanında değil, 2^64 tabanındadır. Her word 0'dan 2^64-1'e kadar değer alır; tıpkı onluk sistemde her basamağın 0'dan 9'a kadar olması gibi
    [0] https://github.com/LegionMammal978/bigfoot-sim

  • Son optimizasyondaki gibi başarısız olunca yeni rastgele sayı üretmek yerine sayıyı 2 artırmak güvenliği biraz zedeler
    Asallar eşit dağılmadığı için, büyük asal aralıklarının hemen arkasındaki asallara doğru bir yanlılık oluşur

    • Araştırırken bunu okumuştum
      Çalışma hızı ile asalların rastgeleliği arasında bir ödünleşim; 16 thread'in her birinin rastgele bir sayıdan başlayıp asal bulmak için yarışmasının yeterince rastgelelik eklediğini düşünüp hızı seçtim
      Hızdan çok rastgelelik istiyorsanız +=2'yi rng() çağrısıyla değiştirmek kolay bir değişiklik

  • Güzel ve iyi yazılmış bir yazı
    Yazarın base-255 değil base-256 demek istediğini sanıyorum

  • Birkaç 1–2 KB'lık sayı L1 cache'e rahatlıkla sığar; sığmasa bile erişim süresi yaklaşık 3 ns olan megabaytlarca L2 cache var
    Yazıda L1 cache miss'leri nedeniyle RAM okuma/yazma beklenmiş olabileceği söylenmiş, ama sonra bu noktaya geri dönülmüyor
    Ayrıca bu yalnızca asal üretimini ele aldığı için RSA'in tuzaklarının çoğundan kaçınıyor ve urandom güvenli olmalı. Kod düzgün çalışıyorsa çok büyük yanlış yapılabilecek fazla yer yok
    RSA'de kaçınılması gereken zayıf asallar ile ilgili bazı sorunlar var, ama burada gerçekten sorun olacak kadar yaygın olup olmadıklarını bilmiyorum

  • Birkaç on yıl önceki üniversite birinci sınıf projemi hatırlattı
    Proje ortağım, arkadaşım ve sonradan mezuniyet konuşmacısı olan kişi fikri ortaya atmış ve temel matematiği uygulamıştı; amaç 4096 bit RSA şifreleme yapmaktı
    Son uygulamada asal üretiminin ne kadar yavaş olduğunu hatırlıyorum. PA-RISC iş istasyonunda üretim yaklaşık 20 dakika sürüyordu
    Matematik meraklısı arkadaşım proje bittikten sonra da kodu optimize etmeye devam etti; asallık testi ve büyük tamsayı matematiği uygulamaları üzerine makaleler okuduğunu hatırlıyorum
    Örneğin bileşen çarpımında sayılardan biri 0 ise çarpımı atlayıp sonucu 0 vermek muazzam bir iyileştirme sağlamıştı

    • Yavaş donanımda eliptik eğri anahtarları üretmek çok daha iyi
      Ya da uzun süre beklersiniz, ya da geleceğe dayanacak güvenlikten fedakârlık edersiniz

  • Düşük biti 1 olarak ayarlamayı anlıyorum. Çünkü çift sayılar asla asal değildir; elbette 2 istisna
    Ama yüksek bitin neden 1 olarak ayarlandığını bilmiyorum. Asallar ya da kripto konusunda uzman değilim, ama gereksiz yere 1 bit entropiden vazgeçmek gibi görünüyor. Neyi kaçırıyorum?

    • Yüksek bit her zaman ayarlıysa ve asal o bit dahil edilerek kodlanıyorsa, asal her zaman aynı bayt sayısıyla kodlanır
      Değişken uzunluklu bayt kodlaması, spesifikasyon çok net değilse ve iyi test edilmemişse farklı yazılımlar arasında veri alışverişinde sorun çıkarabilir
      Sunucu açık anahtarında başta 0 bulunduğunda RSA tabanlı DHE'de oluşan sorunlara bakın
    • İki basamaklı bir sayı üretmek gibi
      İlk basamak 0 ise iki basamaklı sayı değildir
    • İlk biti 1 olarak ayarlamak 1 bit entropi kaybettirir, ama asalın yeterince büyük olmasını garanti eder
      Bir de RSA'de iki asal çarpılır. Biri 1024 bit ise, yanlış hatırlamıyorsam diğeri yaklaşık 200 bit olsa bile anahtar için gereken entropi bit sayısına ulaşılabilir
      Bu yüzden iki asalın ikisini de 1024 bit yapmak biraz güvenlik payı da sağlar
    • 1 bit entropiden vazgeçildiği doğru, ama yine de 1022 bit kalıyor
      Biri 1024 bit asal istemişken 1020 bit asal da olur mu diye düşünmektense bu taraf daha güvenli görünüyor. Genelde 00042'yi 5 basamaklı sayı saymayız
      Teknik olarak tam olarak nerede kullanılacağına göre en iyi seçim değişebilir, ama yazıdaki yöntem daha güvenli bir varsayılan gibi görünüyor
    • Sonuçta 50 bitlikte kalmayan bir asal üretmek için 1 bit entropi kaybetmek gayet makul bir ödünleşim gibi görünüyor