Cryptographie et sécurité · Information, calcul et communication

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

distinguer les quatre objectifs de sécurité — confidentialité, intégrité, authenticité, non-répudiation — et nommer le mécanisme qui répond à chacun;
énoncer le principe de Kerckhoffs et expliquer pourquoi la sécurité doit reposer sur la clef et non sur le secret de l'algorithme;
casser un chiffrement par décalage ou par substitution périodique au moyen de l'analyse des fréquences, et démontrer que le masque jetable est parfaitement sûr au sens de Shannon;
calculer une exponentiation modulaire par carrés successifs, appliquer les théorèmes de Fermat et d'Euler, et dérouler l'échange de Diffie-Hellman ainsi que le chiffrement et le déchiffrement RSA sur de petits nombres;
démontrer la correction de RSA et énoncer honnêtement sur quelle conjecture repose sa sécurité;
énoncer les trois propriétés attendues d'une fonction de hachage, calculer la borne des anniversaires pour une taille d'empreinte donnée, et décrire ce qu'une signature numérique prouve et ce qu'elle ne prouve pas.

Quatre objectifs, un principe

La sécurité n'est pas une grandeur unique

Les huit premiers chapitres ont traité l'information comme une quantité neutre: il fallait la représenter (chapitre 1), la calculer (chapitres 2 à 5), la comprimer (chapitres 6 et 7), la protéger contre le bruit (chapitre 8). Le bruit n'a pas d'intention. Ce chapitre introduit un adversaire: quelqu'un qui veut lire, modifier ou usurper. Cela change tout, y compris la manière de mesurer le succès — un code correcteur est jugé sur une probabilité d'erreur résiduelle, un système cryptographique sur ce qu'un adversaire intelligent, patient et bien équipé peut en faire.

Dire d'un système qu'il est «sécurisé» ne veut rien dire tant qu'on n'a pas dit contre quoi. On distingue quatre objectifs, indépendants les uns des autres, et servis par des mécanismes différents.

Ces objectifs sont réellement distincts, et l'erreur la plus fréquente consiste à croire que l'un entraîne les autres. Un message chiffré peut être modifié en transit sans que le destinataire s'en aperçoive: le chiffrement seul ne donne pas l'intégrité. Un message parfaitement intègre peut venir de n'importe qui: l'intégrité seule ne donne pas l'authenticité. Un message authentifié par une clef partagée entre deux personnes ne prouve rien devant un tiers, puisque chacune des deux aurait pu le fabriquer: l'authenticité partagée ne donne pas la non-répudiation. Le chapitre est organisé autour de ces mécanismes, dans cet ordre.

Trois métiers qu'on confond sans arrêt

Le chapitre 8 a déjà prévenu: une somme de contrôle (checksum), un code correcteur d'erreurs et une empreinte cryptographique (hash) font trois métiers différents. La somme de contrôle détecte les erreurs accidentelles d'un canal bruité, à très bas coût, et se laisse tromper en quelques secondes par un adversaire. Le code correcteur répare une erreur accidentelle et n'a aucune ambition de sécurité. L'empreinte cryptographique est conçue pour qu'un adversaire disposant d'un budget de calcul énorme ne parvienne pas à fabriquer deux messages de même empreinte. Un CRC-32 posé sur un fichier téléchargé n'authentifie rien; une empreinte SHA-256 publiée sur un canal non sûr non plus, d'ailleurs, car l'adversaire qui remplace le fichier remplace aussi l'empreinte. C'est le genre de distinction qui décide de la sécurité réelle d'un système bien plus souvent que le choix de l'algorithme.

Le principe de Kerckhoffs

En 1883, dans un article intitulé «La cryptographie militaire» paru en deux parties dans le Journal des sciences militaires (vol. IX, janvier et février 1883), le linguiste néerlandais Auguste Kerckhoffs énonce six exigences pratiques pour les chiffres de campagne. La deuxième est restée: le système ne doit pas exiger le secret, et il doit pouvoir tomber sans inconvénient entre les mains de l'ennemi.

Ce n'est pas une position morale mais une hypothèse de travail, et elle est justifiée par quatre arguments concrets.

D'abord, un algorithme finit toujours par être connu. Il est dans du logiciel, dans du matériel, dans la tête d'employés qui changent d'entreprise; il est soumis à la rétro-ingénierie. Une clef, elle, est une chaîne de bits que l'on peut détruire et remplacer.

Ensuite, une clef se change, un algorithme non. Si une clef est compromise, on en tire une autre en quelques microsecondes. Si un algorithme secret est compromis, il faut remplacer tout le parc déployé.

Puis, un algorithme public est un algorithme examiné. Les chiffrements sérieux d'aujourd'hui sont le produit de concours ouverts et de vingt ans de tentatives de cryptanalyse publiées. Un algorithme tenu secret n'a été examiné que par ceux qui l'ont écrit, c'est-à-dire par les personnes les moins susceptibles d'en voir le défaut.

Enfin, le principe rend la sécurité quantifiable. Si la sécurité tient à la clef, on peut parler de la taille de l'espace des clefs, du coût d'une recherche exhaustive, du nombre de messages qu'un adversaire devrait observer. Si elle tient au secret de l'algorithme, on ne peut mesurer que la confiance que l'on place dans ses auteurs, ce qui n'est pas une mesure.

Le corollaire s'énonce en une phrase: la sécurité par l'obscurité n'est pas une sécurité. Elle peut être une couche de gêne supplémentaire; elle ne doit jamais être la couche qui porte.

Question 9.1

Un fournisseur affirme: «notre protocole est très sûr, nous ne publions pas son fonctionnement». Que dit le principe de Kerckhoffs de cette affirmation?

Chiffrement symétrique

Le cadre

La condition $D_{k} (E_{k} (m)) = m$ dit seulement que le chiffrement est inversible à clef fixée; elle ne dit rien de la sécurité. Un chiffrement qui laisse le message en clair la vérifie aussi. Tout le sujet est de savoir ce que le chiffré révèle du clair à quelqu'un qui ne connaît pas $k$ .

César: décaler l'alphabet

Le plus ancien chiffre documenté décale chaque lettre d'un nombre fixe de positions. En identifiant les lettres A…Z aux entiers $0, \dots, 25$ , le chiffrement s'écrit

E_{k} (x) = (x + k) mod 26, D_{k} (y) = (y - k) mod 26, (9.1)

avec $k \in {0, 1, \dots, 25}$ . C'est déjà de l'arithmétique modulaire, et c'est le premier de nos chiffres à obéir formellement à la définition ci-dessus.

Sa faiblesse est immédiate: il y a 26 clefs, dont une triviale. Un adversaire les essaie toutes et lit le résultat: on appelle cela une recherche exhaustive (brute force). Un espace de clefs de 26 éléments, c'est $lo g_{2} 26 \approx 4, 70$ bits de clef. Pour référence, une clef AES-128 en contient 128.

On pourrait croire que remplacer le décalage par une permutation arbitraire de l'alphabet règle l'affaire: l'espace des clefs passe à $26! \approx 4, 03 \cdot 1 0^{26}$ , soit environ 88 bits, ce qui est hors de portée d'une recherche exhaustive à la main. Et pourtant ce chiffre tombe en quelques minutes, parce qu'un espace de clefs vaste n'est une protection que si aucune structure du clair ne survit au chiffrement.

L'analyse des fréquences

Dans un texte français, les lettres n'apparaissent pas à égalité. Le E domine largement, et le groupe E, S, A, I, T, N, R, U, L, O représente à lui seul environ trois quarts des lettres. Une substitution mono-alphabétique — qu'il s'agisse d'un décalage ou d'une permutation quelconque — laisse ce profil intact: elle ne fait que renommer les barres de l'histogramme. Il suffit donc de compter.

Voici le programme que nous avons réellement exécuté. Le texte clair est une phrase du chapitre, normalisée en 201 lettres majuscules sans accents ni espaces; on le chiffre par un décalage de $k = 11$ inconnu du cryptanalyste.

from collections import Counter
# Fréquences de référence du français, normalisées à 100 (valeurs usuelles arrondies)
FR = {"E": 15.19, "S": 8.20, "A": 7.88, "I": 7.77, "T": 7.47, "N": 7.33, "R": 6.76,
      "U": 6.51, "L": 5.63, "O"

Voici le chiffré intercepté, en entier, pour que vous puissiez refaire chacun des calculs qui suivent (201 lettres, à recopier d'un seul tenant dans la variable chiffre):

WLDPNFCTEPOFYDJDEPXPNCJAEZRCLASTBFPYPOZTEULXLTDCPAZ
DPCDFCWPDPNCPEOPWLWRZCTESXPXLTDFYTBFPXPYEDFCNPWFTOP
WLNWPQNLCFYLWRZCTESXPQTYTEEZFUZFCDALCPECPNZYYFOPWLO
GPCDLTCPLWZCDBFFYPNWPQAPFEPECPNSLYRPPPYFYTYDELYE

Ses six lettres les plus fréquentes, telles que le programme les a comptées:

Lettre du chiffré	P	C	F	L	E	Y
Occurrences (sur 201)	32	18	16	15	15	14
Fréquence	15,9 %	9,0 %	8,0 %	7,5 %	7,5 %	7,0 %

Le profil est celui du français, décalé. La lettre P à 15,9 % est presque certainement le E, ce qui donne $k = P - E = 15 - 4 = 11$ . Le test du khi-deux, qui mesure l'écart entre la distribution observée après déchiffrement et celle du français, confirme sans ambiguïté: il vaut $20, 6$ pour $k = 11$ , contre $1396, 1$ pour $k = 0$ , pour et pour ; la deuxième meilleure clef, , est déjà à . Le minimum est atteint pour la bonne clef, et il en est très loin des autres.

Vigenère: une clef par position

Le chiffre de Vigenère (publié au seizième siècle, longtemps réputé indéchiffrable) applique un décalage différent à chaque position, dicté par une clef répétée le long du message. Avec la clef CLEF $= (2, 11, 4, 5)$ , la première lettre est décalée de 2, la deuxième de 11, la troisième de 4, la quatrième de 5, la cinquième à nouveau de 2, et ainsi de suite:

E_{k} (x_{i}) = (x_{i} + k_{i mod ℓ}) mod 26, (9.2)

où $ℓ$ est la longueur de la clef. L'histogramme global du chiffré est maintenant presque plat: le E du clair ne devient plus une seule lettre, mais $ℓ$ lettres différentes selon sa position. L'analyse des fréquences naïve échoue.

Elle échoue globalement. Elle réussit par colonnes, dès que $ℓ$ est connu: les positions $i \equiv 0 (mod ℓ)$ forment un sous-texte chiffré par un simple César de clef $k_{0}$ , celles $i \equiv 1$ un César de clef $k_{1}$ , etc. On casse donc chiffres de César indépendants.

Reste à trouver $ℓ$ . L'outil classique est l'indice de coïncidence: la probabilité que deux lettres tirées au hasard dans un texte soient égales,

IC = l = A \sum Z \frac{n _{l} ( n _{l} - 1 )}{n ( n - 1 )} . (9.3)

Pour un texte aléatoire uniforme, $IC = 1/26 \approx 0, 0385$ . Pour du français, $IC \approx \sum p_{l}^{2} = 0, 0734$ avec la distribution de référence ci-dessus. Un chiffré de Vigenère a un indice intermédiaire; mais si l'on découpe le chiffré en $ℓ$ colonnes avec la bonne valeur de , chaque colonne est un texte français décalé, donc son indice remonte à la valeur du français.

Exemple 9.2 · Vigenère cassé par l'indice de coïncidence, avec les nombres du calcul

Nous avons chiffré un texte français de 350 lettres avec la clef CLEF et exécuté le calcul. Voici le chiffré en entier, pour que les nombres qui suivent soient vérifiables:

NPGMKQJWGOIAKRISGCIKWEPTPRXJOAWHQYWNFPVJEZQRGTRIGN
LNHQVFDWIUCCGJSFMQCATQKBYJCNLFSFIQGEXWGFRIGNEQCRII
KQJJTPRYFTGYGAEWNLGQGQVJRPXJGWIQQYKIWXIXULKJOLMXEP
XYGCIUGEMYKZRJUETWGNMXGXISVDEKCTFQGDWJELVXKWEQQYKZ
GFVIGWEHNPJJUEGTPYYJNPXJZEIXGOIHQFTJGYEZVLRYFPGTNZ
RSGDGMCNYSGNLNHQVJGAEWWYWNOAPJFPGFNLKJFPGJULVJVNLF
SFIHQWSSPPGJFPEQQCWFNLRFNJWJFPWKTPUZGYGJUZVIKYENTP

L'indice de coïncidence, calculé par (9.3), vaut $0, 0833$ pour le clair et $0, 0476$ pour ce chiffré: le chiffrement a bien aplati la distribution. En découpant le chiffré en $ℓ$ colonnes et en moyennant les indices des colonnes, on obtient:

Longueur $ℓ$ testée	1	2	3	4	5	6	7	8
Indice moyen des colonnes	0,0476	0,0633	0,0489	0,0853	0,0449	0,0648	0,0457	0,0853

Les valeurs $ℓ = 4$ et ressortent nettement (0,0853 contre 0,045 à 0,065 ailleurs); on retient la plus petite, , car un multiple de la vraie longueur donne le même effet. Le test du khi-deux appliqué colonne par colonne rend alors les décalages , c'est-à-dire , et le déchiffrement redonne le texte original — nous l'avons vérifié par une assertion d'égalité en Python, pas à l'œil.

Question 9.2

Un chiffre par substitution mono-alphabétique sur l'alphabet latin de 26 lettres admet $26!$ clefs. Combien de bits de clef cela représente-t-il, c'est-à-dire combien vaut $lo g_{2} (26!)$ ? Donnez la valeur à une décimale près.

Le masque jetable et le secret parfait

Définition du secret parfait

Shannon, dans un article de 1949 qui prolonge celui de 1948 dont le chapitre 6 tire l'entropie, a donné la seule définition de sécurité qui ne dépende d'aucune hypothèse de calcul.

C'est une exigence extrêmement forte. Elle ne dit pas que l'adversaire aurait besoin de beaucoup de temps: elle dit qu'il n'apprend rien, même avec un temps de calcul infini. Aucun des chiffres utilisés sur le web ne l'atteint. Un seul schéma classique l'atteint, et il est d'une simplicité désarmante.

Le masque jetable

Le déchiffrement fonctionne parce que $\oplus$ est sa propre réciproque: $(m \oplus k) \oplus k = m \oplus (k \oplus k) = m \oplus 0 = m$ . Sur un octet, avec $m =$ et , on obtient , et rechiffrer avec redonne .

Démonstration. Fixons $c$ . Pour un message $m$ donné, l'événement $C = c$ se produit si et seulement si $K = m \oplus c$ : la clef est entièrement déterminée par $m$ et $c$ , et c'est la seule qui convienne. Comme $K$ est uniforme sur un ensemble de $2^{n}$ éléments et indépendante de ,

P (C = c ∣ M = m) = P (K = m \oplus c) = 2^{- n},

et cette valeur ne dépend pas de $m$ . Par la formule des probabilités totales,

P (C = c) = m^{'} \sum P (M = m^{'}) P (C = c ∣ M = m^{'}) = 2^{- n} m^{'} \sum P (M = m^{'}) = 2^{- n} .

La formule de Bayes donne alors

P (M = m ∣ C = c) = \frac{P ( C = c ∣ M = m ) P ( M = m )}{P ( C = c )} = \frac{2 ^{- n} P ( M = m )}{2 ^{- n}} = P (M = m) . □

L'interprétation vaut d'être formulée en mots. Étant donné un chiffré de 100 bits, tout clair de 100 bits est possible, et exactement aussi probable qu'avant l'interception: il existe une clef qui transforme ce chiffré en «ATTAQUEZ À L'AUBE» et une autre qui le transforme en «RENDEZ-VOUS DEMAIN». L'adversaire qui essaie toutes les clefs obtient tous les messages possibles et n'a aucun moyen de choisir. Ce n'est pas qu'il calcule trop lentement: il n'y a rien à calculer.

Pourquoi personne ne l'utilise pour le web

Le masque jetable est le seul chiffre dont la sécurité soit démontrée et non conjecturée. Il est aussi inutilisable à l'échelle d'Internet, pour trois raisons qui sont toutes des conséquences directes de sa définition.

Première condition: la clef est aussi longue que le message. Pour chiffrer un film de 4 Go, il faut 4 Go de clef. Mais si l'on dispose d'un canal capable de transporter secrètement 4 Go de clef, on peut y faire passer le film. Le masque jetable ne résout donc pas le problème de la confidentialité: il le déplace vers la distribution des clefs, sans le réduire d'un octet. Ce n'est pas un défaut de l'implémentation, c'est une loi.

Démonstration (de l'inégalité sur les cardinaux). Supposons $∣ K ∣ < ∣ M ∣$ et supposons tous les messages de probabilité non nulle. Fixons un chiffré $c$ atteignable. L'ensemble ${D_{k} (c) : k \in K}$ des clairs compatibles avec $c$ a au plus $∣ K ∣$ éléments, donc strictement moins que : il existe un message qui n'y figure pas. Alors , alors que : l'égalité (9.4) est violée.

Deuxième condition: la clef doit être véritablement aléatoire. Uniforme et indépendante, pas «produite par un générateur qui a l'air aléatoire». Remplacer la clef par la sortie d'un générateur pseudo-aléatoire de graine 128 bits remplace $2^{n}$ clefs possibles par $2^{128}$ : le théorème 9.1 ne s'applique plus, et l'on retombe sur une sécurité calculatoire — celle, précisément, du chiffrement par flot que le générateur définit. C'est parfaitement légitime, mais ce n'est plus le secret parfait.

Troisième condition: la clef ne doit jamais servir deux fois. C'est la contrainte la plus violée, et sa violation est catastrophique. Si $c_{1} = m_{1} \oplus k$ et $c_{2} = m_{2} \oplus k$ avec la même clef, alors

c_{1} \oplus c_{2} = (m_{1} \oplus k) \oplus (m_{2} \oplus k) = m_{1} \oplus m_{2} : (9.6)

la clef disparaît. L'adversaire obtient le OU exclusif des deux clairs, et deux textes en langue naturelle superposés se séparent par les méthodes statistiques de la section précédente. Nous avons vérifié (9.6) en Python sur OUI et NON chiffrés avec la même clef de trois octets: $c_{1} \oplus c_{2}$ et $m_{1} \oplus m_{2}$ valent tous deux en hexadécimal.

Le masque jetable a été et reste employé là où la contrainte de distribution est acceptable: liaisons diplomatiques, agents de terrain munis de carnets de clefs à usage unique. Pour un navigateur qui ouvre une connexion vers un serveur qu'il n'a jamais vu, il est hors de question.

Question 9.3

Alice chiffre deux messages différents avec le même masque jetable. Que peut en déduire un adversaire qui intercepte les deux chiffrés?

Chiffrement par blocs: le standard AES

Puisque le secret parfait est hors d'atteinte, la cryptographie moderne vise un objectif plus modeste et parfaitement suffisant: la sécurité calculatoire. On ne demande plus que l'adversaire n'apprenne rien, mais qu'il ne puisse rien apprendre avec les ressources de calcul dont l'humanité dispose.

L'AES (Advanced Encryption Standard) est le standard actuel. Il est issu de l'algorithme Rijndael, conçu par Joan Daemen et Vincent Rijmen, retenu à l'issue d'un concours public et normalisé par le NIST en 2001 (FIPS 197). Il opère sur des blocs de 128 bits, avec des clefs de 128, 192 ou 256 bits. Aucune attaque ne le met en défaut en pratique: contre AES-128, la meilleure approche réaliste reste la recherche exhaustive sur $2^{128}$ clefs.

Ce dernier nombre mérite qu'on s'y arrête, parce qu'il est la raison pour laquelle on n'a pas besoin de mieux. On a $2^{128} \approx 3, 40 \cdot 1 0^{38}$ . Une machine hypothétique testant $1 0^{18}$ clefs par seconde — mille milliards de milliards par seconde, ce qui est très au-delà de toute installation existante — mettrait $3, 4 \cdot 1 0^{20}$ secondes, soit environ années: près de mille fois l'âge de l'univers. Avec , on approche le nombre d'atomes de l'univers observable, estimé à environ par les modèles cosmologiques usuels — en vaut à peu près le millième. Une clef bien choisie ne se devine pas; c'est tout autour d'elle que les systèmes cassent.

Chiffré ne veut pas dire sécurisé

Trois pièges, tous fréquents et tous indépendants de la force de l'algorithme.

Le mode opératoire compte autant que le chiffre. Si l'on chiffre chaque bloc indépendamment avec la même clef (mode dit ECB), deux blocs de clair identiques donnent deux blocs de chiffré identiques: la structure du document transparaît dans le chiffré. Les modes utilisés en pratique introduisent une valeur d'initialisation qui rend le chiffrement de chaque bloc dépendant du contexte.

Le chiffrement ne protège pas l'intégrité. Sans mécanisme d'authentification ajouté, un adversaire peut modifier le chiffré; le destinataire déchiffrera un clair différent sans le savoir. Les protocoles modernes utilisent des modes qui chiffrent et authentifient d'un même mouvement.

Le chiffrement ne cache pas les métadonnées. La taille des messages, leur nombre, leur rythme et l'identité des correspondants traversent le chiffrement intacts. Un canal parfaitement chiffré peut révéler énormément de ce qui s'y passe.

Nous ne détaillerons pas la structure interne de l'AES: elle relève d'un cours de cryptographie et son étude n'apporterait rien à la question du chapitre. Ce qu'il faut en retenir tient en une ligne: un bon chiffrement symétrique est disponible, rapide et gratuit; le problème qui reste est celui de la clef.

Le problème de la distribution des clefs

Un chiffrement symétrique exige que les deux correspondants partagent déjà un secret. Comment le partagent-ils?

Si Alice et Bob peuvent se rencontrer, la question ne se pose pas. Mais un navigateur qui ouvre https:// vers un serveur inconnu ne peut rencontrer personne, et la difficulté croît vite avec le nombre de participants. Pour que $n$ personnes puissent toutes communiquer deux à deux, il faut une clef par paire, soit

(2 n) = \frac{n ( n - 1 )}{2} (9.7)

clefs. Pour $n = 10$ , cela fait 45 clefs, ce qui est gérable. Pour $n = 1000$ , il en faut $499500$ . Pour un million d'utilisateurs, $499999500000$ , soit près de $5 \cdot 1 0^{11}$ clefs, chacune devant être transmise par un canal sûr préexistant. Le coût croît en $Θ (n^{2})$ alors que le nombre de participants croît en : le modèle ne passe pas à l'échelle.

Question 9.4

Dans une entreprise de 1000 collaborateurs qui veulent tous pouvoir s'écrire deux à deux de façon confidentielle avec un chiffrement symétrique, combien de clefs distinctes faut-il distribuer?

Arithmétique modulaire: la boîte à outils

Tout ce qui suit repose sur quelques résultats d'arithmétique. Nous démontrons exactement ce dont RSA a besoin et rien de plus; le cours de Mathématiques discrètes traite le reste (théorème des restes chinois, racines primitives, tests de primalité, structure des groupes cycliques), et l'annexe A du présent cours en donne un mémento.

Congruences

La compatibilité avec la multiplication est ce qui rend les calculs possibles: pour calculer $6 5^{17} mod 3233$ , on n'a pas besoin de connaître $6 5^{17}$ , qui a 31 chiffres décimaux. On peut réduire modulo $3233$ après chaque produit, et ne jamais manipuler de nombre dépassant $323 2^{2} < 1, 1 \cdot 1 0^{7}$ .

La division, en revanche, n'est pas toujours possible: $a$ admet un inverse modulo $n$ si et seulement si $g cd (a, n) = 1$ , et cet inverse se calcule par l'algorithme d'Euclide étendu, qui produit les coefficients de Bézout $u, v$ tels que $a u + n v = 1$ ; on a alors $a u \equiv 1 (mod n)$ . C'est cette condition d'inversibilité qui décidera de l'existence de la clef privée RSA, et l'explorateur de ce chapitre la fait sentir en la violant.

Exponentiation rapide

Calculer $a^{k} mod n$ en multipliant $k - 1$ fois par $a$ est hors de question dès que $k$ a quelques centaines de bits — ce qui est le cas de tout exposant RSA réel. La méthode des carrés successifs ramène le coût au nombre de bits de l'exposant.

L'idée tient dans l'écriture binaire de $k$ . Si $k = (b_{r - 1} b_{r - 2} \dots b_{0})_{2}$ , alors on part de et l'on parcourt les bits de gauche à droite: à chaque bit on élève au carré, et l'on multiplie en plus par lorsque le bit vaut 1.

def exp_mod(a, k, n):
    """a^k mod n par carrés successifs, de gauche à droite."""
    resultat = 1
    for bit in bin(k)[2:]:          # bits de k, du plus fort au plus faible
        resultat = resultat * resultat % n      # élévation au carré
        if bit == "1":
            resultat = resultat * a % n         # multiplication par a
    return resultat

Le coût est de $r - 1$ élévations au carré et d'autant de multiplications qu'il y a de bits à 1 (moins celui de tête, qui ne fait qu'initialiser). Comme $r = ⌊ lo g_{2} k ⌋ + 1$ , le nombre total de multiplications modulaires est au plus $2 lo g_{2} k$ : on passe de à , ce qui est exactement la différence entre impossible et instantané.

Question 9.5

Remettez dans l'ordre les étapes du calcul de $a^{k} mod n$ par carrés successifs, de gauche à droite.

Glissez les éléments pour les mettre dans le bon ordre

Écrire l'exposant

k

en binaire

Renvoyer le résultat après le dernier bit

Si le bit vaut

1

, multiplier en plus le résultat par

a

et réduire modulo

n

À chaque bit, élever le résultat au carré et le réduire modulo

n

Parcourir les bits de

k

du plus fort au plus faible

Initialiser le résultat à

1

Fermat, Euler et l'indicatrice

Démonstration. Considérons les $p - 1$ entiers $a, 2 a, \dots, (p - 1) a$ réduits modulo $p$ . Aucun n'est nul, car $p$ est premier et ne divise ni $a$ ni $j$ pour $1 \leq j \leq p - 1$ . Ils sont deux à deux distincts: si alors divise , donc divise , donc vu que . Ces valeurs distinctes et non nulles sont donc exactement dans un autre ordre. En multipliant,

a^{p - 1} (p - 1)! \equiv (p - 1)! (mod p),

et comme $(p - 1)!$ n'est pas divisible par $p$ , il est inversible modulo $p$ : on simplifie et il reste $a^{p - 1} \equiv 1$ . $□$

Vérification numérique: $3^{16} mod 17 = 1$ , calculé en Python.

Deux cas suffisent ici. Si $p$ est premier, tous les entiers de 1 à $p - 1$ sont premiers avec $p$ , donc $φ (p) = p - 1$ . Si $n = p q$ avec $p \neq = q$ premiers, les entiers de à qui ne sont premiers avec sont les multiples de (il y en a ) et les multiples de (il y en a ), le seul compté deux fois étant lui-même. D'où

φ (p q) = p q - p - q + 1 = (p - 1) (q - 1) . (9.9)

Pour la clef du cours: $φ (3233) = 60 \times 52 = 3120$ . Notez tout de suite ce point, car c'est le cœur de RSA: calculer $φ (n)$ à partir de $n$ seul revient à factoriser $n$ . En effet, connaissant $n$ et $φ (n)$ , on connaît $p + q = n - φ (n) + 1$ et , donc et sont les racines d'une équation du second degré que l'on résout immédiatement.

Démonstration. Soit $U = {u_{1}, \dots, u_{φ (n)}}$ l'ensemble des classes inversibles modulo $n$ . L'application $u \mapsto a u$ envoie $U$ dans (un produit d'inversibles est inversible) et elle est injective (multiplier par l'inverse de la renverse), donc c'est une bijection de sur lui-même. En multipliant toutes les images,

i \prod (a u_{i}) \equiv i \prod u_{i} (mod n), c’est- \overset{a}{ˋ} -dire a^{φ (n)} i \prod u_{i} \equiv i \prod u_{i} .

Le produit $\prod_{i} u_{i}$ est inversible comme produit d'inversibles; on simplifie et il reste $a^{φ (n)} \equiv 1$ . $□$

Le petit théorème de Fermat en est le cas particulier $n = p$ premier, où $φ (p) = p - 1$ . Vérification numérique sur la clef du cours: $2^{3120} mod 3233 = 1$ , calculé en Python par exponentiation rapide.

Question 9.6

Pourquoi la connaissance de $φ (n)$ est-elle aussi précieuse que celle de la factorisation de $n = p q$ ?

L'échange de Diffie-Hellman

Le protocole

En 1976, Whitfield Diffie et Martin Hellman publient «New Directions in Cryptography» et montrent que deux personnes qui n'ont jamais rien partagé peuvent, par un échange entièrement public, se retrouver en possession d'un secret commun.

Le mécanisme repose sur une asymétrie de coût. Élever $g$ à la puissance $a$ modulo $p$ est facile (section précédente: $Θ (lo g a)$ multiplications). Retrouver $a$ à partir de $g^{a} mod p$ — le logarithme discret — ne l'est pas: aucun algorithme connu ne le fait en temps polynomial en le nombre de bits de $p$ .

Pourquoi l'espion est bloqué

L'adversaire connaît $p$ , $g$ , $A = g^{a}$ et $B = g^{b}$ , et veut $g^{ab}$ . Deux chemins s'offrent à lui.

Le premier consiste à extraire $a$ de $A$ , c'est-à-dire à résoudre le problème du logarithme discret: trouver $x$ tel que $g^{x} \equiv A (mod p)$ . L'algorithme générique le plus simple, dit «pas de bébé, pas de géant», y parvient en environ $p$ opérations et autant de mémoire — ce qui, pour un de 2048 bits, signifie opérations, un nombre sans rapport avec quoi que ce soit de physique. Des algorithmes plus rapides existent pour les corps finis, mais aucun n'est polynomial, et c'est la raison pour laquelle on choisit grand.

Le second consiste à calculer $g^{ab}$ directement à partir de $g^{a}$ et $g^{b}$ sans passer par $a$ ni $b$ : c'est le problème de Diffie-Hellman calculatoire. On ne sait pas le résoudre autrement qu'en résolvant le logarithme discret, mais on n'a pas démontré qu'il lui soit équivalent.

Il faut être clair sur le statut de cette sécurité, et le chapitre 5 a donné le vocabulaire pour le faire. Le logarithme discret est un problème dont on croit qu'il est difficile, parce que personne n'a publié d'algorithme efficace malgré cinquante ans d'efforts. Ce n'est pas un théorème. Si quelqu'un démontrait demain que $P = NP$ , ou trouvait simplement un algorithme polynomial pour ce problème particulier, l'échange s'effondrerait. Toute la cryptographie à clef publique vit sur des conjectures de ce type.

Ce que Diffie-Hellman ne donne pas

Un secret partagé, avec personne en particulier

L'échange de Diffie-Hellman fournit un secret commun sans aucune authentification. Alice sait qu'elle partage une clef avec l'entité qui lui a envoyé $B$ ; elle n'a aucun moyen de savoir que cette entité est Bob. Le protocole, tel quel, est vulnérable à l'attaque de l'intercepteur (man-in-the-middle), et cette vulnérabilité n'est pas un défaut d'implémentation: elle est inhérente au protocole nu.

C'est pourquoi tout usage réel de Diffie-Hellman est accompagné d'une authentification des valeurs échangées — typiquement une signature numérique vérifiée au moyen d'un certificat, ce que la fin du chapitre décrit. Un échange de clefs non authentifié donne la confidentialité contre un adversaire passif et rien du tout contre un adversaire actif.

Question 9.7

Que faut-il ajouter à un échange de Diffie-Hellman pour le protéger contre l'attaque de l'intercepteur?

RSA

Génération des clefs

RSA, publié en 1978 par Ronald Rivest, Adi Shamir et Leonard Adleman, va plus loin que Diffie-Hellman: il fournit un véritable chiffrement à clef publique, où chacun publie une clef de chiffrement et garde une clef de déchiffrement.

La condition (9.11) n'est pas un choix esthétique, c'est exactement ce qu'il faut pour que le déchiffrement annule le chiffrement. Chiffrer puis déchiffrer élève le message à la puissance $e d$ ; or (9.11) dit précisément que $e d = 1 + k φ (n)$ pour un entier $k$ , de sorte que

m^{e d} = m^{1 + k φ (n)} = m \cdot (m^{φ (n)})^{k} \equiv m \cdot 1^{k} = m (mod n)

par le théorème d'Euler, du moins lorsque $g cd (m, n) = 1$ . Le théorème 9.5 traite le cas général.

Le choix de $e$ demande $g cd (e, φ (n)) = 1$ pour que l'inverse existe. Si cette condition est violée, il n'existe aucun exposant privé: le chiffrement reste calculable, mais il n'est plus injectif, et ce qui est chiffré est définitivement perdu. L'explorateur ci-dessous vous laisse provoquer cette situation.

Le cours de l'exemple, en entier

Correction

Démonstration. Écrivons $e d = 1 + k φ (n) = 1 + k (p - 1) (q - 1)$ avec $k \geq 1$ entier, ce qui est exactement (9.11).

Premier cas: $g cd (m, n) = 1$ . Le théorème d'Euler donne $m^{φ (n)} \equiv 1 (mod n)$ , donc

m^{e d} = m \cdot (m^{φ (n)})^{k} \equiv m \cdot 1^{k} = m (mod n) .

Cas général. Montrons la congruence modulo $p$ et modulo $q$ séparément. Modulo $p$ , deux sous-cas. Si $p$ divise $m$ , alors $m \equiv 0$ et $m^{e d} \equiv 0 \equiv m (mod p)$ , la congruence est vraie. Sinon et le petit théorème de Fermat donne , d'où

m^{e d} = m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1^{k (q - 1)} = m (mod p) .

Dans les deux sous-cas, $m^{e d} \equiv m (mod p)$ . Le même raisonnement, en échangeant les rôles de $p$ et $q$ , donne $m^{e d} \equiv m (mod q)$ . Ainsi et divisent tous deux ; comme ils sont premiers et distincts, leur produit le divise aussi, c'est-à-dire . Enfin, garantit que le représentant obtenu est lui-même.

Le passage « $p$ et $q$ divisent, donc $pq$ divise» est le théorème des restes chinois sous sa forme la plus élémentaire; le cours de Mathématiques discrètes en donne la version générale.

Explorateur 9.1 · Explorateur RSA jouet

Choisissez deux petits nombres premiers p et q et un exposant public e impair. L'explorateur recalcule n = p·q, φ(n) = (p−1)(q−1), l'exposant privé d = e⁻¹ mod φ(n) et le chiffré du message m = 65. Quand e n'est pas premier avec φ(n), aucun d n'existe: l'explorateur le dit au lieu d'afficher une valeur fausse. Les clés réelles utilisent des premiers de plus de 300 chiffres.

Premier p61

Premier q53

Exposant public e17

Module n = p·q

3233

Indicatrice φ(n)

3120

pgcd(e, φ(n))

Exposant privé d

2753

Chiffré de m = 65

2790

Déchiffré (doit valoir 65)

Question 9.8

Avec $p = 11$ , $q = 13$ et $e = 7$ , calculez l'exposant privé $d$ , c'est-à-dire l'inverse de 7 modulo $φ (n)$ .

Sur quoi repose la sécurité de RSA

La clef privée se déduit de $φ (n)$ , qui se déduit de la factorisation de $n$ . La sécurité de RSA exige donc au minimum que factoriser un grand entier soit difficile. Il faut maintenant être précis, et honnête, sur ce que l'on sait et ce que l'on ne sait pas.

Ce que l'on sait. Aucun algorithme classique connu ne factorise un entier de $b$ bits en temps polynomial en $b$ . Le meilleur algorithme général publié est sous-exponentiel, ce qui est bien mieux que l'essai de tous les diviseurs mais reste hors de portée pour les tailles utilisées. Les records publics de factorisation ont progressé régulièrement: des modules de 512 bits ont été factorisés dès la fin des années 1990, et les records publics portent aujourd'hui sur des modules de l'ordre de 800 bits, au prix de plusieurs milliers d'années de calcul cumulées. C'est ce qui justifie les recommandations actuelles: 2048 bits au minimum, 3072 ou 4096 pour du long terme.

Ce que l'on ne sait pas, et c'est l'essentiel. Il n'est pas démontré que factoriser soit difficile. Personne n'a prouvé de borne inférieure non triviale sur le coût de la factorisation. Il n'est pas démontré non plus que casser RSA exige de factoriser: peut-être existe-t-il un moyen de calculer les racines $e$ -ièmes modulo $n$ sans jamais obtenir $p$ ni $q$ . La sécurité de RSA repose donc sur deux conjectures, pas sur un théorème.

Le statut exact de cette sécurité, et ce que le chapitre 5 en dit

Le chapitre 5 a introduit les classes P et NP et a insisté sur un point qui trouve ici son application. Le problème de la factorisation est dans NP — un facteur est un certificat que l'on vérifie par une multiplication — mais on ne le croit pas NP-complet; il est même dans NP ∩ co-NP, ce qui rend sa NP-complétude improbable. Par conséquent, même une démonstration de $P \neq = NP$ ne garantirait pas la sécurité de RSA, et même $P = NP$ ne la détruirait pas nécessairement de façon pratique: les deux questions sont liées mais distinctes.

La phrase honnête est donc: nous ne savons pas démontrer que RSA est sûr; nous savons que beaucoup de gens compétents ont essayé de le casser sans y parvenir. C'est une croyance étayée, pas une certitude — et l'écart entre les deux est exactement ce qu'un cours d'informatique doit apprendre à voir. Ajoutons, pour être complet, qu'un algorithme quantique dû à Shor factorise en temps polynomial sur un calculateur quantique de taille suffisante; de tels calculateurs n'existent pas aujourd'hui à cette échelle, mais cette perspective suffit à motiver les travaux sur une cryptographie dite post-quantique.

Une dernière précision de vocabulaire. RSA tel qu'il vient d'être décrit — élever le message brut à la puissance $e$ — s'appelle le «RSA scolaire» (textbook RSA) et ne doit jamais être utilisé tel quel: il est déterministe, donc chiffrer deux fois le même message donne deux fois le même chiffré, et il possède des propriétés algébriques exploitables. Les implémentations réelles ajoutent un remplissage (padding) normalisé et aléatoire avant l'exponentiation. Par ailleurs, RSA est lent comparé à l'AES; on ne l'utilise donc pas pour chiffrer des données, mais pour transporter une clef symétrique, exactement comme Diffie-Hellman.

Fonctions de hachage

Trois propriétés, pas une

Les collisions existent nécessairement: il y a une infinité de messages et seulement $2^{ν}$ empreintes, donc le principe des tiroirs (déjà employé au chapitre 7 pour prouver qu'aucun compresseur ne réduit toutes les entrées) en garantit une infinité. La propriété demandée n'est pas leur absence mais l'impossibilité pratique d'en exhiber une.

Les trois propriétés ne sont pas équivalentes et la troisième est strictement plus forte que la deuxième: dans le cas de la seconde préimage, l'adversaire subit $m_{1}$ ; dans celui de la collision, il choisit les deux messages, ce qui est bien plus facile. Cette différence de difficulté se quantifie exactement.

La borne des anniversaires

Le nom vient du fait classique que, dans un groupe de 23 personnes, la probabilité que deux partagent une date d'anniversaire dépasse $1/2$ — bien moins que les 183 personnes qu'une intuition naïve suggère. Le même calcul gouverne les collisions de hachage.

Démonstration (esquisse, admise pour l'approximation). La probabilité qu'aucune collision ne se produise vaut

j = 1 \prod k - 1 (1 - \frac{j}{N}) \approx exp (- j = 1 \sum k - 1 \frac{j}{N}) = exp (- \frac{k ( k - 1 )}{2 N}),

en utilisant $1 - x \approx e^{- x}$ pour $x$ petit. Poser cette quantité égale à $1/2$ donne $k (k - 1) / (2 N) = ln 2$ , soit $k \approx 2 N ln 2$ .

L'enseignement pratique est brutal: la résistance aux collisions d'une empreinte de $ν$ bits ne vaut que $2^{ν /2}$ , pas $2^{ν}$ . Le tableau, calculé en Python:

Taille d'empreinte $ν$	Coût d'une préimage	Coût d'une collision, $2^{ν} = 2^{ν /2}$
64 bits	$1, 8 \cdot 1 0^{19}$

Une empreinte de 64 bits est cassable en collision avec $4, 3$ milliards d'essais, ce qui est l'affaire d'un ordinateur de bureau: elle est inutilisable pour la sécurité. Une empreinte de 256 bits, comme celle de SHA-256, offre $2^{128} \approx 3, 4 \cdot 1 0^{38}$ opérations de résistance aux collisions — le même ordre que la recherche exhaustive sur une clef AES-128. C'est exactement pourquoi l'on dimensionne les empreintes au double du niveau de sécurité visé.

Question 9.9

Une fonction de hachage produit des empreintes de 128 bits. Combien de messages faut-il hacher, en ordre de grandeur, pour avoir une chance sur deux d'observer une collision? Donnez $lo g_{2}$ de ce nombre.

L'effet d'avalanche

Une bonne fonction de hachage se comporte, du point de vue de l'observateur, comme un tirage uniforme: changer un seul bit de l'entrée doit changer environ la moitié des bits de la sortie, de façon imprévisible. C'est l'effet d'avalanche, et il est facile à constater.

Les deux empreintes de la figure 9.3 sont les vraies sorties de SHA-256, obtenues en Python:

from hashlib import sha256
a = "Le paiement est de 1000 francs."
b = "Le paiement est de 1001 francs."
print(sha256(a.encode()).hexdigest())
# 484c22143c3fe01d00ec7e24c31ca94914425aa5f06a56ad762463f1727becf1
print(sha256(b.encode()).hexdigest())
# 0c56b0540be3ae9ab65bf1e679cae082472a4bd4d4211cac2712ae2be05a192f

Le OU exclusif des deux empreintes contient 121 bits à 1 sur 256, soit $47, 3 %$ . L'espérance pour deux valeurs indépendantes uniformes est de 128 bits, soit $50 %$ ; l'écart observé est celui d'une fluctuation ordinaire. Aucune ressemblance entre les entrées ne survit: on ne peut pas «approcher» une empreinte.

À quoi servent les empreintes

Intégrité. Comparer $h (m)$ à une valeur de référence détecte toute modification, accidentelle ou volontaire — à condition que la valeur de référence, elle, soit authentique. Publier l'empreinte d'un fichier sur la même page que le fichier ne protège contre rien d'autre que les erreurs de transmission: qui remplace le fichier remplace l'empreinte. Pour se protéger d'un adversaire, il faut que l'empreinte soit signée, ou transportée par un canal dont l'authenticité est garantie autrement.

Mots de passe. Un serveur ne doit jamais stocker les mots de passe. Il stocke $h (mot de passe)$ , et compare l'empreinte fournie à l'empreinte stockée. Deux raffinements sont indispensables. Le sel (salt) est une valeur aléatoire distincte pour chaque utilisateur, concaténée au mot de passe avant hachage: deux utilisateurs ayant le même mot de passe obtiennent alors des empreintes différentes, et les tables précalculées d'empreintes courantes deviennent inutiles. Nous l'avons vérifié: sha256("motdepasse") commence par 967520ae, tandis que sha256("7f3a9c2e" + "motdepasse") commence par 527d56cd — aucune parenté. Le second raffinement est la lenteur délibérée: on emploie non pas SHA-256 seul mais une fonction de dérivation conçue pour être coûteuse en temps et en mémoire, de sorte qu'un adversaire qui aurait volé la base ne puisse tester que très peu de candidats par seconde. Une fonction de hachage rapide est une qualité pour l'intégrité et un défaut pour les mots de passe.

Signatures. On ne signe jamais un message long directement: on signe son empreinte. C'est l'objet de la dernière section.

Signatures numériques

Le principe

RSA a une propriété remarquable: les exposants $e$ et $d$ jouent des rôles symétriques dans (9.12), puisque $(m^{d})^{e} = m^{d e} = m^{e d} = (m^{e})^{d}$ . On peut donc : appliquer d'abord la clef privée, puis la clef publique. Ce qui est chiffré avec la clef privée se «déchiffre» avec la clef publique — et comme la clef publique est connue de tous, cela ne cache rien. Cela quelque chose.

La vérification fonctionne par le théorème 9.5: $σ^{e} = (y^{d})^{e} = y^{d e} \equiv y = h (m) (mod n)$ . Seul le détenteur de pouvait produire un satisfaisant cette relation, puisque produire à partir de demande d'extraire une racine -ième modulo .

Deux raisons imposent de signer l'empreinte plutôt que le message. D'abord la taille: $m$ doit être inférieur à $n$ , donc un message plus long que le module ne peut pas être élevé à une puissance en une fois; l'empreinte, elle, tient toujours. Ensuite le coût: une exponentiation modulaire sur 2048 bits est lente, tandis que SHA-256 traite des mégaoctets par seconde.

Ce qu'une signature prouve, et ce qu'elle ne prouve pas

Une signature valide prouve trois choses, et seulement trois.

L'intégrité: le message n'a pas été modifié depuis la signature, car toute modification changerait $h (m)$ (résistance à la seconde préimage) et la vérification échouerait.
L'authenticité par rapport à une clef: le signataire détenait la clef privée associée à $(n, e)$ .
La non-répudiation: contrairement à un code d'authentification à clef partagée, que les deux parties peuvent fabriquer, seule Alice pouvait produire $σ$ . Bob peut donc montrer $(m, σ)$ à un tiers, qui vérifie lui-même.

Elle ne prouve rien d'autre, et la liste de ce qu'elle ne prouve pas est aussi importante.

Elle ne dit pas qui est Alice. Elle relie le message à une clef, pas à une personne. Le lien entre une clef publique et une identité est le rôle d'un certificat, délivré par une autorité de certification dont la clef est elle-même certifiée, jusqu'à une racine que votre navigateur ou votre système d'exploitation contient déjà. Toute la sécurité du web repose sur cette chaîne, et elle sort du domaine de la mathématique pour entrer dans celui de la gouvernance: qui certifie qui, selon quelles vérifications, et que se passe-t-il quand une autorité se trompe ou est compromise.

Elle ne dit pas quand. La signature ne contient aucune date vérifiable. Établir qu'un document existait avant une certaine date exige un service d'horodatage qui contresigne l'empreinte.

Elle ne dit pas que la clef n'a pas été volée. Une signature produite par un adversaire qui a dérobé la clef privée est mathématiquement parfaite. D'où les mécanismes de révocation, les durées de validité limitées et le stockage des clefs dans des composants matériels dédiés.

Elle ne dit pas que le signataire a compris ce qu'il signait. Un logiciel qui signe automatiquement ce qu'on lui présente signe aussi bien un ordre de paiement qu'un fichier quelconque. La signature engage la clef, pas le jugement.

Question 9.10

Bob vérifie avec succès la signature RSA d'un document reçu, en utilisant la clef publique $(n, e)$ qu'il a trouvée sur un site web. Que peut-il en conclure?

Là où les systèmes cassent vraiment

Ce chapitre a présenté des mathématiques solides: une preuve de secret parfait, une preuve de correction de RSA, une borne exacte sur les collisions. Il serait trompeur de conclure que la sécurité d'un système réel est affaire de mathématiques. Elle l'est rarement.

Les mécanismes présentés ici, correctement paramétrés, ne sont pas cassés par la cryptanalyse. Ce qui cède se trouve ailleurs, et toujours aux quatre mêmes endroits. Les clefs: engendrées avec un générateur aléatoire de mauvaise qualité, donc prévisibles; stockées dans un fichier de configuration; copiées dans un dépôt de code; jamais renouvelées; partagées entre systèmes. Les implémentations: un algorithme correct sur le papier peut fuir par son temps d'exécution ou sa consommation, ce qu'on appelle un canal auxiliaire (side channel); une erreur de gestion de mémoire expose des secrets; une bibliothèque n'est pas mise à jour. Les protocoles: chaque brique est sûre, mais leur composition ne l'est pas; une négociation permet de revenir à une version affaiblie; une erreur est renvoyée à l'adversaire et lui apprend ce qu'il cherchait; un cas limite n'a pas été prévu. Les personnes: un mot de passe réutilisé, un message convaincant qui demande de valider une connexion, un employé qui contourne une procédure gênante, une autorité de certification qui délivre un certificat à qui ne devait pas l'obtenir.

La conclusion pratique n'est pas le découragement mais un déplacement d'attention. La question utile n'est presque jamais «quel algorithme?» — la réponse est connue et publique — mais «d'où vient cette clef, qui y a accès, comment sait-on que cette clef publique est bien celle de l'interlocuteur, et que se passe-t-il quand quelque chose échoue?». Le chapitre 10 montrera le contexte dans lequel tout cela s'exécute réellement: des protocoles en couches, où le chiffrement n'est qu'une couche parmi d'autres.

Synthèse

Quatre objectifs distincts, quatre familles de mécanismes: confidentialité (chiffrement), intégrité (empreintes), authenticité (signatures et protocoles), non-répudiation (signatures à clef publique et certificats). Aucun n'entraîne les autres, et «chiffré» ne veut pas dire «sécurisé».
Principe de Kerckhoffs: la sécurité repose sur la clef, jamais sur le secret de l'algorithme — parce qu'un algorithme finit par être connu, ne se remplace pas, n'est pas examiné s'il est secret, et ne se quantifie pas.
Le masque jetable est le seul chiffre parfaitement sûr, au sens où le chiffré est indépendant du clair (théorème 9.1). Il est inutilisable à grande échelle parce que la clef doit être aussi longue que le message (théorème 9.2), véritablement aléatoire et jamais réutilisée: réutiliser une clef livre $m_{1} \oplus m_{2}$ . En pratique on emploie l'AES, dont la sécurité est calculatoire: $2^{128} \approx 3, 4 \cdot 1 0^{38}$ clefs mettent une recherche exhaustive hors de portée physique.

Série d'exercices du chapitre 9Exercice 1 sur 5

Question 9.11

Parmi les quatre affirmations suivantes, laquelle est correcte?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 9.1 · Kerckhoffs et les quatre objectifs

Pour chacune des situations suivantes, dire quel objectif de sécurité est en jeu et quel mécanisme y répond: (a) un client veut être sûr que le site bancaire auquel il parle est bien celui de sa banque; (b) une entreprise veut que le contenu d'un courriel reste illisible pour un intermédiaire; (c) un éditeur veut qu'un utilisateur puisse constater qu'un fichier téléchargé n'a pas été altéré; (d) une administration veut pouvoir prouver devant un tribunal qu'un fournisseur a bien émis une facture donnée.
Une équipe propose d'utiliser un algorithme de chiffrement qu'elle a conçu elle-même et qu'elle refuse de publier, en argumentant qu'un attaquant ne pourra pas l'analyser. Formuler trois objections précises.
On propose de compenser la faiblesse d'un chiffre par le fait que le format du fichier chiffré est inconnu de l'adversaire. Que répond le principe de Kerckhoffs?

Solution

1. (a) Authenticité: le client doit être sûr de l'identité du serveur. Mécanisme: un certificat émis par une autorité de certification, vérifié au moyen d'une signature numérique. (b) Confidentialité: mécanisme du chiffrement, symétrique pour les données et à clef publique pour établir la clef. (c) Intégrité: mécanisme d'une empreinte cryptographique — mais publiée par un canal authentique, sans quoi elle ne protège que contre les erreurs de transmission. (d) Non-répudiation: seule une signature numérique à clef publique permet à un tiers de vérifier lui-même, car un code d'authentification à clef partagée aurait pu être fabriqué par l'administration elle-même.

2. Premièrement, l'algorithme sera connu: il est déployé dans du logiciel et se rétro-analyse. Deuxièmement, il n'a été examiné que par ses auteurs, c'est-à-dire par les personnes les moins susceptibles d'en découvrir le défaut; les chiffrements standardisés ont subi des années de cryptanalyse publique. Troisièmement, aucune mesure de sécurité n'est possible: on ne peut pas énoncer le coût d'une attaque, alors qu'avec un chiffre public on parle de la taille de la clef et du coût d'une recherche exhaustive. On peut ajouter une quatrième objection pratique: le jour où l'algorithme est compromis, il faut remplacer tout le parc, alors qu'une clef compromise se remplace en une microseconde.

Exercice 9.2 · Analyse des fréquences et masque jetable

On intercepte un chiffré de César de 500 lettres dont la lettre la plus fréquente est le J. Quelle clef proposez-vous, et pourquoi cette conclusion est-elle plus fiable sur 500 lettres que sur 20?
Un chiffré de Vigenère de longueur 600 a un indice de coïncidence de $0, 045$ . Que peut-on en déduire? Comment procéderiez-vous pour trouver la longueur de la clef?
Alice utilise un masque jetable et chiffre deux messages de 8 bits avec la même clef $k$ . On intercepte $c_{1} = 10110010$ et $c_{2} = 11010110$ . Que peut-on calculer sans connaître ?

Exercice 9.3 · Arithmétique modulaire

Calculer $7^{22} mod 23$ sans calculatrice, en utilisant le petit théorème de Fermat, puis vérifier le résultat par carrés successifs pour $7^{11} mod 23$ .
Calculer $φ (3233)$ , et , où .

Exercice 9.4 · Diffie-Hellman et l'intercepteur

On prend $p = 227$ et $g = 2$ .

Alice choisit $a = 57$ et Bob $b = 101$ . Écrire ce qui transite sur le canal et ce que chacun calcule; donner le secret commun.
Un espion passif enregistre tout le trafic. Quel problème doit-il résoudre, et pourquoi $p = 227$ ne le protège-t-il pas en pratique?

Exercice 9.5 · Une clef RSA complète, et sa signature

On prend $p = 17$ et $q = 23$ .

Calculer $n$ et $φ (n)$ . Parmi $e \in {3, 5, 7, 11}$ , lesquels sont des exposants publics admissibles?

Références

Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, Boston, chapitre 5 (cryptographie et vie privée).
Kerckhoffs, A., «La cryptographie militaire», Journal des sciences militaires, vol. IX, pp. 5–38 (janvier 1883) et pp. 161–191 (février 1883) — les six desiderata, dont le deuxième est devenu «le principe de Kerckhoffs».
Shannon, C. E., «Communication Theory of Secrecy Systems», Bell System Technical Journal, 1949 (définition du secret parfait et borne sur la taille des clefs).
Diffie, W. et Hellman, M., «New Directions in Cryptography», IEEE Transactions on Information Theory, 1976.
Rivest, R., Shamir, A. et Adleman, L., «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems», Communications of the ACM, 1978.
Katz, J. et Lindell, Y., Introduction to Modern Cryptography, 3e éd., CRC Press, Boca Raton (traitement rigoureux du secret parfait, des définitions de sécurité et des signatures).
Ferguson, N., Schneier, B. et Kohno, T., Cryptography Engineering, Wiley, Indianapolis (ce qui casse dans les systèmes réels: clefs, implémentations, protocoles).
Polycopiés du cours ICC de l'EPFL, partie «sécurité et cryptographie».

Objectifs du chapitre

Quatre objectifs, un principe

La sécurité n'est pas une grandeur unique

Le principe de Kerckhoffs

Chiffrement symétrique

Le cadre

César: décaler l'alphabet

L'analyse des fréquences

Vigenère: une clef par position

Le masque jetable et le secret parfait

Définition du secret parfait

Le masque jetable

Pourquoi personne ne l'utilise pour le web

Chiffrement par blocs: le standard AES

Le problème de la distribution des clefs

Arithmétique modulaire: la boîte à outils

Congruences

Exponentiation rapide

Fermat, Euler et l'indicatrice

L'échange de Diffie-Hellman

Le protocole

Pourquoi l'espion est bloqué

Ce que Diffie-Hellman ne donne pas

RSA

Génération des clefs

Le cours de l'exemple, en entier

Correction

Sur quoi repose la sécurité de RSA

Fonctions de hachage

Trois propriétés, pas une

La borne des anniversaires

L'effet d'avalanche

À quoi servent les empreintes

Signatures numériques

Le principe

Ce qu'une signature prouve, et ce qu'elle ne prouve pas

Là où les systèmes cassent vraiment

Synthèse

Exercices

Références

Module et indicatrice

Exposant privé

Chiffrement

Déchiffrement et vérification