Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Au sujet des 0.2% des clés RSA faibles
21 views
Skip to first unread message
Kevin Denis
Feb 26, 2012, 8:21:25 AM2/26/12
to
Bonjour,
je suppose que vous avez lu: http://eprint.iacr.org/2012/064 , ou
< https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs >
Je ne suis pas sûr de bien comprendre le problème.
J'ai appris que la solidité de RSA repose sur le fait qu'il est très
difficile de factoriser un très grand nombre composé de deux très
grands nombres premiers. Bien.
Les auteurs du papier ci dessus ont téléchargés un très grand nombre
de clés publiques RSA et ont effectués des PGCD entre chacune des
paires possibles. Si on trouve un PGCD différent de 1, alors cela
signifie que les deux nombres ont un facteur en commun, et de fait, on
retrouve les diviseurs de chacune des deux clés.
Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
on retrouve a et b, puis découle les clés privées de A et B.
RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
des facteurs communs.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
et B. Pourquoi ce moyen serait il plus rapide que de calculer les
facteurs premiers de A et B?
La seconde chose qui m'étonne concerne l'explication de la faiblesse. Il
est indiqué qu'un mauvais générateur aléatoire créerait ses clés comme
cela:
prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
N = p*q
Avec l'explication suivante:
Si le (seed) est mauvais, alors on peut connaître N et tous les
équipements utilisant cette méthode auraient le même 'N'.
Certes, mais faut il encore que le seed soit mauvais partout, et de la
même manière sur tous les équipements employant la méthode.
La seconde méthode, utilisée pour augmenter la sécurité est la
suivante:
prng.seed(seed)
p = prng.generate_random_prime()
prng.add_randomness(bits)
q = prng.generate_random_prime()
N = p*q
Avec l'explication:
Si le seed est mauvais, alors p est identique entre tous les équipements
employant cet algo, et q change. Si on a plusieurs clés d'un équipement,
on calcule le PGCD de ces clés et on retrouve chacun des 'p' et 'q'.
Encore une fois, il faut que le seed soit tout le temps mauvais de la
même manière. L'article continue en indiquant:
"OpenSSL's RSA key generation functions this way: each time random bits
are produced from the entropy pool to generate the primes p and q, the
current time in seconds is added to the entropy pool. Many, but not all,
of the vulnerable keys were generated by OpenSSL and OpenSSH, which
calls OpenSSL's RSA key generation code."
On parle donc bien de la seconde manière dont est générée le 'q'
puisque add_randomness(seconds) est utilisé, mais d'où viendrait
le faible prng.seed(seed) faible?
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
publique ssh en différents endroits, et la clé publique de mon
serveur est accessible. Cela signifie qu'au moins plusieurs
personnes en ont deux, et peuvent donc faire le PGCD afin de
retrouver mes clés privées?
Merci pour toute remarque, précisions sur ce sujet.
--
Kevin
je suppose que vous avez lu: http://eprint.iacr.org/2012/064 , ou
< https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs >
Je ne suis pas sûr de bien comprendre le problème.
J'ai appris que la solidité de RSA repose sur le fait qu'il est très
difficile de factoriser un très grand nombre composé de deux très
grands nombres premiers. Bien.
Les auteurs du papier ci dessus ont téléchargés un très grand nombre
de clés publiques RSA et ont effectués des PGCD entre chacune des
paires possibles. Si on trouve un PGCD différent de 1, alors cela
signifie que les deux nombres ont un facteur en commun, et de fait, on
retrouve les diviseurs de chacune des deux clés.
Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
on retrouve a et b, puis découle les clés privées de A et B.
RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
des facteurs communs.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
et B. Pourquoi ce moyen serait il plus rapide que de calculer les
facteurs premiers de A et B?
La seconde chose qui m'étonne concerne l'explication de la faiblesse. Il
est indiqué qu'un mauvais générateur aléatoire créerait ses clés comme
cela:
prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
N = p*q
Avec l'explication suivante:
Si le (seed) est mauvais, alors on peut connaître N et tous les
équipements utilisant cette méthode auraient le même 'N'.
Certes, mais faut il encore que le seed soit mauvais partout, et de la
même manière sur tous les équipements employant la méthode.
La seconde méthode, utilisée pour augmenter la sécurité est la
suivante:
prng.seed(seed)
p = prng.generate_random_prime()
prng.add_randomness(bits)
q = prng.generate_random_prime()
N = p*q
Avec l'explication:
Si le seed est mauvais, alors p est identique entre tous les équipements
employant cet algo, et q change. Si on a plusieurs clés d'un équipement,
on calcule le PGCD de ces clés et on retrouve chacun des 'p' et 'q'.
Encore une fois, il faut que le seed soit tout le temps mauvais de la
même manière. L'article continue en indiquant:
"OpenSSL's RSA key generation functions this way: each time random bits
are produced from the entropy pool to generate the primes p and q, the
current time in seconds is added to the entropy pool. Many, but not all,
of the vulnerable keys were generated by OpenSSL and OpenSSH, which
calls OpenSSL's RSA key generation code."
On parle donc bien de la seconde manière dont est générée le 'q'
puisque add_randomness(seconds) est utilisé, mais d'où viendrait
le faible prng.seed(seed) faible?
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
publique ssh en différents endroits, et la clé publique de mon
serveur est accessible. Cela signifie qu'au moins plusieurs
personnes en ont deux, et peuvent donc faire le PGCD afin de
retrouver mes clés privées?
Merci pour toute remarque, précisions sur ce sujet.
--
Kevin
Mehdi Tibouchi
Feb 26, 2012, 10:14:40 PM2/26/12
to
Kevin Denis wrote in message
<slrnjkkfsb...@slackwall.local.tux>:
> Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
> et B. Pourquoi ce moyen serait il plus rapide que de calculer les
> facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des
PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
PGCD de deux entiers de n bits en temps quasi-linéaire en n.
En revanche, on ne connaît pas d'algorithme efficace pour la
factorisation. Le meilleur dont on dispose actuellement a une complexité
en quelque chose comme exp(n^{1/3}).
> Certes, mais faut il encore que le seed soit mauvais partout, et de la
> même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les
clefs produites soient identiques.
> De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
> publique ssh en différents endroits, et la clé publique de mon
> serveur est accessible. Cela signifie qu'au moins plusieurs
> personnes en ont deux, et peuvent donc faire le PGCD afin de
> retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun,
heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa
faibles qui aboutissent occasionnellement à des facteurs communs.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre
clef RSA quelque part, mais ce n'est vraisemblable que si elle a été
générée sur un système dont le générateur aléatoire n'ait pas eu assez
d'entropie. Il semblerait d'après le billet de Heninger que cela concerne
principalement des systèmes embarqués.
--
M. Tibouchi.
<slrnjkkfsb...@slackwall.local.tux>:
>
> Les auteurs du papier ci dessus ont téléchargés un très grand nombre
> de clés publiques RSA et ont effectués des PGCD entre chacune des
> paires possibles. Si on trouve un PGCD différent de 1, alors cela
> signifie que les deux nombres ont un facteur en commun, et de fait, on
> retrouve les diviseurs de chacune des deux clés.
> Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
> on retrouve a et b, puis découle les clés privées de A et B.
> RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
> des facteurs communs.
Pas juste « affaibli », complètement cassé.
> Les auteurs du papier ci dessus ont téléchargés un très grand nombre
> de clés publiques RSA et ont effectués des PGCD entre chacune des
> paires possibles. Si on trouve un PGCD différent de 1, alors cela
> signifie que les deux nombres ont un facteur en commun, et de fait, on
> retrouve les diviseurs de chacune des deux clés.
> Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
> on retrouve a et b, puis découle les clés privées de A et B.
> RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
> des facteurs communs.
> Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
> et B. Pourquoi ce moyen serait il plus rapide que de calculer les
> facteurs premiers de A et B?
PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
PGCD de deux entiers de n bits en temps quasi-linéaire en n.
En revanche, on ne connaît pas d'algorithme efficace pour la
factorisation. Le meilleur dont on dispose actuellement a une complexité
en quelque chose comme exp(n^{1/3}).
> Certes, mais faut il encore que le seed soit mauvais partout, et de la
> même manière sur tous les équipements employant la méthode.
clefs produites soient identiques.
> De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
> publique ssh en différents endroits, et la clé publique de mon
> serveur est accessible. Cela signifie qu'au moins plusieurs
> personnes en ont deux, et peuvent donc faire le PGCD afin de
> retrouver mes clés privées?
heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa
faibles qui aboutissent occasionnellement à des facteurs communs.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre
clef RSA quelque part, mais ce n'est vraisemblable que si elle a été
générée sur un système dont le générateur aléatoire n'ait pas eu assez
d'entropie. Il semblerait d'après le billet de Heninger que cela concerne
principalement des systèmes embarqués.
--
M. Tibouchi.
Kevin Denis
Feb 27, 2012, 10:26:36 AM2/27/12
to
Le 27-02-2012, Mehdi Tibouchi <med...@alussinan.org> a écrit :
>> Les auteurs du papier ci dessus ont téléchargés un très grand nombre
>> de clés publiques RSA et ont effectués des PGCD entre chacune des
>> paires possibles. Si on trouve un PGCD différent de 1, alors cela
>> signifie que les deux nombres ont un facteur en commun, et de fait, on
>> retrouve les diviseurs de chacune des deux clés.
>> Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
>> on retrouve a et b, puis découle les clés privées de A et B.
>> RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
>> des facteurs communs.
>
> Pas juste « affaibli », complètement cassé.
>
>> Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
>> et B. Pourquoi ce moyen serait il plus rapide que de calculer les
>> facteurs premiers de A et B?
>
> On connaît depuis fort longtemps un algorithme rapide pour le calcul des
> PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
> PGCD de deux entiers de n bits en temps quasi-linéaire en n.
>
bon, wikipedions la division d'Euclide.
>> Les auteurs du papier ci dessus ont téléchargés un très grand nombre
>> de clés publiques RSA et ont effectués des PGCD entre chacune des
>> paires possibles. Si on trouve un PGCD différent de 1, alors cela
>> signifie que les deux nombres ont un facteur en commun, et de fait, on
>> retrouve les diviseurs de chacune des deux clés.
>> Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
>> on retrouve a et b, puis découle les clés privées de A et B.
>> RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
>> des facteurs communs.
>
> Pas juste « affaibli », complètement cassé.
>
>> Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
>> et B. Pourquoi ce moyen serait il plus rapide que de calculer les
>> facteurs premiers de A et B?
>
> On connaît depuis fort longtemps un algorithme rapide pour le calcul des
> PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
> PGCD de deux entiers de n bits en temps quasi-linéaire en n.
>
> En revanche, on ne connaît pas d'algorithme efficace pour la
> factorisation. Le meilleur dont on dispose actuellement a une complexité
> en quelque chose comme exp(n^{1/3}).
>
>> Certes, mais faut il encore que le seed soit mauvais partout, et de la
>> même manière sur tous les équipements employant la méthode.
>
> Non, il suffit que le seed soit le même juste deux fois pour que les
> clefs produites soient identiques.
>
>> De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
>> publique ssh en différents endroits, et la clé publique de mon
>> serveur est accessible. Cela signifie qu'au moins plusieurs
>> personnes en ont deux, et peuvent donc faire le PGCD afin de
>> retrouver mes clés privées?
>
> L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun,
> heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa
> faibles qui aboutissent occasionnellement à des facteurs communs.
>
de 'p' prend de l'aléa, puis en rajoute avant de calculer 'q' dans le cas
d'openSSL, et donc d'openssh. Mais j'ai peut être mal compris l'exemple.
> Il se peut que l'une de vos clefs ait un facteur commun avec une autre
> clef RSA quelque part, mais ce n'est vraisemblable que si elle a été
> générée sur un système dont le générateur aléatoire n'ait pas eu assez
> d'entropie. Il semblerait d'après le billet de Heninger que cela concerne
> principalement des systèmes embarqués.
>
aléatoires faibles. Si leur générateur d'aléa est faible, alors la
crypto (au sens large) basée dessus est faible, comme par exemple la
génération de clés RSA.
Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
--
Kevin
Tanguy Ortolo
Feb 27, 2012, 10:43:03 AM2/27/12
to
Si j'ai tout bien compris, ça ne devrait pas introduire de faiblesse
supplémentaire. Certes, étant donné deux clefs partageant un même
facteur, il est facile de les factoriser et donc de les casser.
Mais cette possibilité ne rend pas compte de la difficulté, en amont de
cette étape, de trouver pour une clef donnée une seconde clef partageant
un facteur.
De la même façon, on pourrait remarquer qu'étant donnés une clef et un
nombre premier divisant celle-ci, il est très facile de la factoriser.
Certes, mais pour ça il faut déjà trouver le nombre premier en question,
et c'est là toute la difficulté. :-)
En prenant le point de vue d'Alice, qui a publié sa clef publique, si
quelqu'un parmi les milliers d'utilisateurs de clefs RSA a publié une
clef partageant un facteur avec la sienne, elle n'a pas de chance. Mais
la probabilité en est très faible, c'est du même ordre que si quelqu'un
a publié un nombre premier composant la clef d'Alice.
--
Tanguy Ortolo
supplémentaire. Certes, étant donné deux clefs partageant un même
facteur, il est facile de les factoriser et donc de les casser.
Mais cette possibilité ne rend pas compte de la difficulté, en amont de
cette étape, de trouver pour une clef donnée une seconde clef partageant
un facteur.
De la même façon, on pourrait remarquer qu'étant donnés une clef et un
nombre premier divisant celle-ci, il est très facile de la factoriser.
Certes, mais pour ça il faut déjà trouver le nombre premier en question,
et c'est là toute la difficulté. :-)
En prenant le point de vue d'Alice, qui a publié sa clef publique, si
quelqu'un parmi les milliers d'utilisateurs de clefs RSA a publié une
clef partageant un facteur avec la sienne, elle n'a pas de chance. Mais
la probabilité en est très faible, c'est du même ordre que si quelqu'un
a publié un nombre premier composant la clef d'Alice.
--
Tanguy Ortolo
Jean-Marc Desperrier
Feb 28, 2012, 10:31:43 AM2/28/12
to
Kevin Denis a écrit :
- jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
celle avec à la fois la clé publique identique, donc p *et* q identiques
(faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
faible), le papier met en avant cette seconde catégorie quand seulement
p ou bien seulement q est identique.
- la seconde catégorie est quelque part encore plus pourrie que la
première :-)
En effet quand on a 2 clé publique identique, on ne sait pas
instantanément si c'est vraiment un mauvais générateur ou si c'est
quelqu'un qui a réutilisé 2 fois la même clé. Même quand c'est à peu
près évident que c'est dû à un mauvais générateur aléatoire, A peut
attaquer B et réciproquement, mais un tiers C auquel ni A ni B ne
transmet la clé privé doit retrouver de quel générateur il s'agit, quel
soft, sous quelles conditions, pour recréer la même collision et casser
la clé. Suivant le cas, c'est très facile ou quand même un peu moins.
Avec cette nouvelle catégorie, c'est automatiquement instantané pour C
de récupérer les clés privées de A et de B quand elles partagent un
facteur commun, et on est sur à 100% que c'est un problème de générateur
et pas une copie de clé privée.
Du coup, ça a permis d'identifier un problème avec les générateurs d'un
certain nombre de VPN/routeur, ce qui est un point positif.
> Donc si on résume: certains systèmes embarqués ont des générateurs
> aléatoires faibles. Si leur générateur d'aléa est faible, alors la
> crypto (au sens large) basée dessus est faible, comme par exemple la
> génération de clés RSA.
> Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
Deux point sont nouveaux en gros, sans être révolutionnaires :
> aléatoires faibles. Si leur générateur d'aléa est faible, alors la
> crypto (au sens large) basée dessus est faible, comme par exemple la
> génération de clés RSA.
> Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
- jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
celle avec à la fois la clé publique identique, donc p *et* q identiques
(faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
faible), le papier met en avant cette seconde catégorie quand seulement
p ou bien seulement q est identique.
- la seconde catégorie est quelque part encore plus pourrie que la
première :-)
En effet quand on a 2 clé publique identique, on ne sait pas
instantanément si c'est vraiment un mauvais générateur ou si c'est
quelqu'un qui a réutilisé 2 fois la même clé. Même quand c'est à peu
près évident que c'est dû à un mauvais générateur aléatoire, A peut
attaquer B et réciproquement, mais un tiers C auquel ni A ni B ne
transmet la clé privé doit retrouver de quel générateur il s'agit, quel
soft, sous quelles conditions, pour recréer la même collision et casser
la clé. Suivant le cas, c'est très facile ou quand même un peu moins.
Avec cette nouvelle catégorie, c'est automatiquement instantané pour C
de récupérer les clés privées de A et de B quand elles partagent un
facteur commun, et on est sur à 100% que c'est un problème de générateur
et pas une copie de clé privée.
Du coup, ça a permis d'identifier un problème avec les générateurs d'un
certain nombre de VPN/routeur, ce qui est un point positif.
Mehdi Tibouchi
Feb 29, 2012, 2:15:24 AM2/29/12
to
Jean-Marc Desperrier wrote in message
<jiis0b$odq$1...@writer.imaginet.fr>:
dans cet exposé de Don Johnson en 1999 (voir en page 13) :
http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf
Mais je suppose qu'il y a une différence entre savoir qu'une
vulnérabilité est possible en principe, et constater empiriquement
qu'elle existe et est exploitable en pratique.
C'est comme la différence entre les nombreux papiers qui pointent les
faiblesses de (EC)DSA lorsque l'aléa k n'est pas tiré uniformément au
hasard d'une part, et le fait de retrouver la clef secrète des
PlayStation 3 d'autre part.
Cela dit, je ne me prononce pas sur la pertinence ou non d'aller faire la
publicité d'un résultat comme celui-là jusque dans les colonnes du New
York Times.
--
M. Tibouchi.
<jiis0b$odq$1...@writer.imaginet.fr>:
>
> Deux point sont nouveaux en gros, sans être révolutionnaires :
> - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
> celle avec à la fois la clé publique identique, donc p *et* q identiques
> (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
> faible), le papier met en avant cette seconde catégorie quand seulement
> p ou bien seulement q est identique.
> - la seconde catégorie est quelque part encore plus pourrie que la
> première :-)
Même ce point n'est pas nouveau en fait. Il est par exemple mentionné
> Deux point sont nouveaux en gros, sans être révolutionnaires :
> - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
> celle avec à la fois la clé publique identique, donc p *et* q identiques
> (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
> faible), le papier met en avant cette seconde catégorie quand seulement
> p ou bien seulement q est identique.
> - la seconde catégorie est quelque part encore plus pourrie que la
> première :-)
dans cet exposé de Don Johnson en 1999 (voir en page 13) :
http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf
Mais je suppose qu'il y a une différence entre savoir qu'une
vulnérabilité est possible en principe, et constater empiriquement
qu'elle existe et est exploitable en pratique.
C'est comme la différence entre les nombreux papiers qui pointent les
faiblesses de (EC)DSA lorsque l'aléa k n'est pas tiré uniformément au
hasard d'une part, et le fait de retrouver la clef secrète des
PlayStation 3 d'autre part.
Cela dit, je ne me prononce pas sur la pertinence ou non d'aller faire la
publicité d'un résultat comme celui-là jusque dans les colonnes du New
York Times.
--
M. Tibouchi.
Jean-Marc Desperrier
Mar 5, 2012, 8:11:50 AM3/5/12
to
Mehdi Tibouchi a écrit :
Cependant je vois un deuxième point qui fait une grosse différence sur
le "exploitable en pratique" : Le papier décrit une méthode pas
performante du tout en terme de complexité algorithmique, et du coup
pour illustrer prend un cas où on a relativement peu de clé à tester et
un espoir important de trouver une collision.
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
donne envie de tester même quand on ne crois pas trop que ça va réussir.
Ceci dit l'algo optimisé est plutôt évident, il est bien possible qu'il
avait été publié avant si on fouille les archives.
> Il est par exemple mentionné
> dans cet exposé de Don Johnson en 1999 (voir en page 13) :
>
> http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf
>
> Mais je suppose qu'il y a une différence entre savoir qu'une
> vulnérabilité est possible en principe, et constater empiriquement
> qu'elle existe et est exploitable en pratique.
Merci pour cette référence, elle est très intéressante.
> dans cet exposé de Don Johnson en 1999 (voir en page 13) :
>
> http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf
>
> Mais je suppose qu'il y a une différence entre savoir qu'une
> vulnérabilité est possible en principe, et constater empiriquement
> qu'elle existe et est exploitable en pratique.
Cependant je vois un deuxième point qui fait une grosse différence sur
le "exploitable en pratique" : Le papier décrit une méthode pas
performante du tout en terme de complexité algorithmique, et du coup
pour illustrer prend un cas où on a relativement peu de clé à tester et
un espoir important de trouver une collision.
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
donne envie de tester même quand on ne crois pas trop que ça va réussir.
Ceci dit l'algo optimisé est plutôt évident, il est bien possible qu'il
avait été publié avant si on fouille les archives.
Mehdi Tibouchi
Mar 9, 2012, 3:40:36 AM3/9/12
to
Jean-Marc Desperrier wrote in message
<jj2e1t$t7v$1...@writer.imaginet.fr>:
>
> Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
> donne envie de tester même quand on ne crois pas trop que ça va réussir.
Le papier de Lenstra et al. prend spécifiquement soin de ne pas
> Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
> donne envie de tester même quand on ne crois pas trop que ça va réussir.
mentionner l'algo quasi-linéaire utilisé, et les auteurs considèrent
qu'il est évident pour le spécialiste (« sapienti sat », écrivent-ils),
donc on peut difficilement parler de « nouvel algo publié ».
0 new messages