garder secrete ou retrouver une clé publique
Le
Alain
Salut,
je m'amuse a penser a des systèmes crypto marrants
et j'ai pensé a un cas ou il faudrait cacher la clé publique
RSA comme la clé privé
l'idée c'est d'avoir 3 populations,
ceux qui savent rien,
ceux qui connaissent la clé publique
et peuvent produire des messages cryptés et les comparer
(parler et reconnaitre les messages qu'il ont imaginés),
et ceux qui peuvent les décrypter aussi
(écouter les messages même pas imaginés)
mais je me pose une question sur la clé publique
déjà l'exposant "e" associé est connu (il y en a 3 ou 4 de classiques,
genre 3 ou 65535)
mais peut t'on retrouver le modulo "n" aussi avec pleins de couple
clair/chiffre "m/c" et l'exposant "e"
trouver n connaissant e et plein de cas m/c
c=m^e mod n
ou même simplement
c=m^3 mod n
mais si un attaquant dispose d'un tas de clair et du chiffré associé,
et souhaite simplement découvrir la clé publique pour pouvoir chiffrer
(et donc retrouver des chiffrés correspondant a des clairs connus)
je m'amuse a penser a des systèmes crypto marrants
et j'ai pensé a un cas ou il faudrait cacher la clé publique
RSA comme la clé privé
l'idée c'est d'avoir 3 populations,
ceux qui savent rien,
ceux qui connaissent la clé publique
et peuvent produire des messages cryptés et les comparer
(parler et reconnaitre les messages qu'il ont imaginés),
et ceux qui peuvent les décrypter aussi
(écouter les messages même pas imaginés)
mais je me pose une question sur la clé publique
déjà l'exposant "e" associé est connu (il y en a 3 ou 4 de classiques,
genre 3 ou 65535)
mais peut t'on retrouver le modulo "n" aussi avec pleins de couple
clair/chiffre "m/c" et l'exposant "e"
trouver n connaissant e et plein de cas m/c
c=m^e mod n
ou même simplement
c=m^3 mod n
mais si un attaquant dispose d'un tas de clair et du chiffré associé,
et souhaite simplement découvrir la clé publique pour pouvoir chiffrer
(et donc retrouver des chiffrés correspondant a des clairs connus)
Poser une question
c'est en effet une fréquente mauvaise manie que d'utiliser 10001h;
mauvaise car ayant un impact très couteux sur la génération
(vérifier gcd(q-1, e) == 1 à e fixé conduit à jeter pas mal de q, alors
qu'en jouant sur e, on conserve plus de q acceptable).
e restant petit, une recherche exhaustive le revèlera assez vite avec un
couple {m,c} (connaissant n).
Sylvain.
65537 est premier, ce qui conduit à rejeter 1 candidat sur 65537, soit
0.0015%... En bref, le "pas mal" est en fait assez réduit.
Le plus fort taux de rejet est avec e = 3, qui conduit à rejeter un
tiers des candidats "q". Mais on peut faire le test de divisibilité
par 3 _avant_ le test de primalité (une réduction modulo 3, c'est
beaucoup moins coûteux qu'un Miller-Rabin), ce qui rend ce surcoût
négligeable sur toute la procédure.
L'usage de 65537 plutôt que 3 est une Tradition. Ça rassure les gens,
pour des raisons qui n'ont pas de base scientifique.
--Thomas Pornin
Oui. En effet n divise (m^e)-c. Et en prenant le PGCD de
plusieurs (m^e)-c on retrouve n.
François Grieu
Ils ne sont pas les seuls. Certaines applications utilisent
des exposants e aléatoires de 64 bits (impairs et >2).
Beaucoup de versions de PGP choisissent p et q, puis e en
fonction de p et q, et l'on trouve par exemple des clés
publiques PGP avec un exposant de 19, parceque 17
divise p-1 ou q-1.
Tout cela n'a guère d'importance. Dès lors que l'on
formatte convenablement les messages, e=3 convient.
Il est trivial de n'examiner des candidats pour p et q
que de la forme 6*x+2 ou 6x+5, ce qui garanti de pouvoir
utiliser e=3.
Les seules raisons de choisir un plus grand e sont
théoriquement mauvaises:
- Chiffrer le même message (ou des messages approchants)
avec avec e clés publiques distinctes révèle le
message ? Formattons systématiquement les messages
de manière aléatoire (si on veut un chiffrement
déterministe, utilisons n pour diversifier le message
à chiffrer)
- Les formattages de signature faibles (ISO/IEC 9796:1991,
voire ISO/IEC 9796-2:1997) permettent des attaques à message
choisi légèrement moins difficilement quand e est petit ?
Utilisons un formattage à sécurité (quasiment..) démontrée
(ISO/IEC 9796-2:2002)
- On vous assène un obscur article qui disserte sur ce que
RSA à grand e est peut-être moins difficile à réduire
à la factorisation que RSA avec e=3 ? Sortez un non moins
obscur article arguant exatement du contraire.
François Grieu
Ils ne sont pas les seuls. Certaines applications utilisent
des exposants e aléatoires de 64 bits (impairs et >2).
Beaucoup de versions de PGP choisissent p et q, puis e en
fonction de p et q, et l'on trouve par exemple des clés
publiques PGP avec un exposant de 19, parceque 17
divise p-1 ou q-1.
Tout cela n'a guère d'importance. Dès lors que l'on
formatte convenablement les messages, e=3 convient.
Il est trivial de n'examiner des candidats pour p et q
que de la forme 6*x+2 ou 6x+5, ce qui garanti de pouvoir
utiliser e=3.
Les seules raisons de choisir un plus grand e sont
théoriquement mauvaises:
- Chiffrer le même message (ou des messages approchants)
avec avec e clés publiques distinctes révèle le
message ? Formattons systématiquement les messages
de manière aléatoire (si on veut un chiffrement
déterministe, utilisons n pour diversifier le message
à chiffrer)
- Les formattages de signature faibles (ISO/IEC 9796:1991,
voire ISO/IEC 9796-2:1997) permettent des attaques à message
choisi légèrement moins difficilement quand e est petit ?
Utilisons un formattage à sécurité (quasiment..) démontrée
(ISO/IEC 9796-2:2002)
- On vous assène un obscur article qui disserte sur ce que
RSA à grand e est peut-être plus équivalent à la
factorisation que RSA avec e=3 ? Sortez un non moins
obscur article arguant exatement du contraire.
François Grieu