Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

garder secrete ou retrouver une clé publique

21 réponses
Avatar
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)

10 réponses

1 2 3
Avatar
Sylvain
Alain wrote on 13/09/2005 22:25:

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)


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).

mais peut t'on retrouver le modulo "n" aussi avec pleins de couple
clair/chiffre "m/c" et l'exposant "e"...


e restant petit, une recherche exhaustive le revèlera assez vite avec un
couple {m,c} (connaissant n).

Sylvain.

Avatar
pornin
According to Sylvain :
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).


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

Avatar
Francois Grieu
Dans l'article <432735af$0$5369$,
Alain demande:

peut t'on retrouver le modulo "n" aussi avec pleins de couple
clair/chiffre "m/c" et l'exposant "e"


Oui. En effet n divise (m^e)-c. Et en prenant le PGCD de
plusieurs (m^e)-c on retrouve n.


François Grieu

Avatar
Francois Grieu
Dans l'article <432754a8$0$27409$,
Sylvain a écrit:

amha (ces arguement) expliquent pourquoi (3, 17 et 65537) sont
de bons candidats pas pourquoi ils seraient les seuls.


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

Avatar
Francois Grieu
Dans l'article <432754a8$0$27409$,
Sylvain a écrit:

amha (ces arguement) expliquent pourquoi (3, 17 et 65537) sont
de bons candidats pas pourquoi ils seraient les seuls.


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

Avatar
Francois Grieu
Dans l'article <432754a8$0$27409$,
Sylvain a écrit:

amha (ces arguement) expliquent pourquoi (3, 17 et 65537) sont
de bons candidats pas pourquoi ils seraient les seuls.


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 6x+5, ce qui garanti de pouvoir utiliser
e=3. [on apréciera quad dans deux précédentes versions de ce
message, je me suis trompté sur la forme 6x+5]

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

Avatar
Francois Grieu
Dans l'article <432754a8$0$27409$,
Sylvain a écrit:

amha (ces arguement) expliquent pourquoi (3, 17 et 65537) sont
de bons candidats pas pourquoi ils seraient les seuls.


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 6x+5, ce qui garanti de pouvoir utiliser
e=3. [on apréciera quad dans deux précédentes versions de ce
message, je me suis trompté sur la forme 6x+5]

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
[excuses à ceux dont le serveur ne gère pas Supersedes]

Avatar
pornin
According to Francois 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.


Notons au passage que l'implémentation de RSA intégrée dans Windows
ne sait gérer que les exposants publics de 32 bits ou moins. Donc les
certificats X.509 avec des exposants publics plus grands ne seront pas
gérés par Internet Explorer ou Outlook...


--Thomas Pornin

(Remarquons tout de même que ee537 est "traditionnel" -- les premiers
PGP l'utilisaient systématiquement -- et que la Tradition, ça rassure
les utilisateurs. Et la tranquillité de l'utilisateur est aussi un but
honorable et important d'un système de sécurité.)

Avatar
Erwan David
(Thomas Pornin) écrivait :

(Remarquons tout de même que ee537 est "traditionnel" -- les premiers
PGP l'utilisaient systématiquement -- et que la Tradition, ça rassure
les utilisateurs. Et la tranquillité de l'utilisateur est aussi un but
honorable et important d'un système de sécurité.)


Et qu'après tout il n'est pas plus mauvais qu'un autre...

--
Il n'y a pas besoin d'être riche, il suffit d'avoir de l'argent
(Chambre de commerce de Palau)

Avatar
Francois Grieu
Dans l'article <dg9b67$1r49$,
(Thomas Pornin) a écrit:

Remarquons tout de même que ee537 est "traditionnel" -- les premiers
PGP l'utilisaient systématiquement -- et que la Tradition, ça rassure
les utilisateurs. Et la tranquillité de l'utilisateur est aussi un but
honorable et important d'un système de sécurité.


J'ai regardé (il y a longtemps) le source de PGP 2.3,
et suis arrivé à la conclusion que par défaut il utilise
le plus souvent e, et e avec une probabilité notable
(genre 12% je crois). Pour les curieux
http://google.fr/search?qÞrive_rsakeys+%22small+as+17%22

A l'époque j'avais du temps :-) et j'ai vérifié que e et
e sont assez fréquents dans les vieux dictionnaires de
clés PGP, et que le rapport des fréquences de e, e et
e! sont à peu près conformes à la prédiction théorique.

Même si on met le paramètre ebits à 17 (comme le fait
notemment au moins une version 2.63 avec GUI),
ee539 est généré avec une probabilité non complètement
négligeable, et je conjecture que c'est arrivé.


François Grieu

1 2 3