Je cherche à "casser" une signature DSA dont les paramètres sont les
suivants (à titre informatif) :
- Y (clé publique) :
EECD3CD177BF5794F3AA1D78BADA071BCA379C4FD123026AFC27E7CD8631FE4994958A96082BF88EB4058623ECC8CD6EC226B61A0BEF2FBCEF6878A41C052F45
- P :
FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17
- Q : 962EDDCC369CBA8EBB260EE6B6A126D9346E38C5
- G :
678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4
Je doute qu'il soit possible de résoudre le logarithme discret (i.e.
trouver X tel que Y = G ^ X mod P) en un temps raisonnable, vu la taille
des nombres utilisés; mais votre avis sur la question m'intéresse...
Sinon, je voulais savoir si le meilleur algorithme pour résoudre le DLP
était effectivement l'Index Calculus, et si oui, est-ce que quelqu'un
aurait de la documentation détaillant son implémentation ?
Enfin, je me demandais ce qui faisait la "robustesse" du DSA : peut-on
parler de DSA-512, par exemple (comme RSA-1024, etc), et si c'est le
cas, qu'est ce que 512 représente ? (longueur de Y, de G, ... ?)
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
pornin
According to Damien Chambaud :
Bonjour,
Je cherche à "casser" une signature DSA dont les paramètres sont les suivants (à titre informatif) :
- Y (clé publique) : EECD3CD177BF5794F3AA1D78BADA071BCA379C4FD123026AFC27E7CD8631FE4994958A96082BF88EB4058623ECC8CD6EC226B61A0BEF2FBCEF6878A41C052F45 - P : FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17 - Q : 962EDDCC369CBA8EBB260EE6B6A126D9346E38C5 - G : 678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4
(Techniquement, ceci n'est pas une signature DSA mais une clé publique DSA. Mais c'est un détail. Je suppose que vous parlez de fabriquer une signature valide vis-à-vis de cette clé, sur un message de votre choix.)
Je doute qu'il soit possible de résoudre le logarithme discret (i.e. trouver X tel que Y = G ^ X mod P) en un temps raisonnable, vu la taille des nombres utilisés; mais votre avis sur la question m'intéresse...
P a une taille de 1024 bits. J'ai vérifié que P est premier, Q est premier, Q divise P-1, et G et Y sont d'ordre Q modulo P. Cela ressemble à une bonne clé DSA choisie dans les règles. Si c'est le cas, alors, effectivement, il n'est pas actuellement possible, avec les ordinateurs de 2005 et les algorithmes connus en 2005, de "casser" cette clé, i.e. de retrouver X tel que G^X mod P = Y.
Notons néanmoins qu'il est possible de fabriquer des clés DSA qui sont "valides" au sens ci-dessus (P est premier, etc...) mais qui sont d'une forme "friable" (le logarithme discret est facile pour elles). Je ne peux pas garantir que cette clé n'est pas dans ce cas. Un moyen tout bête pour faire un clé friable est de choisir X (la clé secrète) petit. Par exemple, un X de 80 bits (au lieu des 160 usuels) sera retrouvable avec un effort de l'ordre de 2^40 exponentiations modulaires (ce qui est assez lourd mais pas inenvisageable avec quelques dizaines de banals PC).
Sinon, je voulais savoir si le meilleur algorithme pour résoudre le DLP était effectivement l'Index Calculus, et si oui, est-ce que quelqu'un aurait de la documentation détaillant son implémentation ?
À ma connaissance, le meilleur algorithme connu pour le DLP dans le cas qui nous intéresse ici est le "number field sieve" qui est une variation de l'"index-calculus" (notons qu'il existe un algorithme de factorisation, utilisé pour attaquer RSA, qui est quasiment le même et qui s'appelle aussi "number field sieve").
(Note : cette information date de 1999 ; je ne pense pas avoir entendu parler d'un meilleur algorithme, mais je ne garantis rien à ce sujet.)
Un bon point de départ pour se documenter sur le sujet est le chapitre 3 du "handbook of applied cryptography", téléchargeable gratuitement là : http://www.cacr.math.uwaterloo.ca/hac
L'index-calculus y est décrit, en page 109. C'est la version simple ; NFS est nettement plus compliqué. De plus, il y a beaucoup de détails subtils qui changent fortement la vitesse d'exécution dans les cas pratique, et la maîtrise de ces détails est très dure à obtenir (globalement, sur notre planète, ceux qui maîtrisent ces détails sont Montgomery et la poignées de génies qui arrivent à comprendre ce que Montgomery raconte).
Enfin, je me demandais ce qui faisait la "robustesse" du DSA : peut-on parler de DSA-512, par exemple (comme RSA-1024, etc), et si c'est le cas, qu'est ce que 512 représente ? (longueur de Y, de G, ... ?)
DSA est décrit dans un standard (nommé DSS) ; ce standard limite explicitement la taille de P à exactement 1024 bits. C'est un choix arbitraire et d'anciennes versions de DSS autorisaient toutes les tailles multiples de 64 entre 512 et 1024 bits pour P. En fait, l'algorithme fonctionne quelle que soit la taille de P ; il en faut un pas trop petit (pour que le DLP soit infaisable) mais pas trop grand (le temps de production ou de vérification d'une signature est proportionnel au cube de la taille de P, donc mieux vaut ne pas trop forcer la dose).
Dans DSA-512, on désigne la taille de P en bits. DSS spécifie qu'on ne doit utiliser que DSA-1024, donc avec 2^1023 <= P < 2^1024. Par construction, Y, G et Q sont plus petits que P.
Concernant la taille de Q : pour appliquer le DLP, il y a deux sortes d'algorithmes, ceux qui utilisent le fait qu'on a des entiers modulaires, et ceux qui se contentent de travailler sur le fait que G définit un groupe. Pour la première sorte (dont fait partie NFS), il faut que P soit assez grand (1024 bits devraient tenir encore quelques années). La deuxième sorte est dite "algorithmes génériques" et leur complexité dépend surtout de la taille du groupe engendré par G, donc Q. Les meilleurs algorithmes connus ont un coût proportionnel à la racine carrée de l'ordre du groupe. Donc on choisit Q classiquement de 160 bits pour que les algorithmes génériques aient un coût en au moins 2^80, ce qu'on estime comme suffisamment infaisable pour le moment (il faudra probablement augmenter un peu la taille de Q d'ici dix ou vingt ans).
--Thomas Pornin
According to Damien Chambaud <dean22@online.fr>:
Bonjour,
Je cherche à "casser" une signature DSA dont les paramètres sont les
suivants (à titre informatif) :
- Y (clé publique) :
EECD3CD177BF5794F3AA1D78BADA071BCA379C4FD123026AFC27E7CD8631FE4994958A96082BF88EB4058623ECC8CD6EC226B61A0BEF2FBCEF6878A41C052F45
- P :
FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17
- Q : 962EDDCC369CBA8EBB260EE6B6A126D9346E38C5
- G :
678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4
(Techniquement, ceci n'est pas une signature DSA mais une clé publique
DSA. Mais c'est un détail. Je suppose que vous parlez de fabriquer une
signature valide vis-à-vis de cette clé, sur un message de votre choix.)
Je doute qu'il soit possible de résoudre le logarithme discret (i.e.
trouver X tel que Y = G ^ X mod P) en un temps raisonnable, vu la taille
des nombres utilisés; mais votre avis sur la question m'intéresse...
P a une taille de 1024 bits. J'ai vérifié que P est premier, Q est
premier, Q divise P-1, et G et Y sont d'ordre Q modulo P. Cela ressemble
à une bonne clé DSA choisie dans les règles. Si c'est le cas, alors,
effectivement, il n'est pas actuellement possible, avec les ordinateurs
de 2005 et les algorithmes connus en 2005, de "casser" cette clé, i.e.
de retrouver X tel que G^X mod P = Y.
Notons néanmoins qu'il est possible de fabriquer des clés DSA qui sont
"valides" au sens ci-dessus (P est premier, etc...) mais qui sont d'une
forme "friable" (le logarithme discret est facile pour elles). Je ne
peux pas garantir que cette clé n'est pas dans ce cas. Un moyen tout
bête pour faire un clé friable est de choisir X (la clé secrète) petit.
Par exemple, un X de 80 bits (au lieu des 160 usuels) sera retrouvable
avec un effort de l'ordre de 2^40 exponentiations modulaires (ce qui est
assez lourd mais pas inenvisageable avec quelques dizaines de banals
PC).
Sinon, je voulais savoir si le meilleur algorithme pour résoudre le DLP
était effectivement l'Index Calculus, et si oui, est-ce que quelqu'un
aurait de la documentation détaillant son implémentation ?
À ma connaissance, le meilleur algorithme connu pour le DLP dans le
cas qui nous intéresse ici est le "number field sieve" qui est une
variation de l'"index-calculus" (notons qu'il existe un algorithme de
factorisation, utilisé pour attaquer RSA, qui est quasiment le même et
qui s'appelle aussi "number field sieve").
(Note : cette information date de 1999 ; je ne pense pas avoir entendu
parler d'un meilleur algorithme, mais je ne garantis rien à ce sujet.)
Un bon point de départ pour se documenter sur le sujet est le
chapitre 3 du "handbook of applied cryptography", téléchargeable
gratuitement là :
http://www.cacr.math.uwaterloo.ca/hac
L'index-calculus y est décrit, en page 109. C'est la version simple ;
NFS est nettement plus compliqué. De plus, il y a beaucoup de détails
subtils qui changent fortement la vitesse d'exécution dans les cas
pratique, et la maîtrise de ces détails est très dure à obtenir
(globalement, sur notre planète, ceux qui maîtrisent ces détails sont
Montgomery et la poignées de génies qui arrivent à comprendre ce que
Montgomery raconte).
Enfin, je me demandais ce qui faisait la "robustesse" du DSA : peut-on
parler de DSA-512, par exemple (comme RSA-1024, etc), et si c'est le
cas, qu'est ce que 512 représente ? (longueur de Y, de G, ... ?)
DSA est décrit dans un standard (nommé DSS) ; ce standard limite
explicitement la taille de P à exactement 1024 bits. C'est un choix
arbitraire et d'anciennes versions de DSS autorisaient toutes les
tailles multiples de 64 entre 512 et 1024 bits pour P. En fait,
l'algorithme fonctionne quelle que soit la taille de P ; il en faut un
pas trop petit (pour que le DLP soit infaisable) mais pas trop grand (le
temps de production ou de vérification d'une signature est proportionnel
au cube de la taille de P, donc mieux vaut ne pas trop forcer la dose).
Dans DSA-512, on désigne la taille de P en bits. DSS spécifie qu'on
ne doit utiliser que DSA-1024, donc avec 2^1023 <= P < 2^1024. Par
construction, Y, G et Q sont plus petits que P.
Concernant la taille de Q : pour appliquer le DLP, il y a deux
sortes d'algorithmes, ceux qui utilisent le fait qu'on a des entiers
modulaires, et ceux qui se contentent de travailler sur le fait que G
définit un groupe. Pour la première sorte (dont fait partie NFS), il
faut que P soit assez grand (1024 bits devraient tenir encore quelques
années). La deuxième sorte est dite "algorithmes génériques" et leur
complexité dépend surtout de la taille du groupe engendré par G, donc Q.
Les meilleurs algorithmes connus ont un coût proportionnel à la racine
carrée de l'ordre du groupe. Donc on choisit Q classiquement de 160 bits
pour que les algorithmes génériques aient un coût en au moins 2^80, ce
qu'on estime comme suffisamment infaisable pour le moment (il faudra
probablement augmenter un peu la taille de Q d'ici dix ou vingt ans).
Je cherche à "casser" une signature DSA dont les paramètres sont les suivants (à titre informatif) :
- Y (clé publique) : EECD3CD177BF5794F3AA1D78BADA071BCA379C4FD123026AFC27E7CD8631FE4994958A96082BF88EB4058623ECC8CD6EC226B61A0BEF2FBCEF6878A41C052F45 - P : FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17 - Q : 962EDDCC369CBA8EBB260EE6B6A126D9346E38C5 - G : 678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4
(Techniquement, ceci n'est pas une signature DSA mais une clé publique DSA. Mais c'est un détail. Je suppose que vous parlez de fabriquer une signature valide vis-à-vis de cette clé, sur un message de votre choix.)
Je doute qu'il soit possible de résoudre le logarithme discret (i.e. trouver X tel que Y = G ^ X mod P) en un temps raisonnable, vu la taille des nombres utilisés; mais votre avis sur la question m'intéresse...
P a une taille de 1024 bits. J'ai vérifié que P est premier, Q est premier, Q divise P-1, et G et Y sont d'ordre Q modulo P. Cela ressemble à une bonne clé DSA choisie dans les règles. Si c'est le cas, alors, effectivement, il n'est pas actuellement possible, avec les ordinateurs de 2005 et les algorithmes connus en 2005, de "casser" cette clé, i.e. de retrouver X tel que G^X mod P = Y.
Notons néanmoins qu'il est possible de fabriquer des clés DSA qui sont "valides" au sens ci-dessus (P est premier, etc...) mais qui sont d'une forme "friable" (le logarithme discret est facile pour elles). Je ne peux pas garantir que cette clé n'est pas dans ce cas. Un moyen tout bête pour faire un clé friable est de choisir X (la clé secrète) petit. Par exemple, un X de 80 bits (au lieu des 160 usuels) sera retrouvable avec un effort de l'ordre de 2^40 exponentiations modulaires (ce qui est assez lourd mais pas inenvisageable avec quelques dizaines de banals PC).
Sinon, je voulais savoir si le meilleur algorithme pour résoudre le DLP était effectivement l'Index Calculus, et si oui, est-ce que quelqu'un aurait de la documentation détaillant son implémentation ?
À ma connaissance, le meilleur algorithme connu pour le DLP dans le cas qui nous intéresse ici est le "number field sieve" qui est une variation de l'"index-calculus" (notons qu'il existe un algorithme de factorisation, utilisé pour attaquer RSA, qui est quasiment le même et qui s'appelle aussi "number field sieve").
(Note : cette information date de 1999 ; je ne pense pas avoir entendu parler d'un meilleur algorithme, mais je ne garantis rien à ce sujet.)
Un bon point de départ pour se documenter sur le sujet est le chapitre 3 du "handbook of applied cryptography", téléchargeable gratuitement là : http://www.cacr.math.uwaterloo.ca/hac
L'index-calculus y est décrit, en page 109. C'est la version simple ; NFS est nettement plus compliqué. De plus, il y a beaucoup de détails subtils qui changent fortement la vitesse d'exécution dans les cas pratique, et la maîtrise de ces détails est très dure à obtenir (globalement, sur notre planète, ceux qui maîtrisent ces détails sont Montgomery et la poignées de génies qui arrivent à comprendre ce que Montgomery raconte).
Enfin, je me demandais ce qui faisait la "robustesse" du DSA : peut-on parler de DSA-512, par exemple (comme RSA-1024, etc), et si c'est le cas, qu'est ce que 512 représente ? (longueur de Y, de G, ... ?)
DSA est décrit dans un standard (nommé DSS) ; ce standard limite explicitement la taille de P à exactement 1024 bits. C'est un choix arbitraire et d'anciennes versions de DSS autorisaient toutes les tailles multiples de 64 entre 512 et 1024 bits pour P. En fait, l'algorithme fonctionne quelle que soit la taille de P ; il en faut un pas trop petit (pour que le DLP soit infaisable) mais pas trop grand (le temps de production ou de vérification d'une signature est proportionnel au cube de la taille de P, donc mieux vaut ne pas trop forcer la dose).
Dans DSA-512, on désigne la taille de P en bits. DSS spécifie qu'on ne doit utiliser que DSA-1024, donc avec 2^1023 <= P < 2^1024. Par construction, Y, G et Q sont plus petits que P.
Concernant la taille de Q : pour appliquer le DLP, il y a deux sortes d'algorithmes, ceux qui utilisent le fait qu'on a des entiers modulaires, et ceux qui se contentent de travailler sur le fait que G définit un groupe. Pour la première sorte (dont fait partie NFS), il faut que P soit assez grand (1024 bits devraient tenir encore quelques années). La deuxième sorte est dite "algorithmes génériques" et leur complexité dépend surtout de la taille du groupe engendré par G, donc Q. Les meilleurs algorithmes connus ont un coût proportionnel à la racine carrée de l'ordre du groupe. Donc on choisit Q classiquement de 160 bits pour que les algorithmes génériques aient un coût en au moins 2^80, ce qu'on estime comme suffisamment infaisable pour le moment (il faudra probablement augmenter un peu la taille de Q d'ici dix ou vingt ans).
--Thomas Pornin
Dean22
Merci pour votre réponse, elle me satisfait entièrement. :)
J'avais effectivement vu (après coup) que le HAC proposait pas mal d'algorithmes, j'ai aussi feuilleté le FIPS 186-2 sur le standard DSS ; mais comme ce n'est pas ma spécialité, il est dur de s'y mettre dedans.
Je voulais donc savoir si cette clé était cassable, ce n'est apparemment pas le cas ; cela est sans importance.
Merci encore,
Damien C.
Merci pour votre réponse, elle me satisfait entièrement. :)
J'avais effectivement vu (après coup) que le HAC proposait pas mal
d'algorithmes, j'ai aussi feuilleté le FIPS 186-2 sur le standard DSS ;
mais comme ce n'est pas ma spécialité, il est dur de s'y mettre dedans.
Je voulais donc savoir si cette clé était cassable, ce n'est apparemment
pas le cas ; cela est sans importance.
Merci pour votre réponse, elle me satisfait entièrement. :)
J'avais effectivement vu (après coup) que le HAC proposait pas mal d'algorithmes, j'ai aussi feuilleté le FIPS 186-2 sur le standard DSS ; mais comme ce n'est pas ma spécialité, il est dur de s'y mettre dedans.
Je voulais donc savoir si cette clé était cassable, ce n'est apparemment pas le cas ; cela est sans importance.
