EPFL : un nombre de 307 chiffres cassé après onze mois de calculs
4 réponses
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.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Jean-Marc Desperrier
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&NewsID40
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.
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&NewsID40
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.
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&NewsID40
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
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
According to Jean-Marc Desperrier <jmdesp@alussinan.org>:
- 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.
- 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
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.
Thomas Pornin wrote:
According to Jean-Marc Desperrier <jmdesp@alussinan.org>:
- 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.
- 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.
"(...) 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]).(...)"
On 29 mai, 16:34, Thomas Pornin <por...@nerim.net> wrote:
"(...) 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]).(...)"
"(...) 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]).(...)"
