Fonction réciproque et modulo

[christo]

Bonjour à tous.
Je prépare mes examens de cryptographie et je suis tombé sur un problème simple que je n'arrive pas a résoudre :

Soit E, une fonction d'encodage et D, une fonction de décodage.
Soit k, un entier constant (la clé)

E(x) = (x.k) mod 26

E et D sont par définition des fonctions réciproques d'où :
E(x) = D^(-1)(x), D(x)=E^(-1)(x) et D(E(x)) = x

Ne connaissant pas la fonction réciproque du modulo, je n'arrive pas à définir la fonction D.

Ce devrair être un problème facile pour un mathématicien ?
:we: Merci d'avance pour vos réponses

[Rafar]

Salut,
je ne connais rien en cryptographie, mais j'imagine que si tu ne veux pas perdre d'information en codant, ton entier k ne doit pas être quelconque mais qu'il doit être premier avec 26, non ?

[christo]

Ici, c'est x qui doit être premier avec 26. k doit juste ête impaire.

Le but est de trouver D, la réciproque de la fonction E.

Voici un exemple :

Avec un clé fixe k=19 et un message clair x=12, on trouve le message chiffré c

E(12) = (12x19) mod 26 = 9 d'où c=9

et D(9) = 12

[Rafar]

Si k est fixé, premier avec 26, alors c'est facile.
Tu calcules l'inverse de k dans Z/26Z.
Pour cela, tu utilises la relation de Bezout ie tu trouves 2 entiers u et v tels que : u.k + v.26 = 1 (obtenu par l'algorithme d'Euclide)

Par exemple pour k = 19, 11.19 - 8.26 = 1. (et donc u = 11 et v = -8 )

Alors l'inverse de k dans Z/26Z est l'entier u (pour k = 19, on a u = 11)
et pour inverser E (et donc calculer D) il suffit alors de multiplier par u et de calculer le résultat modulo 26.

Par exemple pour E(12) = 12.19 mod 26 = 20 (20 et non 9 ! :hum: ) et pour calculer l'original D(20) = 11.20 mod 26 = 12
Autre exemple E(5) = 5.19 mod 26 = 17 et pour calculer l'original D(17) = 11.17 mod 26 = 5.
Tu as donc (pour la clef k=19) D(x) = x.11 mod 26

Maintenant pour une clef non première avec 26, tu ne peux pas toujours calculer D ! (l'application E n'est pas bijective)
Par exemple si tu prend k = 13, alors tu as E(2) = E(0) = 0 donc quand tu as 0 dans ton message codé, tu ne sais pas si c'est le codage de 0 ou bien de 2 (ou 4 ou 6 ou etc...).

Je ne peux pas t'aider plus, je ne connais pas la crypto.
Si tu as des questions, esaie au maximum de les traduire en termes compréhensibles par un pauvre matheux comme moi :happy2:

[Rafar]

Ici, c'est x qui doit être premier avec 26. k doit juste ête impaire.

Le but est de trouver D, la réciproque de la fonction E.

Voici un exemple :

Avec un clé fixe k=19 et un message clair x=12, on trouve le message chiffré c

E(12) = (12x19) mod 26 = 9 d'où c=9

et D(9) = 12

Y'a un truc que je comprends pas : tu dis que x doit être premier avec 26 et tu prends x = 12 qui n'est pas premier avec 26 :hein: