Cryptographie : coder, chiffrer, signer

Coder, chiffrer, hacher

L'outillage arithmétique est complet : il peut maintenant servir. Avant d'en faire 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.

Chiffrement mono-alphabétique

Chaque symbole est remplacé par un autre, toujours le même. Le chiffre de César est le cas le plus simple : un décalage constant.

L'analyse de fréquence

En français, le $e$ représente environ 15 % des lettres, loin devant tous les autres. Un chiffrement mono-alphabétique déplace cette signature sans la détruire : la lettre la plus fréquente du texte chiffré est presque sûrement un $e$ chiffré.

Le chiffre de Vigenère répond à cette attaque en utilisant plusieurs alphabets, pilotés par un mot-clé : une même lettre claire devient des lettres chiffrées différentes selon sa position. Les fréquences sont lissées, mais l'attaque de Kasiski retrouve la longueur de la clé en repérant les motifs répétés, et ramène le problème à autant de chiffres de César.

Symétrique et asymétrique

RSA, pas à pas

La figure ci-dessous déroule ces quatre étapes. Cliquer sur chacune montre à quoi elle sert et, surtout, ce que devient sa valeur : publiée, gardée, ou détruite. C'est cette répartition qui fait toute la sécurité, et elle disparaît dans une liste à puces.

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

• $\varphi(N)$ est détruit. C'est la seule des cinq valeurs à ne finir ni dans la clé publique ni dans la privée. Elle est pourtant celle qui les relie : 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.

Pourquoi ça marche

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

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

Et le théorème d'Euler donne $M^{\varphi(N)} \equiv 1 \ [N]$, d'où $C^D \equiv M \times 1^k \equiv M \ [N]$. ∎

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 y passe : la division euclidienne pour obtenir $D$, les congruences pour réduire, l'indicatrice d'Euler pour faire disparaître le facteur parasite. Rien n'y est superflu, et retirer une seule des quatre étapes de la génération casse la démonstration.

Le second parchemin

Un message a été intercepté : une liste de blocs chiffrés avec la clé publique jouet $N = 3233$, $E = 17$. Le programme ci-dessous mène l'attaque de bout en bout : factoriser $N$, en déduire $D$, déchiffrer.

Confidentialité, authentification, intégrité

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

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.

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.

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 est chiffré, c'est son empreinte. Personne d'autre qu'Alice ne peut produire cette signature, mais tout le monde peut la vérifier, puisque la clé publique est publique.

À calculer soi-même

RSA se comprend en le faisant tourner une fois sur de petits nombres. Toutes les étapes tiennent dans un bloc, et aucune ne demande autre chose qu'une division.

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 ce chiffrement se casse pourtant en quelques minutes sur un texte d'une page. 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.

Où la démarche dérape

Un calcul de clé mené sans faute, sur une valeur de $\varphi$ qui ne tient pas.

Vérification

Exercices type

La méthode

1. Nommer la propriété visée avant de choisir un outil : confidentialité, authentification ou intégrité. Chacune appelle une opération différente, et les confondre produit un système qui ne protège rien de ce qu'on croyait.
2. Pour RSA, dérouler les quatre étapes dans l'ordre : $N$, puis $\varphi(N)$, puis l'exposant privé, puis le déchiffrement.
3. Contrôler que $E \times D \equiv 1 \pmod{\varphi(N)}$ avant d'aller plus loin. Une erreur ici rend tout le reste faux sans qu'aucun calcul ne proteste.
4. 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.
5. Vérifier par l'aller-retour : rechiffrer le message obtenu et comparer au chiffré de départ.
6. Ne jamais employer RSA nu, ni conclure qu'un chiffrement est solide parce que son espace de clés est grand.

Synthèse

• Coder ≠ chiffrer ≠ hacher : réversible sans clé, réversible avec la clé, irréversible et sans clé.
• Un chiffrement mono-alphabétique tombe par l'analyse de fréquence, quelle que soit la taille de son espace de clés. La solidité ne se mesure pas au nombre de clés.
• Kerckhoffs : la sécurité repose sur la clé, jamais sur le secret de l'algorithme.
• Le symétrique est rapide et pose un problème d'échange de clé ; l'asymétrique résout l'échange et coûte cher. Les protocoles réels emploient les deux.
• RSA : $C = M^E \bmod N$ et $M = C^D \bmod N$, avec $ED \equiv 1 \pmod{\varphi(N)}$. C'est le théorème d'Euler qui fait retomber le déchiffrement sur le message.
• RSA est déterministe, donc à ne jamais employer sans remplissage aléatoire.
• Confidentialité : clé publique du destinataire. Authentification : clé privée de l'expéditeur. Intégrité : hachage.
• Toute la sécurité tient à ce que calculer $\varphi(N)$ exige de factoriser $N$, ce que personne ne sait faire vite.

Et ensuite

Le chiffrement protège contre un adversaire. Il ne protège contre rien d'autre, et surtout pas contre le bruit : un bit retourné par une ligne défaillante donne un déchiffrement faux sans que rien ne le signale. Codes correcteurs d'erreurs traite ce second problème avec la même arithmétique, et une intention opposée.