RSA Faktoring Mücadelesi - RSA Factoring Challenge

RSA Faktoring meydan bir meydan okuma tarafından ileri sürülen oldu RSA Laboratories içine araştırmayı teşvik etmek 18 Mart 1991 tarihinde hesaplama sayılar teorisi ve pratik zorluk faktoring büyük tamsayılar ve çatlama RSA kullanılan anahtarlar şifreleme . RSA numaraları olarak bilinen yarı suçların (tam olarak iki asal çarpana sahip sayılar) bir listesini yayınladılar ve bunlardan bazılarının başarılı bir şekilde çarpanlarına ayrılması için nakit para ödülü aldılar . Bunların en küçüğü, 100 ondalık basamaklı sayı olarak adlandırılan RSA-100 Ancak gelişmeler, daha büyük sayılar birçoğu hala çarpanlarına edilmemiş ve oldukça zaman unfactored kalması beklenmektedir 1991 1 Nisan tarafından çarpanlarına edildi kuantum bilgisayarları yapmak Shor'un algoritması nedeniyle bu tahmin belirsizdir .

2001 yılında RSA Laboratories, faktoring mücadelesini genişletti ve 576 bitten 2048 bite kadar faktoring sayıları için 10.000 ila 200.000 $ arasında değişen ödüller teklif etti.

RSA Factoring Challenges 2007'de sona erdi. RSA Laboratories, "Sektörün ortak simetrik anahtar ve açık anahtar algoritmalarının kriptanalitik gücüne ilişkin önemli ölçüde daha gelişmiş bir anlayışa sahip olduğuna göre , bu zorluklar artık aktif değil." Zorluk 2007'de sona erdiğinde, sadece RSA-576 ve RSA-640, 2001 meydan okuma numaralarından çarpanlara ayrıldı.

Faktoring zorluğunun amacı, tamsayı çarpanlara ayırmada son teknolojiyi takip etmekti. Birincil uygulama seçtiğiniz için ise anahtar uzunluğu arasında RSA açık anahtarlı şifreleme şeması. Bu zorluktaki ilerleme, hangi anahtar boyutlarının hala güvenli ve ne kadar süreyle güvenli olduğuna dair bir fikir vermelidir . 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ı.

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

Matematik

RSA Laboratories şunu belirtir: her RSA numarası n için , asal sayılar p ve q vardır, öyle ki

n = p × q .

Sorun, yalnızca n verildiğinde bu iki asalı bulmaktır .

Ödüller ve rekorlar

Aşağıdaki tablo tüm RSA numaralarına genel bir bakış sağlar. RSA Factoring Challenge'ın 2007'de sona erdiğini ve daha yüksek sayıları faktoring için başka bir ödül verilmeyeceğini unutmayın.

Beyaz çizgilerdeki meydan okuma numaraları, 10 tabanında ifade edilen sayılardır, sarı çizgilerdeki deneme numaraları ise 2 tabanında ifade edilen sayılardır.
RSA numarası Ondalık basamak İkili rakamlar Nakit para ödülü teklif edildi Faktored Faktore eden
RSA-100 100 330 1.000 ABD doları 1 Nisan 1991 Arjen K. Lenstra
RSA-110 110 364 4.429 abd doları 14 Nisan 1992 Arjen K. Lenstra ve MS Manasse
RSA-120 120 397 5.898 abd doları 9 Temmuz 1993 T. Denny vd.
RSA-129 129 426 100 ABD doları 26 Nisan 1994 Arjen K. Lenstra ve diğerleri.
RSA-130 130 430 14.527 abd doları 10 Nisan 1996 Arjen K. Lenstra ve diğerleri.
RSA-140 140 463 17.226 abd doları 2 Şubat 1999 Herman te Riele vd.
RSA-150 150 496   16 Nisan 2004 Kazumaro Aoki vd.
RSA-155 155 512 9,383 ABD doları 22 Ağustos 1999 Herman te Riele vd.
RSA-160 160 530   1 Nisan 2003 Jens Franke vd. , Bonn Üniversitesi
RSA-170 170 563   29 Aralık 2009 D. Bonenberger ve M. Krone
RSA-576 174 576 10.000 ABD doları 3 Aralık 2003 Jens Franke vd. , Bonn Üniversitesi
RSA-180 180 596   8 Mayıs 2010 SA Danilov ve IA Popovyan, Moskova Devlet Üniversitesi
RSA-190 190 629   8 Kasım 2010 A. Timofeev ve IA Popovyan
RSA-640 193 640 20.000 ABD Doları 2 Kasım 2005 Jens Franke vd. , Bonn Üniversitesi
RSA-200   ? 200 663   9 Mayıs 2005 Jens Franke vd. , Bonn Üniversitesi
RSA-210 210 696 26 Eylül 2013 Ryan Propper
RSA-704 212 704 30.000 ABD Doları 2 Temmuz 2012 Shi Bai, Emmanuel Thomé ve Paul Zimmermann
RSA-220 220 729   Mayıs 13, 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé ve P. Zimmermann
RSA-230 230 762   15 Ağustos 2018 Samuel S. Gross, Noblis, Inc.
RSA-232 232 768   17 Şubat 2020 NL Zamarashkin, DA Zheltkov ve SA Matveev.
RSA-768 232 768 50.000 ABD Doları 12 Aralık 2009 Thorsten Kleinjung ve diğerleri.
RSA-240 240 795   2 Aralık 2019 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé ve P. Zimmermann
RSA-250 250 829   28 Şub 2020 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé ve P. Zimmermann
RSA-260 260 862  
RSA-270 270 895  
RSA-896 270 896 75.000 ABD Doları
RSA-280 280 928  
RSA-290 290 962  
RSA-300 300 995  
RSA-309 309 1024  
RSA-1024 309 1024 100.000 ABD Doları
RSA-310 310 1028  
RSA-320 320 1061  
RSA-330 330 1094  
RSA-340 340 1128  
RSA-350 350 1161  
RSA-360 360 1194  
RSA-370 370 1227  
RSA-380 380 1261  
RSA-390 390 1294  
RSA-400 400 1327  
RSA-410 410 1360  
RSA-420 420 1393  
RSA-430 430 1427  
RSA-440 440 1460  
RSA-450 450 1493  
RSA-460 460 1526  
RSA-1536 463 1536 150.000 ABD Doları
RSA-470 470 1559  
RSA-480 480 1593  
RSA-490 490 1626  
RSA-500 500 1659  
RSA-617 617 2048  
RSA-2048 617 2048 200.000 ABD Doları

Ayrıca bakınız

Notlar

  1. ^ Kaliski, Burt (18 Mart 1991). RSA Faktoring itirazı "ilanı ' ' " . Erişim tarihi: 8 Mart 2021 .
  2. ^ Leyden, John (25 Tem 2001). "RSA, 200.000 $ 'lık kripto mücadelesi veriyor . Kayıt . Erişim tarihi: 8 Mart 2021 .
  3. ^ RSA Laboratuvarları. "Yeni RSA Faktoring Mücadelesi" . 2001-07-14 tarihinde orjinalinden arşivlendi .
  4. ^ RSA Laboratuvarları. "RSA Mücadele Numaraları" . 2001-08-05 tarihinde orjinalinden arşivlendi .
  5. ^ a b RSA Laboratuvarları. "RSA Faktoring Mücadelesi" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
  6. ^ a b RSA Laboratuvarları. "RSA Factoring Challenge SSS" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
  7. ^ RSA Laboratuvarları. "RSA Mücadele Numaraları" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
  8. ^ a b c d e "Durum / RSA veri güvenliği faktörleme sorunuyla ilgili haber raporu (30.03.2020 itibarıyla)" . 30 Ocak 2002.
  9. ^ a b c RSA Onur Listesi
  10. ^ Denny, T .; Dodson, B .; Lenstra, AK; Manasse, MS (1994). RSA-120'nin çarpanlara ayrılması üzerine . Kriptolojideki Gelişmeler - CRYPTO '93 . s. 166–174. doi : 10.1007 / 3-540-48329-2_15 .
  11. ^ a b Danilov, SA; Popovyan, IA (9 Mayıs 2010). "RSA-180'in Faktorizasyonu" (PDF) . Cryptology ePrint Arşivi .
  12. ^ RSA-210 faktörlü , mersenneforum.org
  13. ^ INM RAS haberleri
  14. ^ Kleinjung, Thomas (18 Şub 2010). "768 bitlik bir RSA modülünün ayrıştırılması" (PDF) . Alıntı dergisi gerektirir |journal= ( yardım )
  15. ^ Thomé, Emmanuel (2 Aralık 2019). "795-bit faktoring ve ayrık logaritmalar" . cado-nfs-Discuss (Posta listesi).
  16. ^ Zimmermann, Paul (28 Şubat 2020). "RSA-250'nin ayrıştırılması" . cado-nfs-Discuss (Posta listesi).