En mathématiques, les nombres RSA sont des nombres semi-premiers (c'est-à-dire des nombres qui ont exactement deux facteurs premiers), tels que ceux utilisés par le chiffrement RSA. Le but de la compétition de factorisation RSA, lancée en et organisée par la société RSA Security, était d'obtenir leur factorisation. Des récompenses étaient offertes pour les factorisations de RSA-576 à RSA-2048 jusqu'en , date à laquelle la société RSA a arrêté la compétition. Cependant des équipes ont continué et continuent depuis à travailler sur la factorisation des nombres restant.
Les premiers nombres RSA générés, de RSA-100 à RSA-500, furent baptisés en référence à leurs nombres de chiffres décimaux ; plus tard, néanmoins, en commençant avec RSA-576, les chiffres binaires furent comptés à la place. Une exception à ceci est le nombre RSA-617, qui a été créé avant le changement du schéma de numération. Problème Soit n un nombre RSA. Il existe des nombres premiers p et q tels que
Le problème est de trouver ces deux nombres premiers, connaissant seulement n.
Les prix et les records La table suivante donne une vue d'ensemble de tous les nombres RSA (les prix mentionnés étaient proposés pour une factorisation avant ): Nombre RSA Chiffresdécimaux Chiffresbinaires Prix offert Factorisé le Factorisé par RSA-100 100 330 Arjen K. Lenstra RSA-110 110 364 Arjen K. Lenstra et M. S. Manasse RSA-120 120 397 T. Denny et al. RSA-129 129 426 100 $ Arjen K. Lenstra et al. RSA-130 130 430 Arjen K. Lenstra et al. RSA-140 140 463 Herman te Riele et al. RSA-150 150 496 Kazumaro Aoki et al. RSA-155 155 512 Herman te Riele et al. RSA-160 160 530 Jens Franke et al., Université de Bonn RSA-170 170 563 D. Bonenberger et M. Krone RSA-576 174 576 10 000 $ 3 décembre, 2003 Jens Franke et al., Université de Bonn RSA-180 180 596 A. Danilov et I.A. Popovyan, Université d'État de Moscou RSA-190 190 629 I.Popovyan et A. Timofeev RSA-640 193 640 20 000 $ Jens Franke et al., Université de Bonn RSA-200 200 663 Jens Franke et al., Université de Bonn RSA-210 210 696 Ryan Propper RSA-704 212 704 (30 000 $) Shi Bai, Emmanuel Thomé et Paul Zimmermann RSA-220 220 729 S. Bai, P. Gaudry, A. Kruppa, E. Thomé et P. Zimmermann RSA-230 230 762 Samuel S. Gross et al., Noblis RSA-232 232 768 N. L. Zamarashkin, D. A. Zheltkov et S. A. Matveev RSA-768 232 768 (50 000 $) Thorsten Kleinjung et al. RSA-240 240 795 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann RSA-250 250 829 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann RSA-260 260 862 3 septembre 2026Eric Lu RSA-270 270 895 ouvert RSA-896 270 896 (75 000 $) 19 septembre 2026Steve Weis RSA-280 280 928 ouvert RSA-290 290 962 ouvert RSA-300 300 995 ouvert RSA-309 309 1024 ouvert RSA-1024 309 1024 (100 000 $) ouvert RSA-310 310 1028 ouvert RSA-320 320 1061 ouvert RSA-330 330 1094 ouvert RSA-340 340 1128 ouvert RSA-350 350 1161 ouvert RSA-360 360 1194 ouvert RSA-370 370 1227 ouvert RSA-380 380 1261 ouvert RSA-390 390 1294 ouvert RSA-400 400 1327 ouvert RSA-410 410 1360 ouvert RSA-420 420 1393 ouvert RSA-430 430 1427 ouvert RSA-440 440 1460 ouvert RSA-450 450 1493 ouvert RSA-460 460 1526 ouvert RSA-1536 463 1536 (150 000 $) ouvert RSA-470 470 1559 ouvert RSA-480 480 1593 ouvert RSA-490 490 1626 ouvert RSA-500 500 1659 ouvert RSA-2048 617 2048 (200 000 $) ouvert
Liste des nombres RSA Nombres RSA déjà factorisés RSA-100 RSA-100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
RSA-100 a été factorisé en : RSA-100 = 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061
RSA-110 RSA-110 = 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
RSA-110 a été factorisé en : RSA-110 = 6122421090493547576937037317561418841225758554253106999 × 5846418214406154678836553182979162384198610505601062333
RSA-120 RSA-120 = 227010481295437363334259960947493668895875336466084780038173258247009162675779735389791151574049166747880487470296548479
RSA-120 a été factorisé en : RSA-120 = 327414555693498015751146303749141488063642403240171463406883 × 693342667110830181197325401899700641361965863127336680673013
RSA-129 RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
RSA-129 a été factorisé en par une équipe conduite par Arjen K. Lenstra, utilisant 600 ordinateurs connectés sur Internet. et un algorithme de crible quadratique (MPQS). Un prix de USD a été attribué par RSA Security pour sa factorisation, qui a été donné à la Free Software Foundation.
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577 × 32769132993266709549961988190834461413177642967992942539798288533
L'épreuve de factorisation incluait un message chiffré avec RSA-129. Lors de son déchiffrement en utilisant la factorisation, le message se révéla être « » (les mots magiques sont « délicat ossifrage »).
RSA-130
RSA-130 = 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557
Il a été factorisé le par une équipe conduite par Arjen K. Lenstra et composée de Jim Cowie, Marije Elkenbracht-Huizing, Wojtek Furmanski, Peter Montgomery, Damian Weber et Joerg Zayer :
RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 × 45534498646735972188403686897274408864356301263205069600999044599
La factorisation a été trouvée en utilisant l'algorithme du crible sur les corps de nombres généralisé (GNFS) et le polynôme :
5748302248738405200 * X^5 + 9882261917482286102 * X^4 - 13392499389128176685 * X^3 + 16875252458877684989 * X^2 + + 3759900174855208738 * X - 46769930553931905995
qui a pour racine modulo RSA-130 : 12574411168418005980468 .
RSA-140 RSA-140 = 21290246318258757547497882016271517497806703963277216278233383215381949984056495911366573853021918316783107387995317230889569230873441936471
Il a été factorisé le par une équipe conduite par Herman te Riele et composée de Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul Leyland, Walter Lioen, Peter Montgomery, Brian Murphy et Paul Zimmermann .. La factorisation a été trouvée en utilisant l'algorithme Number Field Sieve (GNFS) et fut estimée à 2000 années MIPS de temps de calcul : RSA-140 = 3398717423028438554530123627613875835633986495969597423490929302771479 × 6264200187401285096151654948264442219302037178623509019111660653946049
RSA-150
RSA-150 = 155089812478348440509606754370011861770654545830995430655466945774312632703463465954363335027577729025391453996787414027003501631772186840890795964683 Il a été retiré de la compétition par RSA Security. RSA-150 a été factorisé en deux nombres premiers de 75 chiffres par Aoki et al. en 2004 :
RSA-150 = 348009867102283695483970451047593424831012817350385456889559637548278410717 × 445647744903640741533241125787086176005442536297766153493419724532460296199
RSA-155 RSA-155 = 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
Il a été factorisé le par une équipe conduite par Herman te Riele et composée de Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, Francois Morain, Alec Muffett, Craig Putnam, Chris Putnam et Paul Zimmermann .. La factorisation a été trouvée en utilisant l'algorithme Number Field Sieve (GNFS) et fut estimée à 8000 années MIPS de temps de calcul :
RSA-155 = 102639592829741105772054196573991675900716567808038066803341933521790711307779 × 106603488380168454820927220360012878679207958575989291522270608237193062808643
RSA-160 RSA-160 = 2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753
Il a été factorisé le par une équipe de l'Université de Bonn et la Bundesamt für Sicherheit in der Informationstechnik. . (BSI, « Office fédéral de l'information sur la sécurité ») allemand (J. Franke, F. Bahr, T. Kleinjung, M. Lochter, M. Böhm) en utilisant l'algorithme GNFS.
RSA-160 = 45427892858481394071686190649738831656137145778469793250959984709250004157335359 × 47388090603832016196633832303788951973268922921040957944741354648812028493909367
RSA-170 RSA-170 = 26062623684139844921529879266674432197085925380486406416164785191859999628542069361450283931914514618683512198164805919882053057222974116478065095809832377336510711545759
RSA-170 a une longueur de 170 chiffres décimaux. Il a été factorisé par D. Bonenberger et M. Krone de Fachhochschule Braunschweig/Wolfenbüttel. RSA-170 = 3586420730428501486799804587268520423291459681059978161140231860633948450858040593963 × 7267029064107019078863797763923946264136137803856996670313708936002281582249587494493
RSA-576 RSA-576 = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
RSA-576 possède en tout 174 chiffres. Il a été factorisé le par J. Franke et T. Kleinjung de l'Université de Bonn (Allemagne) en utilisant l’algorithme GNFS.Repost of an announcement email to the primenumbers Yahoo group :
RSA-576 = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 × 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
RSA-180 RSA-180 = 191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041
RSA-180 a une longueur de 180 chiffres décimaux et a été factorisé par S. A. Danilov et I. A. Popovyan de l'Université d'État de Moscou le S.A. Danilov and I.A. Popovyan Factorization of RSA-180 , consulté le . : RSA-180 = 400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377 × 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833
RSA-190 RSA-190 = 1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481 RSA-190 a une longueur de 190 chiffres décimaux. Il a été factorisé le par I.Popovyan from MSU, Russia et A. Timofeev du CWI aux Pays-Bas :
RSA-190 = 60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899 × 31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619
RSA-640 RSA-640 = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
RSA-640 a une longueur de 193 chiffres décimaux, il a été factorisé le .. à l'aide d'un réseau de 80La page du site rsasecurity fait référence à 30 processeurs, mais le mail d'annonce y indique bien 80. processeurs Opteron de 2,2 GHz pendant 5 mois.
L'équipe gagnante de F. Bahr, M. Boehm, J. Franke et T. Kleinjung remporta 20 000 dollars US.
RSA-640 = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 × 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571
RSA-200 RSA-200 = 27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983