Dans RSA, supposons que j'ai mes deux nombres p,q , premiers.
On a le module RSA qui vaut: n= p.q
Il faut ensuite choisir un nombre e, premier avec phi(n)=(p-1).(q-1)
Il n'y a aucune indication sur le choix de e (je lis: Intro à l'algo)
Comment le choisit-on ? On prend 3, et on vérifie que not(3 | phi(n)) ?,
etc... sinon on essaie le suivant ?
L'étape suivante, c'est le calcul de d, tel que: d.e = 1 (mod phi(n))
Ici c'est une résolution d'équation linéaires modulaires ? Ah oui ca
utilise Euclide-étendu, un algorithme qui s'éxecute en O(log(n))
Est-ce que le choix de e, (c'est l'exposant public son nom?), a une
influence sur la sécurité ?
Si on le prend petit, l'application de la clef publique sera-t'elle
plus rapide ? P(M)=M^e (mod n). En fait l'algo employé pour
l'exponentiation modulaire s'exécute en O(lg b), b est l'exposant; donc
ca a l'air très bon a priori, à moins qu'il y ait des coûts très élevés
dûs aux grands entiers?
Egalement, s'il est petit, est-ce qu'il rend la réversibilité de
l'opération moins coûteuse ?
P(M) = M^e (mod n)
Donc si on arrive à trouver un nombre N tel que N^e = P(M), alors on a
trouvé M. Est-ce que c'est ça le logarithme discret ?
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 Antoine L. :
Dans RSA, supposons que j'ai mes deux nombres p,q , premiers. On a le module RSA qui vaut: n= p.q Il faut ensuite choisir un nombre e, premier avec phi(n)=(p-1).(q-1) Il n'y a aucune indication sur le choix de e (je lis: Intro à l'algo) Comment le choisit-on ? On prend 3, et on vérifie que not(3 | phi(n)) ?, etc... sinon on essaie le suivant ?
On choisit habituellement e petit et avec un "poids de Hamming" (nombre de bits à 1 dans l'écriture en base 2) faible : le but est d'accélérer les opérations mettant en jeu l'exposant public (chiffrement, et vérification d'une signature). Par ailleurs, certaines implémentations ont du mal à gérer les exposants publics qui dépassent une certaine taille (par exemple, le code cryptographique inclus dans Windows ne sait pas gérer les "e" de plus de 32 bits...).
Quand on fabrique la clé, on fait comme ça : 1. on choisit e arbitrairement 2. on choisit p nombre aléatoire de la taille recherchée (512 bits si on veut un module de 1024 bits) 3. si e n'est pas premier avec p-1, on retourne en 2. 4. si p n'est pas premier, on retourne en 2. 5. on choisit q nombre aléatoire dans le bon intervalle (il faut que p*q ait la taille de module recherchée) 6. si e n'est pas premier avec q-1, on retourne en 2. 7. si q n'est pas premier, on retourne en 2.
et voilà. Pour que les étapes 3 et 6 n'échouent pas trop souvent, le plus simple est de choisir un "e" qui soit en plus un nombre premier. Les choix usuels sont 3, 17 et 65537 (respectivement 11, 10001 et 10000000000000001 en binaire), qui sont des nombres premiers.
L'étape suivante, c'est le calcul de d, tel que: d.e = 1 (mod phi(n)) Ici c'est une résolution d'équation linéaires modulaires ? Ah oui ca utilise Euclide-étendu, un algorithme qui s'éxecute en O(log(n))
O((log n)^2) (quadratique en la taille du module).
Est-ce que le choix de e, (c'est l'exposant public son nom?), a une influence sur la sécurité ?
Il existe une "attaque" dans le cas de e très petit : si un même message m est chiffré avec RSA par rapport à e clés publiques utilisant l'exposant e (par exemple 3 clés publiques ayant l'exposant public 3), alors on peut reconstituer le message sans connaître aucune des clés privées. Dans la pratique, cette attaque n'est pas applicable, parce qu'on ne chiffre jamais un message "tel quel" : on applique un "padding" comportant des octets aléatoires, ce qui fait que ce n'est pas le même entier qui est envoyé en entrée des différentes clés publiques.
À part ça, il semblerait que la taille de l'exposant public n'influe pas notablement sur la sécurité. Je ne sais pas si c'est prouvé.
Si on le prend petit, l'application de la clef publique sera-t'elle plus rapide ? P(M)=M^e (mod n). En fait l'algo employé pour l'exponentiation modulaire s'exécute en O(lg b), b est l'exposant; donc ca a l'air très bon a priori, à moins qu'il y ait des coûts très élevés dûs aux grands entiers?
C'est O(log b) multiplications modulaires, chacune ayant un coût en O((log n)^2) (sauf finasseries complexes, peu rentables pour des nombres de quelques milliers de bits). L'optimisation des opérations sur la clé publique est importante, surtout quand ces opérations doivent être réalisées par des matériels peu puissants (genre des cartes à puces).
P(M) = M^e (mod n) Donc si on arrive à trouver un nombre N tel que N^e = P(M), alors on a trouvé M. Est-ce que c'est ça le logarithme discret ?
Non. Le logarithme discret, c'est : étant donnés g, p et g^x mod p, trouver x.
--Thomas Pornin
According to Antoine L. <alecail@polland.xanafoo.invalid.nospam>:
Dans RSA, supposons que j'ai mes deux nombres p,q , premiers.
On a le module RSA qui vaut: n= p.q
Il faut ensuite choisir un nombre e, premier avec phi(n)=(p-1).(q-1)
Il n'y a aucune indication sur le choix de e (je lis: Intro à l'algo)
Comment le choisit-on ? On prend 3, et on vérifie que not(3 | phi(n)) ?,
etc... sinon on essaie le suivant ?
On choisit habituellement e petit et avec un "poids de Hamming" (nombre
de bits à 1 dans l'écriture en base 2) faible : le but est d'accélérer
les opérations mettant en jeu l'exposant public (chiffrement, et
vérification d'une signature). Par ailleurs, certaines implémentations
ont du mal à gérer les exposants publics qui dépassent une certaine
taille (par exemple, le code cryptographique inclus dans Windows ne
sait pas gérer les "e" de plus de 32 bits...).
Quand on fabrique la clé, on fait comme ça :
1. on choisit e arbitrairement
2. on choisit p nombre aléatoire de la taille recherchée (512 bits si on
veut un module de 1024 bits)
3. si e n'est pas premier avec p-1, on retourne en 2.
4. si p n'est pas premier, on retourne en 2.
5. on choisit q nombre aléatoire dans le bon intervalle (il faut que p*q
ait la taille de module recherchée)
6. si e n'est pas premier avec q-1, on retourne en 2.
7. si q n'est pas premier, on retourne en 2.
et voilà. Pour que les étapes 3 et 6 n'échouent pas trop souvent, le plus
simple est de choisir un "e" qui soit en plus un nombre premier. Les choix
usuels sont 3, 17 et 65537 (respectivement 11, 10001 et 10000000000000001
en binaire), qui sont des nombres premiers.
L'étape suivante, c'est le calcul de d, tel que: d.e = 1 (mod phi(n))
Ici c'est une résolution d'équation linéaires modulaires ? Ah oui ca
utilise Euclide-étendu, un algorithme qui s'éxecute en O(log(n))
O((log n)^2) (quadratique en la taille du module).
Est-ce que le choix de e, (c'est l'exposant public son nom?), a une
influence sur la sécurité ?
Il existe une "attaque" dans le cas de e très petit : si un même
message m est chiffré avec RSA par rapport à e clés publiques utilisant
l'exposant e (par exemple 3 clés publiques ayant l'exposant public 3),
alors on peut reconstituer le message sans connaître aucune des clés
privées. Dans la pratique, cette attaque n'est pas applicable, parce
qu'on ne chiffre jamais un message "tel quel" : on applique un "padding"
comportant des octets aléatoires, ce qui fait que ce n'est pas le même
entier qui est envoyé en entrée des différentes clés publiques.
À part ça, il semblerait que la taille de l'exposant public n'influe
pas notablement sur la sécurité. Je ne sais pas si c'est prouvé.
Si on le prend petit, l'application de la clef publique sera-t'elle
plus rapide ? P(M)=M^e (mod n). En fait l'algo employé pour
l'exponentiation modulaire s'exécute en O(lg b), b est l'exposant; donc
ca a l'air très bon a priori, à moins qu'il y ait des coûts très élevés
dûs aux grands entiers?
C'est O(log b) multiplications modulaires, chacune ayant un coût en
O((log n)^2) (sauf finasseries complexes, peu rentables pour des nombres
de quelques milliers de bits). L'optimisation des opérations sur la
clé publique est importante, surtout quand ces opérations doivent être
réalisées par des matériels peu puissants (genre des cartes à puces).
P(M) = M^e (mod n)
Donc si on arrive à trouver un nombre N tel que N^e = P(M), alors on a
trouvé M. Est-ce que c'est ça le logarithme discret ?
Non. Le logarithme discret, c'est : étant donnés g, p et g^x mod p,
trouver x.
Dans RSA, supposons que j'ai mes deux nombres p,q , premiers. On a le module RSA qui vaut: n= p.q Il faut ensuite choisir un nombre e, premier avec phi(n)=(p-1).(q-1) Il n'y a aucune indication sur le choix de e (je lis: Intro à l'algo) Comment le choisit-on ? On prend 3, et on vérifie que not(3 | phi(n)) ?, etc... sinon on essaie le suivant ?
On choisit habituellement e petit et avec un "poids de Hamming" (nombre de bits à 1 dans l'écriture en base 2) faible : le but est d'accélérer les opérations mettant en jeu l'exposant public (chiffrement, et vérification d'une signature). Par ailleurs, certaines implémentations ont du mal à gérer les exposants publics qui dépassent une certaine taille (par exemple, le code cryptographique inclus dans Windows ne sait pas gérer les "e" de plus de 32 bits...).
Quand on fabrique la clé, on fait comme ça : 1. on choisit e arbitrairement 2. on choisit p nombre aléatoire de la taille recherchée (512 bits si on veut un module de 1024 bits) 3. si e n'est pas premier avec p-1, on retourne en 2. 4. si p n'est pas premier, on retourne en 2. 5. on choisit q nombre aléatoire dans le bon intervalle (il faut que p*q ait la taille de module recherchée) 6. si e n'est pas premier avec q-1, on retourne en 2. 7. si q n'est pas premier, on retourne en 2.
et voilà. Pour que les étapes 3 et 6 n'échouent pas trop souvent, le plus simple est de choisir un "e" qui soit en plus un nombre premier. Les choix usuels sont 3, 17 et 65537 (respectivement 11, 10001 et 10000000000000001 en binaire), qui sont des nombres premiers.
L'étape suivante, c'est le calcul de d, tel que: d.e = 1 (mod phi(n)) Ici c'est une résolution d'équation linéaires modulaires ? Ah oui ca utilise Euclide-étendu, un algorithme qui s'éxecute en O(log(n))
O((log n)^2) (quadratique en la taille du module).
Est-ce que le choix de e, (c'est l'exposant public son nom?), a une influence sur la sécurité ?
Il existe une "attaque" dans le cas de e très petit : si un même message m est chiffré avec RSA par rapport à e clés publiques utilisant l'exposant e (par exemple 3 clés publiques ayant l'exposant public 3), alors on peut reconstituer le message sans connaître aucune des clés privées. Dans la pratique, cette attaque n'est pas applicable, parce qu'on ne chiffre jamais un message "tel quel" : on applique un "padding" comportant des octets aléatoires, ce qui fait que ce n'est pas le même entier qui est envoyé en entrée des différentes clés publiques.
À part ça, il semblerait que la taille de l'exposant public n'influe pas notablement sur la sécurité. Je ne sais pas si c'est prouvé.
Si on le prend petit, l'application de la clef publique sera-t'elle plus rapide ? P(M)=M^e (mod n). En fait l'algo employé pour l'exponentiation modulaire s'exécute en O(lg b), b est l'exposant; donc ca a l'air très bon a priori, à moins qu'il y ait des coûts très élevés dûs aux grands entiers?
C'est O(log b) multiplications modulaires, chacune ayant un coût en O((log n)^2) (sauf finasseries complexes, peu rentables pour des nombres de quelques milliers de bits). L'optimisation des opérations sur la clé publique est importante, surtout quand ces opérations doivent être réalisées par des matériels peu puissants (genre des cartes à puces).
P(M) = M^e (mod n) Donc si on arrive à trouver un nombre N tel que N^e = P(M), alors on a trouvé M. Est-ce que c'est ça le logarithme discret ?
Non. Le logarithme discret, c'est : étant donnés g, p et g^x mod p, trouver x.
