Nombre RSA

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir RSA.

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 mars 1991 et organisée par la société RSA Security, était d'obtenir leur factorisation. Des récompenses ont été offertes pour les factorisations de RSA-576 à RSA-2048. La compétition est interrompue depuis mai 2007.

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.

Les mathématiques[modifier | modifier le code]

Soit n un nombre RSA. Il existe des nombres premiers p et q tels que

n=pq.

Le problème est de trouver ces deux nombres premiers, connaissant seulement n.

Si s=p+q alors les valeurs de certaines fonctions arithmétiques basiques sont

d(n) = 2
\varphi(n)=(p-1)(q-1) = n + 1 - s
\sigma(n)=(p+1)(q+1) = n + 1 + s

\varphi est l'indicatrice d'Euler.

Les prix et les records[modifier | modifier le code]

La table suivante donne une vue d'ensemble de tous les nombres RSA :

Nombre RSA Chiffres
décimaux
Chiffres
binaires
Prix offert Factorisé le Factorisé par
RSA-100 100 330   Avril 1991  
RSA-110 110 364   Avril 1992  
RSA-120 120 397   Juin 1993  
RSA-129 129 426 100 $ Avril 1994 Arjen K. Lenstra et al.
RSA-130 130 430   10 avril 1996 Arjen K. Lenstra et al.
RSA-140 140 463   2 février 1999 Herman te Riele et al.
RSA-150 150 496   retiré mais factorisé en 2004
RSA-155 155 512   22 août 1999 Herman te Riele et al.
RSA-160 160 530   1er avril 2003 Jens Franke (en) et al., Université de Bonn
RSA-170 170 563   factorisé en 2009 par 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   12 mai 2010 A. Danilov et I.A. Popovyan, Université d'État de Moscou
RSA-190 190 629   Factorisé en 2010 par I.Popovyan et A. Timofeev.
RSA-640 193 640 20 000 $ 2 novembre 2005 Jens Franke et al., Université de Bonn
RSA-200 200 663   9 mai 2005 Jens Franke et al., Université de Bonn
RSA-210 210 696   26 septembre 2013 Ryan Propper
RSA-704 212 704 30 000 $ 2 juillet 2012 Shi Bai, Emmanuel Thomé et Paul Zimmermann
RSA-220 220 729   ouvert
RSA-230 230 762   ouvert
RSA-232 232 768   ouvert
RSA-768 232 768 50 000 $ 12 décembre 2009 Thorsten Kleinjung et al[1]
RSA-240 240 795   ouvert
RSA-250 250 829   ouvert
RSA-260 260 862   ouvert
RSA-270 270 895   ouvert
RSA-896 270 896 75 000 $ ouvert
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

Quelques nombres[modifier | modifier le code]

RSA-250[modifier | modifier le code]

RSA-250 a une longueur de 250 chiffres décimaux (829 bits) et n’a pas encore été factorisé.

RSA-250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447
          1 401 366 433 455 190 958 046 796 109 928 518 724 709 145 876 873 962 619 215 573 630 474 547 705 208
          0 511 905 649 310 668 769 159 001 975 940 569 345 745 223 058 932 597 669 747 168 173 806 936 489 469
          9 871 578 494 975 937 497 937

Note et référence[modifier | modifier le code]

Liens externes[modifier | modifier le code]