Théorie du chiffrement de Shannon

Une référence : [Sha49] (publication d’un rapport classifié de 1945)

Formalisme adopté

Un cryptosystème est la donnée de \((\cM,\cC,\cK,e,d)\) où

  • \(\cM\), l’ensemble des messages possibles

  • \(\cC\), l’ensemble des chiffrés

  • \(\cK\), l’ensemble des clefs

  • \(e:\cM\times \cK\to \cC\) la fonction de chiffrement

  • \(d:\cC\times \cK\to \cM\) la fonction de déchiffrement

vérifient

\[\forall k_e \in \cK, \exists k_d\in\cK, \forall m\in \cM , d( e(m,k_e) , k_d ) = m.\]

Le chiffrement est dit symétrique si \(k_e=k_d\), et asymétrique si connaissant \(k_e\) il est calculatoirement très difficile de déterminer \(k_d\).

Exemple des chiffres classiques

Attaques cryptographiques

Pour mesurer la résistance d’un chiffre à la cryptanalyse, on distingue les degrés d’intrusion dans le sytème cryptographique suivants :

  1. chiffré seul: on connaît un chiffré. C’est le cadre classique.

  2. clair connu: on connaît un ou plusieurs couples clair-chiffré.

  3. clair choisi: on a accès à la fonction de chiffrement \(m\mapsto e(m,k)\) pour une ou plusieurs clefs \(k\) inconnues.

  4. chiffré choisi: on a accès à la fonction de déchiffrement.

Un chiffre peut succomber à certaines attaques et résister à d’autres. Ces attaques étant toutes très plausibles, un chiffre doit être résistant pour chacune d’elles.

Exemple: le chiffre de Hill succombe immédiatement aux attaques 2-4.

Quelques techniques d’attaque :

  • cryptanalyse fréquentielle : triviale pour le chiffre de César, voir cette illustration pour le chiffre de Vigenère.

  • force brute sur les clefs : on essaie toutes les clefs, on utilise des mes mesures statistiques pour reconnaître les bonnes clefs.

  • technique du mot probable : on suppose la présence d’une séquence dans le clair, et on réalise une attaque à clair connu. C’est le principe de la bombe de Turing pour attaquer Enigma, on réalise une attaque à force brute pour trouver les clefs compatibles avec un message contenant la date ou des indications de bulletin météo.

Principes de la cryptographie moderne

Principe de Kerchkoffs

La sécurité d’un chiffre ne doit pas reposer sur le secret de la méthode, mais sur le secret de la clef utilisée.

Principes de Shannon

Un chiffre doit apporter de la confusion et de la diffusion, c’est-à-dire :

Confusion

Il n’y a pas de relation algébrique simple entre le clair et le chiffré. En particulier, connaître un certain nombre de couples clair-chiffré ne permet pas d’interpoler la fonction de chiffrement pour les autres messages. Tout le contraire d’un chiffre affine.

Diffusion

La modification d’une lettre du clair doit modifier l’ensemble du chiffré. On ne peut pas casser le chiffre morceau par morceau. Tout le contraire d’un chiffre monoalphabétique.

Le théorème du secret parfait

Pour étudier un cryptosystème, Shannon introduit un modèle de sécurité probabiliste. La sécurité est en effet toujours de nature probabiliste : un attaquant peut tomber par hasard sur la bonne clef. L’essentiel est que les interceptions de messages n’augmentent pas ses chances.

Soit \((\cM,\cC,\cK,e,d)\) un cryptosystème. On suppose que l’émetteur choisit ses clefs de manière aléatoire indépendamment des messages. Les messages qu’il envoie n’ont rien d’aléatoire, eux, mais l’attaquant qui essaie de les deviner attribue à chacun une certaine probabilité a priori (par exemple on pourrait considérer probable que le message soit un texte en français, ou dans l’ensemble des en-têtes xml valides, etc.).

On a donc deux variables aléatoire à valeurs dans \(\cM\) et \(\cK\).

  • Pour toute clef \(k\in\cK\), on note \(\Pr(k)\) la probabilité que l’émetteur utilise la clef \(k\).

  • Pour tout message \(m\in\cM\), on note \(\Pr(m)\) la probabilité a priori que le message émi soit \(m\).

La fonction de chiffrement \(e:(m,k)\mapsto c=e(m,k)\) munit \(\cC\) d’une probabilité sur les chiffrés, qui par indépendance vaut

\[\Pr(c)=\sum_{e(m,k)=c} \Pr(m)\Pr(k).\]

On a par ailleurs les probabilités conditionnelles suivantes

  • \(\Pr(c|m)\), la probabilité d’obtenir le chiffré \(c\) à partir de \(m\), qui est la probabilité de choisir une clef \(k\) qui envoie \(m\) sur \(c\). Cette probabilité vaut donc

    \[\Pr(c|m) = \sum_{k,e(m,k)=c} \Pr(k)\]

  • \(\Pr(m|c)\), la probabilité que \(c\) soit issu de \(m\). C’est cette probabilité a posteriori que l’émetteur ait émi \(m\) sachant qu’on a intercepté le chiffré \(c\), qui intéresse l’attaquant. Via la formule de Bayes, elle vaut

    \[\Pr(m|c) = \frac{\Pr(c|m)\Pr(m)}{\Pr(c)}\]

Définition

Un cryptosystème est dit à secret parfait si la réception d’un chiffré ne donne aucune information sur le clair dont il est issu

\[\forall m,c, \Pr(m|c) = \Pr(m)\]

théorème du secret parfait, Shannon 1949

Soit \((\cM,\cC,\cK,e,d)\) un cryptosystème. On suppose que \(\card{\cM}=\card{\cC}=\card{\cK}<\infty\), et que \(\Pr(m)>0\) pour tout clair \(m\in\cM\). Alors ce cryptosystème a secret parfait si et seulement si

  • la distribution des clefs suit une loi uniforme ;

  • pour tout clair \(m\in \cM\),

    \[\phi_m: \begin{cases} \cK &\to \cC \\ k &\mapsto e(m,k) \end{cases}\]

    est une bijection.

Démonstration

On suppose avoir secret parfait. On montre d’abord la bijectivité, puis l’équiprobabilité.

Bijectivité

s’il existe \(m\) tel que \(\phi_m:k\mapsto e(m,k)\) est non surjective, il existe \(c\) tel que \(\forall k\in \cK, e(m,k)\neq c\). En particulier \(\Pr(c|m)=0\), d’où l’on tire \(\Pr(m|c)=0\neq\Pr(m)>0\), impossible. Donc \(\phi_m\) est surjective, et par égalité des cardinaux bijective.

Équiprobabilité

Soit \(c\in\cC\) un chiffré fixé. Pour tout \(m\in\cM\), on note \(k(m)\) l’unique clef telle que \(e(m,k(m))=c\) (d’après la bijectivité). On a \(\Pr(c|m) = \Pr(k(m))\).

Puisque par hypothèse \(\Pr(m|c)=\Pr(m)\), on obtient \(\Pr(k(m))=\Pr(c)\).

Or le chiffrement \(m\mapsto e(m,k)\) est injectif à clef fixé, donc bijectif. Donc pour toute clef \(k\), il existe \(m\) tel que \(k=k(m)\).

Ainsi, \(\Pr(k) = \Pr(k(m)) = \Pr(c)\) est constante, et vaut \(1/\card{\cK}\).

Dans le sens réciproque, il suffit d’effectuer le calcul : par équiprobabilité des clefs on a \(\Pr(c) = \sum_{m,k}\Pr(m)\Pr(k) = \Pr(k)\), d’où \(\Pr(m|c) = \Pr(c|m)\Pr(m)/\Pr(c) = \Pr(m)\Pr(k)/\Pr(k) = \Pr(m)\).

Exercice

Montrer qu’un cryptosystème est à secret parfait si la probabilité d’obtenir un chiffré donné est indépendante du message clair dont il est issu. En d’autres termes,

\[\forall m_1,m_2\in\cM, \forall c\in\cC, p(c|m_1)=p(c|m_2).\]

Le chiffre de Vernam (1917)

Construire un cryptosystème à secret parfait est très simple : le chiffre de Vigenère convient, à condition que la clef soit tirée uniformément parmi les chaînes de même longueur que le message. Et pour ne pas divulguer cette longueur, il faut même se placer dans un espace de messages de longueur fixée suffisante, au moyen de padding.

Pour simplifier, on ne perd rien à effectuer les choses sur l’alphabet \(\set{0,1}\), si bien que le chiffre de Vernam n’est autre que le xor du message et de la clef.

Évidemment, la clef ne doit être utilisée qu’une fois, puisque \(m\oplus k\oplus m = k\) (attaque à clair connu sur la clef).