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 assymé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, é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 est bien sûr abordé.

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

Présentation du système de Vigenère
On se propose de faire la cryptanalyse du système de Vigenère. Le système de Vigenère tente de remédier à la simplicité des systèmes monoalphabétiques dans lesquels un symbole a toujours le même chiffré. Cette caractéristique invalide ces systèmes quand bien même la taille de l'espace des clés est suffisante pour éviter une recherche exhaustive des clés secrètes. Le chiffrement par permutation en est la parfaite illustration puisque la taille de l'espace des clés est de 26! soit environ 288 et que la clef est retrouvée en une fraction de seconde avec une simple analyse en fréquence des lettres (et des digrammes éventuellement).

Le chiffrement de Vigenère est en quelque sorte un chiffrement de César multidimensionnel. De la même façon que pour César, on identifie l'ensemble Σ := {A,..., Z} des 26 lettres de l'alphabet à l'anneau modulaire Z/26Z avec la bijection croissante φ qui associe à chaque lettre son ordre dans N, soit 0 pour A, 1 pour B, ..., et 25 pour Z. On peut donc à travers cette identification "additionner" des lettres modulo 26, la somme x + y sur Σ de deux lettres x et y de Σ est définie par φ-1(φ(x) + φ(y)). Ainsi, on écrira D + X = B.

Une clé k est tout simplement un mot de Σ*, la fermeture de Kleene de l'alphabet fini Σ. La longueur de la clef k doit être suffisante pour éviter une attaque brute, autrement dit pour une sécurité de 128 bits, il faudra que la longueur l de la clé soit telle que 26l ≥ 2128, soit l ≥ 28. On segmente alors le message à chiffrer en mots x de l lettres et la fonction de chiffrement de Vigenère est définie par

ek(x) := x + k
où l'addition sur Σ est étendue naturellement sur l'espace produit Σ × Σ × ... × Σ l fois. La fonction de déchiffrement est ek(y) := y - k.

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, le programme les filtre automatiquement. Notez que si vous saisissez une clé d'une seule lettre le programme calcule le chiffrement de César.

Cryptanalyse
La cryptanalyse du système de chiffrement de Vigenère est la plus réaliste puisqu'il s'agit d'une attaque à chiffré connu. On rappelle que tous les systèmes de chiffrement apppliquent le principe de Kerckhoffs. L'attaquant Oscar connaît donc exactement la méthode chiffrement. À, titre de rappel, les types d'attaques dans l'ordre décroissant de difficulté (et de moins en moins réaliste):

  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 de son choix x (sans pour autant disposer de la clé secrète.)
  4. chiffré choisi (Oscar peut déchiffrer des chiffrés y (sans pour autant disposer de la clé secrète.)

La première étape de la cryptanalyse consiste à déterminer la longueur l de la clé 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 l'existence de tels motifs:

  1. C'est une pure coïncidence.
  2. Les motifs antécédents du message x sont identiques.

Exemple: la clef est k = "SECRETS" et le message clair est "SUDESTRHODESAPPLIQUERCODESXX":

Message x SUDESTR HODESAP PLIQUER CODESXX
Clef k SECRETS SECRETS SECRETS SECRETS
Chiffré y KYFVWMJ ZTFVWTH HPKHYXJ USFVWQP
Indices 0123456 7890123 4567890 1234567

Le motif FVW est présent trois fois dans le message chiffré. Les positions de ces trois motifs dans le message chiffré sont 2, 9 et 23. Si l'on calcule les décalages entre le premier motif et les suivants, on obtient 9 - 2 = 7 et 23 - 2 = 21. En calculant le pgcd (7,21) = 7 on peut légitimement faire l'hypothèse que la longueur l de la clef est égale à 7.

En regroupant les termes du chiffré selon la congruence modulo 7 de leurs indices, on obtiendrait 7 chaînes qui seraient les chiffrés de César avec les 7 clés partielles de k (i.e. les 7 symbole qui constituent k):

0KZHU
1YTPS
2FFKF
3VVHV
4WWYW
5MTXQ
6JHJP

Et on pourrait refaire une analyse classique sur le fréquence des lettres puisque mais on peut être plus subtile. L'étape suivante consiste à valider l'hypothèse de cette longueur en calculant deux quantités:

  1. l'indice d'autocoïncidence;
  2. l'indice d'intercoïncidence.

[W. Friedman, 1920] Soit x := x1,x2, ..., xn ∈ Σ* où Σ est un alphabet fini. On définit la fonction d'autocoïncidence φ: Σ* → [0,1] par
φ(x) := Pr({deux symboles tirés au hasard de x sont égaux})

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 clé 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 clés 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 clés partielles.

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