Introduction à la cryptographie symétrique : La méthode de Substitution et de Permutation

La cryptographie ne peut exister sans un support formel. Avant d'être une technique utilisée pour dissimuler de l'information, elle est d'abord une science de la représentation. Pour sécuriser une information, il faut la traduire d'un état intelligible (le message initial) vers un système de symboles rigoureux (le résulat), capable d'être manipulé par des algorithmes mathématiques. C'est ce qu'on appelle le codage. Et la cryptographie est l'une des branches de cette dernière.

Codage de l'information

Le codage est le processus de mise en correspondance d'un message source avec une représentation symbolique cible, déterminée par les contraintes connues.

\[C(m, \sigma) = m'\]

• \(C\) : l'opération de codage
• \(m\) : le message initial
• \(\sigma\) : La contrainte
• \(m'\) : Le résultat

La notion de contrainte connue est importante, puisque la réversibilité du processus en dépend : sans l'accès à la règle de correspondance (σ) ayant présidé à la transformation, le message devient indiscernable d'un bruit aléatoire. Le décodage est le processus inverse qui, à partir du résultat et par l'application de la fonction inverse régie par la même contrainte (ou clé) de correspondance, produit le message source.

\[D(C(m, \sigma), \sigma) = m - \epsilon\]

Le terme \(\epsilon\) désigne l’"erreur résiduelle" ou la "perte d’intégrité" consécutive à la transcription :

• \(\epsilon = 0\) (Codage sans perte ou "Lossless") : La réversibilité est parfaite. C'est un impératif en cryptographie où l'intégrité du message source doit être préservée.
• \(\epsilon > 0\) (Codage avec perte ) : La transcription est volontairement destructive. On accepte une dégradation de la précision (comme dans le standard JPEG) pour satisfaire une contrainte de compression mais tout en maintenant un résultat jugé acceptable pour l'usage final.

On peut diviser le codage en trois grandes familles, chacune répondant à une contrainte spécifique (\(σ\)).

1. Le Codage de Source (Compression) : L'objectif est de réduire la redondance du message initiale pour économiser de l'espace disque ou de la bande passante. Il peut s'agir d'une réduction sans perte (\(\epsilon = 0\), dans le cas de ZIP, PNG ou FLAC) ou avec perte (\(\epsilon > 0\), comme pour JPEG, MP3).
2. Le codage de représentation (Transcodage) : Substitution d'un alphabet source par un alphabet cible, sans modification de l'entropie du message pour permettre son échange entre deux systèmes ou support de communication.
3. Le codage secret (Cryptographie) : La cryptographie est un processus de transformation visant à garantir la confidentialité du message en rendant son contenu inintelligible pour un tiers qui ne connait pas la contrainte (\(\sigma\)).

Ce qui nous intéresse dans cet article c'est donc la dernière famille, la cryptographie. Et nous allons étudier quelques exemples de méthodes par ordre croissant de difficulté de décodage sans la contrainte ; en somme, de la méthode la moins robuste à la plus robuste.

Méthode de substitution mono-alphabétique

La méthode de substitution mono-alphabétique est l'une des techniques de chiffrement les plus anciennes. Elle consiste à remplacer chaque lettre d'un message par une autre lettre tout en conservant la cette correspondance (la contrainte) tout au long du texte.

L'une des applications les plus connus est "Le chiffre de César" : Pour protéger ses messages militaires confidentiels, Jules César utilisait cette méthode. Il décalait chaque lettre du message à chiffrer d'un nombre fixe de places dans l'alphabet. Par exemple, avec un décalage de 3 :

• A devient D
• B devient E
• C devient F

Le message Hello World, devient Khoor Zruog (un véritable nom d'Orc !).

Ainsi, le chiffrement de César traite chaque caractère individuellement comme un élément du groupe additif \(\mathbb{Z} / 26\mathbb{Z}\) nommé "groupe quotient" où l'on considère 2 caractères comme étant les mêmes si il diffère d'un multiple de 26 (pour un alphabet de 26 caractères).

De manière formelle, considérons \(x\) la valeur numérique (ou le rang), d'une lettre claire et \(k\) la clé (le décalage). La fonction de chiffrement \(C\) est une translation dans l'anneau des entiers modulo 26 :

\[E_k(x) = (x + k) \pmod{26}\]

Le déchiffrement \(D\) est l'opération inverse :

\[D_k(y) = (y - k) \pmod{26}\]

Le chiffrement de César est une application linéaire très simpliste qui souffre de nombreuses faiblesses :

• Comme il s'agit d'une bijection sur un ensemble de cardinalité faible (n = 26), l'espace des clés est d'autant plus réduite à \(\lvert K \rvert = n - 1 = 25\)
• D'un point de vue statistique, cette méthode de modifie pas l'histogramme des fréquences des élements de l'alphabet. Par exemple, en français, la lettre \(e\) est la plus fréquente. Dans le texte chiffré, la lette la plus fréquente sera donc \((4 - k) \pmod{26}\).
• Afin, la forme du signal est identique. Le vocabulaire (répétitions de patterns) et grammaire (structures répétitive comme la terminaisons des verbes ou la présence d'article) restent identifiables par leurs fréquences.

Méthodes de permutation

La méthode de chiffrement par permutation consiste à mélanger l'ordre des lettres ou des blocs d'un message selon une règle ou une clé (la contrainte) sans modifier les lettres elles-mêmes. Contrairement à la méthode par substitution, les lettres d'origines restent les mêmes et seules leurs positions changent, créant ainsi une sorte d'anagramme.

Pour éviter d'avoir une clé qui doit s'adapter à la taille du message à chiffrer, on décide arbitrairement que la clé fera 5 caractères. On découpe ainsi notre message à chiffrer par bloc de 5 caractères correspondant à la longueur de la clé. Ainsi dans l'exemple suivant :

• Message à chiffrer : Hello World
• Clé : 31524

La clé indique pour chaque caractère du bloc sa nouvelle position :

1. On découpe notre message en bloc de 5 : Helloet World.
2. Pour chaque bloc, on applique la clé :
   1. Hello(31524)
   2. World(31524)
3. Pour Hello, le Hpasse en en 3ème position, le e passe en 1ère position ...

Message d'origine	h	e	l	l	o
Clé	3	1	5	2	4
Message chiffré	e	l	h	o	l

De manière formelle, soit l'alphabet A fini de longueur \(n \in \mathbb{N}^*\), le message clair Mest donc un élément de l'ensemble \(A^n\). La clé quant à elle, est une permutation \(\sigma\), c'est à dire une bijection de l'ensembles des indices \(\{1, 2, \dots, n\}\) vers lui-même.

Soit \(M = (m_1, m_2, \dots, m_n) \in {A}^n\), le chiffrement par clé est l'application \(e_\sigma : {A}^n \to {A}^n\) qui associe à \(M\) un vecteur chiffré \(C = (c_1, c_2, \dots, c_n)\) défini par :

\[ e_\sigma(m_1, m_2, \dots, m_n) = (m_{\sigma(1)}, m_{\sigma(2)}, \dots, m_{\sigma(n)})\]

Qui se traduit par une relation d'indéxation :

\[\forall i \in \{1, 2, \dots, n\}, \quad c_i = m_{\sigma(i)}\]

Pour \(K\) l'ensemble des clés possibles et donc \(\lvert K \rvert\) le nombre total de clés valides que l'on peut utiliser :

• Comme il s'agit d'une bijection sur un ensemble d'indices de taille de bloc \(L\) généralement faible, l'espace des clés est d'autant plus réduit à \(\lvert K \rvert = L! - 1\). Bien que la croissance soit factorielle, le cassage par force brute reste instantané pour des petites tailles de bloc.
• Comme pour la substitution, cette méthode ne modifie pas l'histogramme des fréquences des éléments de l'alphabet.
• Pour finir, comme la substitution, la forme du signal conserve une structure périodique. Le vocabulaire et la grammaire restent identifiables par leurs fréquences à des intervalles réguliers multiples de \(L\).

Méthode couplée Substitution + Permutation

Pour pallier les faiblesses intrinsèques des méthodes de substitution et de permutation utilisées de manière isolée, la cryptographie moderne s'appuie sur leur combinaison. Celle-ci, souvent appelée réseau de substitution-permutation (SPN), vise à briser la corrélation statistique des fréquence et la structure positionnelle du message.

Le principe d'un réseau de substitution-permutation (SPN), est l'alternance des méthodes. Considérons le message \(M\) composé de blocs de taille \(L\), une itération du chiffrement "couplé" se décomponse en deux phases successives :

1. Phase de Confusion (Substitution) : Chaque symbole du bloc est remplacé par un autre selon une table de substitution (dit S-box) définie par une sous-clé \(K_S\). Grâce à l'alternance de la clé, la linéarité de la substitution est brisée et l'histogramme des fréquences est modifiée. Ainsi l'opération \(S(M) = (s(m_1), s(m_2), \dots, s(m_L))\) où \(s\) est une bijection non-linéaire dépendante de la clé.
2. Phase de Diffusion (Permutation) : Les symboles résultants sont réarrangés selon une permutation \(/omega\) définie par une sous-clé \(K_p\). Cette opération "disperse" l'influence d'un seul symbole clair sur plusieurs symboles chiffrés. L'opération est \(P(S(M)) = (s(m_{\sigma(1)}), s(m_{\sigma(2)}), \dots, s(m_{\sigma(L)}))\)

L'opération compl!te de chiffrement \(E\) sur un bloc \(M\) avec une clé \(K = (K_s, K_p)\) s'écrit : \(E_K(M) = P_{K_p}(S_{K_s}(M))\)

Cette séquence est itérée sur plusieurs tours où la sortie d'un tour devient l'entrée du suivant, souvent avec l'ajout d'une clé de tour différente (\(K_i\)) via une opération XOR à chaque étape. C'est sur ce principe itératif que reposent certains des algorithmes standards modernes tels que l'AES (Advanced Encryption Standard), qui utilise des tours successifs de substitutions (via la S-box), de permutations (ShiftRows et MixColumns) et d'additions de clés.

Exemple

Prenons un exemple, le message "Hello" avec les contraintes suivantes :

• Clé de Substitution (\(K_s\)) : \(s(x)=x+2\) (substitution de +2 positions)
• Clé de Permutation (\(K_p\)) : Clé \(\sigma\) de bloc 5 :
  • \(\sigma(1)\) = 3
  • \(\sigma(2)\) = 5
  • \(\sigma(3)\) = 1
  • \(\sigma(4)\) = 4
  • \(\sigma(5)\) = 2

La 1ère étape, la susbtitution :

Position	Lettre Claire (mi)	Calcul (mi+2)	Lettre Substituée (s(mi))
1	H	H + 2	J
2	e	e + 2	g
3	l	l + 2	n
4	l	l + 2	n
5	o	o + 2	q

Le résultat au moment de la méthode : Jgnnq

La 2ème étape, la permutation :

Position	Valeur Initiale	Nouvelle Position	Nouvelle Valeur (Placée ici)
1	J	3	n
2	g	5	q
3	n	1	J
4	n	4	n
5	q	2	g

Le message chiffré est nqJng

• La fréquence du message initiale est détruite (remarque : Dans "Hello", la lettre l apparaît deux fois. Dans le texte chiffré nqJng, la lettre n apparaît deux fois. Cependant, ces deux n ne proviennent pas de la même position relative initiale)
• La structure est brisée : nqJng ne ressemble à aucun mot anglais ou français. La permutation a mélangé l'ordre des sons.

Et enfin, le chiffrement est réversible : Pour déchiffrer, on doit faire exactement l'inverse dans l'ordre inverse. D'abord, inverser la permutation (remettre les lettres à leur place originale : n en 3, q en 5, J en 1 ... etc) et ensuite inverser la substitution (retirer 2 à chaque lettre : J-2=H, g-2=e ... etc).