Chiffrement parfait et limites

Il existe un chiffrement inviolable. Pas « très difficile à casser » : inviolable, au sens où aucun adversaire, quelle que soit sa puissance de calcul et quel que soit le temps dont il dispose, ne peut tirer du chiffré la moindre information sur le clair. Il a été breveté par Gilbert Vernam en 1919 et sa sécurité a été démontrée par Claude Shannon en 1949.

Ce chapitre explique pourquoi la discipline ne s'est pas arrêtée là — et pourquoi ce théorème d'impossibilité, loin d'être une curiosité historique, est ce qui justifie tout le reste du cours.

Le masque jetable

Le procédé tient en une ligne. Soit un message $m$ de $n$ bits et une clé $k$ de $n$ bits tirée uniformément au hasard :

Le déchiffrement est le même calcul, puisque le XOR est son propre inverse. Trois conditions sont exigées, et le nom du procédé les résume : la clé doit être aussi longue que le message, parfaitement aléatoire, et jetée après un seul usage.

Le secret parfait, défini

Shannon donne à l'intuition « le chiffré n'apprend rien » une forme mathématique. Un chiffrement est parfaitement sûr si, pour tout message $m$ et tout chiffré $c$ :

Observer le chiffré ne modifie donc en rien la distribution des messages possibles. Une formulation équivalente, plus commode à manipuler : pour tous messages $m$ et $m'$ de même longueur, $\Pr[C = c \mid M = m] = \Pr[C = c \mid M = m']$ — le chiffré est également probable quel que soit le clair.

Le masque jetable vérifie cette définition, et la preuve tient en une phrase. Fixons $c$. Pour chaque message $m$, il existe exactement une clé qui produit ce chiffré, à savoir $k = m \oplus c$. Comme la clé est uniforme sur $2^n$ valeurs, on a $\Pr[C = c \mid M = m] = 2^{-n}$, indépendamment de $m$. Tous les clairs sont exactement aussi plausibles après observation qu'avant.

C'est une propriété d'un autre ordre que celles du reste du cours. Elle ne suppose aucune limite sur l'adversaire, ne repose sur aucun problème réputé difficile, et ne vieillira pas : ni les progrès de la cryptanalyse ni un ordinateur quantique n'y peuvent rien.

Le théorème de Shannon

La contrepartie est un théorème d'impossibilité, et il est sans échappatoire.

Théorème. Si un chiffrement est parfaitement sûr, alors $|\mathcal{K}| \geq |\mathcal{M}|$ : l'espace des clés est au moins aussi grand que l'espace des messages.

La démonstration se fait par l'absurde et mérite d'être suivie, car elle explique pourquoi la borne est incontournable. Supposons $|\mathcal{K}| < |\mathcal{M}|$ et fixons un chiffré $c$ de probabilité non nulle. Considérons l'ensemble des déchiffrements possibles de $c$ :

Cet ensemble contient au plus $|\mathcal{K}|$ éléments, donc strictement moins que $|\mathcal{M}|$. Il existe donc un message $m'$ qui n'y figure pas — aucune clé ne le transforme en $c$. On a alors $\Pr[M = m' \mid C = c] = 0$, alors que $\Pr[M = m'] > 0$. La définition du secret parfait est violée : le chiffré a appris à l'adversaire que le message n'était pas $m'$.

Le raisonnement est purement combinatoire. Aucune ingéniosité de conception ne le contourne : une clé plus courte que le message laisse forcément des messages inatteignables, et un message inatteignable est une information.

Le prix, et pourquoi on le refuse

La borne de Shannon rend le masque jetable impraticable dans presque tous les cas, pour une raison de logistique plus que de mathématiques : il faut acheminer une clé aussi longue que le message, par un canal sûr, avant de communiquer. Si un tel canal existe, il aurait pu transporter le message.

Le procédé n'a donc de sens que lorsque le canal sûr existe à un moment et pas à un autre : on remet des carnets de clés à un ambassadeur avant son départ, il les consomme sur place. La ligne directe Moscou-Washington l'a employé, ainsi que plusieurs services diplomatiques. Toutes ces utilisations partagent le même profil — un volume faible, une valeur très élevée, et une distribution physique préalable.

S'y ajoutent deux exigences que la pratique respecte mal. L'aléa doit être vraiment uniforme, ce qui suppose une source physique et non un générateur logiciel — le chapitre 13 montrera ce que coûtent les défaillances de ce côté. Et la clé ne doit jamais resservir.

Ce que coûte un masque réutilisé

Cette dernière condition n'est pas un raffinement. Si deux messages sont chiffrés avec le même masque :

La clé s'annule. L'adversaire obtient le XOR des deux clairs, et la redondance de la langue suffit à les séparer : on fait glisser un mot probable le long du résultat, et toute position qui produit du texte lisible dans l'autre message est la bonne. La méthode porte un nom, le crib dragging, et elle est mécanique.

L'histoire a fourni le cas d'école. Pendant la Seconde Guerre mondiale, la production soviétique de carnets de clés a dupliqué certaines pages ; les services américains, dans le cadre du projet Venona, ont exploité ces répétitions pendant des décennies et déchiffré plusieurs milliers de messages. Le chiffrement était parfait, sa mise en œuvre ne l'était pas — et la sécurité est l'intersection des deux, jamais leur réunion.

// Deux messages, un seul masque. C'est l'erreur de Venona.
//
// c1 = m1 ⊕ k     c2 = m2 ⊕ k
// donc  c1 ⊕ c2 = m1 ⊕ m2 : la clé a disparu.
//
// Il ne reste plus qu'à séparer m1 de m2, et le français s'en charge.

const xor = (a, b) => a.map((x, i) => x ^ b[i]);
const enOctets = (s) => [...s].map((c) => c.charCodeAt(0));
const enTexte = (o) => o.map((c) => String.fromCharCode(c)).join("");

// Les deux clairs, que vous n'êtes pas censé connaître.
const M1 = "rendez-vous a minuit sous le pont neuf";
const M2 = "le convoi part demain a huit heures.";
const n = Math.min(M1.length, M2.length);

// Un masque aléatoire, uniforme, secret — et réutilisé.
const cle = Array.from({ length: n }, () => Math.floor(Math.random() * 256));
const c1 = xor(enOctets(M1.slice(0, n)), cle);
const c2 = xor(enOctets(M2.slice(0, n)), cle);

// ── À VOUS ────────────────────────────────────────────────────────────────
// Vous ne disposez que de c1 et c2.
//
// 1. Calculez d = c1 ⊕ c2. Vérifiez qu'il ne dépend plus de la clé.
// 2. Faites glisser un mot probable (« crib ») le long de d : à chaque
//    position, d ⊕ crib donne ce que l'AUTRE message contiendrait si le crib
//    était là. Si le résultat est du texte lisible, la position est la bonne.
// 3. Le mot " le " est un bon candidat en français.

const d = []; // à compléter

function essayer(crib, position) {
  // à compléter : renvoyer le fragment de l'autre message
  return "";
}

// Testez toutes les positions et affichez celles qui donnent du lisible.
const lisible = (s) => [...s].every((c) => /[a-z .,'-]/.test(c));

for (let p = 0; p + 4 <= n; p++) {
  const fragment = essayer(" le ", p);
  if (fragment && lisible(fragment)) console.log(p, JSON.stringify(fragment));
}

Ce qui survit

Renoncer au secret parfait, ce n'est pas renoncer au masque : c'est renoncer à ce que la suite masquante soit vraiment aléatoire. Un chiffrement par flot engendre, à partir d'une clé courte, une suite pseudo-aléatoire aussi longue qu'il faut, et l'applique par XOR exactement comme Vernam. La sécurité devient calculatoire — elle vaut ce que vaut le générateur — mais le problème logistique disparaît. C'est le chapitre 5.

L'équation $c_1 \oplus c_2 = m_1 \oplus m_2$, elle, ne disparaît pas. Elle se déplace. Sous le nom de « réutilisation de nonce », c'est aujourd'hui l'une des erreurs les plus coûteuses de la cryptographie appliquée : elle casse ChaCha20 au chapitre 5, et en mode GCM au chapitre 8 elle fait plus que révéler les clairs, puisqu'elle compromet aussi la clé d'authentification et permet de forger des messages.

À retenir