Cryptographie : coder, chiffrer, signer

Un compteur qui parle à un serveur qu'il n'a jamais rencontré.

Chaque nuit, un compteur d'eau connecté envoie son relevé au serveur du distributeur, par une liaison radio que n'importe qui, à portée d'antenne, peut écouter. Trois exigences pèsent sur ce relevé : personne d'autre que le distributeur ne doit le lire, le serveur doit savoir qu'il vient bien de ce compteur, et rien ne doit avoir été modifié en route. Or le compteur et le serveur n'ont aucun secret en commun : le constructeur fabrique les compteurs à la chaîne, par milliers, et personne n'a convenu d'un mot de passe à la pose. Comment tenir les trois exigences ?

Ce chapitre construit la réponse pièce par pièce. Il sépare d'abord des mots que l'usage confond, montre pourquoi un chiffrement qui paraît solide tombe en moins d'une heure, puis déroule RSA de bout en bout sur de petits nombres, à la main, avec les outils du chapitre précédent. La réponse au compteur vient à la fin, dans la section « Retour au compteur ».

Travailler seul, section par section

Chaque notion suit le même chemin : un encadré de définition ou de rappel de cours (la notion, sa formule, un petit exemple résolu), puis un calcul à faire à la main, dans un cadre qui juge la réponse dès qu'elle est validée et où un indice s'ouvre à la demande. Les quelques blocs Python ne servent qu'à vérifier à la machine un calcul déjà fait à la main. Les questions à déplier se travaillent par écrit, en une ou deux phrases, avant d'ouvrir la réponse.

Coder, chiffrer, hacher

Avant de construire un système de chiffrement, il faut lever une confusion de vocabulaire qui fausse ensuite tous les raisonnements de sécurité. Trois mots qu'on confond, trois opérations différentes. Le quatrième verbe du titre, signer, les emploie toutes les trois : il vient en dernière section.

Les distinguer

Coder (ou encoder) : représenter une information dans un autre alphabet. ASCII, UTF-8, base64. Réversible, sans secret : ce n'est pas de la sécurité. Le base64, par exemple, écrit chaque groupe de trois octets avec quatre caractères pris parmi 64 (les lettres, les chiffres, + et /) : il rallonge le texte d'un tiers et le rend illisible à l'œil, mais n'importe qui le défait.

Chiffrer : rendre une information incompréhensible sans la clé. Réversible avec la clé. Les cryptographes disent « chiffrer », jamais « crypter » ; « décrypter », c'est lire sans la clé, donc casser.

Hacher : calculer, à partir d'un contenu de taille quelconque, une empreinte de taille fixe : 256 bits pour SHA-256, écrits en 64 chiffres hexadécimaux. Irréversible, et sans clé. Changer un seul caractère du contenu change toute l'empreinte, et personne ne sait fabriquer deux contenus de même empreinte : c'est ce qui la fait servir à l'intégrité. MD5 et SHA-1 ont perdu cette seconde propriété (des collisions ont été fabriquées en 2004 et en 2017) et ne doivent plus servir contre un adversaire.

Les mots de passe

Un site ne garde pas le mot de passe, mais son empreinte, qu'il compare à la connexion. Pas celle d'un SHA-256 seul : une carte graphique en calcule des milliards par seconde, et un mot de passe tiré d'un dictionnaire tombe aussitôt. On emploie une fonction volontairement lente (Argon2, scrypt ou bcrypt) et un sel, un nombre tiré au hasard pour chaque compte et haché avec le mot de passe, pour que deux comptes au même mot de passe n'aient pas la même empreinte. Le sel oblige en outre l'attaquant à recommencer son dictionnaire compte par compte, au lieu d'une seule fois pour toute la base.

Vérification rapideon peut se reprendre

Un automate transmet sa consigne en base64, « pour qu'elle ne se lise pas sur le réseau ». Qui peut la lire ?

Chiffrement mono-alphabétique

Chaque symbole est remplacé par un autre, toujours le même, d'après une seule table de correspondance : un seul « alphabet » chiffré, d'où le nom. Le chiffre de César en est le cas le plus simple.

Le chiffre de César

On numérote les lettres de 0 à 25 : a 0, b 1, c 2, d 3, e 4, f 5, g 6, h 7, i 8, j 9, k 10, l 11, m 12, n 13, o 14, p 15, q 16, r 17, s 18, t 19, u 20, v 21, w 22, x 23, y 24, z 25. La clé est un décalage $K$ compris entre 0 et 25, et chaque lettre avance de $K$ rangs, en repartant de a après z :

\text{rang chiffré} = (\text{rang clair} + K) \bmod 26 \qquad \text{rang clair} = (\text{rang chiffré} - K) \bmod 26

Les espaces et les chiffres ne sont pas touchés.

Exemple résolu, avec $K = 3$  : la consigne purger la zone devient sxujhu od crqh. Le p (15) devient s (18), le u (20) devient x (23), et le z (25) devient c, car $25 + 3 = 28$ et $28 \bmod 26 = 2$ . Pour déchiffrer, on recule : le c (2) redonne $(2 - 3) \bmod 26$ , et le reste de $-1$ dans la division par 26 vaut 25, puisque $-1 = (-1) \times 26 + 25$ . On retrouve bien le z.

Le chiffrement affine généralise César : le rang chiffré vaut $(a \times \text{rang clair} + b) \bmod 26$ . Il ne se déchiffre que si $a$ est premier avec 26, c'est-à-dire inversible modulo 26 au sens du chapitre précédent ; il reste mono-alphabétique, et tombe de la même façon.

Sans la clé, un César n'offre que 26 possibilités, et les essayer toutes est immédiat. Encore faut-il reconnaître le bon clair. Sur un texte, c'est évident, puisqu'un seul candidat se lit ; sur un mot très court, non : orw se lit lot avec $K = 3$ , et fin avec $K = 9$ , deux mots tout aussi plausibles. Seul le contexte départage.

Pourquoi ce chiffrement ne vaut rien

L'espace des clés de César compte 26 possibilités : les essayer toutes prend une microseconde. Une substitution quelconque, où une table tirée au hasard associe à chaque lettre une autre lettre, offre $26!$ clés, plus de $4 \times 10^{26}$ , et aucune machine ne les essaiera toutes. Elle tombe pourtant en quelques secondes sur machine, et en moins d'une heure à la main sur une page de texte, parce qu'elle préserve les fréquences.

L'analyse de fréquence

En français, le e est de loin la lettre la plus fréquente : environ 15 % des lettres d'un texte accentué, davantage quand les accents sont retirés et que é, è et ê s'écrivent e. Un chiffrement mono-alphabétique déplace cette signature sans la détruire : chaque lettre claire garde son effectif, sous un autre nom.

Soit la phrase, écrite sans accents : « la cryptographie moderne ne repose pas sur le secret de la methode mais sur le secret de la cle car une methode publique est etudiee par tous et ses faiblesses finissent par etre connues de tous ». Le e y compte 34 lettres sur 159, soit 21 %. Chiffrée par César avec $K = 7$ , voici ce que deviennent ses six lettres les plus fréquentes.

Lettre claire	e	s	r	t	a	u
Effectif	34	18	12	12	10	9
Lettre chiffrée ( $K = 7$ )	l	z	y	a	h	b

L'attaquant ne voit que la dernière ligne, et constate que l domine, avec 34 occurrences. Il parie que l cache le e, et la clé vaut l'écart des rangs : $11 - 4 = 7$ . Une seule lettre identifiée livre toute la clé, sans en essayer aucune. Le bloc ci-dessous vérifie à la machine le tableau et la clé.

main.py

Sortie

>_ Prêt à exécuter…

Un décalage se casse avec une seule lettre. Une substitution quelconque demande plus de patience, mais pas plus de calcul. Les fréquences désignent le $e$ , puis le groupe serré des $s$ , $a$ , $i$ , $t$ , $n$  ; les mots courts (le, la, de, et) départagent les hésitations, et chaque lettre trouvée rend les mots voisins plus lisibles. L'attaquant résout ainsi vingt-six petits problèmes l'un après l'autre au lieu d'un seul immense : c'est pour cela que les $26!$ clés ne le ralentissent pas.

Le César et l'analyse de fréquence, à la main

1.
Avec la clé $K = 3$ , quelle lettre claire se cache derrière la lettre chiffrée b ? Donner son rang, de 0 pour a à 25 pour z.
2.
Dans un long relevé chiffré par César, la lettre la plus fréquente est p. En pariant qu'elle cache le e, combien vaut la clé $K$  ?
3.
Avec cette clé, quel est le rang de la lettre claire cachée derrière c ?
4.
Combien de clés distinctes une substitution quelconque des 26 lettres offre-t-elle ? L'écrire en notation scientifique, par exemple 1,5e12 pour $1{,}5 \times 10^{12}$ .

La dernière réponse est celle qui trompe. Vingt-six factorielle dépasse quatre cents millions de milliards de milliards de clés, et la substitution se casse pourtant en moins d'une heure sur une page de texte. La taille de l'espace des clés ne mesure pas la solidité d'un chiffrement : elle ne mesure que le coût d'une recherche exhaustive, qui n'est pas l'attaque employée.

Plusieurs alphabets : Vigenère

Le chiffre de Vigenère

Un mot-clé se répète le long du texte, et chacune de ses lettres donne un décalage : a décale de 0, b de 1, jusqu'à z qui décale de 25. Chaque lettre claire est décalée par la lettre de clé qui lui fait face. Plusieurs alphabets servent ainsi à tour de rôle : le chiffrement est polyalphabétique.

Exemple résolu. Avec le mot-clé cle, qui décale de 2, 11 et 4 rangs à tour de rôle, vanne devient xlrpp : le v (21) devient x (23), le a (0) devient l (11), le premier n (13) devient r (17), le second n devient p (15), et le e (4) devient p lui aussi. Une même lettre claire donne deux lettres chiffrées, deux lettres claires donnent la même : le compte des lettres ne désigne plus rien.

L'attaque de Kasiski retrouve pourtant la longueur $L$ du mot-clé. Un même groupe de lettres, chiffré au même endroit de la clé, produit le même groupe chiffré, et l'écart entre deux répétitions est un multiple de $L$ . Les lettres de rangs $1$ , $L + 1$ , $2L + 1$ … ont alors toutes subi le même décalage, et le problème se ramène à $L$ chiffres de César, cassés un par un par l'analyse de fréquence.

Vérification rapideon peut se reprendre

1.Avec le chiffre de Vigenère et le mot-clé « cle », que devient le clair « eee » ?

2.Pourquoi un chiffrement mono-alphabétique tombe-t-il malgré ses 26 factorielle clés ?

Symétrique et asymétrique

Deux familles

Symétrique : la même clé chiffre et déchiffre. Rapide, adapté aux gros volumes : AES, le standard actuel, chiffre de l'ordre d'un gigaoctet par seconde. Problème : il faut avoir transmis la clé au préalable, par un canal sûr.

Asymétrique : deux clés liées mathématiquement. La clé publique chiffre et se diffuse à tous ; la clé privée déchiffre et ne quitte jamais son propriétaire. Standard historique : RSA. Lent, puisqu'une seule opération demande des milliers de multiplications de nombres de plusieurs centaines de chiffres, mais il résout le problème de l'échange de clé : pour écrire à quelqu'un, il suffit de sa clé publique, qui peut circuler en clair.

En pratique, les deux ensemble. Une connexion HTTPS commence par de l'asymétrique pour convenir d'une clé de session, puis bascule en symétrique pour toute la suite. On paie le coût du calcul lent une seule fois, au début, et l'on obtient la rapidité d'AES. Aujourd'hui, la clé de session se convient le plus souvent par un échange de Diffie-Hellman, un autre procédé asymétrique que ce chapitre ne détaille pas, et RSA sert surtout à signer le certificat du site. Aucun secret n'a dû être partagé à l'avance : c'est la première pièce de la réponse au compteur de l'ouverture.

Le principe de Kerckhoffs

La sécurité d'un système ne doit reposer que sur le secret de la clé, jamais sur celui de l'algorithme. AES et RSA sont entièrement publics, spécifiés, et attaqués par la communauté depuis des décennies : c'est ce qui fonde la confiance qu'on leur accorde. Un algorithme secret est un algorithme que personne n'a pu casser publiquement, ce qui n'est pas la même chose.

Vérification rapideon peut se reprendre

Que dit le principe de Kerckhoffs ?

RSA, pas à pas

RSA emploie six outils du chapitre précédent. Les voici rappelés, sur les nombres mêmes de l'exemple qui suit : le reste de la section s'en sert sans y revenir.

Rappel de cours : ce que RSA emprunte au chapitre précédent

La congruence. $a \equiv b \ [n]$ , «  $a$ est congru à $b$ modulo $n$  », signifie que $a$ et $b$ ont le même reste dans la division par $n$  ; $a \bmod n$ désigne ce reste, compris entre 0 et $n - 1$ . Exemple : $7657 = 2 \times 3828 + 1$ , donc $7657 \bmod 3828 = 1$ et $7657 \equiv 1 \ [3828]$ . Dans un produit, on peut remplacer chaque facteur par son reste à chaque étape sans changer le reste final.

L'inverse modulaire. L'inverse de $a$ modulo $n$ est l'entier $x$ de $[0 ; n - 1]$ tel que $a x \equiv 1 \ [n]$ . Il existe si et seulement si $\operatorname{pgcd}(a, n) = 1$ .

Euclide étendu le calcule. La descente divise jusqu'au reste 1 ; la remontée réécrit ce 1 comme une combinaison des deux nombres ; le coefficient du nombre à inverser, ramené dans $[0 ; n - 1]$ , est l'inverse. Sur 3828 et 13 :

$3828 = 13 \times 294 + 6$ , puis $13 = 6 \times 2 + 1$  ;

$1 = 13 - 2 \times 6 = 13 - 2 \times (3828 - 294 \times 13) = 589 \times 13 - 2 \times 3828$ .

Le coefficient de 13 vaut 589 : c'est l'inverse de 13 modulo 3828. Quand ce coefficient sort négatif, on lui ajoute $n$ .

L'indicatrice d'Euler $\varphi(n)$ compte les entiers de 1 à $n$ premiers avec $n$ . Pour deux premiers distincts $P$ et $Q$ , $\varphi(PQ) = (P - 1)(Q - 1)$ , jamais $PQ - 1$  : $\varphi(15) = 2 \times 4 = 8$ , et non 14.

Le théorème d'Euler. Si $\operatorname{pgcd}(a, n) = 1$ , alors $a^{\varphi(n)} \equiv 1 \ [n]$ . Exemple : $2^{8} = 256 = 17 \times 15 + 1$ , donc $2^{8} \equiv 1 \ [15]$ .

L'exponentiation rapide. Écrire l'exposant en somme de puissances de 2, élever au carré en réduisant à chaque fois, puis multiplier les carrés retenus. Pour $65^{13}$ modulo 3953, avec $13 = 8 + 4 + 1$  :

Puissance	Calcul	Reste modulo 3953
$65^{2}$	$4225 = 3953 + 272$	272
$65^{4}$	$272^2 = 73\,984 = 18 \times 3953 + 2830$	2830
$65^{8}$	$2830^2 = 8\,008\,900 = 2026 \times 3953 + 122$	122
$65^{12} = 65^{8} \times 65^{4}$	$122 \times 2830 = 345\,260 = 87 \times 3953 + 1349$	1349
$65^{13} = 65^{12} \times 65$	$1349 \times 65 = 87\,685 = 22 \times 3953 + 719$	719

Cinq multiplications, et aucun nombre de plus de sept chiffres, là où $65^{13}$ écrit en entier en compterait vingt-quatre.

L'algorithme complet

Génération des clés

Choisir deux grands premiers $P$ et $Q$ , et poser $N = PQ$ .
Calculer $\varphi(N) = (P - 1)(Q - 1)$ .
Choisir $E$ premier avec $\varphi(N)$ .
Calculer $D = E^{-1} \bmod \varphi(N)$ par Euclide étendu.

Clé publique : $(N, E)$ . Clé privée : $(N, D)$ . On détruit $\varphi(N)$ , et $P$ et $Q$ ne sont jamais publiés. (En pratique, les logiciels gardent souvent $P$ et $Q$ dans le fichier de la clé privée, aussi secrets qu'elle, pour accélérer le déchiffrement.)

Chiffrement : $C = M^E \bmod N$ Déchiffrement : $M = C^D \bmod N$

Les deux dernières formules se lisent à voix haute : le chiffré est le message élevé à la puissance $E$ , modulo $N$  ; le message est le chiffré élevé à la puissance $D$ , modulo $N$ . C'est la même opération dans les deux sens, avec deux exposants différents, et c'est l'exponentiation rapide qui l'exécute.

Le message $M$ est un nombre compris entre $0$ et $N - 1$  : le déchiffrement rend un reste modulo $N$ , et ne retrouve donc $M$ que s'il est plus petit que $N$ . Un texte devient une suite de tels nombres par un simple codage, au sens de la première section : en ASCII, la lettre A vaut 65, et c'est elle que chiffre l'exemple qui suit.

Générer la clé jouet, étape par étape

1. Deux premiers. $P = 59$ et $Q = 67$ , d'où $N = 59 \times 67 = 3953$ . C'est 3953, avec l'exposant public, qui sera publié : 59 et 67 ne le seront jamais.

2. L'indicatrice. $\varphi(3953) = (59 - 1)(67 - 1) = 58 \times 66 = 3828$ . Le calcul est immédiat parce qu'on connaît la factorisation ; sans elle il faudrait la retrouver, et c'est précisément ce qui est hors de portée sur de vrais nombres.

3. L'exposant public. $E = 13$ . Il doit être premier avec 3828 : la descente d'Euclide du rappel de cours aboutit au reste 1, donc $\operatorname{pgcd}(3828, 13) = 1$ .

4. L'exposant privé. $D = 13^{-1} \bmod 3828$ , le coefficient de 13 trouvé par la remontée : $D = 589$ . Contrôle : $13 \times 589 = 7657 = 2 \times 3828 + 1$ , donc bien $13 \times 589 \equiv 1 \ [3828]$ .

Clé publique $(3953 ; 13)$ , clé privée $(3953 ; 589)$ . On détruit 3828.

Un tour complet sur un message. Avec $M = 65$  : le chiffré vaut $65^{13} \bmod 3953 = 719$ , calculé dans le rappel de cours en cinq multiplications, et le déchiffré $719^{589} \bmod 3953 = 65$ . La seconde puissance est énorme, $719^{589}$ compte 1 683 chiffres, mais l'exponentiation rapide la calcule en treize multiplications : $589 = 512 + 64 + 8 + 4 + 1$ , soit neuf mises au carré et quatre produits.

Le bloc ci-dessous vérifie à la machine ces calculs faits à la main : pow(a, -1, n) rend l'inverse de $a$ modulo $n$ , et pow(a, k, n) la puissance $a^k$ réduite modulo $n$ , par exponentiation rapide.

main.py

Sortie

>_ Prêt à exécuter…

La figure ci-dessous déroule ces quatre étapes sur la clé jouet, et suit chaque valeur jusqu'à son sort final.

PQEmessage

message65^13 mod 3953clé publiquechiffré719^589 mod 3953clé privéedéchiffré65

Les deux puissances sont énormes et pourtant instantanées : pour chiffrer, l'exponentiation rapide remplace 12 multiplications à la suite par 3 mises au carré et 2 multiplications.

Ce qui circule : N = 3953 et E = 13. Pour en tirer D, il faut φ(N) ; pour φ(N), il faut P et Q ; pour P et Q, il faut factoriser N.

Ici, 58 divisions suffisent, un ordinateur les fait en une fraction de seconde. Sur une clé réelle, N compte plus de 600 chiffres et c'est cette seule étape qui devient impossible : toutes les autres restent aussi rapides qu'ici.

La clé jouet du cours, étape par étape, et un aller-retour sur le message 65.

À manipuler

Le sort de chaque valeur, publique, privée ou détruite, s'affiche en face de son étape ; cliquer sur une étape ouvre, juste en dessous, ce à quoi elle sert. C'est cette répartition qui fait toute la sécurité.

Saisir ensuite $E = 11$  : il est premier, et pourtant il divise $3828 = 2^2 \times 3 \times 11 \times 29$ . La troisième étape affiche un pgcd de 11 au lieu de 1, et la quatrième devient impossible, faute d'inverse. Reprendre avec $E = 5$ , qui convient : la clé privée passe de 589 à 2297, sans ressemblance avec la précédente. Sur 3828 et 5, la remontée d'Euclide donne $1 = 2 \times 3828 - 1531 \times 5$  : le coefficient de 5 sort négatif, et $-1531 + 3828 = 2297$ .

Trois choses se lisent sur cette figure, et chacune se retient mieux qu'une phrase de conclusion.

$\varphi(N)$ est détruit. Des quatre valeurs que suit la figure, c'est la seule à ne finir ni dans la clé publique ni dans la privée. Elle est pourtant celle qui relie les deux clés : qui la connaît calcule $D$ en une ligne.
$E$ doit être premier avec $\varphi(N)$ , sinon il n'a pas d'inverse et la quatrième étape n'a rien à calculer. Ce n'est pas une précaution, c'est une condition d'existence.
L'aller-retour referme la boucle parce que $ED \equiv 1 \ [\varphi(N)]$ , et pour aucune autre raison. Changer $D$ d'une unité suffit à ne plus rien retrouver.

À la main, sur une autre clé

Le même chemin, sur une clé assez petite pour que chaque calcul tienne sur une calculatrice : le rappel de cours et l'exemple ci-dessus en donnent tous les gestes.

Une clé RSA à la main

1.
Deux premiers valent 11 et 13. Combien vaut le module $N$  ?
2.
Combien vaut $\varphi(N)$  ?
3.
L'exposant public vaut 7, et la descente d'Euclide atteint le reste 1 dès la première division : $120 = 7 \times 17 + 1$ . Combien vaut l'exposant privé $D$ , entre 1 et 119 ?
4.
Un relevé vaut $M = 5$ . Combien vaut le chiffré $C = 5^{7} \bmod 143$  ?
5.
Un autre relevé arrive chiffré : $C = 2$ . Combien vaut le relevé clair, $2^{103} \bmod 143$  ?

Pourquoi ça marche

Par construction $ED \equiv 1 \ [\varphi(N)]$ , donc $ED = 1 + k\varphi(N)$ pour un entier $k$ . Alors :

$C^D \equiv (M^E)^D = M^{ED} = M^{1 + k\varphi(N)} = M \times \left(M^{\varphi(N)}\right)^k \ [N]$

En clair : déchiffrer revient à élever $M$ à la puissance $ED$ , c'est-à-dire à multiplier $M$ par $k$ « tours complets » $M^{\varphi(N)}$ . Sur la clé du calcul précédent, $7 \times 103 = 721 = 1 + 6 \times 120$  : le déchiffrement multiplie le message par six tours complets. Le premier signe est une congruence et non une égalité, parce que $C$ a déjà été réduit modulo $N$ .

Et le théorème d'Euler dit que chaque tour complet vaut 1 : $M^{\varphi(N)} \equiv 1 \ [N]$ , d'où $C^D \equiv M \times 1^k \equiv M \ [N]$ . Comme $M$ est compris entre $0$ et $N - 1$ , ce reste est $M$ lui-même. ∎

Le théorème d'Euler suppose $M$ premier avec $N$ , c'est-à-dire non multiple de $P$ ni de $Q$ . C'est le cas de presque tous les messages, et le cas restant fonctionne aussi, par un raisonnement séparé modulo $P$ puis modulo $Q$ .

Trois lignes, et tout le chapitre précédent y passe : Euclide étendu pour obtenir $D$ , les congruences pour réduire, le théorème d'Euler pour ramener à 1 le facteur $\left(M^{\varphi(N)}\right)^k$ qui encombre le résultat. Rien n'y est superflu, et retirer une seule des quatre étapes de la génération casse la démonstration.

Où est le secret. Tout le monde connaît $N$ et $E$ . Pour trouver $D$ , il faut $\varphi(N)$  ; pour $\varphi(N)$ , il faut $P$ et $Q$  ; pour $P$ et $Q$ , il faut factoriser $N$ . Qui factorise $N$ lit tout : c'est le maillon dont dépend la clé. La réciproque ne vaut pas, et la suite le montre : un RSA mal employé se lit sans rien factoriser.

Ces nombres sont bien trop petits

Un $N$ de quatre chiffres se factorise de tête, ou presque : il suffit de tester les diviseurs jusqu'à $\sqrt{3953} \approx 62{,}9$ , et le premier qui tombe juste est 59 : dix-sept divisions si l'on ne teste que les nombres premiers, cinquante-huit si l'on teste tous les entiers à partir de 2. La clé jouet sert à voir le mécanisme, jamais à protéger quoi que ce soit.

Une clé réelle de 2048 bits emploie $P$ et $Q$ d'environ 309 chiffres chacun, pour un $N$ de 617 chiffres. Toutes les étapes ci-dessus restent les mêmes, et s'exécutent encore en une fraction de seconde : c'est la seule étape absente, la factorisation, qui devient hors de portée.

Bits de clé, bits de sécurité

La sécurité se mesure en bits : une clé de $k$ bits offre $2^k$ possibilités, et chaque bit ajouté double le travail d'une recherche exhaustive. Une clé de 56 bits (l'ancien DES) est tombée par recherche exhaustive en moins d'une journée dès 1999 ; AES-128 et AES-256 sont hors d'atteinte de toute recherche exhaustive concevable.

Pour RSA, ce n'est pas l'attaque exhaustive qui compte mais la factorisation, bien plus rapide : un module de 2048 bits n'offre que 112 bits de sécurité, et il en faut 3072 pour égaler AES-128. La recommandation est passée de 1024 à 2048 bits, puis à 3072 au-delà de 2030. L'étape suivante n'est pas une clé plus longue : un ordinateur quantique assez grand factoriserait n'importe quel module, et le NIST a normalisé en 2024 des remplaçants post-quantiques (ML-KEM pour convenir d'une clé, ML-DSA pour signer), que les navigateurs emploient déjà, associés aux procédés actuels.

Un nombre de $k$ bits s'écrit avec environ $0{,}301 \times k$ chiffres décimaux, arrondi à l'entier supérieur, puisque $2^{10} = 1024 \approx 10^3$  : dix bits valent à peu près trois chiffres. Exemple : 3953 est compris entre $2^{11} = 2048$ et $2^{12} = 4096$ , c'est un nombre de 12 bits, et $12 \times 0{,}301 \approx 3{,}6$ annonce bien quatre chiffres.

Des bits aux chiffres

1.
Un module RSA de 2048 bits s'écrit avec combien de chiffres décimaux ?
2.
Passer d'une clé de 56 bits à une clé de 64 bits multiplie le travail d'une recherche exhaustive par combien ?

RSA nu est déterministe

La barrière d'un dépôt reçoit à distance un seul ordre à la fois : 2 pour ouvrir, 3 pour fermer. Le poste de garde chiffre l'ordre avec la clé publique de la barrière, la clé du cours $(3953 ; 13)$ , et l'envoie tel quel. Un espion écoute la liaison. Il ne sait pas factoriser $N$ , comme sur une clé réelle, et n'en a pas besoin.

Rappel de cours : chiffrer est à la portée de tous

Chiffrer avec RSA, c'est calculer $C = M^E \bmod N$ avec la seule clé publique, que tout le monde connaît. Employé seul, le calcul est déterministe : un même message donne toujours le même chiffré. Exemple : sous la clé du cours, 65 se chiffre en 719, aujourd'hui, demain, et pour quiconque refait le calcul.

L'espion qui ne casse rien

1.
Combien vaut le chiffré de l'ordre d'ouvrir, $2^{13} \bmod 3953$  ?
2.
L'espion intercepte le chiffré 1264. Quel ordre cache-t-il, 2 ou 3 ?

Ce RSA-là est cassé, et pour une raison instructive

L'espion n'a rien factorisé : il a chiffré les deux ordres possibles avec la clé publique, comme n'importe qui peut le faire, et comparé. RSA employé seul est déterministe, et tout message pris dans un petit ensemble (un ordre, un montant, une réponse par oui ou non) se lit de cette façon. La même faiblesse frappe un texte chiffré caractère par caractère : la même lettre donne toujours le même bloc, et l'on retombe sur un chiffrement mono-alphabétique, que l'analyse de fréquence casse sans jamais factoriser $N$ .

Le vrai RSA ne chiffre jamais le texte lui-même, seulement une clé de session de quelques dizaines d'octets, complétée jusqu'à la taille de $N$ par un remplissage aléatoire (OAEP) : deux chiffrements du même message donnent alors deux résultats différents. Un algorithme correct mal employé ne protège rien.

Vérification rapideon peut se reprendre

1.Sur quoi repose la sécurité de RSA ?

2.Pourquoi calcule-t-on les puissances par exponentiation rapide ?

3.Que devient φ(N) une fois la clé générée ?

Confidentialité, authentification, intégrité

Chiffrer ne répond qu'à une question sur trois.

Trois propriétés distinctes

Confidentialité : personne d'autre ne peut lire. Chiffrer avec la clé publique du destinataire : lui seul possède la privée qui déchiffre.

Authentification : le destinataire sait qui a écrit. C'est la signature : l'expéditeur applique sa clé privée à l'empreinte du message, et n'importe qui vérifie avec sa clé publique. Avec RSA, signer est le même calcul que déchiffrer (une puissance $D$ modulo $N$ ), et vérifier le même que chiffrer (une puissance $E$ ). Ce n'est pourtant pas chiffrer : la clé publique, que tout le monde possède, défait l'opération. Une signature ne cache rien, elle prouve qui l'a produite.

Intégrité : le message n'a pas été modifié. C'est le rôle du hachage : le destinataire recalcule l'empreinte du message reçu et la compare à l'empreinte de référence. Contre une erreur de transmission, cela suffit. Contre un adversaire, non : le hachage est public et sans clé, et qui modifie le message recalcule sans peine l'empreinte qui va avec. L'empreinte de référence doit donc être hors de sa portée : signée par l'expéditeur, calculée avec une clé secrète partagée (un code d'authentification), ou publiée par un autre canal, comme celle qu'un éditeur affiche sur son site à côté d'un fichier à télécharger.

Les deux premières se confondent tant qu'on n'a pas vu quelle clé sert à quoi, et dans quel sens. Les deux schémas ci-dessous se lisent en trois secondes et règlent la question.

Pour la confidentialité, Alice chiffre avec la clé publique de Bob. Elle est publique : n'importe qui peut donc écrire à Bob, ce qui est voulu. Seul Bob possède la privée correspondante, donc lui seul peut lire.

Diagramme de séquence

Alice, pour lui-même : chiffre(message, clé publique de Bob).
Alice vers Bob : message chiffré. Note : interceptable, mais illisible.
Bob, pour lui-même : déchiffre(message chiffré, clé privée de Bob).

Ce qu'il faut regarder sur ce schéma : à qui appartiennent les deux clés citées. Les deux sont à Bob. Alice ne détient aucun secret, et pourtant elle chiffre : c'est là toute la nouveauté de l'asymétrique. Seule la flèche du milieu traverse le réseau, et ce qu'elle transporte ne se lit pas sans la clé privée, qui n'a jamais circulé.

Pour l'authentification, tout s'inverse. Alice signe avec sa propre clé privée, que personne d'autre ne possède. N'importe qui vérifie avec sa clé publique, et cette vérification prouve que le message vient bien d'elle.

Diagramme de séquence

Alice, pour lui-même : empreinte = hache(message).
Alice, pour lui-même : signature = signe(empreinte, clé privée d'Alice).
Alice vers Bob : message + signature.
Bob, pour lui-même : vérifie(signature, clé publique d'Alice).
Bob, pour lui-même : compare à hache(message reçu). Note : identiques, donc le message vient d'Alice et n'a pas changé.

Même lecture, et la comparaison des deux schémas donne la règle : ici, les deux clés citées appartiennent à Alice, l'expéditrice. Le message lui-même circule en clair ; ce qui l'accompagne, c'est son empreinte signée, que tout le monde peut contrôler. Personne d'autre qu'Alice ne peut produire cette signature, mais tout le monde peut la vérifier, puisque la clé publique est publique.

La question qui tranche : à qui appartient la clé employée ?

Clé publique du destinataire : confidentialité. Beaucoup peuvent écrire, un seul peut lire.

Clé privée de l'expéditeur : authentification. Un seul peut signer, beaucoup peuvent vérifier, avec sa clé publique.

En pratique on fait les deux à la fois, en signant puis en chiffrant. Et l'on ne signe jamais le message entier, seulement son empreinte : c'est plus court, et cela apporte l'intégrité par la même opération, pourvu que personne ne sache fabriquer un second message de même empreinte.

L'intégrité contre le bruit

Le code-barres d'un produit (EAN-13) se termine par un chiffre de contrôle, choisi pour que la somme des treize chiffres, pondérés alternativement par 1 et par 3, soit un multiple de 10. Pour le code 376004512893, la somme pondérée des douze premiers chiffres vaut $3 + 21 + 6 + 0 + 0 + 12 + 5 + 3 + 2 + 24 + 9 + 9 = 94$  : le chiffre de contrôle est 6, qui complète à 100. Une erreur de lecture sur un seul chiffre change la somme, et la caisse refuse le code.

Mais qui veut changer le code recalcule le chiffre de contrôle qui va avec, en une ligne. Ces clés de contrôle, comme la somme de contrôle d'une trame réseau qu'étudie le chapitre suivant, détectent une altération accidentelle, pas celle d'un adversaire : c'est de l'intégrité contre le bruit, pas contre un attaquant.

Le bloc ci-dessous montre l'effet d'un seul caractère changé sur une empreinte SHA-256, qui ne se calcule pas à la main.

main.py

Sortie

>_ Prêt à exécuter…

Les deux empreintes n'ont que trois caractères sur 64 en commun au même rang, quand le hasard pur en donnerait quatre en moyenne, une chance sur seize par rang : rien ne relie les deux, et rien ne permet de remonter de l'empreinte au message.

Vérification rapideon peut se reprendre

1.Chiffrer avec la clé publique du destinataire assure…

2.Hacher un message assure…

3.Pour signer un message, quelle clé l'expéditeur emploie-t-il ?

Vérifier une signature, à la main

Rappel de cours : signer et vérifier avec RSA

Le signataire possède la clé privée $(N, D)$ , et tout le monde connaît sa clé publique $(N, E)$ . Pour une empreinte $h$ plus petite que $N$  :

s = h^{D} \bmod N \ \text{(signer, clé privée)} \qquad s^{E} \bmod N \overset{?}{=} h \ \text{(vérifier, clé publique)}

Le vérificateur recalcule lui-même l'empreinte $h$ du message reçu, élève la signature à la puissance $E$ modulo $N$ , et compare : s'il retrouve $h$ , la signature est acceptée ; sinon, elle est refusée.

Exemple résolu, sur la clé du cours $(3953 ; 13)$ . L'empreinte d'un relevé vaut 719, et le détenteur de $D = 589$ la signe : $719^{589} \bmod 3953 = 65$ , le calcul même du déchiffrement de l'exemple. Le vérificateur calcule $65^{13} \bmod 3953$ , soit 719 par les cinq multiplications du rappel de cours : c'est l'empreinte, la signature est acceptée. Avec une signature inventée, 66, il trouverait $66^{13} \bmod 3953 = 535$ , et refuserait.

Vérifier la signature d'un compteur

1.
Un compteur signe ses relevés avec la clé privée $(143 ; 103)$ , et sa clé publique est $(143 ; 7)$ . Un relevé arrive avec la signature 3, et son empreinte, recalculée par le serveur, vaut 42. Combien vaut $3^{7} \bmod 143$  ?
2.
Le même relevé arrive une autre fois, avec la signature 4, inventée par quelqu'un qui n'a pas la clé privée. Combien vaut $4^{7} \bmod 143$  ?

Que prouve la vérification réussie, et que ne prouve-t-elle pas ?

Elle prouve deux choses d'un coup. Le relevé vient du détenteur de la clé privée, puisque personne d'autre ne sait produire une signature que la clé publique ramène à l'empreinte ; et il n'a pas changé, puisqu'un relevé modifié aurait une autre empreinte. Le serveur n'a employé pour cela que la clé publique du compteur.

Elle ne prouve pas que le relevé soit secret : il a circulé en clair. Ni qu'il soit récent : un relevé authentique de la veille, renvoyé tel quel, passe la même vérification.

Retour au compteur

Le compteur de l'ouverture a maintenant toutes ses pièces. Il ne partage aucun secret avec le serveur, mais deux clés publiques circulent sans risque : celle du serveur, que le constructeur a inscrite dans le compteur, et celle du compteur, que le distributeur a enregistrée à la pose. Chaque nuit :

Personne d'autre ne lit. Le compteur convient avec le serveur d'une clé de session, par un procédé asymétrique, puis chiffre le relevé avec AES et cette clé. Seul le serveur peut retrouver la clé de session, donc lire.
Le relevé vient de ce compteur. Le compteur calcule l'empreinte du relevé et la signe avec sa clé privée. Le serveur vérifie avec la clé publique du compteur, comme dans le calcul plus haut : la signature 3 du relevé d'empreinte 42 passait, la signature 4 non.
Rien n'a changé en route. La même signature y répond : un relevé modifié n'a plus la même empreinte, et la vérification échoue.

Reste à s'assurer que chaque clé publique appartient bien à celui qu'elle annonce : c'est le rôle des certificats, traités au chapitre Certificats, TLS et accès distants du parcours d'administration système.

Deux risques échappent à ces outils. Un relevé authentique de la veille, renvoyé tel quel, passe toutes les vérifications : contre ce rejeu, le compteur signe aussi la date et un numéro d'ordre, que le serveur refuse de voir revenir en arrière. Et une liaison radio défaillante qui retourne un bit fait rejeter le relevé entier, sans le réparer : c'est l'affaire du chapitre suivant.

La méthode

Nommer la propriété visée avant de choisir un outil : confidentialité, authentification ou intégrité. Puis nommer la clé : publique du destinataire pour chiffrer, privée de l'expéditeur pour signer, secrète partagée pour un code d'authentification. Les confondre produit un système qui ne protège rien de ce qu'on croyait.
Pour RSA, dérouler les quatre étapes de la génération dans l'ordre : $N$ , puis $\varphi(N)$ , puis le choix de $E$ premier avec $\varphi(N)$ , puis $D$ par Euclide étendu. Chiffrer et déchiffrer ne viennent qu'après.
Contrôler que $E \times D \equiv 1 \ [\varphi(N)]$ avant d'aller plus loin. Une erreur ici rend tout le reste faux sans qu'aucun calcul ne proteste.
Réduire à chaque étape dans un calcul modulaire, et procéder par carrés successifs pour une puissance. Ne jamais développer une grande puissance.
Vérifier par l'aller-retour : rechiffrer le message obtenu et comparer au chiffré de départ. Pour une signature, élever la signature à la puissance $E$ et comparer à l'empreinte recalculée.
Ne jamais employer RSA nu, ni conclure qu'un chiffrement est solide parce que son espace de clés est grand.

Mettre en pratique

Rappel de cours : ce qu'emploient ces questions

Le déterminisme. Sans remplissage, $C = M^E \bmod N$ donne toujours le même chiffré pour le même message : sous la clé du cours, l'ordre 2 se chiffre toujours en 286.

Quelle clé, pour quoi. La clé publique du destinataire chiffre, pour la confidentialité ; la clé privée de l'expéditeur signe, pour l'authentification ; sa clé publique vérifie.

Le coût. Une opération RSA sur des nombres de six cents chiffres demande des milliers de multiplications de grands entiers ; AES chiffre de l'ordre d'un gigaoctet par seconde.

L'empreinte. Irréversible et sans clé : n'importe qui peut hacher un candidat et comparer le résultat à une empreinte interceptée.

Factoriser. Le plus petit facteur de $N$ ne dépasse pas $\sqrt{N}$ , et $a^2 - b^2 = (a - b)(a + b)$ . Exemple : $72^2 - 5183 = 5184 - 5183 = 1 = 1^2$ , donc $5183 = (72 - 1)(72 + 1) = 71 \times 73$ .

Pourquoi RSA ne se chiffre-t-il jamais nu ?

Parce qu'il est déterministe : un même message donne toujours le même chiffré. Un attaquant qui soupçonne le contenu peut donc le chiffrer lui-même avec la clé publique, qui est publique, et comparer.

Sur un message pris dans un petit ensemble, un montant, une réponse par oui ou non, une date, la comparaison suffit à tout révéler sans rien casser. Le remplissage aléatoire ajouté avant le chiffrement rompt ce déterminisme, et c'est pour cela qu'il n'est jamais facultatif.

Clé publique ou clé privée : qu'est-ce que cela change ?

Tout, et les deux usages ne se remplacent pas.

Chiffrer avec la clé publique du destinataire assure la confidentialité : lui seul possède la clé privée qui défait l'opération.

Appliquer sa propre clé privée à l'empreinte, c'est signer : tout le monde vérifie avec la clé publique correspondante, et lui seul a pu produire la signature. Ce n'est pas un chiffrement, puisque rien n'est caché : c'est une preuve d'origine.

Pourquoi emploie-t-on un chiffrement symétrique alors que l'asymétrique suffirait ?

Pour une raison de coût. L'asymétrique est de plusieurs ordres de grandeur plus lent, parce qu'il repose sur des exponentiations modulaires sur des nombres de plusieurs centaines de chiffres.

Les protocoles réels emploient donc les deux : l'asymétrique pour convenir d'une clé de session tirée au hasard, le symétrique pour chiffrer les données avec cette clé. L'asymétrique résout le problème de l'échange de clé, et le symétrique fait le travail.

Un hachage protège-t-il la confidentialité ?

Non, et il n'est pas fait pour. Un hachage est irréversible et sans clé : le destinataire légitime ne peut pas plus le défaire que l'adversaire, donc il ne transmet rien qu'on puisse lire. Et sur un message pris dans un petit ensemble, n'importe qui hache chacun des candidats et compare, exactement comme pour RSA sans remplissage.

Ce qu'il garantit est l'intégrité : personne ne sait fabriquer deux contenus de même empreinte. Comparer l'empreinte de référence à l'empreinte recalculée dit si le contenu a été modifié, pourvu que cette référence soit elle-même hors d'atteinte, signée par exemple.

Que se passe-t-il si les deux premiers

P

Q

sont trop proches l'un de l'autre ?

Le module se factorise en un instant. Si $P$ et $Q$ sont voisins, ils encadrent $\sqrt{N}$ de près, et $N$ s'écrit $a^2 - b^2$ avec $a$ à peine plus grand que $\sqrt{N}$ et $b$ tout petit : c'est la méthode de Fermat. Sur $N = 9991$ , $\sqrt{9991} \approx 99{,}95$  ; on essaie $a = 100$ , et $100^2 - 9991 = 9 = 3^2$ , donc $9991 = (100 - 3)(100 + 3) = 97 \times 103$ , trouvé au premier essai, là où la division d'essai depuis 2 aurait demandé 96 divisions.

C'est pourquoi une génération de clé sérieuse n'impose pas seulement que les deux facteurs soient premiers et grands : elle impose aussi qu'ils soient éloignés. La difficulté de la factorisation n'est pas une propriété de la taille seule.

Coder, chiffrer, hacher

Chiffrement mono-alphabétique

L'analyse de fréquence

Plusieurs alphabets : Vigenère

Symétrique et asymétrique

RSA, pas à pas

À la main, sur une autre clé

Pourquoi ça marche

RSA nu est déterministe

Confidentialité, authentification, intégrité

Vérifier une signature, à la main

Retour au compteur

La méthode

Mettre en pratique

Dans la bibliothèque d'exercices

Plusieurs alphabets : Vigenère