Reconstruire une clé privé RSA à partir de l'exposant privé
3 réponses
Jean-Marc Desperrier
Salut,
Je suis en train de regarder quel est le maximum que l'on puisse faire
pour stocker une clé privée RSA avec le moins de place possible.
La littérature dit que si on dispose par ailleurs des éléments de la clé
publique (module, exposant publique) il suffit de stocker l'exposant privé.
Cependant les calculs derrière sont un peu longs et complexes, et je ne
dispose pas de la description étape par étape de la méthode, surtout en
fait pour la première étape retrouver l'un des premiers (pour être
honnête ce qui me conviendrait totalement serait de dénicher un exemple
du code pour le faire, à défaut j'essaierais de faire travailler mes
neurones ;-) ).
J'ai trouvé un message de Stephen Henson renvoyant sur cryptoapi pour
une description complète du procédé :
http://groups.google.fr/group/mailing.openssl.dev/msg/7b33b04307682513
Mais le message n'est plus accessible directement.
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
Francois Grieu
Dans l'article <dfh83p$4b4$, Jean-Marc Desperrier écrit:
Je suis en train de regarder quel est le maximum que l'on puisse faire pour stocker une clé privée RSA avec le moins de place possible.
Une des méthodes les plus compactes est de garder (p,q,e); ça a la taille de la clé publique (n,e) [dans le cas général de clés où seule la taille de n est imposée]. on recalcule une clé privée (n,d) qui fonctionne par n = p*q d = e^-1 mod ((p-1)*(q-1))
On trouve ce dernier calcul dans toute librairie qui fabrique une clé RSA.
François Grieu
Dans l'article <dfh83p$4b4$1@reader1.imaginet.fr>,
Jean-Marc Desperrier <jmdesp@alussinan.org> écrit:
Je suis en train de regarder quel est le maximum que l'on puisse faire
pour stocker une clé privée RSA avec le moins de place possible.
Une des méthodes les plus compactes est de garder
(p,q,e); ça a la taille de la clé publique (n,e)
[dans le cas général de clés où seule la taille de n est imposée].
on recalcule une clé privée (n,d) qui fonctionne par
n = p*q
d = e^-1 mod ((p-1)*(q-1))
On trouve ce dernier calcul dans toute librairie qui
fabrique une clé RSA.
Dans l'article <dfh83p$4b4$, Jean-Marc Desperrier écrit:
Je suis en train de regarder quel est le maximum que l'on puisse faire pour stocker une clé privée RSA avec le moins de place possible.
Une des méthodes les plus compactes est de garder (p,q,e); ça a la taille de la clé publique (n,e) [dans le cas général de clés où seule la taille de n est imposée]. on recalcule une clé privée (n,d) qui fonctionne par n = p*q d = e^-1 mod ((p-1)*(q-1))
On trouve ce dernier calcul dans toute librairie qui fabrique une clé RSA.
François Grieu
pornin
According to Jean-Marc Desperrier :
La littérature dit que si on dispose par ailleurs des éléments de la clé publique (module, exposant publique) il suffit de stocker l'exposant privé.
Cependant les calculs derrière sont un peu longs et complexes, et je ne dispose pas de la description étape par étape de la méthode, surtout en fait pour la première étape retrouver l'un des premiers
La connaissance des facteurs premiers n'est pas nécessaire pour faire du RSA. Si on note :
n = module public e = exposant public d = exposant privé p = premier facteur q = second facteur (n = p * q) m = message après application du padding qui va bien
alors le chiffrement de m est : c = m^e mod n et le déchiffrement : c^d mod n = m
Autrement dit, avec juste n et d, on peut calculer ce qu'on veut.
Il s'avère qu'en connaissant les facteurs premiers p et q, on peut aussi calculer les valeurs suivantes :
dp = d mod p-1 dq = d mod q-1 iq = 1/q mod p
qui permettent de calculer l'opération centrale du RSA (l'exponentiation modulaire avec l'exposant privé) en travaillant modulo p et modulo q, et en recombinant le tout avec le "chinese remainder theorem" (CRT, pour les intimes). Cette opération est en gros trois à quatre fois plus rapide que la méthode qui utilise seulement n et d. Mais ça calcule les mêmes choses ; donc c'est quand même du domaine de l'optimisation.
Ceci étant, si on veut retrouver les facteurs p et q à partir de n, e et d, alors on fait comme ça :
1. On calcule e*d-1 = t*(2^s): "e*d-1" est un nombre pair, donc on le calcule, et on le divise par 2 autant de fois qu'il faut pour obtenir un nombre impair "t". Le nombre de fois où on a divisé par 2 est "s".
2. On prend un nombre aléatoire "a" modulo n, et on calcule z = a^t mod n. Si z vaut 1 ou n-1 modulo n, on recommence avec un autre "a". On peut montrer qu'au moins un "a" sur deux donnera un z différent de 1 et n-1 modulo n ; autrement dit, on ne va pas boucler longtemps ici.
3. On calcule w = z^2 mod n. Si w ne vaut pas 1 ou n-1 modulo n, alors on stocke w dans z, et on recommence cette opération. On peut montrer qu'on va le faire au plus s fois.
4. À ce point-là, on a un entier z entre 0 et n tel que z n'est ni 1, ni n-1, mais z^2 = 1 ou n-1 modulo n. Il est alors garanti que le pgcd de z et n est un diviseur strict de n strictement supérieur à 1 (autrement dit, le calcul de ce pgcd par un banal algorithme d'Euclide donne p ou q).
Ça, c'est la méthode générale, qui marche avec un exposant public quelconque (pas forcément petit), et même si on a calculé d de telle sorte que e*d = 1 mod l, où l est le ppcm de p-1 et q-1 (la méthode traditionnelle utilise e*d = 1 mod phi(n) où phi(n) = (p-1)*(q-1)). Ça marche aussi si on a une clé RSA un peu plus générale, avec plus de deux facteurs (c'est possible aussi, mais c'est quand même rare) : on obtient des diviseurs de n, et en quelques itérations, on a la décomposition en facteurs premiers.
Maintenant, on peut faire plus simple et plus rapide si on a les conditions suivantes :
-- "e" est petit (genre : moins de 32 bits) -- "e" et "d" sont tels que e*d = 1 mod phi(n) -- "p" et "q" sont grosso-modo de même taille.
Ces conditions sont déterminées par le processus de génération de la clé et c'est le cas courant: utiliser l = ppcm(p-1, q-1) plutôt que phi(n) nécessite du code en plus, et n'amène pas à des performances substantiellement meilleures ; quant à la taille de "e", on le choisit petit parce que ça permet un chiffrement ou une vérification de signature rapides -- et certains logiciels très répandus ne savent pas gérer les exposants publics plus grands que 32 bits de toutes façons. Enfin, avoir "p" et "q" de même taille est un bon point pour la sécurité (la complexité des algorithmes de factorisation est souvent liée à la taille du plus petit des facteurs, donc pour maximiser cette taille, on prend tous les facteurs aussi grands les uns que les autres).
Dans ce cas, on a :
e*d = 1 mod phi(n)
donc il existe un entier k tel que e*d-1 = k*phi(n)
Comme p et q sont moitié moins grand que n, alors phi(n) ressemble beaucoup à n : si n fait 1024 bits, phi(n) et n sont identiques sur leurs 512 bits de poids fort. De plus, comme d est plus petit que n, alors k est de la taille de e, ou plus petit.
Il s'en suit que k se calcule facilement avec une division : en calculant (e*d-1)/n, on obtient k, ou, dans de très rare cas (hautement improbable), k-1.
Une fois qu'on a k, on calcule phi(n) = (e*d-1)/k (cette division "tombe juste"). D'où on tire : p+q = n+1-((e*d-1)/k)
On a alors p+q, et aussi p*q (c'est le module n, tout bêtement). On peut alors calculer p et q en résolvant en X l'équation : X^2 - (p+q)*X + p*q = 0
C'est une banale équation du second degré, on apprend à faire ça au collège. Les solutions sont p et q. Et hop.
--Thomas Pornin
According to Jean-Marc Desperrier <jmdesp@alussinan.org>:
La littérature dit que si on dispose par ailleurs des éléments de la clé
publique (module, exposant publique) il suffit de stocker l'exposant privé.
Cependant les calculs derrière sont un peu longs et complexes, et je ne
dispose pas de la description étape par étape de la méthode, surtout en
fait pour la première étape retrouver l'un des premiers
La connaissance des facteurs premiers n'est pas nécessaire pour
faire du RSA. Si on note :
n = module public
e = exposant public
d = exposant privé
p = premier facteur
q = second facteur (n = p * q)
m = message après application du padding qui va bien
alors le chiffrement de m est : c = m^e mod n
et le déchiffrement : c^d mod n = m
Autrement dit, avec juste n et d, on peut calculer ce qu'on veut.
Il s'avère qu'en connaissant les facteurs premiers p et q, on peut
aussi calculer les valeurs suivantes :
dp = d mod p-1
dq = d mod q-1
iq = 1/q mod p
qui permettent de calculer l'opération centrale du RSA (l'exponentiation
modulaire avec l'exposant privé) en travaillant modulo p et modulo q,
et en recombinant le tout avec le "chinese remainder theorem" (CRT,
pour les intimes). Cette opération est en gros trois à quatre fois plus
rapide que la méthode qui utilise seulement n et d. Mais ça calcule les
mêmes choses ; donc c'est quand même du domaine de l'optimisation.
Ceci étant, si on veut retrouver les facteurs p et q à partir de n, e
et d, alors on fait comme ça :
1. On calcule e*d-1 = t*(2^s): "e*d-1" est un nombre pair, donc on
le calcule, et on le divise par 2 autant de fois qu'il faut pour
obtenir un nombre impair "t". Le nombre de fois où on a divisé par 2
est "s".
2. On prend un nombre aléatoire "a" modulo n, et on calcule z = a^t mod n.
Si z vaut 1 ou n-1 modulo n, on recommence avec un autre "a". On peut
montrer qu'au moins un "a" sur deux donnera un z différent de 1 et n-1
modulo n ; autrement dit, on ne va pas boucler longtemps ici.
3. On calcule w = z^2 mod n. Si w ne vaut pas 1 ou n-1 modulo n, alors
on stocke w dans z, et on recommence cette opération. On peut montrer
qu'on va le faire au plus s fois.
4. À ce point-là, on a un entier z entre 0 et n tel que z n'est ni 1,
ni n-1, mais z^2 = 1 ou n-1 modulo n. Il est alors garanti que le
pgcd de z et n est un diviseur strict de n strictement supérieur à 1
(autrement dit, le calcul de ce pgcd par un banal algorithme d'Euclide
donne p ou q).
Ça, c'est la méthode générale, qui marche avec un exposant public
quelconque (pas forcément petit), et même si on a calculé d de telle
sorte que e*d = 1 mod l, où l est le ppcm de p-1 et q-1 (la méthode
traditionnelle utilise e*d = 1 mod phi(n) où phi(n) = (p-1)*(q-1)). Ça
marche aussi si on a une clé RSA un peu plus générale, avec plus de deux
facteurs (c'est possible aussi, mais c'est quand même rare) : on obtient
des diviseurs de n, et en quelques itérations, on a la décomposition en
facteurs premiers.
Maintenant, on peut faire plus simple et plus rapide si on a les
conditions suivantes :
-- "e" est petit (genre : moins de 32 bits)
-- "e" et "d" sont tels que e*d = 1 mod phi(n)
-- "p" et "q" sont grosso-modo de même taille.
Ces conditions sont déterminées par le processus de génération de la
clé et c'est le cas courant: utiliser l = ppcm(p-1, q-1) plutôt que
phi(n) nécessite du code en plus, et n'amène pas à des performances
substantiellement meilleures ; quant à la taille de "e", on le choisit
petit parce que ça permet un chiffrement ou une vérification de
signature rapides -- et certains logiciels très répandus ne savent pas
gérer les exposants publics plus grands que 32 bits de toutes façons.
Enfin, avoir "p" et "q" de même taille est un bon point pour la sécurité
(la complexité des algorithmes de factorisation est souvent liée à la
taille du plus petit des facteurs, donc pour maximiser cette taille, on
prend tous les facteurs aussi grands les uns que les autres).
Dans ce cas, on a :
e*d = 1 mod phi(n)
donc il existe un entier k tel que e*d-1 = k*phi(n)
Comme p et q sont moitié moins grand que n, alors phi(n) ressemble
beaucoup à n : si n fait 1024 bits, phi(n) et n sont identiques sur
leurs 512 bits de poids fort. De plus, comme d est plus petit que n,
alors k est de la taille de e, ou plus petit.
Il s'en suit que k se calcule facilement avec une division : en
calculant (e*d-1)/n, on obtient k, ou, dans de très rare cas
(hautement improbable), k-1.
Une fois qu'on a k, on calcule phi(n) = (e*d-1)/k (cette division
"tombe juste"). D'où on tire : p+q = n+1-((e*d-1)/k)
On a alors p+q, et aussi p*q (c'est le module n, tout bêtement).
On peut alors calculer p et q en résolvant en X l'équation :
X^2 - (p+q)*X + p*q = 0
C'est une banale équation du second degré, on apprend à faire ça au
collège. Les solutions sont p et q. Et hop.
La littérature dit que si on dispose par ailleurs des éléments de la clé publique (module, exposant publique) il suffit de stocker l'exposant privé.
Cependant les calculs derrière sont un peu longs et complexes, et je ne dispose pas de la description étape par étape de la méthode, surtout en fait pour la première étape retrouver l'un des premiers
La connaissance des facteurs premiers n'est pas nécessaire pour faire du RSA. Si on note :
n = module public e = exposant public d = exposant privé p = premier facteur q = second facteur (n = p * q) m = message après application du padding qui va bien
alors le chiffrement de m est : c = m^e mod n et le déchiffrement : c^d mod n = m
Autrement dit, avec juste n et d, on peut calculer ce qu'on veut.
Il s'avère qu'en connaissant les facteurs premiers p et q, on peut aussi calculer les valeurs suivantes :
dp = d mod p-1 dq = d mod q-1 iq = 1/q mod p
qui permettent de calculer l'opération centrale du RSA (l'exponentiation modulaire avec l'exposant privé) en travaillant modulo p et modulo q, et en recombinant le tout avec le "chinese remainder theorem" (CRT, pour les intimes). Cette opération est en gros trois à quatre fois plus rapide que la méthode qui utilise seulement n et d. Mais ça calcule les mêmes choses ; donc c'est quand même du domaine de l'optimisation.
Ceci étant, si on veut retrouver les facteurs p et q à partir de n, e et d, alors on fait comme ça :
1. On calcule e*d-1 = t*(2^s): "e*d-1" est un nombre pair, donc on le calcule, et on le divise par 2 autant de fois qu'il faut pour obtenir un nombre impair "t". Le nombre de fois où on a divisé par 2 est "s".
2. On prend un nombre aléatoire "a" modulo n, et on calcule z = a^t mod n. Si z vaut 1 ou n-1 modulo n, on recommence avec un autre "a". On peut montrer qu'au moins un "a" sur deux donnera un z différent de 1 et n-1 modulo n ; autrement dit, on ne va pas boucler longtemps ici.
3. On calcule w = z^2 mod n. Si w ne vaut pas 1 ou n-1 modulo n, alors on stocke w dans z, et on recommence cette opération. On peut montrer qu'on va le faire au plus s fois.
4. À ce point-là, on a un entier z entre 0 et n tel que z n'est ni 1, ni n-1, mais z^2 = 1 ou n-1 modulo n. Il est alors garanti que le pgcd de z et n est un diviseur strict de n strictement supérieur à 1 (autrement dit, le calcul de ce pgcd par un banal algorithme d'Euclide donne p ou q).
Ça, c'est la méthode générale, qui marche avec un exposant public quelconque (pas forcément petit), et même si on a calculé d de telle sorte que e*d = 1 mod l, où l est le ppcm de p-1 et q-1 (la méthode traditionnelle utilise e*d = 1 mod phi(n) où phi(n) = (p-1)*(q-1)). Ça marche aussi si on a une clé RSA un peu plus générale, avec plus de deux facteurs (c'est possible aussi, mais c'est quand même rare) : on obtient des diviseurs de n, et en quelques itérations, on a la décomposition en facteurs premiers.
Maintenant, on peut faire plus simple et plus rapide si on a les conditions suivantes :
-- "e" est petit (genre : moins de 32 bits) -- "e" et "d" sont tels que e*d = 1 mod phi(n) -- "p" et "q" sont grosso-modo de même taille.
Ces conditions sont déterminées par le processus de génération de la clé et c'est le cas courant: utiliser l = ppcm(p-1, q-1) plutôt que phi(n) nécessite du code en plus, et n'amène pas à des performances substantiellement meilleures ; quant à la taille de "e", on le choisit petit parce que ça permet un chiffrement ou une vérification de signature rapides -- et certains logiciels très répandus ne savent pas gérer les exposants publics plus grands que 32 bits de toutes façons. Enfin, avoir "p" et "q" de même taille est un bon point pour la sécurité (la complexité des algorithmes de factorisation est souvent liée à la taille du plus petit des facteurs, donc pour maximiser cette taille, on prend tous les facteurs aussi grands les uns que les autres).
Dans ce cas, on a :
e*d = 1 mod phi(n)
donc il existe un entier k tel que e*d-1 = k*phi(n)
Comme p et q sont moitié moins grand que n, alors phi(n) ressemble beaucoup à n : si n fait 1024 bits, phi(n) et n sont identiques sur leurs 512 bits de poids fort. De plus, comme d est plus petit que n, alors k est de la taille de e, ou plus petit.
Il s'en suit que k se calcule facilement avec une division : en calculant (e*d-1)/n, on obtient k, ou, dans de très rare cas (hautement improbable), k-1.
Une fois qu'on a k, on calcule phi(n) = (e*d-1)/k (cette division "tombe juste"). D'où on tire : p+q = n+1-((e*d-1)/k)
On a alors p+q, et aussi p*q (c'est le module n, tout bêtement). On peut alors calculer p et q en résolvant en X l'équation : X^2 - (p+q)*X + p*q = 0
C'est une banale équation du second degré, on apprend à faire ça au collège. Les solutions sont p et q. Et hop.
--Thomas Pornin
pornin
According to Jean-Marc Desperrier :
Je suis en train de regarder quel est le maximum que l'on puisse faire pour stocker une clé privée RSA avec le moins de place possible.
Si on contrôle le processus de génération de la clé RSA, alors voilà une méthode très compacte : une génération de clé RSA, c'est essentiellement l'application d'un algorithme avec un générateur aléatoire, et pas mal de tests sur des nombres. Hormis le générateur, tout est déterministe là-dedans. Donc, si on utilise un bon PRNG (à base d'AES ou SHA-256 ou n'importe quel autre mécanisme de bon aloi), alors la connaissance de la "graine" de ce PRNG suffit pour recalculer toute la clé RSA.
On peut donc se contenter de stocker la graine, qui fera, disons, 128 bits, pour une excellente sécurité. On ne peut pas faire mieux que cette méthode, en termes de taille : on stocke une valeur de x bits pour une entropie de clé de x bits.
Évidemment, il y a pas mal de travail pour utiliser un tel stockage, puisqu'il faut refaire une génération de clé. Ce processus a tendance à être quelques centaines de fois plus coûteux en temps de calcul que le calcul d'une signature RSA en elle-même. Il faut aussi maîtriser le système de génération de la clé. Donc il faut voir dans quelle mesure c'est applicable, suivant la situation.
--Thomas Pornin
According to Jean-Marc Desperrier <jmdesp@alussinan.org>:
Je suis en train de regarder quel est le maximum que l'on puisse faire
pour stocker une clé privée RSA avec le moins de place possible.
Si on contrôle le processus de génération de la clé RSA, alors voilà une
méthode très compacte : une génération de clé RSA, c'est essentiellement
l'application d'un algorithme avec un générateur aléatoire, et pas mal
de tests sur des nombres. Hormis le générateur, tout est déterministe
là-dedans. Donc, si on utilise un bon PRNG (à base d'AES ou SHA-256 ou
n'importe quel autre mécanisme de bon aloi), alors la connaissance de la
"graine" de ce PRNG suffit pour recalculer toute la clé RSA.
On peut donc se contenter de stocker la graine, qui fera, disons, 128
bits, pour une excellente sécurité. On ne peut pas faire mieux que cette
méthode, en termes de taille : on stocke une valeur de x bits pour une
entropie de clé de x bits.
Évidemment, il y a pas mal de travail pour utiliser un tel stockage,
puisqu'il faut refaire une génération de clé. Ce processus a tendance
à être quelques centaines de fois plus coûteux en temps de calcul que
le calcul d'une signature RSA en elle-même. Il faut aussi maîtriser le
système de génération de la clé. Donc il faut voir dans quelle mesure
c'est applicable, suivant la situation.
Je suis en train de regarder quel est le maximum que l'on puisse faire pour stocker une clé privée RSA avec le moins de place possible.
Si on contrôle le processus de génération de la clé RSA, alors voilà une méthode très compacte : une génération de clé RSA, c'est essentiellement l'application d'un algorithme avec un générateur aléatoire, et pas mal de tests sur des nombres. Hormis le générateur, tout est déterministe là-dedans. Donc, si on utilise un bon PRNG (à base d'AES ou SHA-256 ou n'importe quel autre mécanisme de bon aloi), alors la connaissance de la "graine" de ce PRNG suffit pour recalculer toute la clé RSA.
On peut donc se contenter de stocker la graine, qui fera, disons, 128 bits, pour une excellente sécurité. On ne peut pas faire mieux que cette méthode, en termes de taille : on stocke une valeur de x bits pour une entropie de clé de x bits.
Évidemment, il y a pas mal de travail pour utiliser un tel stockage, puisqu'il faut refaire une génération de clé. Ce processus a tendance à être quelques centaines de fois plus coûteux en temps de calcul que le calcul d'une signature RSA en elle-même. Il faut aussi maîtriser le système de génération de la clé. Donc il faut voir dans quelle mesure c'est applicable, suivant la situation.
