Chiffrement Rabin

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Mavil
Membre Naturel
Messages: 10
Enregistré le: 29 Mai 2019, 11:24

Chiffrement Rabin

par Mavil » 15 Juin 2019, 01:37

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
Habitué(e)
Messages: 772
Enregistré le: 05 Nov 2017, 18:32

Re: Chiffrement Rabin

par LB2 » 15 Juin 2019, 01:52

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
Membre Naturel
Messages: 10
Enregistré le: 29 Mai 2019, 11:24

Re: Chiffrement Rabin

par Mavil » 15 Juin 2019, 02:02

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
Habitué(e)
Messages: 772
Enregistré le: 05 Nov 2017, 18:32

Re: Chiffrement Rabin

par LB2 » 15 Juin 2019, 02:06

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
Habitué(e)
Messages: 772
Enregistré le: 05 Nov 2017, 18:32

Re: Chiffrement Rabin

par LB2 » 15 Juin 2019, 02:15

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
Membre Naturel
Messages: 10
Enregistré le: 29 Mai 2019, 11:24

Re: Chiffrement Rabin

par Mavil » 15 Juin 2019, 02:19

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

Mavil
Membre Naturel
Messages: 10
Enregistré le: 29 Mai 2019, 11:24

Re: Chiffrement Rabin

par Mavil » 15 Juin 2019, 02:23

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
Membre Naturel
Messages: 10
Enregistré le: 29 Mai 2019, 11:24

Re: Chiffrement Rabin

par Mavil » 15 Juin 2019, 02:37

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

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 14 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite