Exercice d'arithmétique sur le cryptosystème de Elgamal

[Solofein]

Bonjour,
Je suis en train de travailler sur un exercice d'arithmétique qui parle du cryptosystème de Elgamal et je ne comprend pas pourquoi je bloque ...
Je ne sais pas si j'ai fait une erreur de calcul ou si j''ai mal compris la méthode ...

Exercice

Alice et Bernard décident d’utiliser l’algorithme d’El Gamal. Il utilise le corps avec
l’élément .

1 Déterminer l’ordre de 15 dans

Ma réponse : 15 est générateur de 19 et donc d'ordre 18

2 Bernard choisit sa clé privée . Déterminer sa clé publique .

Ma réponse : ( dans ).
Donc C = 9.


3 Alice choisit une clé temporaire privée . Quelle est sa clé publique D ? Elle souhaite
envoyer le message . Elle le chiffre en utilisant la clé publique C de Bernard par . Calculer ce message chiffré.

Ma réponse :
- ( dans ).
-On cherche (dans ).
Le message qu'elle envoie est donc : (2,6)

4 Comment Bernard retrouve-t-il le message m ?

Donc la je me suis aidé de wikipedia qui m'a dit que Sauf que je tombe sur un truc du genre :

sauf que je devrais retrouver 17 non ? parceque c'eset pas définit sur


!!!
Pliiiiiiz help me xD,
merci d'avance ^^

[Ben314]

J'ai pas vérifié tout les calculs, mas, le calcul final qui te pose problème, il est lui aussi modulo 19 et, comme F19 est un corps et que 16 est non nul modulo 19, on peut parfaitement calculer 6/16 modulo 19.

Comment on fait pour calculer 6/16 modulo 19 ?

Avec des nombres petits comme ici, on peut le faire "comme au primaire", c'est à dire essayer 16x0, 16x1, 16x2,... (modulo 19 évidement) j'usqu'à ce que l'on trouve 6 comme résultat. Bien sur si 16xA=6, c'est que... A=6/16

Sinon, avec un peu plus de bagage, on peut utiliser l'algo. d'euclide sur 16 et 19 pour trouver deux entiers u et v tels que 16u+19v=1. cela signifie que 16u=1 modulo 19 et donc que u=1/16 modulo 19.
Bien évidement, 6/16=6u modulo 19.

Edit : remarque qu'ici, tout ce que je t'ai dit est un peu con : tu sait que tu doit trouver 6/16=17. Il te suffit évidement de vérifier que 16x17=6 modulo 19 (ce qui est VRAI !!!!)

[Solofein]

Ah, merci beaucoup pour la réponse rapide, oui j'avais complètement zappé d'utiliser bezout pour chercher l'inverse de 16 modulo 19 ... "^^ j'ai honte, merci beaucoup

EDIT : d'utiliser l'algorithme d'Euclide. ^^

[Ben314]

Regarde aussi mon edit : ici, vu qu'on a le résultat...

Enfin, ça permet de faire un "rappel"...