Chiffrement Rabin

[Mavil]

Bonjour, je veux commencer par vous annoncer que je suis nulle en maths! Tout d'abord je veux essayer de comprendre ce que se passe ici.

On utilise les applications de la forme f(x) = x(x+B) dans Z/pqZ, ou p et q sont 2 nombres premiers distincts, congrus à 3 modulo 4 et . En posant n=pq, on appelle clé publique de Rabin le couple (n, B).

Soit L le message a transmettre et m=L(L+B) le message envoyé. Il faut donc résoudre l'équation dans Z/nZ

Alice envoie la clé publique (77,9). Bob veut informer Alice d'un événement secret. Il lui renvoie le message 22.

a) Verifier que la clef fournie par Alice est un clé Rabin.

77 = p*q ou p et q sont nombres premier distincts donc p = 7 et q =11.
B=9 et B appartient a [0, 76].
7 congru à 3 mod 4 car 4+3 = 7 Vrai.
11 congru à 3 mod 4 car 4*2+3=11 Vrai.
En conclusion la clé est une clé Rabin.

b) Montrer qu'Alice doit résoudre le système:


Ici je suis bloqué. Le message envoyé est 22 donc on a l'équation dans Z/nZ
dans Z/nZ
J'ai trouvé x = -11 et x = 2 et la c'est mort.

[LB2]

Bonsoir,

réduis ton équation modulo 7 :

x^2+9x=22 ssi x^2+2x=1 ssi x(x+2) = 1

Si tu fais la table des inverses de Z/7Z, on trouve ...

Même méthode (pas forcément optimale) pour Z/11Z

[Mavil]

Ah oui je vois. Donc on a x=2 car 8 = 1 mod 7.

La deuxieme est x^2 +9x = 22 ssi x^2 -2x = 0 ssi x(x-2) = 0 et x peut etre 0 ou 2 ???

[LB2]

attention 22 = 1 modulo 7

Ce qu'on a gagné, c'est que Z/7Z et Z/11Z sont des corps, donc on peut résoudre les équations du second degré sans trop de problèmes

on trouve x = 2 ou x = 3 modulo 7, x= 0 ou x=2 modulo 11

es tu sur de ton énoncé?

[LB2]

Il me semble qu'il y a une erreur d'énoncé : x = 10 vérifie les conditions x^2 = 2 mod.7 et x^2=1 mod. 11, et pourtant n'est pas solution de x^2+9x=22 dans Z/77Z

[Mavil]

Oui je suis sur que l'énoncé est correct. Je sais comment ressoudre le systeme mais je sais pas comment arriver à ce systeme.

[Mavil]

x^2 = 2 mod 7 donc x= 3 ou x=4
x^2 = 1 mod 11 donc x = 1 ou x=-1 car 1 premier et 11 premier.
Et on a donc 4 systemes

[Mavil]

Je dois résoudre le systeme correspondant dans N aux plus petites valeurs x, donc le premier sys.

On applique la théorème des restes chinois et on a x= 3*11*2 + 1*7*(-3) = 66 - 21 = 45 mod 77