\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\text{\Large$\varepsilon\!\!\varepsilon$}} \newcommand{\supere}{\text{\Large$e\!\!e$}} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\vv}{\overrightarrow{v}} \newcommand{\vu}{\overrightarrow{u}} \newcommand{\vup}{\overrightarrow{u'}} \newcommand{\vx}{\overrightarrow{x}} \newcommand{\vy}{\overrightarrow{y}} \newcommand{\vz}{\overrightarrow{z}} \newcommand{\vt}{\overrightarrow{t}} \newcommand{\va}{\overrightarrow{a}} \newcommand{\vb}{\overrightarrow{b}} \newcommand{\vc}{\overrightarrow{c}} \newcommand{\vd}{\overrightarrow{d}} \newcommand{\ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\dpl{\left\langle #1\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

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 puissante2). 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.