Instructions
Crée une implémentation du chiffre affine, un ancien système de chiffrement apparu au Moyen-Orient.
Le chiffre affine est un type de chiffre de substitution monoalphabétique.
Chaque caractère est associé à son équivalent numérique, chiffré à l'aide d'une fonction mathématique, puis converti en la lettre correspondant à sa nouvelle valeur numérique.
Bien que tous les chiffres monoalphabétiques soient faibles, le chiffre affine est bien plus robuste que le chiffre Atbash, car il possède beaucoup plus de clés.
Chiffrement
La fonction de chiffrement est :
E(x) = (ai + b) mod m
Où :
-
i est l'indice de la lettre, de 0 à la longueur de l'alphabet moins 1.
-
m est la longueur de l'alphabet.
Pour l'alphabet romain, m vaut 26.
-
a et b sont des entiers qui constituent la clé de chiffrement.
Les valeurs a et m doivent être premières entre elles (ou, étrangères entre elles) pour que le déchiffrement automatique fonctionne, c'est-à-dire qu'elles ont pour unique facteur commun le nombre 1 (tu trouveras plus d'informations dans l'article Wikipédia consacré aux nombres premiers entre eux).
Si a n'est pas premier avec m, le programme doit signaler qu'il s'agit d'une erreur.
Sinon, il doit chiffrer ou déchiffrer avec la clé fournie.
Dans cet exercice, les chiffres sont des entrées valides, mais ils ne sont pas chiffrés.
Les espaces et les caractères de ponctuation sont exclus.
Le texte chiffré est écrit par groupes de longueur fixe séparés par un espace, la taille de groupe traditionnelle étant de 5 lettres.
Cela rend plus difficile de deviner le texte chiffré à partir des frontières entre les mots.
Déchiffrement
La fonction de déchiffrement est :
D(y) = (a^-1)(y - b) mod m
Où :
-
y est la valeur numérique d'une lettre chiffrée, c'est-à-dire y = E(x)
- il est important de noter que
a^-1 est l'inverse multiplicatif modulaire (IMM) de a mod m
- l'inverse multiplicatif modulaire n'existe que si
a et m sont premiers entre eux.
L'IMM de a est le x tel que le reste de la division de ax par m soit 1 :
ax mod m = 1
Pour en savoir plus sur la façon de trouver un inverse multiplicatif modulaire et sur ce qu'il signifie, consulte l'article Wikipédia correspondant.
Exemples généraux
- Le chiffrement de
"test" donne "ybty" avec la clé a = 5, b = 7
- Le déchiffrement de
"ybty" donne "test" avec la clé a = 5, b = 7
- Le déchiffrement de
"ybty" donne "lqul" avec la mauvaise clé a = 11, b = 7
- Le déchiffrement de
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" donne "thequickbrownfoxjumpsoverthelazydog" avec la clé a = 19, b = 13
- Chiffrer
"test" avec la clé a = 18, b = 13 est une erreur, car 18 et 26 ne sont pas premiers entre eux
Exemple de recherche d'un inverse multiplicatif modulaire (IMM)
Recherche de l'IMM pour a = 15 :
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, c'est-à-dire 105 mod 26 = 1
-
7 est l'IMM de 15 mod 26
