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
- RSA sayıları , sayıların ondalık açılımları ve bilinen çarpanlara ayırmalar
- LCS35
- Sihirli Kelimeler, 1977'de ortaya çıkan başka bir RSA mücadelesine 1993'te bulunan bir çözüm olan Squeamish Ossifrage'dır.
- RSA Gizli Anahtar Mücadelesi
- Tamsayı çarpanlara ayırma kayıtları
Notlar
- ^ Kaliski, Burt (18 Mart 1991). RSA Faktoring itirazı "ilanı ' ' " . Erişim tarihi: 8 Mart 2021 .
- ^ Leyden, John (25 Tem 2001). "RSA, 200.000 $ 'lık kripto mücadelesi veriyor . Kayıt . Erişim tarihi: 8 Mart 2021 .
- ^ RSA Laboratuvarları. "Yeni RSA Faktoring Mücadelesi" . 2001-07-14 tarihinde orjinalinden arşivlendi .
- ^ RSA Laboratuvarları. "RSA Mücadele Numaraları" . 2001-08-05 tarihinde orjinalinden arşivlendi .
- ^ a b RSA Laboratuvarları. "RSA Faktoring Mücadelesi" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
- ^ a b RSA Laboratuvarları. "RSA Factoring Challenge SSS" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
- ^ RSA Laboratuvarları. "RSA Mücadele Numaraları" . 2013-09-21 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-08-05 .
- ^ 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.
- ^ a b c RSA Onur Listesi
- ^ 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 .
- ^ a b Danilov, SA; Popovyan, IA (9 Mayıs 2010). "RSA-180'in Faktorizasyonu" (PDF) . Cryptology ePrint Arşivi .
- ^ RSA-210 faktörlü , mersenneforum.org
- ^ INM RAS haberleri
-
^ 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 ) - ^ Thomé, Emmanuel (2 Aralık 2019). "795-bit faktoring ve ayrık logaritmalar" . cado-nfs-Discuss (Posta listesi).
- ^ Zimmermann, Paul (28 Şubat 2020). "RSA-250'nin ayrıştırılması" . cado-nfs-Discuss (Posta listesi).