Présentation du système de Vigenère

Ceci montre que la taille de l'espace des clefs n'est pas un critère suffisant pour garantir la sécurité d'un système. Le chiffrement par permutation en est la parfaite illustration puisque la taille de l'es­pa­ce des clefs est de \(26!\) soit environ \(2^{88}\)Ce qui reste considérable même de nos jours s'il fal­lait faire une at­ta­que par force brute. et que l'analyse fréquentielle permet de retrouver la clef en une fraction de seconde.

Le système de Vigenère tente de remédier à cela en chiffrant différemment un même symbole du message clair selon sa position dans le message. Le chiffrement d'un symbole est le chiffrement par décalage circulaire (César), c'est simplement la clef secrète qui dépend de la position du symbole à chiffrer. On parle alors de chiffrement polyalphabétique.

Détaillons le processus. On identifie un alphabet fini \(\Sigma=\{s_0,s_1,\ldots,s_{q-1}\}\) totalement ordonné de car­dinal \(q\) à l'anneau mo­du­lai­re \(\mathbf{Z}/q\mathbf{Z}\) avec la bijection croissante \(s:\mathbf{Z}/q\mathbf{Z}\rightarrow\Sigma\) définie par \begin{equation}\label{eq:bij} i\mapsto s_i. \end{equation}

En pratique, il s'agira de l'alphabet latin \(\Sigma := \{A,B,\ldots,Z\}\) de cardinal \(q=26\) équipé de l'ordre al­pha­bé­ti­que.

On peut maintenant, grâce à cette identification, additionner des symboles modulo \(q\), la somme \(x+ y\) sur \(\Sigma\) de deux symboles \(x\) et \(y\) étant définie par \[x + y:=s(s^{-1}(x)+s^{-1}(y)).\] Ainsi on écrira \(E + X=B\) car \(s^{-1}(E)=4\), \(s^{-1}(X)=23\) et \(4+23\equiv 1\pmod{26}\) et que \(s(1)=B\). On étend l'addition \(+\) sur les symboles de l'alphabet \(\Sigma\) à des \(n\)-uplets de symboles en les ad­di­tion­nant terme à terme : \[(x_1,x_2,\ldots,x_n)+(y_1,y_2,\ldots,y_n):=(x_1+ y_1,x_2+ y_2,\ldots,x_n+ y_n).\] Par commodité, les \(n\)-uplets sont identifiés à des mots du langage \(\Sigma^*\). On écrit donc \[BOB+AME=BAF\] plutôt que \((B,O,B)+(A,M,E)=(B,A,F)\). On définit de la même façon les autres opérations ari­thmé­ti­ques entre symboles de l'alphabet en transportant celles de l'anneau modulaire \(\mathbf{Z}/q\mathbf{Z}\) avec la bijection \(s\).

Si \(k=k_1k_2\ldots k_l\) est la clef de chiffrement, la fonction de déchiffrement est identique à la fonction de chiffrement en remplaçant la clef \(k\) par la clef de déchiffrement \(-k\) qui est donc constituée des sy­mé­tri­ques (ici les opposés puisque l'opération est l'addition) des symboles de la clef \(k\) via l'iden­ti­fi­ca­tion de \(\Sigma\) à \(\mathbf{Z}/q\mathbf{Z}\) avec la bijection \(s\). Ainsi la fonction de déchiffrement \(d\) est définie par \begin{equation} d_k(y):=y-k. \end{equation}

Vous trouverez ci-dessous de quoi chiffrer un message. Vous pouvez copier un texte quelconque dans la zone de saisie. Le programme convertit les lettres minuscules en majuscules et filtre les espaces automatiquement. Le bouton x,k ⇆ y,-k permet d'intervertir les messages clair et chiffré, ainsi que les clefs de chiffrement et de déchiffrement. Notez que si vous saisissez une clef d'une seule lettre le programme calcule le chiffrement de César.

Cryptanalyse

1. chiffré connu, Oscar connaît des chiffrés \(y\).
2. clair connu, Oscar connaît des couples \((x,y)\).
3. clair choisi, Oscar peut chiffrer des clairs \(x\) de son choix (mais ne dispose pas de la clef secrète).
4. chiffré choisi, Oscar peut déchiffrer des chiffrés \(y\) (mais ne dispose pas de la clef secrète.)

La cryptanalyse du système de chiffrement de Vigenère est une attaque à chiffré connu. On rappelle que tous les systèmes de chiffrement sont sensés appliquer le principe de Kerckhoffs, à savoir que l'attaquant Oscar connaît la méthode de chiffrement dans ses moindres détails. Cela sous-entend que la sécurité d'un tel système de chiffrement ne repose que sur la clef secrète \(k\) et pas sur l'ignorance des mécanismes utilisés.

Estimation de la longueur de la clef

1. C'est une pure coïn­ci­den­ce.
2. Les motifs correspondant dans le message clair x sont identiques.

Nous allons étudier les critères qui vont nous permettre de distinguer ces deux situations. Con­si­dé­rons la clef \(k=\;\)SECRETS et le message clair suivant :

La table ci-suivante résume l'opération de chiffrement.

Si des motifs se répètent dans le message clair — comme le motif DES ici aux positions 2, 9 et 23 — et que ces répétitions sont distantes d'un multiple de la longueur de la clef (ici \(9 - 2 = 7\) et \(23 - 2 = 21=3\times 7\)), il est évident qu'il y aura une répétition du motif chiffré, ici FVW. La ré­ci­pro­que n'est pas nécessairement vraie comme le montre le contre-exemple suivant :

Si \(l\) désigne la longueur de la clef et \(i\in[0,l-1]\), alors tous les symboles du message chiffré \(y\) dont la position modulo \(l\) est égale à \(i\) ont été chiffrés avec le même symbole \(k_i\) de la clef \(k\) par un simple décalage circulaire (César). Pour tout \(i\in[0,l-1]\), on définit \(y^{[i]}\in\Sigma^*\) le \(i\)-ème congruent de \(y\) mo­du­lo \(l\) par \[\forall k\in\mathbf{N}\ \mid\ kl+i\leq |y|,\qquad y^{[i]}_k:=y_{kl+i}.\] et on note \(n_i\) sa longueur. La table ci-dessous regroupe les symboles du message chiffré \(y\) selon la con­gruen­ce modulo \(l=7\) de leur position dans le message :

Sachant que chacun des \(l\) congruents est un chiffré par décalage circulaire, on pourrait pratiquer une simple analyse fréquentielle des symboles afin de déterminer le décalage \(k_i\) le plus probable et re­cons­ti­tuer les \(l\) clefs partielles. Cette approche n'est évidemment pertinente que dans le cas où le message clair est suffisamment long pour que les sous-chaînes de la table ci-dessus soient exploitables. Ce n'est pourtant pas l'ap­pro­che que nous allons adopter car on peut mieux faire.

Autocoïncidence et longueur de clef

Plus formellement, on utilise la distribution de probabilité uniforme \(p_i=1/n\) sur l'ensemble \(\{1,\ldots,n\}\) des indices du mot \(x=x_1x_2\ldots x_n\) pour tirer au hasard les deux symboles \(x_i\) et \(x_j\) de \(x\). On peut calculer la fonction d'autocoïn­ci­den­ce à partir de la fréquence d'apparition des symboles \(s_k\) dans le mot \(x\). On note \(n_k\) le nombre d'occurrences du symbole \(s_k\) dans le mot \(x\) :

La probabilité de l'évènement \(\{x_i=x_j=s_k\}\) se calcule aisément. La probabilité que \(x_i\) soit égale au symbole \(s_k\) est égale à \(n_k/n\) et la probabilité que \(x_j\) soit égale au symbole \(s_k\) est égale à \((n_k-1)/(n-1)\) puisque le symbole est tiré au hasard parmi les \(n-1\) symboles restants qui ne contiennent plus que \(n_k-1\) symboles \(s_k\). Les \(q\) évènements \(\{x_i=x_j=s_k\}\) pour \(k\in[0,q-1]\) sont deux-à-deux in­dé­pen­dants donc la pro­ba­bi­li­té que deux symboles \(x_i\) et \(x_j\) du mot \(x\) soient égaux est égale à la somme des probabilités de ces \(q\) évè­ne­ments : \begin{equation} \varphi(x)=\sum_{k=0}^{q-1}\frac{n_k}{n}\frac{(n_k-1)}{n-1} \end{equation}

On définit l'indice d'autocoïn­ci­den­ce d'un langage \(L\subseteq\Sigma^*\) en passant à la limite (donc sur une chaîne dont la longueur tend vers l'infini) dans la langue donnée : \begin{align*} \varphi(L)&=\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\left(\frac{n_k^2}{n(n-1)}-\frac{n_k}{n(n-1)}\right)\\ &=\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\frac{n_k^2}{n(n-1)}-\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\frac{n_k}{n(n-1)}\\ &=\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\frac{n_k^2}{n(n-1)}-\lim_{n\rightarrow\infty}\left(\frac{1}{n(n-1)}\color{#88D}{\sum_{k=0}^{q-1}n_k}\right)\\ \end{align*}

Mais la somme des \(n_k\) est égale à \(n\), donc \begin{align*} \varphi(L)&=\left(\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\frac{n_k}{n}\frac{n_k}{(n-1)}\right)-\lim_{n\rightarrow\infty}\frac{1}{n-1}\\ &=\lim_{n\rightarrow\infty}\sum_{k=0}^{q-1}\left(\frac{n_k}{n}\right)^2 \end{align*} et finalement

D'après l'expression \((\ref{formule:autoco})\), il est évident que toute permutation des symboles de l'alphabet \(\Sigma\) ne change pas l'indice d'autocoïn­ci­den­ce d'un langage, ainsi en calculant l'indice d'autocoïn­ci­den­ce de chacun des 7 congruents \(y^{[i]}\) du tableau précédent, il suffit d'observer si les valeurs sont proches de 8% ou de 4% pour conforter ou non l'hypothèse sur la longueur \(l\) de la clef secrète. On peut d'ailleurs se passer de l'analyse des répétitions et se contenter de tester l'autocoïncidence des congruents en faisant varier la longueur \(l\) de la clef.

Intercoïncidence et clefs partielles
Supposons que l'on dispose de la longueur \(l\) de la clef \(k\). Il faut à présent déterminer les \(l\) clefs partielles \(k_i\) de la clef \(k=k_1k_2\ldots k_l\). On calcule alors l'indice d'in­ter­coïn­ci­den­ce du clair et du chiffré.

On note \(n_1,n_2,\ldots,n_q\) et \(m_1,m_2,\ldots,m_q\) le nombre d'occurrences respectives des symboles \(s_k\) dans les mots \(x\) et \(y\). Pour les mêmes raisons que pour l'autocoïn­ci­den­ce, l'intercoïn­ci­den­ce \(\psi(x,y)\) est égale à la somme des probabilités des évènements \(\{x_i=x_j=s_k\}\) pour \(k\in[0,q-1]\) : \begin{equation} \psi(x,y)=\sum_{k=0}^{q-1}\frac{n_k}{n}\frac{m_k}{m}. \end{equation}

L'intercoïncidence d'un langage se confond avec son autocoïncidence. Soient \(y^{[i]}\) et \(y^{[j]}\) deux con­gruents du chiffré \(y\) modulo \(l\). On a \begin{align} \label{eq:cong1}y^{[i]} &= x^{[i]} + \color{#FF0}{k_i^{n_i}}\\ \notag y^{[j]} &= x^{[j]} + k_j^{n_j} \end{align} où l'on désigne par \(z^n\) le mot \(\underbrace{zz\ldots z}_{n\ \times}\) si \(z\in\Sigma\) et \(n\in\mathbf{N}\). On a donc \begin{align} \notag y^{[j]} + k_i^{n_j} - k_j^{n_j} &= x^{[j]} + \color{#FF0}{k_i^{n_j}}\\ \label{eq:cong2}z^{[j]}:=y^{[j]} + ({\color{#88F}k_i - k_j})^{n_j} &= x^{[j]} + \color{#FF0}{k_i^{n_j}} \end{align} Autrement dit en opérant un décalage circulaire adéquat sur le congruent \(y^{[j]}\), le mot \(z^{[j]}\) obtenu est un chiffré par décalage circulaire avec la même clef \(k_i\) que celle utilisée pour chiffrer \(x^{[i]}\) en \(y^{[i]}\), cf. equations \((\ref{eq:cong1})\) et \((\ref{eq:cong2})\). Dans ce cas l'intercoïncidence \(\psi\left(y^{[i]},z^{[j]}\right)\) est proche de celle de la langue, soit en français près de 8%.

Ainsi en décalant circulairement chaque congruent \(y^{[j]}\), \(j > 0\) jusqu'à ce que son intercoïncidence avec \(y^{[0]}\) soit maximale, on obtient les \(l-1\) déphasages \(\delta_j:=k_0-k_j\) entre les clefs partielles \(k_j\) et la clef partielle \(k_0\). Autrement dit le mot \begin{equation} \kappa:=s_0s_{\delta_1}s_{\delta_2}\ldots s_{\delta_{l-1}} \end{equation} est un simple décalage circulaire de la clef secrète \(k\) (on rappelle que l'alphabet \(\Sigma=\{s_0,s_1,\ldots,s_{q-1}\}.\))

On achève la cryptanalyse du système en cherchant le symbole le plus fréquent du mot \(y^{[0]}\), qui correspond très probablement au symbole le plus fréquent de la langue utilisée (\(E\) en français). Le décalage \(\delta_0\) entre ces deux symboles permet enfin de retrouver la clef secrète : \begin{equation} k=\kappa+\delta_0^l. \end{equation}

Travaux pratiques

Les zones de saisie sont encadrées en jaune, vous pouvez remplacer le chiffré qui est affiché par défaut.