it-swarm-tr.com

RSA şifrelemesini kırmak için gereken süreyi nasıl tahmin edebilirim?

RSA şifrelemesini kırmak için gereken süreyi nasıl tahmin edebilirim? Yani, Rsa şifrelemesini 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360 ve 16384 anahtar uzunluğu ile kırmak için gereken süreyi mi kastediyorum?

67
Predator

Çeşitli araştırmacılar ve kuruluşlar tarafından kullanılan temel güç tahminlerinin özeti için bu site adresine bakın.

"12μs'de 512 bit" iniz tamamen sahte. Bakalım nereden geliyor. 1999, RSA (şirket) tarafından yayınlanan ve RSA-155 olarak adlandırılan bir meydan okumada ilk 512 bit genel çarpanlaştırmanın yapıldığı yıldı (çünkü sayı 155 ondalık basamaktan oluşuyordu - ikili , uzunluk 512 bittir). Bu çarpanlara ayırma işlemi 6 ay sürdü. Aynı yıl düzenlenen Eurocrypt etkinliğinde (Mayıs ayında; o zaman 512 bit çarpanlara ayırma çabası başlamış ancak henüz tamamlanmamıştır), Adi Shamir , Weizmann'dan Enstitü, PIRILTI adlı teorik bir cihaz sundu, ki bu da bir çarpanlara ayırma çabasında biraz yardımcı olabilir. Dikkatlice seçilmiş frekanslarda, bir tür siyah tüpte yanıp sönen çok sayıda diyottan oluşmalıdır. Shamir, 10 metre uzaklıktan kahve makinesi gibi görünen özel bir cihaz getirdi. İnsanlardan ışığı kapatmasını istedi, böylece Eurocrypt katılımcısı 2, 3, 5 ve 7 saniyelik ters çevrimlerde yanıp sönen dört kırmızı diyotlara hayret edebilirdi. Ooh! ve Aah! gerçek makine, inşa edilecek olsa da, 10 veya 100'de birkaç milyon diyot ve frekans gerektireceklerdi gigahertz. Bu yüzden fikir eğlencelidir (en azından kriptolojide garip bir mizah anlayışı olduğu bilinen araştırmacılar için), ancak henüz teorik taslak adımının ötesine geçmedi. Shamir harika bir şovmen.

Ancak, TWINKLE yalnızca "yardım" dır. Bilinen en iyi çarpanlara ayırma algoritmasına Genel Sayı Alan Eleği ; sonraki iki algoritma Karesel Elek ve Eliptik Eğri Yöntemi . 512 bitlik bir sayı, günümüz teknolojisi ile QS ve ECM'nin ulaşamayacağı ve 1999'un teknolojisi ile bir fortiori. GNFS özellikle karmaşıktır ("polinom seçimi"). Bu yüzden çok akıllı beyinlerin ilk çabaları olmalı (büyük bilgisayarlarda, ancak beyinler en önemlisidir). Daha sonra GNFS iki kısımdan oluşur: elek ve doğrusal azaltma. Elek, nispeten büyük (RAM'de) olması gereken yüzlerce veya binlerce makineye paralel olarak yapılabilir, ancak bu yapılabilir. Doğrusal azaltma, bir bilgisayara sığmayacak kadar büyük bir matrisle şeyleri hesaplamayı içerir (birkaç büyüklükte ve adı geçen bilgisayarın terabayt hızlı RAM'e sahip olduğunu varsaysak bile). Matrisi (oldukça seyrek olan) sıkıştırılmış bir formatta tutmak ve yine de bunu hesaplamak için algoritmalar vardır, ancak bu zordur. 512 bit çarpanlara ayırmada, eleme toplam sürenin yaklaşık% 80'ini aldı, ancak daha büyük sayılar için doğrusal azalma darboğazdır.

TWINKLE sadece eleme parçasını hızlandırmakla ilgilidir. Doğrusal indirgeme hakkında hiçbir şey yapmaz. Başka bir deyişle, kolay (nispeten konuşma) kısmı hızlandırır. TWINKLE ile geliştirilmiş bir eleme yarısı bile 12μs'ye yakın olamaz. Bunun yerine, dört aylık bir eleme çabasını, örneğin üç haftaya indirmeyi tercih eder. Bilimsel bir şekilde iyidir, ancak özellikle daha büyük boyutlar için doğrusal küçültme hakim olduğundan, bir kayıt kırıcı değildir. 12μs rakamı, daha efsanevi bir canavar olan bir karışıklıktan geliyor gibi görünüyor, Kuantum Bilgisayar , 512 "qubit" ile bir QC oluşturulabilirse büyük sayıları kolayca etkileyebilir. D-Wave kısa süre önce 128 kubitlik bir kuantum bilgisayarı duyurdu, ancak bunların "gerçek" kübitler olmadığını ve çarpanlara ayırma için uygun olmadıklarını ortaya koydu (teorik olarak, optimizasyon problemlerinde hala etkili bazı tahminler yapabilirler, bu harika ancak temel olarak kriptografi için geçerli değildir, çünkü kriptografik algoritmalar yaklaşık değerlere uygun değildir - tek bir yanlış bit her şeyi karıştırmak için tasarlanmıştır). Şimdiye kadarki en iyi "gerçek" QC, hatırladığım kadarıyla, 5 kubite sahip olan IBM'in prototipi gibi görünüyor ve 15'in 3'ün 5'e eşit olduğunu belirleyebiliyor.

Mevcut RSA çarpanlara ayırma kaydı Aralık 2009'da açıklanan 768 bitlik bir tam sayı içindir. Dört yıl sürdü ve şu anda Dünya'da yaşayan ve bir şekilde tanrı olan Lenstra ve Montgomery de dahil olmak üzere en akıllı sayı teorisyenlerini içeriyordu. bu çevrelerdeki durum gibi. Son zamanlarda 1024 bit sayı çarpanlarına ayırma için parametrelerin seçiminin başladığını öğrendim (bu "zeki" bölüm); eleme teknik olarak mümkündür (pahalı olacaktır ve birçok üniversite kümesinde yıllarca hesaplama süresi içerecektir), ancak şimdilik, 1024 bitlik bir tam sayı için doğrusal azaltma parçasının nasıl yapılacağını bilmiyor. Bu yüzden yakın zamanda 1024 bitlik bir kırılma beklemeyin.

Şu anda, yayınlanan kodu (örneğin Msieve ) kullanan özel bir amatör, güçlü bilgisayarlara (birkaç düzine büyük PC ve en az bir saat hızlı RAM ile dolu) erişebiliyorsa 512 bit çarpanlara ayırma sağlayabilir. ) ve birkaç aylık serbest zaman; temel olarak, "özel amatör", "zengin bir üniversitede sıkılmış bilgisayar bilimi öğrencisi" anlamına gelir. 512 bitin ötesinde herhangi bir şey bir amatörün ulaşamayacağı bir yer.

Özet: kodunuzda, tüm anahtar uzunlukları için kırılma süresi olarak "neredeyse sonsuz" olarak dönebilirsiniz. Tipik bir kullanıcı 1024 bitlik RSA anahtarını kırmaz, şimdi değil on yıl sonra da kırmaz. Dünya'da, herhangi bir güvenilirlikle, düşük ancak sıfır olmayan bir olasılıkla, akla uygun olduğunu iddia edebilecek yaklaşık bir düzine insan var, bunlar olabilir Tek bir 1024- 2020 yılından önce belirli bir zamanda bit tamsayısı.

(Bununla birlikte, RSA'yı kullanan herhangi bir uygulamanın, RSA anahtarıyla hiç uğraşmadan hangi gizli verilerin kurtarılabileceği şekilde kurtarılması son derece kolaydır. 1024 bit RSA anahtarları kullanırsanız, uygulamanızın saldırıya uğradığı zaman bunun bir RSA anahtarı çarpanlarına ayırma işleminden geçmeyeceğinden emin olabilirsiniz.)

90
Thomas Pornin

Kısa cevap : En kolay yöntem asal sayı teoremi kullanmaktır, ancak bunun bir yaklaşım olduğunu unutmayın. Bu primerlerin her birini denemenizin ne kadar süreceğini tahmin edin; asal zaman * asal sayı toplam süreyi verir. Bu kaba kuvvet arama için bir tahmin verecektir.

karesel elek veya genel sayı alan eleği için çalışma süresi tahminini de kullanabilirsiniz. Bu, aslında RSA numaralarını kıran insanlar tarafından kullanılan faktoring algoritmaları için tahminler verecektir.

Uzun arka plan :

Sayı teorisi zamanı!

İlk olarak, bahsettiğiniz sayıların boyutuna bakalım. İkili olarak 1000 olan 2 ^ 3 = 8 verildiğinde, bunun dört bitlik bir sayı olduğunu görebiliriz, mümkün olan minimum. 2 ^ 2 = 4, 3 bitlik bir sayıdır (100). Bu nedenle, belirli bir x için, yeterli bite sahip olmamızı sağlamak için mümkün olan minimum değer 2 ^ (x-1) 'dir. Burada uğraştığımız sayının büyüklüğü, n yani büyüklüğünde 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. çarpanlarına.

O halde bir sonraki büyük soru n nasıl kurulur? _n=pq_, RSA tanımından bildiğiniz gibi, bu sayının faktörleri olarak iki primer arıyorsunuz. O zaman soru, bir sayının asal olduğunu nasıl belirleyebiliriz ve bunları sayabilir miyiz?

Dolayısıyla, tanım gereği __ (bazı) _x=1_ dışında herhangi bir sayı için x sayısı varsa \gcd(p, x) = 1 ise bir sayı indirgenemez. Ancak, bunu geliştirebiliriz. Herhangi bir sayı için ya birincil olsun ya da olmasın oldukça hızlı bir şekilde fark etmelisiniz. Asal değilse, o zaman gcd'si ve en az bir asal 1'den büyük olmalıdır (aksi takdirde asal olacaktır). Bundan, herhangi bir asal olmayan tam sayının bir dizi asal ile bölünebilmesi gerektiği sonucuna varıyoruz. Resmi bir matematiksel kanıt aslında buradan büyük bir sıçrama değildir.

Buna ariteminin temel teoremi denir ve konuları biraz basitleştirir. Şimdi, eğer bir sayı asal ise, artık her sayıyı denememiz gerekmiyor, sadece zaten bildiğimiz sayılar asal!

Bu açıkça hala çok yavaş, bu yüzden başka bir gözlem yapalım - çiftler halinde faktörler göz önüne alındığında, iki sayının alt kısmı en fazla sayının kare köküdür. N (doğal sayılar kümesi) ile sınırlıysak, kontrol etmemiz gereken mümkün olan en büyük değerin üst sınırını temsil eder. Şimdi, herhangi bir N sayısı için, bu listede asal olarak belirlediğimiz her sayı için 2'den başlayarak sqrt (N) 'ye doğru her tamsayıyı aramalıyız. Böylece, eğer bir asal bulursak, bunun N'nin kendisini etkileyip etkilemediğine karar verebiliriz. Bunun çalışma süresini tahmin etmeyeceğim çünkü şüphesiz yanlış bir şey söyleyeceğim, ama uzun zaman alacak.

Şimdi RSA'nın gücünü görüyorsunuz. Çok büyük bir asal seçin ve uzun bir yol elde edersiniz. Şu anda olduğu gibi, açıkça korkunç olan 2'den başlamak zorundayız.

Öncelik testi bunu çeşitli teknikler kullanarak geliştirmeyi amaçlamaktadır. Saf yöntem, az önce tartıştığımız yöntemdir. Bu tekniklerin ayrıntılı bir tartışmasının muhtemelen Matematik için daha uygun olduğunu düşünüyorum, bu yüzden özetleyeyim: tüm çalışma zamanları çöp ve bunu asal saymak için bir yol olarak kullanmak korkunç olurdu.

Bu nedenle, tam sayı faktörüne etkili bir şekilde benzediğinden, prim sayısını sonsuza dek almadan bir sayıdan daha az güvenilir bir şekilde sayamayız. Bir şekilde primerleri başka şekilde sayan bir işleve ne dersiniz?

\pi(n) = \frac{n}{\log(n) - 1.08366}, Asal Sayı Teoremi değerine bir deneme sayısını girin. Ancak bu tam olarak; böyle bir işlevin amacı, asal sayıları tam olarak saymaktır, ancak şu anda size sadece bir tahmin vermektedir. Amaçlarınız için bu yeterince iyi kabul edilebilir.

Ancak, bu kesinlikle bir yaklaşımdır. Makalenin geri kalanına bir göz atın. Diğer şeylerin yanı sıra, diğer tahminler Riemann Hipotezine bağlıdır.

Peki, tamsayı çarpanlarına ayırma ? Şimdiye kadar ikinci en iyi yönteme Karesel Elek ve en iyisi genel sayı alan eleği denir. Bu yöntemlerin her ikisi de oldukça gelişmiş matematiklere dokunmaktadır; asal faktoring konusunda ciddi olduğunuzu varsayarsak bunlara değineceğim. Şüphesiz, tahminleri hem asal sayı teoremini geliştirmede iyileştirmeler olarak kullanabilmelisiniz, çünkü büyük asalleri hesaba katacaksanız, bunları kaba kuvvet arama yerine kullanmak istiyorsunuz.

Ama kuantum hakkında bilmek istiyorum?

Tamam, yeterince adil. Bir kuantum bilgisayarda tamsayı çarpanlarına ayırma, uygulayabileceğimiz varsayılarak gülünç derecede kısa sürelerle yapılabilir Shor'un Algoritması . Ancak, bunun bir kuantum bilgisayarı gerektirdiğini belirtmeliyim. Bildiğim kadarıyla, RSA'yı kırabilecek kuantum bilgisayarların geliştirilmesi şu anda bir yol. Bakınız kuantum hesaplama gelişmeleri .

Her durumda, Shor'un Algoritması katlanarak daha hızlı olacaktır. Üzerinde bulunan sayfa, tahminlerinize dahil etmek isteyebileceğiniz çalışma zamanı için bir tahmin verir.

25
user2213

Başka bir seçenek, olası anahtarların büyük bir veritabanını oluşturmak ve bunu bir arama tablosu olarak kullanmaktır. Görünüşe göre TÜM asallara bile ihtiyacınız yok, sadece bir çift internet trafiğinin büyük bir yüzdesini alacak.

Kaynak: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny