Casser RSA, BAC+3

[louisky]

Bonjour,

Etant en étude d'informatique, nous étudions RSA et surtout ces failles.
Le problème qui me bloque est le suivant :
Soient
avec :
les et sont des nombres premiers de k bits,
et e premiers avec sachant que et
On choisit un m ayant au plus 3 bits non nuls plus petit que n, c'est à dire que :
si on note le nombre de bits de m (en écriture binaire donc), avec = 1 si le k-ième bit est non nul, et 0 sinon.
En d'autre terme, la décomposition en base 2 de m est avec au maximum 3 non nuls.
et enfin

Il nous est demander de décoder RSA avec ses informations.
Les seules pistes que j'ai trouvées sont que :
(si m a 3 bits non nuls, avec autant de que de bits non nuls)
Je ne peux pas utiliser le binôme de Newton car les k_i peuvent devenir très grand (1024).

ps : Ce n'est pas parcequ'il y a 3 n_i et 3 M_i qu'on se doit de tous les utiliser.

Merci de votre lecture et de votre aide !
Cordialement, Louis.

[louisky]

J'ai une piste qui m'a l'air satisfaisante :
On sait que l'exponentiation modulaire a une compléxitée de O(n) et nous dans notre cas si on testait tous les m possibles, nous serions en O(n^3), donc si on teste tous les m, nous sommes en O(n^4) en temps.
En mémoire, nous sommes en O(1) si je ne m'abuse.

Donc peut-on dire que de tester tous les m avec une écriture de moins de 3 bits est un algorithme polynomial ?

[GaBuZoMeu]

Tu voudrais quelque chose de polynomial en k et pas en n, non ?
Est-ce que tu t'es mélangé les pinceaux entre k et n ?

[louisky]

tout à fait, je fais un abus de langage entre n et log(n) :

J'ai une piste qui m'a l'air satisfaisante :
On sait que l'exponentiation modulaire a une compléxitée de O(n) et nous dans notre cas si on testait tous les m possibles, nous serions en O(n^3), donc si on teste tous les m, nous sommes en O(n^4) en temps.
En mémoire, nous sommes en O(1) si je ne m'abuse.

Donc peut-on dire que de tester tous les m avec une écriture de moins de 3 bits est un algorithme polynomial ?

Je voulais dire :
On sait que l'exponentiation modulaire a une compléxitée de O(log(n)) et nous dans notre cas si on testait tous les m possibles, nous serions en O(log(n)^3), donc si on teste tous les m, nous sommes en O(log(n)^4) en temps.
En mémoire, nous sommes en O(1) si je ne m'abuse.

[GaBuZoMeu]

C'est bien ce que je disais, k est la moitié du log en base 2 de n.

[louisky]

Je ne vois pas trop pourquoi k serait la moitié de log 2 de n.
Pour moi on sait juste que k <= log 2 de n, non ?

[GaBuZoMeu]

n est le produit de deux nombres de k bits.

[louisky]

ah oui en effet !
Je n'ai pas été futé de réutiliser la lettre k ensuite, cela m'a perdu.

Enfin si mon algo est polynomial en log(k), il l'est aussi en log(n) puisque (et inversement ?) O(log(n)) = O(log(k^2)) = O(log(k) + log(k)) = O(log(k)) où suis-je dans l'erreur ?

[GaBuZoMeu]

Nan, ton algo est polynomial en k, qui est égal à log n à un facteur constant près.

À quoi sert d'avoir les trois ?

[louisky]

Je vois, merci.
Mais il est bien polynomial ?

Je suppose que le fait que RSA ne peut pas être décrypté de cette sorte et que ce serait en O(log(k)^log(k)) et ce qui n'est pas polynomial, c'est bien cela ?

[louisky]

À quoi sert d'avoir les trois ?

Notre professeur nous a donné les mêmes indications pour une multitude de questions, les trois étaient à utiliser avec le théorème des restes Chinois et un e = 3.
Pour cette question il suffit d'en avoir un seul, et à chaque itération de tester si notre m^e est le même que celui qui est utilisé pour les (le but étant de retrouver le m qui a codé les ).

[GaBuZoMeu]

Je suppose que le fait que RSA ne peut pas être décrypté de cette sorte et que ce serait en O(log(k)^log(k)) et ce qui n'est pas polynomial, c'est bien cela ?

Tu n'arrêtes pas de mélanger n et k. Fais attention !!!

Si tu essaies tous les entiers jusqu'à n, c'est quasi-linéaire en n et exponentiel en k.
Si tu essaies seulement les entiers à 3 bits non nuls inférieurs à n, c'est polynomial en k.

[louisky]

vous avez totalement raison je me suis mélangé les pinceaux, merci pour ces précisions !