Le chiffrement de Vigenère

Présentation du système de Vigenère

On a vu que la cryptanalyse d'un système de chiffrement monoalphabétique comme le chiffrement de César ou le chiffrement par permutation est aisée. Chaque symbole du message clair étant chiffré de la même manière, la distribution fréquentielle des symboles du message chiffré est identique à celle des symboles du message clair à une permutation près et cette dernière est sensiblement la même que celle de la langue naturelle utilisée. La distribution fréquentielle des symboles d'une langue naturelle n'étant pas uniforme, les symboles les plus fréquents dans le message chiffré sont associés aux symboles de fréquences similaires dans cette langue.

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

Soit \(\Sigma\) un alphabet fini de cardinal \(q\) que l'on identifie à l'anneau \(\mathbf{Z}/q\mathbf{Z}\) et soient \(k\) et \(x\) deux mots de longueur \(n\) de \(\Sigma^*\). La fonction de chiffrement de Vigenère \(e_k:\Sigma^n\rightarrow \left(\mathbf{Z}/q\mathbf{Z}\right)^n\) est définie par : \begin{equation} e_k(x):=x + k. \end{equation}
La taille \(q^l\) de l'espace \(K\) des clefs \(k\) doit être suffisante pour éviter une attaque par force brute. Autrement dit, pour une sécurité de 256 bits par exemple, il faut que \(q^l\geq 2^{256}\), soit \(l\geq 55\) pour \(q=26\).

Si la taille \(n\) du message à chiffrer est supérieure à la longueur de la clef \(k\), on segmente le message à chiffrer en mots de \(l\) lettres que l'on chiffre successivement, le message chiffré est alors la concaténation des différents mots chiffrés.

Si la longueur de la clef de chiffrement est \(l=1\), le chiffrement de Vigenère coïncide avec le chiffrement par décalage circulaire.

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.

clair \(x\) :
clef \(k\) :
\(-k\) :
chiffré \(y\) :

Cryptanalyse

À titre de rappel, dans un protocole de transmission d'un message chiffré, Alice désigne la personne qui envoie le message, Bob est celui à qui ce message est destiné, et Oscar est celui qui tente de pirater le message. Voici les hypothèses qui caractérisent les différents types d'attaques menées par Bob. Elles sont présentées dans l'ordre décroissant de réalisme :
  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
La première étape de la cryptanalyse de ce système est de déterminer la longueur l de la clef secrète. Pour cela on applique le test de Kasiski qui consiste à chercher des motifs identiques de longueur au moins 2 dans le texte chiffré \(y\). Deux raisons peuvent expliquer plusieurs occurrences d'un même mo­tif :

  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 :

\(x=\;\)SUDESTRHODESAPPLIQUERCODESX

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

01234567891011121314151617181920212223242526
  Message \(x\)   SUDESTRHODESAPPLIQUERCODESX
  Clef \(k\)   SECRETSSECRETSSECRETSSECRET
  Chiffré \(y\)   KYFVWMJZTFVWTHHPKHYXJUSFVWQ
Chiffrement de Vigenère avec la clef SECRETS.

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 :

\begin{align*} NON+YMP&=LAC\\ KOD+BMZ&=LAC \end{align*} Néanmoins c'est une piste sérieuse pour la cryptanalyse. On calcule donc le pgcd des distances entre les différentes occurrences du motif dans le message chiffré. S'il est strictement supérieur à 1, on peut suspecter qu'il s'agit de la longueur de la clef ou d'un de ses multiples. L'hypothèse sur la longueur de la clef devient d'autant plus pertinente que le nombre d'oc­cur­ren­ces de motifs identiques dans le message chiffré est im­por­tant. Il ne s'agit néanmoins que d'une hypothèse qu'il va falloir confirmer ou infirmer.

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 :

\(i\)\(k_i\)\(y^{\,[i]}\)
0SKZHU
1EYTPS
2CFFKF
3RVVHV
4EWWYW
5TMTXQ
6SJHJ 
Congruents du message chiffré modulo \(l\).

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.

Notons que pour une taille \(t\) du motif et un chiffré \(y\) de taille \(n\), il y a \(n-t+1\) motifs potentiels à chercher dans \(y\). La recherche d'un motif de taille \(t\) dans un mot de taille \(n\) a une complexité en \(O(tn)\), on a donc une complexité en \(O(tn^2)\) pour l'estimation de la longueur de la clef à base de pgcd.

Autocoïncidence et longueur de clef
L'étape suivante exploite un critère un peu plus fin que la simple analyse fréquentielle. Pour valider l'hypothèse sur la longueur \(l\), on va calculer l'indice d'autocoïn­ci­den­ce des congruences du chiffré.

[W. Friedman, 1920] Soit \(\Sigma\) un alphabet fini. On définit la fonction d'au­to­coïn­ci­den­ce \(\varphi:\Sigma^*\rightarrow[0,1]\) par : \begin{equation} \varphi(x) := \text{Probabilité de tirer au hasard deux symboles identiques dans}\ x \end{equation}

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\) :

\begin{equation} \forall k \in[0,q-1],\quad n_k:=\#\{i\in[1,n]\ \mid\ x_i=s_k\}. \end{equation}

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

Soit \(L\) un langage défini sur un alphabet \(\Sigma\) de cardinal \(q\). L'in­di­ce d'au­to­coïncidence de \(L\) est défini par \begin{equation} \label{formule:autoco} \varphi(L)=\sum_{k=0}^{q-1}p_k^2 \end{equation} où \((p_k)_{k\in[0,q-1]}\) désigne la distribution de probabilité des symboles \(s_k\in\Sigma\) dans le langage \(L\).
Dans le cas de la langue française, on obtient expérimentalement \(\varphi(L)\approx 7,6\%\). Si la distribution des lettres de l'alphabet latin était uniforme, on aurait \[p_A=p_B=\cdots=p_Z=\frac{1}{26}\approx 3,85\%\]
Évaluer expérimentalement l'autocoïn­ci­den­ce de la langue française en calculant la distribution des symboles sur un corpus de texte de grande taille. Le site de la Bibliothèque Nationale de France bnf contient plusieurs dizaines de milliers d'ouvrages téléchargeables en mode texte.

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é.

Soient \(x=x_1x_2\ldots x_n\) et \(y=y_1y_2\ldots y_m\) deux mots sur l'alphabet fini \(\Sigma\). On définit la fonction d'intercoïn­ci­den­ce \(\psi:\Sigma^*\times\Sigma^*\rightarrow[0,1]\) par \begin{align} \psi(x,y):=&\ \text{Probabilité de tirer au hasard deux symboles égaux,}\\ \notag&\ \text{l'un dans \(x\) l'autre dans \(y\)} \end{align}

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

Le programme ci-dessous vous permet de faire vos propres hypothèses sur la taille du motif répétitif à rechercher dans le message chiffré. Pour une taille donnée, le premier bouton lance la recherche du motif avec le plus grand nombre d'occurrences, et instancie la longueur de la clef avec le pgcd de leurs décalages. Vous pouvez changer sa valeur si nécessaire avant de lancer le calcul des indices d'autocoïncidence et d'intercoïncidence pour calculer \(\kappa\). Le programme fait une estimation de \(\delta_0\) mais il est possible de modifier ce décalage.

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

chiffré \(y\) :
TSEUWEEPNIIGWVLKANWBZRNIDBDRUEMIUAGGCBTXVKWLWQAYVEKMGVVTNFNIJSDMAEDNHVZUMMWGTEGMTMBMSGMBWPZRSDWVTBPXVVJQTEEPQVKIYMSOEPEILBICALOAVQFVLAVTNFNIJGSDWLSNPWRZGQJIAENITSEUWMOVGXDIEMUXQHKIJXHMMMEGTIGPMASMRBEIVRSGSGTCCVCISDWVTBWWCIKZSREFGXKSMADXSGQRUYKLWLCNOTJHWKGGCRPXIELQGGAIGGCIVMJGIRTGFVHALKEOWGYEFBVXSNHJIIMAWLFVNIJHWVMBTRVFISMQDEAEFIEJAVLHMOGWFYKTWLCEQWJIKINXCYGWYYABEBLYGJIEFKSBSRUULMFMKHNGREJVWDWGURUHVWTIYGEFCZVGDIVXRAKIIIXMEFEZQVKISZSOEAUFIYUSHHUECZFMJLGGNRCWZPWIDNNQGWESLZWLEAVVVENMUEECGYGPWVWWEYQQSVWMLWIFREIYSDWVEYNIESKNJXRRUHRRKTGKDEGHVPSVMBTPQQDIEWJTNGNEERADWKSNKVVHWTSEIOGVRXAWFWECCVZWBMVBSNKWVGGCLXCRUSZVBMMGEFUIUIEWFIALUPVWUTGVHRUHRRFQNXRFCMIIICALOAPIISFBUHMZGGVPDMKWIYAEHYSBGKZRCRJTMQKLEFVYTILBWYOVUPVWWVLXNQTIVPDMKOOAVWFRFMJIOHTXFMDPGFMNIIUEMRGNRQJYZRSXHXLYGULIDMUAAAVULMNIKXLRXIIQSQFMEACRKGWKZTNGFIJTSZLBSNPWHYWRSBEAVIEHMUMKMHTIIGGUEXUAELRRLLWVOZRPZGABWIUVUTJEDUGWIRTHRRKTWURBWMCPSZVWEFXSJKWAWMLRUFFMKLSESNEIDIDMSNCEKTVVVCVXSZQYKSFAVXSGCFFVKYMTNQNIJFSHGHKNUHVGGZJXZRCZRRUIAXNGCPRVWVUHNGTIUIKKZTRFFIIYFALXDGNEEGWAVXNBWZVEMKGGTEGWKVSATHUEIITSMBWTUWQYIHZCACEHPIJWWLWYRNPGVGWYMBFHVTFYJVGNSYGGYEFBVNMNNLVYJKWLTYCQRVUPWYUAGFIIVMKVEAFVVWICWOOVEMRGGBWWEPGPCIKLWVAEPSKENMUEEFUSCHSBKWEYCRZMVMUXLYGWUINQUMOEJYXSSDWVLRUQZWWZSULRUHVGWTDXSQGNRYJMKOEVNPVIKXSKLNLYJXAKWJURNPVWJMHHSRPXRZWKDXUENSEKUWJMETGHFQTZWLDRHMXYJMWLAHLSLVVPMBJRWRVWKMHNIFUIJXMXWGSRTETILPGFMRESDQWBMTUECMJEHXJHCUGXVWEIAGSQGWRTSCNKESCGVMFNGKMRFYUIJVAXRWQYIHWAWLLRXVVWICAGAICMVRLXSLPNTPVGWRGNRYCICPWMLTIGNIMMKIYXDRNEWVSVUX
motif :
positions :
\(\kappa\ +\)?
autoco. \(\varphi\) :
interco. \(\psi\) :
clair \(x\) :