RSA Faktoring Mücadelesi - RSA Factoring Challenge

RSA Faktoring Mücadelesi tarafından ortaya atılan bir zorluktu RSA Laboratuvarları 18 Mart 1991 tarihinde hesaplamalı sayı teorisi ve pratik zorluk faktoring büyük tamsayılar ve çatlama RSA kullanılan anahtarlar kriptografi. Bir liste yayınladılar yarı mamuller (tam olarak iki olan sayılar asal faktörler ) olarak bilinir RSA numaraları, bazılarının başarılı bir şekilde çarpanlarına ayrılması için bir nakit ödül ile. En küçüğü, 100 ondalık basamaklı sayı olarak adlandırılır. RSA-100 1 Nisan 1991'de faktör haline getirildi, ancak daha büyük rakamların çoğu hala hesaba katılmadı ve oldukça uzun bir süre boyunca yüklenmeden kalması bekleniyor, ancak kuantum bilgisayarlar nedeniyle bu tahmini belirsizleştirin Shor'un algoritması.

RSA zorlukları 2007'de sona erdi.[1] RSA Laboratories şunları söyledi: "Artık sektörün ortak kriptanalitik gücü konusunda çok daha gelişmiş bir anlayışa sahip olduğuna göre simetrik anahtar ve açık anahtar algoritmaları, bu zorluklar artık aktif değil. "[2]

Faktoring zorluğunun amacı, tamsayı çarpanlara ayırmada son teknolojiyi takip etmekti. Birincil uygulama, anahtar uzunluğu of RSA açık anahtarlı şifreleme düzeni. Bu zorluktaki ilerleme, anahtar boyutları hala güvende ve ne kadar süreyle. RSA Laboratories, RSA tabanlı ürünlerin sağlayıcısı olduğu için, bu zorluk, onlar tarafından, akademik topluluğun gücünü kanıtlamak için çözümlerinin özüne saldırması için bir teşvik olarak kullanıldı.

RSA numaraları, herhangi bir ağ bağlantısı olmayan bir bilgisayarda oluşturulmuştur. Bilgisayarın sabit diski daha sonra yok edildi, böylece faktoring sorununun çözümüne ilişkin hiçbir kayıt hiçbir yerde olmayacaktı.[3]

Oluşturulan ilk RSA numaraları, RSA-100 - RSA-500 ve RSA-617, numaralarına göre etiketlendi. ondalık rakamlar; diğer RSA numaraları (RSA-576 ile başlayan) daha sonra oluşturulmuş ve numaralarına göre etiketlenmiştir. ikili rakamlar. Aşağıdaki tablodaki sayılar, bu ondalık sayıdan ikiliye kaymasına rağmen artan sırada listelenmiştir.

Matematik

RSA Laboratories şunları belirtir: her RSA numarası için nvar asal sayılar p ve q öyle ki

n = p × q.

Sorun, yalnızca verilen bu iki asalı bulmaktır. n.

Ödüller ve rekorlar

Aşağıdaki tablo tüm RSA numaralarına genel bir bakış sağlar.

Beyaz çizgilerdeki meydan okuma numaraları, 10 taban sarı çizgilerdeki meydan okuma numaraları, temel 2
RSA numarasıOndalık basamakİkili rakamlarNakit ödül teklif edildiFaktoredFaktore eden
RSA-1001003301.000 ABD doları[4]1 Nisan 1991[5]Arjen K. Lenstra
RSA-1101103644.429 abd doları[4]14 Nisan 1992[5]Arjen K. Lenstra ve HANIM. Manasse
RSA-1201203975.898 abd doları[4]9 Temmuz 1993[6]T. Denny et al.
RSA-129 [**]129426100 ABD doları26 Nisan 1994[5]Arjen K. Lenstra et al.
RSA-13013043014.527 abd doları[4]10 Nisan 1996Arjen K. Lenstra et al.
RSA-14014046317.226 abd doları2 Şubat 1999Herman te Riele et al.
RSA-150150496 16 Nisan 2004Kazumaro Aoki et al.
RSA-1551555129,383 ABD doları[4]22 Ağustos 1999Herman te Riele et al.
RSA-160160530 1 Nisan 2003Jens Franke et al., Bonn Üniversitesi
RSA-170 [*]170563 29 Aralık 2009D. Bonenberger ve M. Krone [***]
RSA-57617457610.000 ABD doları3 Aralık 2003Jens Franke et al., Bonn Üniversitesi
RSA-180 [*]180596 8 Mayıs 2010S. A. Danilov ve I.A. Popovyan, Moskova Devlet Üniversitesi[7]
RSA-190 [*]190629 8 Kasım 2010A. Timofeev ve I.A. Popovyan
RSA-64019364020.000 ABD Doları2 Kasım 2005Jens Franke et al., Bonn Üniversitesi
RSA-200 [*] ?200663 9 Mayıs 2005Jens Franke et al., Bonn Üniversitesi
RSA-210 [*]21069626 Eylül 2013[8]Ryan Propper
RSA-704 [*]21270430.000 ABD Doları2 Temmuz 2012Shi Bai, Emmanuel Thomé ve Paul Zimmermann
RSA-220 [*]220729 Mayıs 13, 2016S. Bai, P. Gaudry, A. Kruppa, E. Thomé ve P. Zimmermann
RSA-230 [*]230762 15 Ağustos 2018Samuel S. Gross, Noblis, Inc.
RSA-232 [*]232768 17 Şubat 2020[9]N. L. Zamarashkin, D. A. Zheltkov ve S. A. Matveev.
RSA-768 [*]23276850.000 ABD Doları12 Aralık 2009Thorsten Kleinjung et al.
RSA-240 [*]240795 2 Aralık 2019[10]F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé ve P. Zimmermann
RSA-250 [*]250829 28 Şub 2020[11]F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé ve P. Zimmermann
RSA-260260862 
RSA-270270895 
RSA-89627089675.000 ABD Doları
RSA-280280928 
RSA-290290962 
RSA-300300995 
RSA-3093091024 
RSA-10243091024100.000 ABD Doları
RSA-3103101028 
RSA-3203201061 
RSA-3303301094 
RSA-3403401128 
RSA-3503501161 
RSA-3603601194 
RSA-3703701227 
RSA-3803801261 
RSA-3903901294 
RSA-4004001327 
RSA-4104101360 
RSA-4204201393 
RSA-4304301427 
RSA-4404401460 
RSA-4504501493 
RSA-4604601526 
RSA-15364631536150.000 ABD Doları
RSA-4704701559 
RSA-4804801593 
RSA-4904901626 
RSA-5005001659 
RSA-6176172048 
RSA-20486172048200.000 ABD Doları

^ * Sayı, zorluk etkisiz hale geldikten sonra çarpanlara ayrıldı.

^ ** RSA-129, RSA Factoring Challenge'ın bir parçası değildi, ancak Martin Gardner'ın Bilimsel amerikalı.

^ *** RSA-170 ayrıca, iki gün sonra S. A. Danilov ve I. A. Popovyan tarafından bağımsız olarak faktörlendirildi.[7]

Ayrıca bakınız

Notlar

  1. ^ RSA Laboratuvarları, RSA Faktoring Mücadelesi Arşivlendi 2013-11-10 Wayback Makinesi. Erişim tarihi: 2013-11-09.
  2. ^ RSA Laboratuvarları, RSA Faktoring Yarışması SSS Arşivlendi 2013-11-10 Wayback Makinesi. Erişim tarihi: 2013-11-09.
  3. ^ RSA Laboratuvarları. "RSA Faktoring Yarışması SSS". Arşivlenen orijinal 2013-09-21 tarihinde. Alındı 2008-08-05.
  4. ^ a b c d e "RSA veri güvenliği faktörleme sorgulamasına ilişkin durum / haber raporu (30.03.2000 itibarıyla). 30 Ocak 2002.
  5. ^ a b c RSA Onur Listesi
  6. ^ Denny, T .; Dodson, B .; Lenstra, A. K .; Manasse, M. S. (1994). RSA-120'nin çarpanlara ayrılması hakkında. Kriptolojideki Gelişmeler - CRYPTO '93. s. 166–174. doi:10.1007/3-540-48329-2_15.
  7. ^ a b Danilov, S. A .; Popovyan, I.A. (9 Mayıs 2010). "RSA-180'in faktorizasyonu" (PDF). Cryptology ePrint Arşivi.
  8. ^ RSA-210 faktörlü, mersenneforum.org
  9. ^ INM RAS haberleri
  10. ^ Thomé, Emmanuel (2 Aralık 2019). "795-bit faktoring ve ayrık logaritmalar". cado-nfs-tartışmak (Mail listesi).
  11. ^ Zimmermann, Paul (28 Şubat 2020). "RSA-250'nin faktörize edilmesi". cado-nfs-tartışmak (Mail listesi).

Dış bağlantılar