J'aimerai avoir l'avis d'experts en crypto.
Quel est la taille minimum d'une clef à utiliser pour une signature
elgamal ? (je suis surtout interressé par la signature)
J'entends pas la, le minimum considéré sur.
La taille des clefs pour la signature correponds elle à la taille de la
clef pour le chiffrement ? (en terme de résistance aux attaques)
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi
ressistant qu'une clef pour Elgamal Encrypt.
Désolé pour ses questions, je ne maitrise pas du tout le sujet.
J'entends souvent parler de RSA en terme de taille de clef, mais
rarement d'Elgamal.
La taille des clefs pour la signature correponds elle à la taille de la clef pour le chiffrement ? (en terme de résistance aux attaques)
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ; la clé privée est un certain nombre x et la clé publique est égale à g^x mod p. Quand on parle de la taille de la clé, on parle en fait de la taille du nombre p.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise El-Gamal en mode chiffrement ou en mode signature.
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi ressistant qu'une clef pour Elgamal Encrypt.
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile à casser, et une clé El-Gamal de signature de 200 bits est également très facile à casser.
Une taille de clé raisonnable est 1024 bits.
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et, dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est encodable en relativement peu de bits, genre 200, avec néanmoins une sécurité raisonnable.
J'entends souvent parler de RSA en terme de taille de clef, mais rarement d'El-Gamal.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a eu la bonne idée de fabriquer des documents faisant office de standards et décrivant comment on encode une clé RSA ou une signature RSA en une suite d'octets. Ceci a assuré le succès industriel de RSA.
--Thomas Pornin
According to Nicolas <no@spam.invalid>:
La taille des clefs pour la signature correponds elle à la taille de la
clef pour le chiffrement ? (en terme de résistance aux attaques)
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ;
la clé privée est un certain nombre x et la clé publique est égale
à g^x mod p. Quand on parle de la taille de la clé, on parle en fait
de la taille du nombre p.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir
de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise
El-Gamal en mode chiffrement ou en mode signature.
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi
ressistant qu'une clef pour Elgamal Encrypt.
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile
à casser, et une clé El-Gamal de signature de 200 bits est également
très facile à casser.
Une taille de clé raisonnable est 1024 bits.
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et,
dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est
encodable en relativement peu de bits, genre 200, avec néanmoins une
sécurité raisonnable.
J'entends souvent parler de RSA en terme de taille de clef, mais
rarement d'El-Gamal.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a
eu la bonne idée de fabriquer des documents faisant office de standards
et décrivant comment on encode une clé RSA ou une signature RSA en une
suite d'octets. Ceci a assuré le succès industriel de RSA.
La taille des clefs pour la signature correponds elle à la taille de la clef pour le chiffrement ? (en terme de résistance aux attaques)
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ; la clé privée est un certain nombre x et la clé publique est égale à g^x mod p. Quand on parle de la taille de la clé, on parle en fait de la taille du nombre p.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise El-Gamal en mode chiffrement ou en mode signature.
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi ressistant qu'une clef pour Elgamal Encrypt.
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile à casser, et une clé El-Gamal de signature de 200 bits est également très facile à casser.
Une taille de clé raisonnable est 1024 bits.
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et, dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est encodable en relativement peu de bits, genre 200, avec néanmoins une sécurité raisonnable.
J'entends souvent parler de RSA en terme de taille de clef, mais rarement d'El-Gamal.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a eu la bonne idée de fabriquer des documents faisant office de standards et décrivant comment on encode une clé RSA ou une signature RSA en une suite d'octets. Ceci a assuré le succès industriel de RSA.
--Thomas Pornin
Nicolas
Bonjour,
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ; la clé privée est un certain nombre x et la clé publique est égale à g^x mod p. Quand on parle de la taille de la clé, on parle en fait de la taille du nombre p.
Oui tout à fait.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise El-Gamal en mode chiffrement ou en mode signature.
Ok, merci pour cette précision. Il faut donc calculer le dlp pour retrouver x apparement?
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi ressistant qu'une clef pour Elgamal Encrypt. Merci de cette confirmation. Une idée du temps nécessaire pour casser
une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200 bit, ca prendra pas enormement de temps..
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile à casser, et une clé El-Gamal de signature de 200 bits est également très facile à casser.
Merci. C'est ce que je voulais savoir.
Une taille de clé raisonnable est 1024 bits. Cela offre en gros autant de sécurité qu'un RSA 1024 ?
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et, dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est encodable en relativement peu de bits, genre 200, avec néanmoins une sécurité raisonnable.
Ok merci. Mais les maths sont assez compliqués dans les courbes eliptiques si mes souvenirs sont bons.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a eu la bonne idée de fabriquer des documents faisant office de standards et décrivant comment on encode une clé RSA ou une signature RSA en une suite d'octets. Ceci a assuré le succès industriel de RSA.
Merci beaucoup pour toutes ses précisions! Bref, mon elgamal 100 bit est un peu a la ramasse :)
Nicolas.
Bonjour,
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ;
la clé privée est un certain nombre x et la clé publique est égale
à g^x mod p. Quand on parle de la taille de la clé, on parle en fait
de la taille du nombre p.
Oui tout à fait.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir
de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise
El-Gamal en mode chiffrement ou en mode signature.
Ok, merci pour cette précision.
Il faut donc calculer le dlp pour retrouver x apparement?
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi
ressistant qu'une clef pour Elgamal Encrypt.
Merci de cette confirmation. Une idée du temps nécessaire pour casser
une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200
bit, ca prendra pas enormement de temps..
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile
à casser, et une clé El-Gamal de signature de 200 bits est également
très facile à casser.
Merci. C'est ce que je voulais savoir.
Une taille de clé raisonnable est 1024 bits.
Cela offre en gros autant de sécurité qu'un RSA 1024 ?
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et,
dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est
encodable en relativement peu de bits, genre 200, avec néanmoins une
sécurité raisonnable.
Ok merci. Mais les maths sont assez compliqués dans les courbes
eliptiques si mes souvenirs sont bons.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a
eu la bonne idée de fabriquer des documents faisant office de standards
et décrivant comment on encode une clé RSA ou une signature RSA en une
suite d'octets. Ceci a assuré le succès industriel de RSA.
Merci beaucoup pour toutes ses précisions!
Bref, mon elgamal 100 bit est un peu a la ramasse :)
En gros oui. Dans El-Gamal, il y a des paramètres publics g et p ; la clé privée est un certain nombre x et la clé publique est égale à g^x mod p. Quand on parle de la taille de la clé, on parle en fait de la taille du nombre p.
Oui tout à fait.
La sécurité d'El-Gamal repose sur la difficulté de retrouver x à partir de g, p et g^x mod p. Ceci est vrai indépendamment du fait qu'on utilise El-Gamal en mode chiffrement ou en mode signature.
Ok, merci pour cette précision. Il faut donc calculer le dlp pour retrouver x apparement?
C'est à dire, est ce que une clef de 200 bit pour Eglamal Sign est aussi ressistant qu'une clef pour Elgamal Encrypt. Merci de cette confirmation. Une idée du temps nécessaire pour casser
une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200 bit, ca prendra pas enormement de temps..
Oui : une clé El-Gamal de chiffrement de 200 bits est très facile à casser, et une clé El-Gamal de signature de 200 bits est également très facile à casser.
Merci. C'est ce que je voulais savoir.
Une taille de clé raisonnable est 1024 bits. Cela offre en gros autant de sécurité qu'un RSA 1024 ?
Il existe une variante d'El-Gamal utilisant des courbes elliptiques, et, dans ce cas, l'équivalent de g^x mod p n'est plus un nombre mais est encodable en relativement peu de bits, genre 200, avec néanmoins une sécurité raisonnable.
Ok merci. Mais les maths sont assez compliqués dans les courbes eliptiques si mes souvenirs sont bons.
RSA a des performances vaguement meilleures, mais surtout, RSA Labs a eu la bonne idée de fabriquer des documents faisant office de standards et décrivant comment on encode une clé RSA ou une signature RSA en une suite d'octets. Ceci a assuré le succès industriel de RSA.
Merci beaucoup pour toutes ses précisions! Bref, mon elgamal 100 bit est un peu a la ramasse :)
Nicolas.
pornin
According to Nicolas :
Il faut donc calculer le dlp pour retrouver x apparement?
Ben oui, par définition même de "Discrete Logarithm Problem" : il s'agit de retrouver x, étant donnés g, p et g^x mod p.
Merci de cette confirmation. Une idée du temps nécessaire pour casser une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200 bit, ca prendra pas enormement de temps..
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret connu actuellement est très similaire au meilleur algorithme de factorisation connu actuellement. Le gros du boulot est le même. Du coup, on obtient la même sécurité avec des tailles de clés similaires.
Ok merci. Mais les maths sont assez compliqués dans les courbes elliptiques si mes souvenirs sont bons.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des algorithmes assez détaillés.
cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk pour savoir comment récupérer ce document.
--Thomas Pornin
According to Nicolas <no@spam.invalid>:
Il faut donc calculer le dlp pour retrouver x apparement?
Ben oui, par définition même de "Discrete Logarithm Problem" : il s'agit
de retrouver x, étant donnés g, p et g^x mod p.
Merci de cette confirmation. Une idée du temps nécessaire pour casser
une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200
bit, ca prendra pas enormement de temps..
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil
plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret
connu actuellement est très similaire au meilleur algorithme de
factorisation connu actuellement. Le gros du boulot est le même. Du
coup, on obtient la même sécurité avec des tailles de clés similaires.
Ok merci. Mais les maths sont assez compliqués dans les courbes
elliptiques si mes souvenirs sont bons.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le
mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des
algorithmes assez détaillés.
cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk
pour savoir comment récupérer ce document.
Il faut donc calculer le dlp pour retrouver x apparement?
Ben oui, par définition même de "Discrete Logarithm Problem" : il s'agit de retrouver x, étant donnés g, p et g^x mod p.
Merci de cette confirmation. Une idée du temps nécessaire pour casser une clef de 200 bit ? Si c'est sensiblement la meme que pour du RSA 200 bit, ca prendra pas enormement de temps..
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret connu actuellement est très similaire au meilleur algorithme de factorisation connu actuellement. Le gros du boulot est le même. Du coup, on obtient la même sécurité avec des tailles de clés similaires.
Ok merci. Mais les maths sont assez compliqués dans les courbes elliptiques si mes souvenirs sont bons.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des algorithmes assez détaillés.
cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk pour savoir comment récupérer ce document.
--Thomas Pornin
Nicolas
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret connu actuellement est très similaire au meilleur algorithme de factorisation connu actuellement. Le gros du boulot est le même. Du coup, on obtient la même sécurité avec des tailles de clés similaires.
Merci pour cette information. Cela me permet de comparer avec des tailles de clef que j'ai testé pour RSA.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des algorithmes assez détaillés. cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk pour savoir comment récupérer ce document. Merci bien, j'ai récuperé ca, je vais regarder.
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ? C'est par simple curiosité seulement.
Merci encore pour toutes vos réponses.
Cordialement,
Nicolas.
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil
plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret
connu actuellement est très similaire au meilleur algorithme de
factorisation connu actuellement. Le gros du boulot est le même. Du
coup, on obtient la même sécurité avec des tailles de clés similaires.
Merci pour cette information. Cela me permet de comparer avec
des tailles de clef que j'ai testé pour RSA.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le
mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des
algorithmes assez détaillés.
cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk
pour savoir comment récupérer ce document.
Merci bien, j'ai récuperé ca, je vais regarder.
Une petite et dernière question, du ECC 56, ca correspondrai à quoi
comme clef RSA en gros ?
C'est par simple curiosité seulement.
C'est sensiblement le même temps que pour du RSA 200 (enfin, c'est un poil plus long, mais pas beaucoup).
C'est parce que le meilleur algorithme de calcul de logarithme discret connu actuellement est très similaire au meilleur algorithme de factorisation connu actuellement. Le gros du boulot est le même. Du coup, on obtient la même sécurité avec des tailles de clés similaires.
Merci pour cette information. Cela me permet de comparer avec des tailles de clef que j'ai testé pour RSA.
Oui, c'est plus difficile à implémenter. Sans être infaisable. Le mieux est de regarder ce qui se fait dans IEEE p1363, qui donne des algorithmes assez détaillés. cf http://groups.google.com/groups?selm>7745D1.E988490C%40zetnet.co.uk pour savoir comment récupérer ce document. Merci bien, j'ai récuperé ca, je vais regarder.
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ? C'est par simple curiosité seulement.
Merci encore pour toutes vos réponses.
Cordialement,
Nicolas.
Clement Seveillac
Ce Tue, 20 Jan 2004 14:38:51 +0100, Nicolas écrivait :
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ?
Une clef publique de 56 bits ? Ce ne serait sans doute pas terrible, les seules stats d'equivalence que j'ai rencontrees commençant a 160 ou 163 bits pour ECC (pour RSA 1024). Voici, d'apres Certicom [1] (le "champion" des ECC), la force des ECC les plus courantes :
[1] http://www.certicom.com/index.php?action=sol,why_ecc_soft [2] ce dernier chiffre provient de la publication 800-57 du NIST (page 97), disponible ici : http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf
Hope this helps, -- clem
Ce Tue, 20 Jan 2004 14:38:51 +0100,
Nicolas <no@spam.invalid> écrivait :
Une petite et dernière question, du ECC 56, ca correspondrai à quoi
comme clef RSA en gros ?
Une clef publique de 56 bits ? Ce ne serait sans doute pas terrible,
les seules stats d'equivalence que j'ai rencontrees commençant a 160
ou 163 bits pour ECC (pour RSA 1024). Voici, d'apres Certicom [1] (le
"champion" des ECC), la force des ECC les plus courantes :
[1] http://www.certicom.com/index.php?action=sol,why_ecc_soft
[2] ce dernier chiffre provient de la publication 800-57 du NIST
(page 97), disponible ici :
http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf
Ce Tue, 20 Jan 2004 14:38:51 +0100, Nicolas écrivait :
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ?
Une clef publique de 56 bits ? Ce ne serait sans doute pas terrible, les seules stats d'equivalence que j'ai rencontrees commençant a 160 ou 163 bits pour ECC (pour RSA 1024). Voici, d'apres Certicom [1] (le "champion" des ECC), la force des ECC les plus courantes :
[1] http://www.certicom.com/index.php?action=sol,why_ecc_soft [2] ce dernier chiffre provient de la publication 800-57 du NIST (page 97), disponible ici : http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf
Hope this helps, -- clem
pornin
According to Nicolas :
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ?
À la grosse louche, ce serait équivalent à du RSA avec des clés entre 150 et 200 bits. Bref, éminemment cassable.
L'équivalent du problème du logarithme discret sur les courbes elliptiques de taille N bits a un coût en O(2^(N/2)) (au vu de l'état des connaissances scientifiques sur le sujet au début 2004, et sous réserve que la courbe ait été choisie dans les règles de l'art). Ça donne 2^80 opérations pour une courbe de 160 bits. Ou 2^28 opérations pour une courbe de 56 bits.
--Thomas Pornin
According to Nicolas <no@spam.invalid>:
Une petite et dernière question, du ECC 56, ca correspondrai à quoi
comme clef RSA en gros ?
À la grosse louche, ce serait équivalent à du RSA avec des clés
entre 150 et 200 bits. Bref, éminemment cassable.
L'équivalent du problème du logarithme discret sur les courbes
elliptiques de taille N bits a un coût en O(2^(N/2)) (au vu de l'état
des connaissances scientifiques sur le sujet au début 2004, et sous
réserve que la courbe ait été choisie dans les règles de l'art). Ça
donne 2^80 opérations pour une courbe de 160 bits. Ou 2^28 opérations
pour une courbe de 56 bits.
Une petite et dernière question, du ECC 56, ca correspondrai à quoi comme clef RSA en gros ?
À la grosse louche, ce serait équivalent à du RSA avec des clés entre 150 et 200 bits. Bref, éminemment cassable.
L'équivalent du problème du logarithme discret sur les courbes elliptiques de taille N bits a un coût en O(2^(N/2)) (au vu de l'état des connaissances scientifiques sur le sujet au début 2004, et sous réserve que la courbe ait été choisie dans les règles de l'art). Ça donne 2^80 opérations pour une courbe de 160 bits. Ou 2^28 opérations pour une courbe de 56 bits.
