Faille RSA

[invitecb6e3de4]

Bonjour,

J'ai remarqué la chose suivante dans le cryptosystème RSA.

Je prendrais comme notations le modulus public avec p et q deux premiers, et l'indicatrice d'Euler de N. L'exposant public est noté e et la clef privée d.
D'après l'égalité , que nous pouvons écrire , nous pouvons exprimer d comme suit :


De plus, .

Donc


Je fais maintenant l'hypothèse que l'exposant public e est petit. D'après l'égalité , si d est de l'ordre de grandeur de (ce qui est le cas dans la pratique) alors k sera de l'ordre de grandeur de e.

Si la factorisation de N est équilibrée (si p et q sont du même ordre de grandeur), alors est de l'ordre de grandeur de , et par conséquent la quantité est très proche de d.

On peut facilement rechercher exhaustivement k puisqu'il est inférieur à e, et donc calculer une quantité qui sera très proche de d (plus précisément, une moitié environ des bits de d (ceux de poids forts) seront égaux à ceux de ).

La seule connaissance des paramètres publics permet de retrouver la moitié des bits de la clef privée à condition que l'exposant public soit petit, et il me semble bien que c'est souvent le cas (e est souvent égal à 3 ou . Quelqu'un sait-il comment cette faille est contournée dans la pratique?
-----

[sylvainc2]

Il me semble que ton objection revient à ceci: il faut que p et q soit suffisamment éloignés l'un de l'autre, de sorte qu'on ne puisse pas factoriser n=pq en divisant n par les entiers impairs près de sqrt(n) jusqu'a ce qu'on trouve p. Si je me souviens bien, dans le logiciel PGP des années 1995 il faisait un test sur p et q de ce genre (|p-q| devait être un nombre de bits minimum) mais je pense que ce n'est plus recommandé aujourd'hui. Si p et q sont déterminés correctement (des entiers aléatoires de m/2 bits pour un n de m bits) alors la probabilité est très faible qu'ils soient trop près l'un de l'autre.

[invitecb6e3de4]

Même en admettant que p et q soient éloignés l'un de l'autre, la quantité sera ridiculement faible par rapport à , et bien qu'on ne puisse pas affirmer avec certitude pouvoir alors récuperer la moitié des bits de , on peut en récupérer la moitié moins une portion de bits dépendant de la taille de l'élément de le plus grand (p ou q) avec probabilité quasiment égale à 1 (enfin on aura une valeur pour chaque , et l'une d'elle sera bonne, mais est un petit entier).
Si je décide de récupérer la moitié moins 10 bits de ma valeur, ces bits seront corrects à moins que p ou q aie plus de 10 bits d'écart en plus par rapport à , ce qui ne doit se produire que très rarement.