Accueilretour

Systèmes modernes à clé secrète

1. One-time pad

Généralités

Stéganographie

Cryptanalyse

Littérature

Transpositions

Subs. monoα

Subs. polyα 1 - 2

One-time pad

codage "parfait"

proba. conditionnelle
application

chiffrage OTP

réalisations
perfection
optimalité
biais

DES 1 - 2

Clef publique

Knapsack

Diffie-Hellman

RSA 1 - 2

Grands noms

Références


 Des cryptographes, conscients que le Vigenère n'était pas infaillible, ont été proposé des améliorations. On voit bien dans les exemples ci-dessous qu'elles ne résolvent pas le problème fondamental...
  • double codage Vigenère ;
  • alphabet désordonné ;
  • clef variable avec le clair ;
  • mot-clef "illimité" :
    • roman...
    • chaîne aléatoire
... à l'exception du dernier point, qui allait conduire à un résultat étonnant.

Un codage "parfait" ?

Qualifier un système de chiffrage de parfait exige une définition rigoureuse. Il revient à Claude Shannon de l'avoir formulée pour la première fois en 1949. Quelques rappels de probabilités sont nécessaires...

probabilité conditionnelle

Étant donné deux événements A et B, la probabilité (conditionnelle) de A sachant B, notée P(A | B) [1] est définie par

        (1)    P(A | B) = P(A et B)/P(B)

C'est la probabilité de l'événement A lorsque l'événement B est supposé réalisé. On définirait de manière symétrique la probabilité de B sachant A.

On dit que l'événement A est indépendant de B si P(A | B) = P(A). Cela signifie que l'issue de l'événement B est sans incidence sur celle de A. Selon (1) cela équivaut donc à : P(A et B)/P(B) = P(A), ou encore : P(A et B) = P(A) × P(B). Sous cette dernière forme, on voit que A et B jouent un rôle identique, autrement dit : "A est indépendant de B" équivaut à "B est indépendant de A" [2]. On peut donc se contenter d'énoncer : "A et B sont indépendants".

retour

application aux systèmes de cryptage

Un système de cryptage sera dit parfait si, pour tous messages clair M et chiffré C :

        (2)    P(clair = M | chiffré = C) = P(clair = M)

Cela signifie donc que la connaissance du chiffré ne procure aucune information sur le clair. On peut la reformuler en termes de probabilité conditionnelles en disant que clair et chiffré sont indépendants. La relation d'indépendance étant symétrique :

        (2b)    ∀M, M'∈ℳ, P(clair = M | chiffré = C) = P(clair = M' | chiffré = C)

Étant donné un chiffré C, tous les clairs sont équiprobables !

Il est facile de voir que les chiffrages monoalphabétiques type César ne vérifient pas cette condition [3], de même que le Vigenère et ses descendants [4].

retour

Le chiffrage "one-time pad"

Ce système est aussi appelé chiffrement à flot ou clé-une-fois ou masque jetable ou chiffre de Vernam, du nom de son inventeur G. Vernam. Celui-ci a mis en forme en 1917 une idée remontant en fait à 1882 (F. Miller). En 1919, Vernam a breveté un système électromécanique réalisant ce cryptage.

Essentiellement, le chiffrage de Vernam répond au même principe que le Vignère. Il effectue une addition modulaire du message clair M avec une clé K pour obtenir le chiffré C : C = M ⊕ K. La différence réside en la clé, qui doit satisfaire deux conditions très strictes :

  • (A) être de longueur illimitée ;
  • (B) être aléatoire.

La condition (A) est évidemment nécessaire puisque, nous l'avons vu, c'est son absence qui permet de casser le chiffrage Vigenère.

La condition (B), nous allons le constater, commande une bonne partie de l'efficacité du système Vernam.

Nous notons toujours ⊕ l'addition modulo N, la soustraction modulo N étant notée ⊖. Cette distinction n'a pas lieu d'être lorsque N = 2 (cas d'un message transcrit en binaire), les deux opérations ⊕ et ⊖ étant alors identiques.

retour

réalisations du one-time pad

Le chiffrage Vernam a été très employé pendant et après la 2nde guerre mondiale. Mais la contrainte de transmission des clés le rendait mal adapté à une utilisation "dans le feu de l'action". Il a donc construit son succès au sein des états-majors, ou dans l'espionnage.

Les espions soviétiques pendant la guerre froide encryptaient leurs transmissions au moyen de minuscules carnets de clés tels celui-ci :

La taille des feuillets était parfois plus petite que celle d'un ongle ! Chacun n'était utilisé que pour un unique message, d'où le nom de one-time pad. Comme on le voit, les feuillets ne comportaient pas des lettres, mais des chiffres. Il fallait d'abord convertir le message sous forme numérique. On effectuait ceci en mettant en correspondance une lettre avec un ou deux chiffres, selon que son utilisation était plus ou moins fréquente. Les mots entiers les plus employés se voyaient affecter un nombre-code propre ; un "livre de codes" était nécessaire pour le chiffrage et le déchiffrage. Les carnets étaient cachés dans les objets les plus divers (trousse de toilette, jouet...)

Le système électromécanique Vernam quant à lui convertissait le clair sous forme binaire avant transmission.

Le "télétype rouge" entre la Maison Blanche et le Kremlin, durant la guerre froide, utilisait ce type de cryptage. C'est dire quelle confiance on plaçait en ce système.

retour

perfection du one-time-pad

En effet, le chiffrage one-time pad satisfait la condition de perfection de Shannon (2). Rappelons la définition de la probabilité conditionnelle :

P(clair = M | chiffré = C) = 
P(clair = M et chiffré = C)
P(chiffré = C)

Dans le cas du one-time pad, le chiffré s'obtient par addition modulaire de la clé K avec le clair : C = M ⊕ K, donc on peut développer :

P(clair = M et chiffré = C) = P(clair = M et clé = C ⊖ M)
            = P(clair = M) × P(clé = C ⊖ M) (la clé et le clair sont indépendants)
            = P(clair = M) × 1/Nℓ (toutes les clés sont équiprobables)

Maintenant, selon la formule de Bayes ("probabilité de causes") (on rappelle que ℳ désigne l'espace des messages clairs) :

P(chiffré = C) = ∑ℳ P(clair = M et chiffré = C)
            = ∑ℳ P(clair = M) × 1/Nℓ
            = 1/Nℓ × ∑ℳ P(clair = M)
            = 1/Nℓ × 1 = 1/Nℓ

de sorte que :

P(clair = M | chiffré = C) = 
P(clair = M) × 1/Nℓ
1/Nℓ


= 
P(clair = M)

C'est bien la condition (2) de Shannon.

Deux remarques :
  • Cet argument ne suppose pas que les messages clairs soient équiprobables (heureusement !). En fait, il est indépendant de la distribution de la probabilité sur ℳ.
  • Par contre, pour qu'il soit valide, il est essentiel de s'assurer de clés équiprobables. Cette condition est assurée par l'hypothèse (B).

retour

optimalité du one-time pad

Le one-time pad, tel que nous l'avons décrit, est théoriquement parfait selon la définition de Shannon. Mais les conditions (A) et (B) sur les clés sont très contraignantes. Peut-on les alléger ? Il n'en est rien, en vertu du fameux principe des tiroirs :

théorème : Pour tout système de cryptage satisfaisant la condition de perfection (2) de Shannon, l'espace des clefs 𝒦 a au moins le même cardinal que l'espace des clairs ℳ : #𝒦 ≥ #ℳ

preuve. Par l'absurde, supposons #𝒦 < #ℳ. Fixons un chiffré C0 provenant d'un clair M0 par l'application d'une clé K0 (C0 = M0 ⊕  K0). Dénombrons les clairs M qui conduisent à C0 par application d'une certaine clé K :

𝒮 = {M∈ℳ | ∃K∈𝒦, C0 = M ⊕ K}

La condition C0 = M ⊕ K équivaut à M = C0 ⊖ K. Comme l'opération de chiffrage est une application injective (un même chiffré ne peut correspondre à deux clairs différents !), on a nécessairement #𝒮 ≤ #𝒦 < #ℳ. L'ensemble 𝒮 '  = ℳ ⧵ 𝒮 = {M∈ℳ | ∀K∈𝒦, C0 ≠ M ⊕ K} est donc non vide. Mais alors

    • pour les M ∈ 𝒮 ', P(clair = M | chiffré = C0) = 0, tandis que
    • pour les M ∈ 𝒮, P(clair = M | chiffré = C0) ≠ 0 (puisque M0 chiffré avec K0 donne C0).

Ainsi, P(clair = M | chiffré = C0) n'est pas indépendante du clair M. Ceci contredit la condition (2b) de Shannon.

La condition (B) ne peut être affaiblie, donc. Mais est-ce là un défaut du système, ou de la définition de la perfection selon Shannon ? Celle-ci attribue à l'adversaire ("Eve") une puissance de calcul infinie. Dans une conception moins rigoureuse mais plus réaliste, on pourrait allouer à Eve une capacité de calcul élevée mais bornée.

Voyons en tout cas les limitations pratiques associées à ces remarques.

retour

biais et défauts du one-time pad

Dans le cas d'une utilisation "gouvernementale", les clés sont disponibles à volonté et leur transmission est assurée. Dans cette configuration, le one-time pad n'est guère pris en défaut.

Il n'en est pas de même lors de son usage "de terrain" (espionnage...). Outre la difficulté de l'acheminement des fameux carnets one-time pads soviétiques présentés plus haut, leur confection et leur utilisation ne vérifiaient pas toujours les critères de sécurité requis :
  • D'une part, ces minuscules carnets n'étaient pas toujours véritablement aléatoires. Ils étaient souvent tapés "au hasard" (?) sur des machines, par des opérateurs. La fourniture d'un grand nombre de clés était une lourde tâche dactylographique :
    • Il arrivait que l'opérateur fatigué se laisse aller à taper des séquences de chiffres consécutifs.
    • Une observation statistique curieuse a également révélé que les premiers chiffres de chaque groupe de cinq étaient sept fois plus souvent dans l'intervalle [1, 5] que dans l'intervalle [6, 0]. L'explication plausible est que l'opérateur tapait l'espace de la main droite, et recommençait presque toujours le groupe de chiffres suivant de la main gauche.
      Toutefois selon D. Kahn, ces irrégularités étaient insuffisantes pour donner prise à la cryptanalyse.
  • Non moins fréquent, mais beaucoup plus dangereux, était le cas de l'agent de terrain ayant épuisé son carnet de clés. Il réutilisait alors des clés déjà employées. Cela rendait le one-time pad aussi faible que le Vigenère.
En conclusion, le one-time pad peut s'appliquer avec succès à des transmissions internes, de volume modéré, impliquant un nombre limité d'individus.

Pour des applications publiques, à grande échelle, d'autres systèmes devaient se révéler mieux adaptés.

retour

Notes

[1]  lire "P de A sachant B" ou "P de A si B"

[2]  On dit que la relation d'indépendance des événements est symétrique.

[3]  à moins que le message ne se limite à... un unique caractère !

[4]  dès que la longueur du clair dépasse celle de la clef