Sécurité de Shannon et secret parfait

Avant de dérouler la mécanique des chiffrements concrets, il faut s’accorder sur ce que « chiffrer sûrement » veut dire. La question n’est pas anodine : cacher la clé ne suffit pas à cacher le message, et l’on peut parfaitement ignorer la clé tout en devinant l’essentiel du clair. C’est ce hiatus que la théorie de Shannon vient combler, en donnant au secret une définition qui ne doive plus rien à l’intuition.

Ce qu’un chiffrement doit cacher

Un chiffrement symétrique se donne par trois algorithmes : un générateur qui produit une clé « aléatoire » $k$, un algorithme de chiffrement $e$ et un algorithme de déchiffrement $d$. Comme $d=e^{-1}$, on peut supposer que la clé de chiffrement et celle de déchiffrement coïncident. On note $m$ le message clair et $c=e(k,m)$ le chiffré associé.

Le chiffrement poursuit alors trois objectifs emboîtés :

1. Cacher la clé. Nécessaire, mais insuffisant : même parfaitement dissimulée, une clé ne garantit pas que le chiffré résiste. Un chiffrement par substitution en témoigne — si le chiffré n’emploie pas toutes les lettres, l’analyse fréquentielle n’en révélera qu’une partie de la clé, ce qui suffit souvent.
2. Cacher le texte clair. L’adversaire peut vouloir décrypter un message précis sans retrouver la clé.
3. Cacher tout ce qui n’est pas déjà connu. C’est là l’exigence forte : rendre impossible la découverte du clair, intégralement, partiellement, ou de toute information connexe.

Cette dernière formulation mérite qu’on s’y arrête. En pratique, une part du message est presque toujours supposée connue de l’attaquant — un courriel commence par « Bonjour », un en-tête XML suit une grammaire fixe. La sécurité ne se juge donc pas dans l’absolu, mais relativement à ce que l’adversaire savait déjà.

Le formalisme de Shannon

On appelle cryptosystème la donnée de $(M,C,K,e,d)$ où $M$ est l’ensemble des messages, $C$ celui des chiffrés, $K$ celui des clés, et où les fonctions $e:M\times K\to C$, $d:C\times K\to M$ vérifient

$\forall k_e\in K,\exists k_d\in K,\forall m\in M,d(e(m,k_e),k_d)=m.$

Le chiffrement est symétrique si $k_e=k_d$, asymétrique si, connaissant $k_e$, déterminer $k_d$ est calculatoirement très difficile.

Tout l’apport de Shannon tient dans le passage au probabiliste. On voit $M$ comme une variable aléatoire dont la distribution encode l’information a priori de l’attaquant : savoir que le message commence par « Bonjour », c’est concentrer la masse de $M$ sur les clairs commençant ainsi. L’attaquant sait seulement que $k$ est tirée selon la loi sur $K$, que $m$ l’est selon la loi sur $M$, et que $e$ peut disposer de son propre aléa. En vertu du principe de Kerckhoffs, il connaît la distribution de $C:=e(K,M)$.

Sécurité au sens de Shannon

Un chiffrement est sûr au sens de Shannon si la connaissance du chiffré n’apporte aucune information sur le clair.

Le secret parfait

Formalisons cette exigence. La fonction de chiffrement induit sur $C$ la distribution

$\mathrm{Pr}(c)={\sum }_{e(m,k)=c}\mathrm{Pr}(m)\mathrm{Pr}(k),$

et la loi de Bayes relie la probabilité a posteriori à la probabilité a priori :

$\mathrm{Pr}(m\mid c)=\frac{\mathrm{Pr}(c\mid m)\mathrm{Pr}(m)}{\mathrm{Pr}(c)},\mathrm{Pr}(c\mid m)={\sum }_{k:e(m,k)=c}\mathrm{Pr}(k).$

Secret parfait

Un cryptosystème est à secret parfait si la réception d’un chiffré ne modifie en rien ce que l’on croit du clair : $\forall m\in M,\forall c\in C,\mathrm{Pr}(m\mid c)=\mathrm{Pr}(m).$

De façon équivalente, chaque chiffré est également probable quel que soit le clair d’origine :

$\forall m_1,m_2\in M,\forall c\in C,\mathrm{Pr}(c\mid m_1)=\mathrm{Pr}(c\mid m_2).$

Shannon a caractérisé exactement ces systèmes, sous l’hypothèse $|M|=|C|=|K|<\infty$ et $\mathrm{Pr}(m)>0$ pour tout $m$ :

Théorème (Shannon, 1949)

Le cryptosystème est à secret parfait si et seulement si

1. la loi des clés est uniforme, et
2. pour tout $m$, l’application ${\phi }_m:k\mapsto e(m,k)$ est une bijection de $K$ sur $C$.

Ces conditions imposent en particulier qu’il y ait au moins autant de clés que de messages : la perfection a un prix, et l’on va voir lequel.

Le masque jetable

Le seul chiffrement à secret parfait d’usage courant est le One-Time Pad, ou masque jetable. On y prend $M=K=\{0,1{\}}^n$, la clé étant tirée uniformément, et l’on pose simplement

$\mathrm{Enc}(k,m)=k\oplus m,\mathrm{Dec}(k,c)=k\oplus c,$

où $\oplus$ désigne le XOR bit à bit. Le déchiffrement n’est que le chiffrement réappliqué, l’opération étant involutive.

Théorème (One-Time Pad)

Le masque jetable est parfaitement sûr, à condition que la clé soit tirée uniformément et n’apparaisse qu’une seule fois.

La double contrainte est fatale à sa généralisation. Le théorème de Shannon impose $|K|\ge |M|$ : les clés sont donc au moins aussi longues que les messages, et, tirées uniformément, elles sont incompressibles. Réutiliser une clé ruine tout — deux chiffrés partageant leur masque révèlent le XOR de leurs clairs. C’est pourquoi le OTP, théoriquement inviolable, demeure impraticable dès que l’on veut chiffrer plus que l’on ne peut au préalable convoyer de clé.

De la perfection à la faisabilité

Ce constat d’impraticabilité est fécond : il déplace l’exigence. Puisqu’on ne peut offrir à un adversaire illimité une ignorance totale, on se contentera de la rendre inaccessible à un adversaire borné en temps et en mémoire. C’est le passage de la sécurité inconditionnelle à la sécurité calculatoire, où l’on ne demande plus que le déchiffrement soit impossible, mais qu’il soit infaisable dans les limites du calcul réaliste. Toute la cryptographie symétrique moderne et la cryptographie à clé publique se déploient dans ce cadre assoupli.