Multiplication modulaire en cryptographie

marvell · February 2016

Bonjour à tous,

Je suis confronté à un problème de cryptographie par substitution polyalphabétique. L'alphabet en question est composé de 36 caractères, représentés par des entiers. Le cryptage est réalisé par l'opération Y = C × X % 37, où X est le caractère clair, C la clé, et Y le caractère crypté. Tous trois sont entiers, et appartiennent à l'intervalle [1 ; 36]. En pièce jointe se trouve deux tableaux : celui du haut représente le caractère crypté en fonction de la clé (en colonne) et du caractère clair (en ligne) ; celui du bas représente le caractère clair en fonction de la clé (en colonne) et du caractère crypté (en ligne).

Comment trouver mathématiquement X lorsque Y et C sont donnés ? J'eu l'idée de déterminer le quotient de la division de C × X par 37, afin de remonter à X… infructueusement. Auriez-vous des idées ?

Merci d'avance !

Fin de partie · February 2016

L'anneau $(\mathbb{Z}/37\mathbb{Z},+,\times)$ est un corps.
En particulier, si $c$ est un entier qui n'est pas divisible par $37$, il existe un entier $d$ tel que $cd$ est congru à $1$ modulo $37$.

PS:
Si tu te demandes d'où vient ce résultat, tu peux essayer de résoudre l'équation $cx-37y=1$, $x,y$ étant les inconnues, qui admet toujours au moins une solution, d'après le théorème de Bézout, si $pgcd(c,37)=1$.

PS2:
Le $d$ ci-dessus est la clef de décodage.

PS3:
Si tu n'es toujours pas convaincu, suppose que $c=2$ et vois ce qui se passe.

Jer anonyme · February 2016

NB : la table est symétrique : on peut sans dommage lire la clé en ligne et la lettre en colonne.

La clé de décryptage est un entier $D$ tel que « multiplier par $D$ » revienne au même que « diviser par $C$ ». Donc on veut avoir $CD=1\;[37]$. On regarde la colonne de $C$ : le $D$ cherché est le numéro de la ligne sur laquelle le « caractère crypté » $Y$ vaut $1$. En effet, c'est la valeur de $X$ pour laquelle $CX=1\;[37]$.

marvell · February 2016

L'inverse modulaire de la clé, bien sûr ! Merci beaucoup !

Multiplication modulaire en cryptographie

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 32