EPFL : un nombre de 307 chiffres cassé après onze mois de calculs

Le
Saphir
Nouvel exploit en matière de décryptage : une équipe internationale, basée
notamment à l'EPFL, a réussi à extraire les nombres premiers d'un nombre
totalisant 307 chiffres. Le tour de force pourrait remettre en cause un
standard de sécurité informatique.
Plus la clé de cryptage est complexe, plus le nombre de bits est élevé, plus
il est difficile de "casser" cette sécurité, explique Pascal Vermot, attaché
de presse de l'EPFL. Factoriser signifie réduire le nombre dans les plus
petits éléments possibles, soit en nombres premiers.

L'opération a nécessité onze mois de calculs. L'équipe internationale n'a
pas voulu s'attaquer au standard 308 mais "montrer les limites actuelles de
la cryptographie", selon Pascal Vermot. Le nouveau record à 307 chiffres,
même s'il n'est pas un nombre RSA n'en représente pas moins un saut
considérable.

Les nombres RSA se définissent par leur propriété quasi incassable : ils
sont immenses et ne sont divisibles que par deux nombres premiers. Ces
facteurs sont tellement difficiles à trouver que cela leur donne une vertu
particulière pour de nombreuses applications de sécurité.

Malgré ces découvertes, le mode de cryptage à 1024 bits reste sûr pour l'
instant, estime le professeur Arjen Lenstra. Le record de factorisation pour
les nombres RSA, détenu par l'Université de Bonn, demeure à 200. Mais cela
pourrait rapidement changer.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-Marc Desperrier
Le #583072
Saphir wrote:
Nouvel exploit en matière de décryptage : une équipe internationale, basée
notamment à l'EPFL, a réussi à extraire les nombres premiers d'un nombre
totalisant 307 chiffres.


Je renvoie vers quelques liens pour des infos plus précises et donc plus
intéressantes d'un point de vue cryptographique.

Annonce officielle d'un des membres de l'équipe avec tous les détails
techniques :
http://www.crypto-world.com/announcements/m1039.txt

Article moins technique, mais avec une analyse sérieuse (contient les
commentaires de Lenstra sur ce résultat):
http://www.techworld.com/security/news/index.cfm?RSS&NewsID‰40

Les faits les plus important :

- Le nombre factorisé est le nombre de Mersenne 1039 (2^1039-1). Lenstra
estime que la difficulté de factoriser ce nombre est comparable à celle
de factoriser une clé quelconque de 700 bits

- Contrairement à ce qui est annoncé à gauche à droite, y compris sur le
site de l'EPFL, c'est un nombre de 313 chiffres (*). J'ai du mal à
comprendre comment cette erreur a pu s'introduire dans *tous* les
communiqués grand public. Ca donne l'impression désagréable qu'"on" a
pas voulu s'embéter à expliquer au public pourquoi le nombre est plus
grand que du 1024 mais plus facile à casser, et réduit arbitrairement le
nombre de chiffres à 307 (< aux 308 du 1024).

- Lenstra rappelle dans l'article suivant
(http://actualites.epfl.ch/presseinfo-com?idD1) qu'il a fallu 9 ans
pour passer de la factorisation d'un nombre de Mersenne à 155 chiffres à
la factorisation d'un nombre quelconque de 155 chiffres.
Il estime donc qu'il y a en encore pour 5 ans à 10 ans avant qu'on
arrive à factoriser un nombre de 1024 bits quelconque.
Son prochain objectif est d'abord de factoriser un nombre de 768 bits.

(*) Soyons précis, le nombre est :
58906808643168367664473872491774762471193869645981501775357568993765
84320794655559932591384900650140340063891615625817543763223144510803
88584562460719428810761069833174599222153387113189363201210623862217
39214690332885215589978237001371848062018269073686695341125238207265
91354912103343876844956209126576528293887

Voir l'annonce sur crypto-world pour les 3 facteurs, dont l'un assez
petit à 7 chiffres.

Thomas Pornin
Le #583070
According to Jean-Marc Desperrier
- Contrairement à ce qui est annoncé à gauche à droite, y compris sur le
site de l'EPFL, c'est un nombre de 313 chiffres (*). J'ai du mal à
comprendre comment cette erreur a pu s'introduire dans *tous* les
communiqués grand public.


C'est bien un nombre de 307 chiffres qui a été factorisé, et plus
précisément (2^1039-1)/5080711. Le facteur 5080711 était connu depuis
plusieurs décennies et ne faisait pas partie de la "cible". Il s'avère
simplement que le fait que 5080711 * N soit égal à 2^1039-1 a été
fortement utilisé dans le détail du calcul, mais c'est quand même N qui
a été factorisé (par extension, ça factorise tout produit de N avec un
nombre premier, par exemple 2^1039-1, mais ce n'est pas le sujet). Et ce
N fait 307 chiffres décimaux (il vaut environ 1.159 * 10^306).

Il est d'usage d'enlever les petits facteurs de ce qu'on considère comme
attaqué, parce que c'est trop facile à faire, et donc la prise en compte
de ces facteurs ne traduit pas la difficulté réelle du problème.


--Thomas Pornin

Jean-Marc Desperrier
Le #583069
Thomas Pornin wrote:
According to Jean-Marc Desperrier
- Contrairement à ce qui est annoncé à gauche à droite, y compris sur le
site de l'EPFL, c'est un nombre de 313 chiffres (*). J'ai du mal à
comprendre comment cette erreur a pu s'introduire dans *tous* les
communiqués grand public.


C'est bien un nombre de 307 chiffres qui a été factorisé, et plus
précisément (2^1039-1)/5080711.


Merci d'avoir corrigé mon erreur, et éclairci la raison pour laquelle on
parle à la fois d'un nombre de 307 chiffres et de 2^1039-1.


JPA
Le #588433
On 29 mai, 16:34, Thomas Pornin
C'est bien un nombre de 307 chiffres qui a été factorisé, et plus
précisément (2^1039-1)/5080711. Le facteur 5080711 était c onnu depuis
plusieurs décennies et ne faisait pas partie de la "cible". Il s'av ère
simplement que le fait que 5080711 * N soit égal à 2^1039-1 a été
fortement utilisé dans le détail du calcul, mais c'est quand m ême N qui
a été factorisé


Pour plus de détails: http://eprint.iacr.org/2007/205

En particulier, l'introduction répondra en partie à vos
interrogations:

"(...) We have determined the complete factorization of the Mersenne
number 21039−1
using the special number field sieve integer factorization method
(SNFS). The factor
5080711 was already known, so we obtained the new factorization of the
composite
1017-bit number (21039 −1)/5080711. The SNFS, however, cannot take
advantage of
the factor 5080711. Therefore, the difficulty of our SNFS factoring
effort is equivalent
to the difficulty of the effort that would be required for a 1039-bit
number that is very
close to a power of two. This makes our factorization the first SNFS
factorization
that reaches the 1024-bit milestone. The previous SNFS record was the
complete
factorization of the 913-bit number 6353 − 1 (cf. [1]).(...)"

Publicité
Poster une réponse
Anonyme