Compétition de factorisation RSA
La compétition de factorisation RSA fut une compétition mise en avant par la société RSA Security jusqu'en mai 2007. Mise en place le , son but était d'encourager la recherche dans la théorie calculatoire des nombres et dans la difficulté pratique de la mise en facteurs de grands entiers. Ils publièrent une liste de nombres semi-premiers connus comme les nombres RSA dotés d'une récompense financière pour les factorisations réussies pour certains d'entre eux. Le plus petit d'entre eux, un nombre à 100 chiffres décimaux, appelé RSA-100, fut factorisé en quelques jours, mais beaucoup de nombres plus grands n'ont pas encore été factorisés et sont supposés le rester pendant encore plusieurs dizaines d'années.
Utilité[modifier | modifier le code]
Cette compétition n'était pas seulement intéressante du point de vue de la théorie des nombres, mais aussi d'un sens très pratique — comme trouver une solution est plus ou moins la même chose que de casser une clé publique RSA. L'algorithme de clé publique RSA est une pierre angulaire de beaucoup de protocoles cryptologiques — incluant certains utilisés par les systèmes financiers. Les progrès de cette compétition donnaient une indication pour savoir la taille des clés encore sûres, et pour combien de temps. Comme les laboratoires RSA sont un fournisseur de produits basé sur l'algorithme RSA, la compétition était utilisée par eux comme un stimulant pour la communauté pour attaquer le noyau de leurs solutions — entre autres pour prouver sa force.
Les compétitions RSA[modifier | modifier le code]
| Compétition | Prix | Statut | Date de factorisation | Par |
|---|---|---|---|---|
| RSA-576 | USD 10 000 | Factorisé | J. Franke et al. | |
| RSA-640 | USD 20 000 | Factorisé | F. Bahr et al. | |
| RSA-704 | USD 30 000 | Annulé | 2 juillet 2012 | Shi Bai, Emmanuel Thomé et Paul Zimmermann[1] |
| RSA-768 | USD 50 000 | Factorisé | Divers organismes[2] | |
| RSA-896 | USD 75 000 | Annulé | — | — |
| RSA-1024 | USD 100 000 | Annulé | — | — |
| RSA-1536 | USD 150 000 | Annulé | — | — |
| RSA-2048 | USD 200 000 | Annulé | — | — |
Notes et références[modifier | modifier le code]
Annexes[modifier | modifier le code]
Bibliographie[modifier | modifier le code]
- (en) Shi Bai, Emmanuel Thomé et Paul Zimmerman, « Factorisation of RSA-704 with CADO-NFS », HAL Inria, (lire en ligne [PDF])
- (en) Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev et Paul Zimmermann, « Factorization of a 768-bit RSA modulus », ePrint Report, (lire en ligne)
Articles connexes[modifier | modifier le code]
- Distributed.net est un projet de calcul distribué dont l'un des projets est la compétition de clé secrète RSA. Actuellement, les projets en cours est le RSA Lab's 72-bit RC5 Encryption Challenge (RC5-72) et la recherche des Règles de Golomb optimales (OGR-27).
