Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Chiffrement Rabin
Posté par MrViyirus
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 . 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
Conclusion, la clé fournie par Alice est une clé Rabin.
2)Montrer qu'Alice doit résoudre le système:
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?
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
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?
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 ?
Ah oui, brainlag, j'aime beaucoup compliquer la situation... t'as raison. Est-que tu as un hint pour exo 2?
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
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
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????
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
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 ...
Annuler
connectez vous
arithmétique en post-bac