Licence CC BY

Preuve de la sécurité du masque jetable de Vernam

Que veut dire fiable et comment pouvons-nous dire que le masque jetable de Vernam l'est à 100% ?

Pour comprendre ce qui suit, il est nécessaire d'avoir des connaissances de base en probabilités. Les notations sont explicitées au tout début, mais leurs sens ne sont pas expliqués : ils sont considérés connus.

Il est donc important de savoir digérer les maths. Si ce n'est pas votre cas, passez votre chemin, je préfère ne pas avoir de mort sur la conscience ! :D

Il faut bien entendu également savoir ce qu'est le masque jetable de Vernam. Pour ce faire, je vous redirige vers un autre article, sur l'histoire de la cryptographie, qui vous expliquera en gros ce procédé. Le voici : C'est toute une histoire : la cryptographie - Partie 3/3. N'hésitez pas à lire les deux articles qui précèdent pour avoir les éventuels prérequis sur cet article.

Rappels des prérequis et notations

Avant de réaliser la preuve, il me faut définir quelques notations que je vais utiliser dans la suite de cet article.

  • $\Gamma$ (ou n'importe quelle lettre grecque majuscule) est un événement. Sa probabilité est notée $p[\Gamma]$ ;
  • la probabilité d'une événement est notée $p[\Gamma]$ tel que $0\,\leq\,p[\Gamma]\,\leq\,1$ ;
  • $\Omega$ est un événement particulier car il représente l'univers. Sa probabilité est donc toujours totale. Donc $p[\Omega]\,=\,1$ ;
  • $X$ est une variable aléatoire, $\text{X}$ est l'ensemble des valeurs $x$ que peut prendre $X$ ;
  • $p[X\,=\,x]$ représente la probabilité que la variable aléatoire $X$ ait la valeur $x$ tel que $x\,\in\,\text{X}$ ;
  • $p[X\,=\,x \,|\, Y\,=\,y]$ est la probabilité que l'on ait $X\,=\,x$ en sachant qu'on a $Y\,=\,y$ tel que $x \in \text{X}, y \in \text{Y}$.

Je dois également rappeler quelques propriétés qui ne seront démontrées ici.

  • $p[X\,=\,x \,|\, Y\,=\,y] \,=\, \dfrac{p[Y\,=\,y \,|\, X\,=\,x] \times p[X\,=\,x]}{p[Y\,=\,y]}$, cette propriété est appelée loi de Baye ;
  • $p[\Omega] \,=\, \displaystyle \sum_{x\,\in\,\text{X}}p[X\,=\,x] \,=\, 1$, cette propriété est déduite des axiomes de Kolmogorov (version simplifiée et version complète) ;
  • $p[X\,=\,x] \,=\, \displaystyle \sum_{y\,\in\,\text{Y}}p[X\,=\,x\,|\,Y\,=\,y] \times p[Y\,=\,y]$.

Une fois ceci fait, il ne me reste plus qu'à utiliser tout cela pour démontrer que le masque jetable est tout à fait fiable.

Sécurité ?

Je vais juste commencer par définir ce que l'on entend par sécurité. À priori, on pourrait commencer par sortir une définition comme celle-ci :

Est sécurisée toute méthode ne permettant pas de retrouver le message original sans la clé.

Une personne quelconque

Alors, il y a de l'idée, mais que se passe-t-il si quelqu'un arrive à déchiffrer 80% de votre message ? Votre méthode est-elle toujours sécurisée ? Difficile à dire. Il faut donc peaufiner notre définition…

Est sécurisée toute méthode ne permettant pas de retrouver une quelconque partie du message original sans la clé.

Une autre personne quelconque

Effectivement, c'est déjà mieux. Si une personne arrive à retrouver ne fût-ce que 50% du message original, c'est que notre méthode n'est pas sûre. Donc, cette définition dit que si quelqu'un arrive à deviner un caractère du message original, la méthode n'est pas sécurisée. Je vais donc vous proposer une autre définition. Et bien évidemment, je n'aurais pas pris la peine de vous faire un rappel sur les probabilités si je ne comptais pas les utiliser… Voici la définition :

Soit m le message clair et c le message chiffré, est sécurisée toute méthode telle que $\forall m\,\in\,\text{M}, c\,\in\,\text{C} : p[M\,=\,m\,|\,C\,=\,c]\,=\,P[M\,=\,m]$.

Pas de moi…

Alors que veut dire cette définition ? Que l'on considère une méthode comme sécurisée SI ET SEULEMENT SI la probabilité que le message clair soit m en sachant que le message chiffré est c est égale à la probabilité que le message clair soit m. Autrement dit, une méthode est considérée comme sécurisée SI ET SEULEMENT SI le fait que le message crypté soit c n'a aucune influence probabiliste sur le fait que le message clair soit m.

C'est très bien, mais il nous faut maintenant le prouver !

Preuve

Nous partons d'un certain postulat de départ qui est que

$$\forall m\,\in\,\text{M}, c\,\in\,\text{C} : p[M\,=\,m\,|\,C\,=\,c]\,=\,P[M\,=\,m]$$

Si nous arrivons à cette égalité, alors on sait que la méthode du masque jetable est tout à fait sûre. Mais avant toute chose, il nous faut être bien sûr de ce que veut dire chaque symbole. Commençons par définir $\mathbb{E}$ comme étant l'ensemble des symboles disponibles pour faire un message. Définissons que $L$ est la longueur du message. On peut en déduire que $\text{M}$, l'ensemble des messages possibles vaut $\mathbb{E}^L$. Ce qui veut dire que l'on prend $L$ éléments de $\mathbb{E}$ et qu'on les aligne. Pour alléger la démonstration, je vais faire la supposition que $m$ et $c$ sont de même longueur et donc que si $k$ (qui est la clé) a exactement la même longueur que $c$ et $m$ (ce qui est une propriété du masque jetable de Vernam). Je vais également supposer que le chiffrage d'un message $m$ avec une clé $k$ donnera toujours le même résultat et que toute tentative donnera un résultat tant que $m$ et $k$ respectent les contraintes imposées par $\mathbb{E}$. Donc $\exists c \,=\, \text{Cryptage}(m, k)\,|\,c, k, m\,\in\,\mathbb{E}^{L}$. Récapitulons…

$$ \begin{aligned} &\mathbb{E} \,=\, \left\{a, b, c, ..., A, B, C, ..., 0, 1, 2, ...\right\} \\ &L\,\in\,\mathbb{N} \\ &\text{M} \,=\, \mathbb{E}^L \\ &m, c, k\,\in\,\text{M} \\ \end{aligned} $$

Je vous propose d'appliquer la loi de Baye à notre membre de gauche :

$$p[M\,=\,m \,|\, C\,=\,c] \,=\, \frac{p[C\,=\,c \,|\,M\,=\,m]\times p[M\,=\,m]}{p[C\,=\,c]}$$

Vous vous dites que ça ne nous avance pas… Mais détrompez-vous. il nous faut certes toujours trouver plein de choses, voire plus, mais celles-ci, nous pouvons les trouver ! Commençons par trouver $p[C\,=\,c\,|\,M\,=\,m]$. Pour ce faire, je vais me servir de la supposition faite plus haut qui disait que j'aurai toujours un résultat unique pour chaque appel à $\text{Cryptage}(m, k)$. Je peux donc changer $p[C\,=\,c\,|\,M\,=\,m]$ en $p[K\,=\,k]$. Effectivement, sachant que l'on a $(M = m)$, $(K\,=\,k) \Longleftrightarrow (C\,=\,c)$. Et la probabilité que $K$ soit $k$ peut être facilement calculée. Le masque jetable implique une clé aléatoire prise dans $\text{M}$. La clé étant aléatoire, chaque élément de $\mathbb{E}$ est équiprobable. Et on en a $L$. Il y a donc $\#\left(\mathbb{E}^L\right)$ clés possibles tel que $\#\mathbb{E}$ représente le nombre d'éléments de $\mathbb{E}$. On a donc $p[K\,=\,k]\,=\,\frac{1}{\#\left(\mathbb{E}^L\right)}$.

Notre formule évolue donc en la formule suivante :

$$p[M\,=\,m \,|\, C\,=\,c] \,=\, \frac{\dfrac{1}{\#\left(\mathbb{E}^L\right)} \times p[M\,=\,m]}{p[C\,=\,c]}$$

Mais attention, cette même probabilité que $C$ soit égale à $c$ est exactement la même que $p[K\,=\,k]$ car $k$ et $c$ sont du même ensemble $\mathbb{E}$ et de même longueur $L$. Ce qui nous donne donc la formule suivante :

$$p[M\,=\,m \,|\, C\,=\,c] \,=\, \frac{\dfrac{1}{\#\left(\mathbb{E}^L\right)} \times p[M\,=\,m]}{\dfrac{1}{\#\left(\mathbb{E}^L\right)}}$$

Et là, on a le même élément au numérateur et au dénominateur. On peut donc les simplifier, ce qui nous laisse avec la formule suivante :

$$p[M\,=\,m \,|\, C\,=\,c] \,=\, p[M\,=\,m]$$

Et l'on a retrouvé notre équation de départ ! CQFD ! :D

Nous avons donc prouvé que le masque jetable de Vernam est effectivement une méthode infaillible (du moins selon notre définition de sécurité).


14 commentaires

Merci beaucoup à Arius pour la relecture attentive de l'article et pour y avoir ajouté sa touche qui l'a rendu meilleur pour vous. Plein de cœurs au loup ! <3

Et gusfl… Je retiens ton pseudo ! :diable:

+1 -0

C'est sympa comme article, c'est finalement la base de toute la crypto. J'ai trouvé ça facile, mais c'est peut être parce que je sors de la même école que le chanteur de Gusfl (il est réellement ingénieur informaticien, il bossait chez Orange aux dernières nouvelles)

Ce n'est en soi pas bien compliqué, ce sont des notions de bases en probabilité (pas besoin d'avoir fait une quelconque école d'ingénieur au final : un enseignement secondaire supérieur et un esprit mathématique font le tout).

+2 -0

L'article est intéressant, mais j'ai quand même une petite question :-) La notation $P[X = x|Y = y]$ est-elle équivalente avec $P_y[X = x]$, la probabilité conditionnelle, où cela n'a t'il rien à voir? Merci d'avance, et pardonnez mon ignorance!

Edit: Merci de vos réponses, il y a donc bien équivalence

+0 -0

Wahou, super article, merci beaucoup ! Juste deux petites remarques :

  • Le lien pour la version simplifiée des axiomes de Kolmogorov est mort (l'URL affichée est http://www.bibmath.net/dico/index.php?action\,=\,affiche&quoi\,=\,./k/kolmogorovaxiomatique.html au lieu de http://www.bibmath.net/dico/index.php?action=affiche&quoi=./k/kolmogorovaxiomatique.html )
  • Je ne suis pas d'accord avec la partie $(K = k) \Leftrightarrow (M = m) \wedge (C = c)$ : on a bien la réciproque, mais l'implication n'est pas gagnée (on peut très bien avoir $ K = k $ mais $(M = m')\wedge(C = c')$). Une formulation appropriée serait : Si $M = m$, alors $(K = k) \Leftrightarrow (C = c)$, ou encore, pour une formule plus indigeste : $(M = m) \Rightarrow ((K = k) \Leftrightarrow (C = c))$, mais je chipote. :)

Edit : Proprification.

Edit 2 : Oh, d'ailleurs, il y a un formulaire pour signaler ce genre d'erreurs (lien mort, typo…) plutôt que de passer par les commentaires (ce que je n'aime pas trop faire, parce que ce n'est pas utile pour le débat) ? Je ne l'ai pas vu.

+1 -0

Wahou, super article, merci beaucoup !

De ta part, ça fait plaisir !

Juste deux petites remarques :

fix'd, merci au staff qu s'en est occupé ! (Ça sent le Ctrl+H sur N++ pour modifier les = en \,=\, pour les rendre plus lisibles en LaTeX. :-° )

  • Je ne suis pas d'accord avec la partie $(K = k) \Leftrightarrow (M = m) \wedge (C = c)$ : on a bien la réciproque, mais l'implication n'est pas gagnée (on peut très bien avoir $ K = k $ mais $(M = m')\wedge(C = c')$). Une formulation appropriée serait : Si $M = m$, alors $(K = k) \Leftrightarrow (C = c)$, ou encore, pour une formule plus indigeste : $(M = m) \Rightarrow ((K = k) \Leftrightarrow (C = c))$, mais je chipote. :)

melepe

Effectivement, je n'y avais pas pensé, je vais rectifier ça. Merci beaucoup de l'avoir fait remarquer !

EDIT : done, réenvoyé en validation. :)

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte