Chiffrement par substitution
() February 17, 2021 1 / 11
Substitution monoalphabétique
La substitution monoalphabétique est une des plus anciennes méthodes de
chiffrement.
Elle consiste à remplacer dans le texte clair chaque lettre par une autre lettre
ou un autre symbole.
Parmi les méthodes de chiffrement les plus connues utilisant cette technique,
on citera le chiffrement de César, le chiffrement affine, ou encore les chiffres
désordonnés.
Toutes ces méthodes de chiffrement sont sensibles à l’analyse de fréquence
d’apparition des lettres (nombre de fois qu’apparait une même lettre dans un
texte).
De nos jours, ces chiffres sont utilisés pour le grand public, pour les énigmes
de revues ou de journaux.
() February 17, 2021 2 / 11
Chiffrement de César
Il s’agit d’un des plus simples et des plus populaires des méthodes de
chiffrement classiques.
Son principe est un décalage des lettres de l’alphabet suivant un ordre
indiqué par la clé.
Dans les formules ci-dessous, p est l’indice de la lettre de l’alphabet, k est le
décalage (la clé).
Pour le chiffrement, on aura la formule
C = E (p) = (p + k) mod 26.
Pour le déchiffrement, il viendra
p = D(C ) = (C − k) mod 26.
Si on connait que le procédé de chiffrement utilisé pour un chiffrement est
celui de César alors la cryptanalyse utilisant l’attaque par force brute est très
facile à réaliser.
En effet, dans le cas du chiffre de César, seules 25! clés sont possibles.
() February 17, 2021 3 / 11
Exemple
Chiffrer le mot ”BONJOUR” en utilisant un décalage de k = 10
A B C D E F G H I J K L M
J K L M N O P Q R S T U V
N O P Q R S T U V W X Y Z
W X Y Z A B C D E F G H I
Le texte chiffré obtenu est alors ”KXWSXDA”.
Pour le déchiffrement, il suffit de refaire le tableau.
() February 17, 2021 4 / 11
Chiffrement affine
C’est une méthode de chiffrement basé sur un chiffrement par substitution
mono-alphabétique.
C’est une version améliorée du chiffrement de César.
L’idée est, au lieu d’additionner le pas de décalage, d’utiliser comme fonction
de chiffrement une fonction affine du type
Y = (aX + b) mod 26
où a et b sont des constantes, X et Y sont des nombres correspondant aux
lettres de l’alphabet (A = 0, B = 1, ...)
On peut remarquer que si a = 1, alors on retrouve le chiffre de César où b est
le décalage (le k du chiffre de César).
Si b = 0, alors ”A” est toujours chiffré ”A” car il ne subit aucun décalage.
En effet, si aucun décalage n’a lieu, l’alphabet de départ se retrouve chiffré
par lui même, et donc ne subit aucune modification.
() February 17, 2021 5 / 11
Chiffrement et déchiffrement
Pour le chiffrement affine, la clé est constituée de (k1 , k2 ) où k1 , k2 ∈ [0, 25]
et tel que PGCD(k1 , 26) = 1.
k1 doit être choisi parmi les lettres suivantes
1,3,5,7,9,11,15,17,19,21,23,25.
k2 peut prendre n’importe quelle valeur dans [0, 25].
Dans ce cas le nombre de clés possibles est 12 ∗ 26 = 312.
Le chiffrement est donné par l’opération
ci = k1 ∗ mi + k2 mod 26
où mi représente la position de la lettre du texte clair, ci le résultat du
chiffrement de la lettre mi et le couple (k1 , k2 ) la clé de chiffrement.
Pour le dchiffrement, on effectue l’opération
mi = k1−1 ∗ (ci − k2 ) mod 26
où ci est le résultat du chiffrement de la lettre mi (mi représentant la
position de la lettre du texte clair), k1−1 est l’inverse modulaire de k1 dans
[0, 25], tel que k1−1 ∗ k1 mod 26 = 1.
Les valeurs de k1−1 selon k1 sont:
k1 1 3 5 7 9 11 15 17 19 21 23 25
k1−1 1 9 21 15 3 19 7 23 11 5 17 25
() February 17, 2021 6 / 11
Exemple
Chiffrer le mot ”CRYPTO” avec la clé (5, 3).
Le PGCD(5, 26) = 1 =⇒ la clé est valide.
mi Rang Chiffrement Résultat ci
C 2 (5 ∗ 2 + 3) mod 26 13 N
R 19 (5 ∗ 17 + 3) mod 26 10 K
Y 24 (5 ∗ 24 + 3) mod 26 19 T
P 15 (5 ∗ 15 + 3) mod 26 0 A
T 19 (5 ∗ 19 + 3) mod 26 20 U
O 14 (5 ∗ 14 + 3) mod 26 21 V
Le texte chiffré est aLors ”NKTAUV”
() February 17, 2021 7 / 11
Dechiffrer le texte chiffré ”NKTAUV” en utilisant la clé (5, 3)
ci Rang déchiffrement Résultat mi
N 13 21 ∗ (13 − 3) mod 26 2 C
K 10 21 ∗ (10 − 3) mod 26 17 R
T 19 21 ∗ (19 − 3) mod 26 24 Y
A 0 21 ∗ (0 − 3) mod 26 15 P
U 20 21 ∗ (20 − 3) mod 26 19 T
V 21 21 ∗ (21 − 3) mod 26 14 O
Le mot clair correspondant est alors ”CRYPTO”.
Remarque
Le chiffrement affine ne résiste pas à une attaque par force brute puisque l’espace
des clés n’est pas suffisamment grand.
Il est également possible de faire l’analyse de fréquence des lettres pour casser ce
système de chiffrement.
() February 17, 2021 8 / 11
