Inscription / Connexion Nouveau Sujet
Niveau maths sup
Partager :

Chiffrement Rabin

Posté par
MrViyirus
14-06-19 à 21:51

Bonjour. J'ai une question sur le chiffrement de Rabin. Le sujet c'est:

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 B\in [[0, pq - 1]] . En posant n=pq, on appelle clé publique de Rabin le couple (n, B).

Soit L le message à transmettre et m = L(L+B) le message envoyé. Il faut donc ressoudre l'équation x2 + Bx = m dans Z/nZ.

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

1) Vérifier que la clef forurnie par Alice est une clé Rabin.

La clé est (77,9) donc pq=77 et les valeurs sont 7 et 11.  B=9 et B\in [[0, 76]]
Conclusion, la clé fournie par Alice est une clé Rabin.

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

\begin{cases} & \text{ } x^2= 2 mod 7 \\ & \text{ } x^2= 1 mod 11 \end{cases}

Je comprend pas comment on est arrivé la. J'ai vu que le message envoyé est m = 22 et on a l'equation :
x2 + Bx = 22 dans Z/77Z

Comment arriver a ce Système?

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 22:00

Bonjour
1) tu as omis la vérification du 3 modulo 4 pour p et q

Posté par
MrViyirus
re : Chiffrement Rabin 14-06-19 à 22:14

hmm, je crois qu'on peut utiliser l'algorithme d'Euclide:
7=3 mod 4
7x-4y=3

On a x= -1 pour 7x-4y=1 donc x = -3
Et pour la deuxieme

11=3 mod 4
11x-4y=3
On a x=-1 pour 11x-4y=1 donc x= -3

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 22:29

je ne comprends pas du tout tes x=-1 et x = -3 ....

Posté par
MrViyirus
re : Chiffrement Rabin 14-06-19 à 22:37

7 = 3 mod 4 est une équation de type 7x - 4y = 3 et j'ai trouvé que x = -3 et y = -6 donc -21 +24= 3

11 = 3 mod 4 est donc 11x - 4y = 3 et donc x = -3 et y = -9 donc -33 + 36 = 3

Tu as une autre méthode?

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 22:45

tu réponds à quelle question, là ? que représentent x et y ?

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 22:45

7 = 3 mod 4 n'est déjà pas une équation, mais une égalité

Posté par
MrViyirus
re : Chiffrement Rabin 14-06-19 à 22:55

Tu m'as dit que j'ai omis la vérification du 3 modulo 4 pour p et q donc j'ai essayé de le prouver.

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 23:02

tu as besoin de trucs aussi tordus pour voir que 7 = 4 + 3 et donc est congru à 3 modulo 4 ? et que 11 = 2*4 + 3 et donc est lui aussi congru à 3 modulo 4 ?

Posté par
MrViyirus
re : Chiffrement Rabin 14-06-19 à 23:09

Ah oui, brainlag, j'aime beaucoup compliquer la situation... t'as raison. Est-que tu as un hint pour exo 2?

Posté par
lafol Moderateur
re : Chiffrement Rabin 14-06-19 à 23:33

ce n'est pas un deuxième exercice mais la deuxième question de celui-ci
essaie de mettre toutes les hypothèses ensemble, de voir ce que tu peux utiliser

Posté par
MrViyirus
re : Chiffrement Rabin 14-06-19 à 23:55

Ok donc, on commence tout d'abord par m. L  est le message envoyé.
m = L(L +B) = 22*31 = 682
S'ill s'agit de Z/nZ on remplace 682 par 66? car 682 = 66 mod 77

Posté par
MrViyirus
re : Chiffrement Rabin 15-06-19 à 01:10

J'ai realisé que j'ai fait une faute. J'ai donc l'equation x^2+9x=22
en Z/7Z j'ai x^2+2x=1 ssi x(x+2)=1 et donc x = 8 car 8=1mod 7
en Z/11Z on a x^2-2x=0 et donc x=0 ou x=2????

Posté par
MrViyirus
re : Chiffrement Rabin 15-06-19 à 01:11

x=2* pour la premiere equation

Posté par
lafol Moderateur
re : Chiffrement Rabin 15-06-19 à 12:02

tu n'as ainsi qu'une des quatre solutions possibles ....
et tu n'as pas répondu à la question posée

Posté par
MrViyirus
re : Chiffrement Rabin 15-06-19 à 12:42

j'ai 4 solutions, pour les 2 equations.

pour 1) x^2 +9x = 22 dans Z/7Z
x^2 +2x=1 ssi x(x+2)=1 donc x = 2 ou x=3

pour 2) x^2 +9x = 22 dans Z/11Z
x^2 - 2x =0 ssi x(x-2)=0 donc x=0 ou x=2

Posté par
carpediem
re : Chiffrement Rabin 15-06-19 à 13:33

modulo 7 :

x^2 + 2x = 1 \iff x^2 - 5x + 6 = 0 \iff (x - 2)(x - 3) = 0

modulo 11 : trivial ...

Posté par
MrViyirus
re : Chiffrement Rabin 15-06-19 à 13:45

Oui j'ai x=2 et x=3 mais comment on est arrivé au systeme \begin{cases} x^2=2mod7 \\ x^2=1mod11 \end{cases}

Posté par
carpediem
re : Chiffrement Rabin 15-06-19 à 14:29

justement je ne suis pas intervenu avant ... parce que je ne vois pas !!!

je sais que tu as trouvé 2 et 3 ... mais ma réponse est là pour te faire réfléchir ... sur la résolution ...

Posté par
lafol Moderateur
re : Chiffrement Rabin 15-06-19 à 21:53

as-tu recopié ton énoncé tel quel ? en particulier, ce que tu appelles x et ce que l'énoncé appelle x, ce n'est pas la même chose
on arrive à ce système en factorisant L²+9L-22 modulo 77, donc avec 9L = 2\times (39\times 9L)
et x ne sera pas L

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1379 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !