Une équipe de la "Bundesamt für Sicherheit in der Informationstechnik" (BSI, agence fédérale pour la sécurité des techniques de l'information) a annoncé le 9 mai la factorisation d'un nombre à 200 chiffres, connu sous le nom de RSA-200.

au sommaire

    Cette équipe s'était déjà illustrée en décembre 2003 pour la factorisation d'un nombre à 174 chiffres (RSARSA-174). Bien que la multiplication a.b de deux nombres a et b constitue une opération simple, la factorisation, qui consiste à retrouver les nombres a et b à partir du produit a.b, peut se révéler très délicate, en particulier lorsque a et b sont des nombres premiers* de plusieurs dizaines de chiffres. La sécurité du système de cryptage RSA (du nom de ses concepteurs R. Rivest, A. Shamir, L. Adleman) repose précisément sur cette difficulté. En effet, un message codé selon ce principe ne peut être lu que si l'on connait une des clés, c'est-à-dire l'un des nombres a ou b.

    Afin de s'assurer que la longueur des clefs de cryptage demeure suffisamment grande pour garantir une sécurité optimale, les laboratoires RSA Security lancent depuis 1977 des défis en soumettant de grands nombres à factoriser. Ceux-ci ont été baptisés RSA suivi du nombres de décimales correspondant. RSA-100, et RSA-110, de 100 et 110 chiffres respectivement, furent par exemple les premiers nombres RSA à être factorisés en 1991 et 1992. On pensait à la fin des années 70 qu'il faudrait des millions d'années pour y parvenir. Mais de nouvelles méthodes (comme le crible quadratique) alliées à la puissance de calcul accrue des ordinateursordinateurs ont changé la donne.

    Pour encourager la recherche, une récompense est offerte à la première équipe qui trouve la factorisation d'un nombre RSA. Parmi les défis encore ouverts, citons le nombre RSA-193 (10 000 dollars) ou le monstre RSA-2048 pour lequel 200 000 dollars sont promis.

    La factorisation de RSA-200 trouvée par l'équipe allemande est la suivante:

    2799783391 1221327870 8294676387 2260162107 0446786955
    4285375600 0992932612 8400107609 3456710529 5536085606
    1822351910 9513657886 3710595448 2006576775 0985805576
    1357909873 4950144178 8631789462 9518723786 9221823983
    =

    3532461934 4027701212 7260497819 8464368671 1974001976
    2502364930 3468776121 2536794232 0005854795 6528088349
    x

    7925869954 4783330333 4708584148 0059687737 9758573642
    1996073433 0341455767 8728181521 3538140930 4740185467

    * Note: un nombre entier est premier s'il n'admet d'autres diviseurs que 1 et lui-même. Par exemple, 6=3x2 n'est pas premier, mais 7 est premier. On sait depuis EuclideEuclide qu'il existe des nombres premiers aussi grands que l'on veut. Le plus grand nombre permier connu comporte 7 816 230 chiffres (2005).