La substitution
Principe
Comme nous l'avons vu le principe la méthode affine est un cas particulier de la méthode de César (en effet une clef affine de la forme \( (1,k)\) donne le même cryptogramme qu'un message chiffré obtenu par la méthode de César de clef \( k\) ). Il existe un moyen de généraliser davantage ces méthodes.
Considérons par exemple un chiffrement affine de taille \( 1\) de clef \( (3,2)\) . Alors
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{La lettre} &A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline
\text{est transformée en}&C&F&I&L&O&R&U&X&A&D&G&J&M\\\hline
\end{array}
\]
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{La lettre} &N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline
\text{est transformée en}&P&S&V&Y&B&E&H&K&N&Q&T&W&Z\\\hline
\end{array}
\]
On observe que chaque lettre est remplacée par une autre (cela ne pouvait pas être autrement par construction du cryptosystème affine).
On pourrait prendre le problème à l'envers et proposer un melange, comme par exemple
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{La lettre} &A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline
\text{est transformée en}&A&Z&E&R&T&Y&U&I&O&P&Q&S&D\\\hline
\end{array}
\]
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{La lettre} &N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline
\text{est transformée en}&F&G&H&J&K&L&M&W&X&C&V&B&N\\\hline
\end{array}
\]
Ce mélange provient-il d'une fonction affine \( C(x)\equiv_{26}ax+b\) ?
Si c'était le cas, le fait que le \( A\) reste identique nous indique que \( C(0)\equiv_{26}0\) soit \( a\times0+b\equiv_{26}0\) . Ainsi, on a \( b\equiv_{26}0\) . En observant la transformation du \( B\) en \( Z\) , on arrive à l'équation
\( a\times1\equiv_{26}25\) et donc \( a\equiv_{26}25\) . Finalement, la fonction affine correspondant à ce mélange ne peut-être que \( C(x)\equiv_{26}25x\) .
Mais \( C(2)\equiv_{26}25\times 2 \equiv_{26} 50 \equiv_{26} 24\) et normalement la lettre \( C\) devrait être cryptée en \( Y\) ce qui n'est pas le cas.
En conclusion, ce mélange ne correspond pas à un cryptosystème affine. Nous pouvons tout de même lui donner un cadre : celui des substitutions.
Le groupe symétrique
Définition
Soit \( X\) , \( Y\) deux ensembles et \( f: X\rightarrow Y\) une application. On dira que \( f\) est une application bijective où une bijection de \( X\) sur \( Y\) si
\[\forall y\in Y,\ \exists ! x\in X,\ f(x)=y\]
Par exemple la fonction \( f:[1;2]\rightarrow [2;3]\) , \( x\mapsto x+1\) est une bijection de \( [1;2]\) vers \( [2;3]\) .
Proposition
Soit \( X\) , \( Y\) deux ensembles et \( f: X\rightarrow Y\) une application bijective. Il existe une application \( g: Y\rightarrow X\) tel que
\[\Big(\forall x\in X,\ g\big(f(x)\big)=x\Big)\quad \wedge
\quad\Big(\forall y\in Y,\ f\big(g(y)\big)=y\Big)\]
On dit que \( g\) est l'application réciproque, ou la bijection inverse et est notée \( f^{-1}\) .
Démonstration
Par définition d'application bijective, pour chaque élément \( y\in Y\) , il existe un unique \( x\in X\) tel que \( f(x)=y\) . On considère l'application \( g\) qui associe à chaque \( y\) cet unique élément \( x\) : \( g(y)=x\) où par construction \( f(x)=y\) . Ainsi \( f(g(y))=f(x)=y\) et \( g(f(x))=g(y)=x\) .
Par exemple la bijection inverse de \( f:[1;2]\rightarrow [2;3]\) , \( x\mapsto x+1\) est \( g:[2,3]\rightarrow[1;3]\) , \( y\mapsto y-1\) .
Remarque
Il faut faire attention à la notation. En général \( f^{-1}(y)\neq \dfrac{1}{f(y)}\) . La notation \( f^{-1}\) fait cependant bien référence à un inverse mais il s'agit de l'inverse pour la composition des fonctions (le \( \circ\) ).
Définition
Soit \( n\in \N\) . Le groupe symétrique d'ordre \( n\) est l'ensemble formé des bijections de l'ensemble \( [\![1;n]\!]\) sur lui-même. On le note \( \mathfrak{S}_n\) . Les éléments de \( \mathfrak{S}_n\) sont appelés des permutations.
Par exemple pour \( n=2\) . L'ensemble \( \mathfrak{S}_2\) est composé des bijections de l'ensemble \( [\![1;2]\!]=\{1;2\}\) . Il est facile de voir qu'il n'y a pas beaucoup de possibilités.
\begin{eqnarray*}
\sigma_1 : [\![1;2]\!] & \longrightarrow & [\![1;2]\!]\\
1&\longmapsto&1\\
2&\longmapsto&2
\end{eqnarray*}
\begin{eqnarray*}
\sigma_2 : [\![1;2]\!] & \longrightarrow & [\![1;2]\!]\\
1&\longmapsto&2\\
2&\longmapsto&1
\end{eqnarray*}
Ainsi \( \mathfrak{S}_2=\{\sigma_1, \sigma_2\}\)
1 est composé de deux éléments.
Détaillons l'exemple de \( \mathfrak{S}_3\) formé des bijections de l'ensemble \( [\![1;3]\!]=\{1;2;3\}\) sur lui-même.
\begin{eqnarray*}
\sigma_1 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&1\\
2&\longmapsto&2\\
3&\longmapsto&3
\end{eqnarray*}
\begin{eqnarray*}
\sigma_2 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&1\\
2&\longmapsto&3\\
3&\longmapsto&2
\end{eqnarray*}
\begin{eqnarray*}
\sigma_3 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&2\\
2&\longmapsto&1\\
3&\longmapsto&3
\end{eqnarray*}
\begin{eqnarray*}
\sigma_4 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&2\\
2&\longmapsto&3\\
3&\longmapsto&1
\end{eqnarray*}
\begin{eqnarray*}
\sigma_5 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&3\\
2&\longmapsto&2\\
3&\longmapsto&1
\end{eqnarray*}
\begin{eqnarray*}
\sigma_6 : [\![1;3]\!] & \longrightarrow & [\![1;3]\!]\\
1&\longmapsto&3\\
2&\longmapsto&1\\
3&\longmapsto&2
\end{eqnarray*}
Ainsi \( \mathfrak{S}_3=\{\sigma_1,\sigma_2,\sigma_3,\sigma_4,\sigma_5,\sigma_6\}\) est composé de six éléments.
Remarque
Dans la pratique, on ne décrit pas les éléments de \( \mathfrak{S}_n\) de la manière ci-dessus. C'est bien trop fastidieux. Nous allons adopter une notation beaucoup plus élégante et adaptée aux manipulations.
Prenons l'exemple de la permutation \( \sigma_6\) qui transforme le \( 1\) en \( 3\) , le \( 2\) en \( 1\) et le \( 3\) en \( 2\) . Nous allons la noter \( (1\ 3\ 2)\) . Le \( 1\) est envoyé vers le \( 3\) qui est lui-même envoyé vers le \( 2\) . Lorsque l'on arrive à la parenthèse fermante on recommence depuis le début. C'est à dire que le \( 2\) est envoyé vers le \( 1\) . Ce qui correspond bien à la permutation \( \sigma_6\) .
L'élément \( (1\ 3 \ 2)\) est toujours une permutation, c'est à dire une application bijective. En tant qu'application, on peut considérer son image par \( 3\) par exemple. Avec la notation des fonctions il n'y a pas d'ambiguïté : on note \( \sigma_6(3)\) . Avec cette nouvelle notation, on va écrire exactement la même chose, à ceci prêt que l'on va substituer \( \sigma_6\) par \( (1\ 3\ 2)\) . Ainsi l'image de \( 3\) par la permutation \( (1\ 3\ 2)\) est \( 2\) est mathématiquement noté
\[(1\ 3\ 2)(3)=2\]
De la même manière \( \sigma_5=(1\ 3)\) . Par construction, on a \( (1\ 3)(1)=3\) et \( (1\ 3)(3)=1\) . Que dire de \( (1\ 3)(2)\) ? On ne le voit pas apparaitre dans la notation \( (1\ 3)\) , donc en fait il n'est pas transformé par cette permutation, il reste \( 2\) :
\[(1\ 3)(2)=2\]
Il est alors naturel de noter \( \sigma_1=(\ )\) .
On peut donc simplement et élégamment décrire le groupe symétrique d'ordre \( 3\) :
\[\mathfrak{S}_3=\Big\{
\underset{\sigma_1}{()},
\underset{\sigma_2}{(2\ 3)},
\underset{\sigma_3}{(1\ 2)},
\underset{\sigma_4}{(1\ 2\ 3)},
\underset{\sigma_5}{(1\ 3)},
\underset{\sigma_6}{(1\ 3\ 2)}
\Big\}\]
Prenons le problème a l'envers. Quelle est la permutation \( \sigma=(3\ 2\ 1)\) ? Nous ne la voyons pas apparaitre dans la liste des permutations de \( \mathfrak{S}_3\) . Cependant \( \sigma(1)=(3\ 2\ 1)(1)=3\) , \( \sigma(2)=(3\ 2\ 1)(2)=1\) et \( \sigma(3)=(3\ 2\ 1)(3)=2\) ce qui est exactement la définition de \( \sigma_6\) . Donc \( \sigma=\sigma_6\) et \( (1\ 3\ 2)=(3\ 2\ 1)\) ! En fait il faut lire une permutation de manière circulaire ; l'ordre des éléments compte mais pas le point de départ de la lecture.
\[
\begin{array}{lclcl}
(\ )& & & &\\
(2\ 3)&=&(3\ 2)& &\\
(1\ 2)&=&(2\ 1)& &\\
(1\ 2\ 3)&=&(2\ 3\ 1)&=&(3\ 1\ 2)\\
(1\ 3)&=&(3\ 1)& &\\
(1\ 3\ 2)&=&(3\ 2\ 1)&=&(2\ 1\ 3)
\end{array}
\]
Prenons un autre exemple et plaçons nous dans \( \mathfrak{S}_5\) . Considérons la permutation
\begin{eqnarray*}
\sigma : [\![1;5]\!]&\longrightarrow&[\![1;5]\!]\\
1&\longmapsto&3\\
2&\longmapsto&4\\
3&\longmapsto&5\\
4&\longmapsto&2\\
5&\longmapsto&1
\end{eqnarray*}
Alors \( \sigma=(1\ 3\ 5)(2\ 4)\) . On observe en effet que
\[
\begin{array}{lclclcl}
\big((1\ 3\ 5)(2\ 4)\big)(1)&=&(1\ 3\ 5)\underbrace{(2\ 4)(1)}_{1} &=&(1\ 3\ 5)(1)&=&3\\
\big((1\ 3\ 5)(2\ 4)\big)(2)&=&(1\ 3\ 5)\underbrace{(2\ 4)(2)}_{4} &=&(1\ 3\ 5)(4)&=&4\\
\big((1\ 3\ 5)(2\ 4)\big)(3)&=&(1\ 3\ 5)\underbrace{(2\ 4)(3)}_{3} &=&(1\ 3\ 5)(3)&=&5\\
\big((1\ 3\ 5)(2\ 4)\big)(4)&=&(1\ 3\ 5)\underbrace{(2\ 4)(4)}_{2} &=&(1\ 3\ 5)(2)&=&2\\
\big((1\ 3\ 5)(2\ 4)\big)(5)&=&(1\ 3\ 5)\underbrace{(2\ 4)(5)}_{5} &=&(1\ 3\ 5)(5)&=&1
\end{array}
\]
Toujours dans \( \mathfrak{S}_5\) , considérons \( \sigma=(1\ 3\ 5)(2\ 1)\) . Pour déterminer l'image de \( 1\) par sigma, il faut d'abord déterminer l'image de \( 1\) par \( (2\ 1)\) . C'est \( 2\) . Ensuite on détermine l'image de \( 2\) par \( (1\ 3\ 5)\) qui reste \( 2\) . Ainsi la permutation \( \sigma\) commence par \( (1\ 2\) .
Déterminons ensuite l'image de \( 2\) par \( \sigma\) et comme précédement commençons par \( (1\ 2)\) qui envoie donc \( 2\) sur \( 1\) . Cet élément est ensuite transformer par la permutation \( (1\ 3\ 5)\) en \( 3\) . Au final \( 2\) est transformer en \( 3\) . En poursuivant donc la simplification de \( \sigma\) on a \( (1\ 2\ 3\) .
On poursuit en cherchant l'image de \( 3\) : \( (1\ 3\ 5)(2\ 1)(3)=(1\ 3\ 5)(3)=5\) . Ainsi \( \sigma=(1\ 2\ 3\ 5\) .
Ensuite, \( (1\ 3\ 5)(2\ 1)(5)=(1\ 3\ 5)(5)=1\) et on peut clore la parenthèse : \( \sigma=(1\ 2\ 3\ 5)\) (on voit que \( 4\) reste bien fixe).
Proposition
Soit \( n\in \N\) . L'ensemble \( \mathfrak{S}_n\) est composé de \( n!\) éléments.
Démonstration
Déterminons tous les éléments de \( \mathfrak{S}_n\) . Il s'agit des bijections de l'ensemble \( [\![1;n]\!]\) dans \( [\![1;n]\!]\) . Ainsi l'élément \( 1\) peut-être associé à \( 1\) ou \( 2\) ou \( 3\) ... ou \( n\) . Il y a \( n\) possibilités d'association pour le \( 1\) . Pour l'élément \( 2\) , c'est la même chose, il y a \( n\) possibilités d'association sauf que nous souhaitons obtenir une bijection, c'est à dire que l'image de \( 2\) doit être différente de l'image de \( 1\) . Il n'y a donc pas \( n\) possibilités mais \( n-1\) (les \( n\) moins celle de \( 1\) ). C'est la même chose pour \( 3\) qui a \( n\) possibilités d'image moins les deux images de \( 1\) et \( 2\) . En poursuivant de la sorte on obtient qu'il y a \( n\times(n-1)\times\dots\times2\times1\) associations différentes possible. C'est, par définition, \( n!\) .
Par exemple \( \mathfrak{S}_4\) est composé de \( 24\) permutations :
\[\mathfrak{S}_4=\left\{
\begin{array}{ccc}
()&&\\
(1\ 2)&(1\ 3)&(1\ 4)\\
(2\ 3)&(2\ 4)&(3\ 4)\\
(1\ 2\ 3)&(1\ 3\ 2)&\\
(1\ 2\ 4)&(1\ 4\ 2)&\\
(1\ 3\ 4)&(1\ 4\ 3)&\\
(2\ 3\ 4)&(2\ 4\ 3)&\\
(1\ 2)(3\ 4)&(1\ 3)(2\ 4)&(1\ 4)(2\ 3)\\
(1\ 2\ 3\ 4)&(1\ 2\ 4\ 3)&\\
(1\ 3\ 2\ 4)&(1\ 3\ 4\ 2)&\\
(1\ 4\ 2\ 3)&(1\ 4\ 3\ 2)&
\end{array}
\right\}
\]
Cryptologie de substitution
Cryptosystème
Nous avons défini \( \mathfrak{S}_{n}\) comme le groupe des bijections de l'ensemble \( [\![1;n]\!]\) . En effectuant une soustraction par \( 1\) on peut également convenir que \( \mathfrak{S}_n\) est le groupe des bijection de l'ensemble \( [\![0;n-1]\!]\) . Puisque nous allons travailler avec des nombres entre \( 0\) et \( 25\) nous allons adopter cette convention.
Définition
Les données suivantes définissent le cryptosystème de
substitution.
- Espace de clefs.
- \( \mathcal{K}=\mathfrak{S}_{26}\)
- Fonction de chiffrement.
- Quelque soit \( \sigma\in \mathcal{K}\) et \( x\in [\![0;25]\!]\) , \( C_\sigma(x)=\sigma(x)\) .
- Fonction de déchiffrement.
- Quelque soit \( \sigma\in \mathcal{K}\) et \( x\in [\![0;25]\!]\) , \( D_\sigma(x)=\sigma^{-1}(x)\) .
La propriété de déchiffrement est une conséquence de la construction de la bijection inverse.
Cryptanalyse
Il est absolument impensable de tenter une attaque en force brute. L'espace des clefs est \( \mathfrak{S}_{26}\) dont la cardinalité est \( 26!=403291461126605635584000000 {>} 4\times 10^{26}\) . Imaginons que nous programmions une machine capable de tester un million de milliard (\( 10^{15}\) ) de clefs par seconde (c'est donc un algorithme très performant avec une machine extrêmement puissante
2). Nous aurons donc besoin de \( \dfrac{4\times 10^{26}}{10^{15}}\) secondes pour tester toutes les clefs soit \( \dfrac{4\times 10^{26}}{10^{15}\times 60\times 60 \times 24\times 365}{>}12683\) ans !
Une manière beaucoup plus intelligente est une
cryptanalyse fréquentielle.
Cette analyse est basée sur le fait que lettre apparaissent toujours avec (à peu près) la même fréquence.
\[
\begin{array}{*{14}{|c}|}
\hline
\text{Caractère}&a&b&c&d&e&f&g&h&i&j&k&l&m\\\hline
\text{Fréquence (\%)}&8.122&0.901&3.345&3.669&17.115&1.066&0.866&0.737&7.580&0.545&0.049&5.456&2.968\\\hline
\end{array}
\]
\[
\begin{array}{*{14}{|c}|}
\hline
\text{Caractère}&n&o&p&q&r&s&t&u&v&w&x&y&z\\\hline
\text{Fréquence (\%)}&7.095&5.378&3.021&1.362&6.553&7.948&7.244&6.311&1.628&0.114&0.387&0.308&0.136\\\hline
\end{array}
\]
(valeurs obtenues par l'analyse d'un texte en français sans vocabulaire spécifique ; les caractères accentués étant ramenés aux caractères dont ils dérivent).
Bien évidement plus le texte est long plus cette méthode sera rapidement efficace. Si par exemple, le texte chiffré est
W ANNATLI, nous ne disposons pas assez de donnée pour pouvoir entamer une analyse fréquentielle. Considérons par exemple le message suivant :
VWLP WI ZXYCRI GI EARAENIRI IPN QYVXRNAZN VWLP W ANNATLI KRITLIZNQIWWI PIRA VIRK XRYAZNI
En comptant les lettres on arrive à
\[
\begin{array}{*{14}{|c}|}
\hline
\text{Caractère} &A&B&C&D&E&F&G&H&I &J&K&L&M\\\hline
\text{Nb apparition}&7&0&1&0&2&0&1&0&14&0&2&4&0\\\hline
\end{array}
\]
\[
\begin{array}{*{14}{|c}|}
\hline
\text{Caractère} &N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline
\text{Nb apparition}&8&0&4&2&8&0&2&0&4&6&3&3&4\\\hline
\end{array}
\]
Il est donc fort probable que le
I corresponde eu
E
VWLP WE ZXYCRE GE EARAENERE EPN QYVXRNAZN VWLP W ANNATLE KRETLEZNQEWWE PERA VERK XRYAZNE
En analysant de la sorte les caractères on peut déchiffrer le message. Dans cette exemple, le nombre de caractère est trop faible pour arriver à exploiter l'attaque fréquentielle. On peut néanmoins déduire que le
A est soit le
A, le
N ou le
R...
A noter que la méthode de l'analyse fréquentiel s'applique également pour les méthodes de César et Affine puisqu'il s'agit de cas particulier de la substitution.
1L'application \( \sigma_1\) est appelé l'identité.
2Rien de tout ça n'existe pour l'instant.
