Introduction à la cryptologie

Le cours

La cryptologie, ou science du secret, est devenue depuis une trentaine d'années une discipline scientifique à part entière qui connaît un engouement spectaculaire à la mesure du rôle de plus en plus important que jouent les réseaux de communication au sein de notre société moderne. La cryptographie est l'étude des techniques d'écriture de messages secrets tandis que la cryptanalyse en fait l'analyse pour les valider ou les invalider.

Les trois grands thèmes de la cryptologie sont :

  1. La confidentialité, qui est toujours l'objectif principal et qui amène à développer et à étudier les techniques permettant de communiquer des informations confidentielles entre plusieurs entités.
  2. L'intégrité ou authentification, ou comment s'assurer qu'un document n'a pas été altéré par une tierce personne.
  3. L'identification qui consiste à certifier l'origine d'un message.
La conjonction des deux derniers thèmes est appelé signature. Deux grandes classes de protocoles sont employés en cryptographie : les protocoles à clef privée ou secrète et les protocoles à clef publique. On parle respectivement de cryptographie symétrique et asymétrique.

Ce cours introductif s'adresse à des étudiants de mathématiques ayant le niveau de la licence, mais il est tout à fait accessible à un informaticien ayant une culture mathématique solide. Le volume d'enseignement étant relativement restreint, deux alternatives étaient envisageables pour une introduction à la cryptologie. La première consistait à faire un panorama nécessairement superficiel de ce domaine de recherche, la seconde pour laquelle j'ai optée (à peine moins superficielle compte tenu du volume horaire disponible) était de me restreindre à un petit nombre de protocoles illustratifs de cette théorie.

Pour les protocoles de chiffrement à clef secrète, j'ai choisi principalement le système de Vigenère, qui a l'avantage d'être simple, d'introduire une démarche générale, et qui peut être mise en oeuvre dans un délai raisonnable pour des mathématiciens peu familiarisés avec la programmation. Le des et l'aes sont bien sûr abordés.

Pour les protocoles de chiffrement à clef publique, j'ai choisi le protocole rsa, parce qu'il est largement utilisé et surtout pour illustrer quelques théorèmes fondamentaux d'arithmétique. Je mets également en avant les aspects algorithmiques incontournables quand on veut faire des calculs effectifs.

Le cours est décomposé en 5 chapitres:

  1. Cryptographie à clef privée, méthodes naïves, notion de clef.
  2. Le système de Vigenère. Introduction au des. Cryptanalyse.
  3. Cryptographie à clef publique. Arithmétique et rsa. Système de McEliece.
  4. Algorithmes et complexité liés à rsa. Problèmes NP-complets. Problèmes Prime et Co-Prime.
  5. Analyse de rsa et problèmes relatifs à la primalité/décomposition.

Documents pédagogiques

Le polycopié (inachevé) du cours est accessible ici en pdf. Les planches de TD sont ici:
  1. Planche A
  2. Planche B
  3. Planche C

Travaux pratiques

On se propose de réaliser un programme de cryptanalyse du système 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 répartition fréquentielle des symboles chiffrés suit sensiblement la même que celle de la langue naturelle utilisée. La distribution des symboles d'une langue naturelle n'étant pas uniforme, le symbole le plus fréquent dans le message chiffré est très naturellement associé au symbole le plus fréquent de 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'espace 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 chiffrant différemment un même symbole du messsage clair selon sa position dans le message. Le chiffrement en question est tout simplement le chiffrement de César, mais la clef dépend de la position du caractère à chiffrer. On parle alors de chiffrement polyalphabétique.

On identifie l'alphabet latin à 26 lettres \(\Sigma := \{A,B,\ldots,Z\}\) à l'anneau modulaire \(\mathbf{Z}/26\mathbf{Z}\) avec la bijection croissante \(\sigma:\Sigma\rightarrow\mathbf{Z}/26\mathbf{Z}\) qui associe à chaque lettre son ordre dans \(\mathbf{N}\), soit \(0\) pour \(A\), 1 pour \(B\), …, et 25 pour la lettre \(Z\). On peut maintenant, grâce à cette identification, additionner des lettres modulo 26, la somme \(x\oplus y\) sur \(\Sigma\) de deux lettres \(x\) et \(y\) étant définie par \[x\oplus y:=\sigma^{-1}(\sigma(x)+\sigma(y)).\] Ainsi on écrira \(E\oplus X=B\) car \(\sigma(E)=4\), \(\sigma(X)=23\) et \(4+23\equiv 1\pmod{26}\) et que \(\sigma^{-1}(1)=B\). On étend alors l'addition \(\oplus\) définie sur les symboles de l'alphabet \(\Sigma\) à des \(n\)-uplets de symboles en additionnant terme à terme : \[(x_1,x_2,\ldots,x_n)\oplus(y_1,y_2,\ldots,y_n):=(x_1\oplus y_1,x_2\oplus y_2,\ldots,x_n\oplus y_n)\]

On peut à présent expliciter le chiffrement de Vigenère. La clef \(k=k_1k_2\ldots k_l\) est un mot de longueur \(l\) identifié au \(l\)-uplet \((k_1,k_2,\ldots,k_l)\) et le message clair également \(x=(x_1,x_2,\ldots,x_l)\), la fonction de chiffrement de Vigenère est alors définie par la simple addition : \begin{equation} e_k(x):=x\oplus k. \end{equation}

Notons que 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 \(26^l\geq 2^{256}\), soit \(l\geq 55\).

Si la taille 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 de César.

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=(-k_1)(-k_2)\ldots,(-k_l)\) constituée des opposés des symboles via l'identification de \(\Sigma\) à \(\mathbf{Z}/26\mathbf{Z}\), c'est-à-dire pour \(s\in\Sigma\),

\begin{equation} -s:=\sigma^{-1}(-\sigma(s)) \end{equation}

Ainsi la fonction de déchiffrement \(d\) est définie par \begin{equation} d_k(y):=y\oplus (-k). \end{equation} ce qui nous permet de définir l'opération \(\ominus\) sur \(\Sigma\) étendue à \(\Sigma^*\) par \(a\ominus b:=a\oplus(-b)\).

Vous trouverez ci-dessous de quoi chiffrer un message. Vous pouvez copier un texte quelconque dans la zone de saisie. Ne vous préoccupez pas des symboles qui ne sont pas des lettres de l'alphabet, y compris les espaces entres mots, le programme les filtre automatiquement. 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 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 réaliste puisqu'il s'agit d'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.

La première étape de la cryptanalyse de ce système consiste à 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é. Deux raisons peuvent expliquer plusieurs occurrences d'un même motif :

  1. C'est une pure coïncidence.
  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=\;\)SUDESTRHODESAPPLIQUERCODESXX

0123456789101112131415161718192021222324252627
  Message \(x\)   SUDESTRHODESAPPLIQUERCODESXX
  Clef \(k\)   SECRETSSECRETSSECRETSSECRETS
  Chiffré \(y\)   KYFVWMJZTFVWTHHPKHYXJUSFVWQP

Le motif FVW est présent trois fois dans le message chiffré aux positions 2, 9 et 23. Si ces répétitions ne sont pas dues au hasard, cela signifie que la portion de clef utilisée pour le décalage circulaire est la même et que ces trois motifs sont donc éloignés d'un multiple de la longueur de la clef. La réciproque n'est pas nécessairement vraie, mais on peut calculer les décalages entre le premier motif et les suivants, soit les valeurs \(9 - 2 = 7\) et \(23 - 2 = 21\). Si ces décalages ont un pgcd différent de 1, comme c'est le cas ici puisque \((7,21) = 7\), on peut suspecter qu'il s'agit de la longueur de la clef ou d'un multiple de cette longueur. Cette approche est d'autant plus pertinente que le nombre d'occurrences de motifs identiques est important. 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). La table ci-dessous regroupe les symboles du message chiffré \(y\) selon la con­gruen­ce modulo \(l=7\) de leur position :

\(i\)\(k_i\)\(y_{\lambda i}\)
0SKZHU
1EYTPS
2CFFKF
3RVVHV
4EWWYW
5TMTXQ
6SJHJP

On pourrait pratiquer une simple analyse fréquentielle des symboles pour chacune des \(l\) lignes de cette table afin de déterminer chacun des décalages le plus probable et reconstituer la clef secrète \(k\). 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 faire un peu mieux.

L'étape suivante exploite un critère un peu plus fin. Pour valider l'hypothèse sur la longueur \(l\), on va calculer deux quantités :

  1. l'indice d'autocoïncidence du chiffré;
  2. l'indice d'intercoïncidence 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 uniforme \(p_i:=1/n\) sur l'ensemble \(\{0,1,\ldots,n-1\}\) des indices du mot \(x=x_1x_2\ldots x_n\) de longueur \(n\) pour choisir le symbole \(x_i\). On peut calculer cette fonction d'autocoïncidence à partir de la distribution de probabilité des symboles de x, on note Σ = {a1,a2, ..., an} les n symboles de l'alphabet Σ et f1,f2, ..., fn leur fréquence d'apparition respective, i.e.

fi := # { j ∈ [1,n]; xj = ai }.
Ainsi la probabilité que deux caractères tirés au hasard soient égaux est égale à la somme des probabilités pour qu'ils soient tout deux égaux à chacun des ai:
φ(x) = ∑i ∈ [1,q] (fi / n) × (fi - 1 / (n - 1))
car Pr({1er symbole = ai}) = fi / n et Pr({2ème symbole = ai}) = fi - 1 / (n - 1). On définit alors l'indice d'autocoïncidence d'un langage L en passant à la limite (donc sur une chaîne dont la longueur tend vers l'infini) dans la langue donnée:
φ(L) = limn → ∞ (n (n - 1))-1i ∈ [1,q] (fi2 - fi)
Mais ∑i ∈ [1,q] fi = n, donc
φ(L) = limn → ∞ (n (n - 1))-1i ∈ [1,q] fi2 - limn → ∞ (n - 1)-1
Soit
φ(L) = limn → ∞i ∈ [1,q] n-2 fi2
et finalement
φ(L) = ∑i ∈ [1,q] pi2.
pi = Pr({un symbole tiré au hasard = ai}). Dans le cas de la langue française, on obtient expérimentalement φ(L) ≈ 0,076, alors que dans le cas où l'alphabet suit une distribution uniforme, c'est-à-dire que ∀ i ∈ [1,q], pi = 1/q, on obtient pour q = 26 la valeur 0,038.

Ainsi en calculant l'indice d'autocoïncidence de chacune des 7 chaînes du tableau précédent, il suffit d'observer si les valeurs sont proches de 4% ou de 8%. Si la longueur de la clef est correcte, la translation de César correspond à une permutation des probabilités ce qui ne change pas l'autocoïncidence d'une langue et la valeur sera proche des 8%, sinon ces séquences seront plus proche d'une distribution aléatoire uniforme.

L'étape suivante consiste à déterminer les clefs partielles ki de la clef k = (k1,k2, ..., kl). On définit alors l'indice d'intercoïncidence:

Soient x := x1,x2, ..., xn et y := y1,y2, ..., ym ∈ Σ* où Σ est un alphabet fini. On définit la fonction d'intercoïncidence φ: Σ* × Σ* → [0,1] par
φ(x,y) := Pr({un symbole de x tiré au hasard = un symbole de y tiré au hasard})

On note f1,f2, ..., fn et g1,g2, ..., gn les fréquences d'apparition respectives des symboles de Σ dans les chaînes x et y. φ(x,y) est alors égal à la somme des probabilités qu'un symbole de x soit égal à un symbole de y tous deux égaux au symbole ai:

φ(x,y) = ∑i ∈ [1,q] fi n-1 × gi m-1
Notons que calculer l'intercoïncidence d'une langue revient à calculer son autocoïncidence (justifiez), elle doit donc valoir environ 7,6%.

En notant σr le décalage circulaire des lettres de r positions (autrement dit l'application xx + r dans Z/qZ), le calcul de l'intercoïncidence entre deux mots xL et y ∈ σr(L) varie entre 3,1% et 4,1%. On obtient donc un critère pour connaître le décalage circulaire entre les différentes séquences du tableau, on se fixe une des chapine x et on calcule tous les décalages circulaires d'une autre σr(y) et la bonne valeur de r donnera une intercorrélation de l'ordre de 8%. En opérant de la sorte avec chacune des séquences, on retrouve l'ensemble des clefs partielles.

Ce programme en ligne reprend l'intégralité de la méthode ci-dessus pour faire cette cryptanalyse.