Une question me trote dans la tête,
soit r clé privée et s clé publique,
j'ai r.s = 1 mod phi(n)
phi(n)= (p-1)(q-1); n = p.q
connaissant r et s peut-on trouver phi(n) ? ou p ?
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 chapi :
Une question me trote dans la tête, soit r clé privée et s clé publique, j'ai r.s = 1 mod phi(n) phi(n)= (p-1)(q-1); n = p.q connaissant r et s peut-on trouver phi(n) ? ou p ?
donc, avec n et phi(n), on a p+q = n + 1 - phi(n) On pose l'équation : X^2 - (p+q)*X + p*q = 0 C'est une équation du second degré, n'importe quel lycéen sait la résoudre (ou devrait savoir, du moins), et ses deux solutions sont exactement p et q.
Avec r et s, on retrouve p et q (donc phi(n) aussi). La méthode est la suivante : on écrit r*s = 2^u * t avec t impair (autrement dit, on divise r*s par 2 autant de fois qu'il faut pour obtenir un nombre impair). Ensuite on choisit un nombre a aléatoire entre 2 et n-1, et on calcule la suite des a^(t*2^i) pour i allant de 0 à u. À un moment donné, on tombe sur la valeur 1 (c'est garanti par le petit théorème de Fermat), pour i = w. Si w = 0, on recommence avec une autre valeur de a. Sinon, on regarde la valeur juste avant : a^(t*2^(w-1)). Je nomme A cette valeur. Si A vaut n-1, on recommence le tout avec un autre a. Sinon, on calcule le pgcd de n et A+1, et ça nous donne un facteur premier de n (p ou q).
En moyenne, il faudra essayer deux nombres "a" aléatoires différents, donc le processus est rapide.
Ceci signifie que la connaissance de la clé privée RSA est équivalente à la factorisation du module : si on sait retrouver cette clé, on sait factoriser, et réciproquement. Ceci ne veut pas dire, en revanche, que la difficulté de casser RSA est équivalente à la factorisation : casser RSA, c'est pouvoir faire les opérations nécessitant normalement la clé privée, alors qu'on ne l'avait pas précédemment. On peut imaginer de casser RSA sans pour autant retrouver la clé privée.
Un exemple : supposons un RSA avec exposant public 3 et un module public de, mettons, 1024 bits. Un message m clair est chiffré en m^3 mod n. Supposons qu'on me montre le message chiffré "729". Je sais que 9*9*9 = 729, et ça reste vrai modulo n (le modulo n'intervient pas dans le calcul parce que le message est un nombre tout petit). Donc je sais déchiffrer le message "729", sans pour autant connaître la clé privée ou factoriser le module n. C'est pourquoi, dans la pratique, on n'utilise jamais RSA tel quel, mais avec un système dit de "padding" qui s'assure que les nombres qui passent à l'exponentiation sont "grands". En attendant, cet exemple permet de voir que l'équivalence RSA <-> factorisation n'a rien d'évident, ce qui explique qu'elle ne soit pas prouvée à l'heure actuelle.
--Thomas Pornin
According to chapi <ymoya@free.fr>:
Une question me trote dans la tête,
soit r clé privée et s clé publique,
j'ai r.s = 1 mod phi(n)
phi(n)= (p-1)(q-1); n = p.q
connaissant r et s peut-on trouver phi(n) ? ou p ?
donc, avec n et phi(n), on a p+q = n + 1 - phi(n)
On pose l'équation : X^2 - (p+q)*X + p*q = 0
C'est une équation du second degré, n'importe quel lycéen sait la
résoudre (ou devrait savoir, du moins), et ses deux solutions sont
exactement p et q.
Avec r et s, on retrouve p et q (donc phi(n) aussi). La méthode
est la suivante : on écrit r*s = 2^u * t avec t impair (autrement
dit, on divise r*s par 2 autant de fois qu'il faut pour obtenir un
nombre impair). Ensuite on choisit un nombre a aléatoire entre 2
et n-1, et on calcule la suite des a^(t*2^i) pour i allant de 0 à u.
À un moment donné, on tombe sur la valeur 1 (c'est garanti par
le petit théorème de Fermat), pour i = w. Si w = 0, on recommence
avec une autre valeur de a. Sinon, on regarde la valeur juste avant :
a^(t*2^(w-1)). Je nomme A cette valeur. Si A vaut n-1, on recommence
le tout avec un autre a. Sinon, on calcule le pgcd de n et A+1, et
ça nous donne un facteur premier de n (p ou q).
En moyenne, il faudra essayer deux nombres "a" aléatoires différents,
donc le processus est rapide.
Ceci signifie que la connaissance de la clé privée RSA est équivalente
à la factorisation du module : si on sait retrouver cette clé, on sait
factoriser, et réciproquement. Ceci ne veut pas dire, en revanche, que
la difficulté de casser RSA est équivalente à la factorisation : casser
RSA, c'est pouvoir faire les opérations nécessitant normalement la clé
privée, alors qu'on ne l'avait pas précédemment. On peut imaginer de
casser RSA sans pour autant retrouver la clé privée.
Un exemple : supposons un RSA avec exposant public 3 et un module
public de, mettons, 1024 bits. Un message m clair est chiffré en
m^3 mod n. Supposons qu'on me montre le message chiffré "729". Je
sais que 9*9*9 = 729, et ça reste vrai modulo n (le modulo n'intervient
pas dans le calcul parce que le message est un nombre tout petit).
Donc je sais déchiffrer le message "729", sans pour autant connaître
la clé privée ou factoriser le module n. C'est pourquoi, dans la
pratique, on n'utilise jamais RSA tel quel, mais avec un système dit
de "padding" qui s'assure que les nombres qui passent à
l'exponentiation sont "grands". En attendant, cet exemple permet de
voir que l'équivalence RSA <-> factorisation n'a rien d'évident,
ce qui explique qu'elle ne soit pas prouvée à l'heure actuelle.
Une question me trote dans la tête, soit r clé privée et s clé publique, j'ai r.s = 1 mod phi(n) phi(n)= (p-1)(q-1); n = p.q connaissant r et s peut-on trouver phi(n) ? ou p ?
donc, avec n et phi(n), on a p+q = n + 1 - phi(n) On pose l'équation : X^2 - (p+q)*X + p*q = 0 C'est une équation du second degré, n'importe quel lycéen sait la résoudre (ou devrait savoir, du moins), et ses deux solutions sont exactement p et q.
Avec r et s, on retrouve p et q (donc phi(n) aussi). La méthode est la suivante : on écrit r*s = 2^u * t avec t impair (autrement dit, on divise r*s par 2 autant de fois qu'il faut pour obtenir un nombre impair). Ensuite on choisit un nombre a aléatoire entre 2 et n-1, et on calcule la suite des a^(t*2^i) pour i allant de 0 à u. À un moment donné, on tombe sur la valeur 1 (c'est garanti par le petit théorème de Fermat), pour i = w. Si w = 0, on recommence avec une autre valeur de a. Sinon, on regarde la valeur juste avant : a^(t*2^(w-1)). Je nomme A cette valeur. Si A vaut n-1, on recommence le tout avec un autre a. Sinon, on calcule le pgcd de n et A+1, et ça nous donne un facteur premier de n (p ou q).
En moyenne, il faudra essayer deux nombres "a" aléatoires différents, donc le processus est rapide.
Ceci signifie que la connaissance de la clé privée RSA est équivalente à la factorisation du module : si on sait retrouver cette clé, on sait factoriser, et réciproquement. Ceci ne veut pas dire, en revanche, que la difficulté de casser RSA est équivalente à la factorisation : casser RSA, c'est pouvoir faire les opérations nécessitant normalement la clé privée, alors qu'on ne l'avait pas précédemment. On peut imaginer de casser RSA sans pour autant retrouver la clé privée.
Un exemple : supposons un RSA avec exposant public 3 et un module public de, mettons, 1024 bits. Un message m clair est chiffré en m^3 mod n. Supposons qu'on me montre le message chiffré "729". Je sais que 9*9*9 = 729, et ça reste vrai modulo n (le modulo n'intervient pas dans le calcul parce que le message est un nombre tout petit). Donc je sais déchiffrer le message "729", sans pour autant connaître la clé privée ou factoriser le module n. C'est pourquoi, dans la pratique, on n'utilise jamais RSA tel quel, mais avec un système dit de "padding" qui s'assure que les nombres qui passent à l'exponentiation sont "grands". En attendant, cet exemple permet de voir que l'équivalence RSA <-> factorisation n'a rien d'évident, ce qui explique qu'elle ne soit pas prouvée à l'heure actuelle.
