Cryptographie et théorie de l'information

Télécharger le fichier  "crypto_entropie.pdf"

La cryptographie et la théorie de l'information

Dans les articles précédents, la question de la sûreté d’un système cryptographique a déjà été soulevée. Pour arriver à faire une comparaison plus rigoureuse entre différents systèmes de codage, nous allons utiliser les outils de la théorie de l’information qui s’articule autour de la notion d’entropie. La théorie de l’information a été mise au point par le mathématicien Claude Shannon en 1948, théorie apparaissant dans son fameux livre Mathematical Theory of Communications

Entropie

Entropie physique

La notion d’entropie vient de la thermodynamique, discipline de la physique. En physique, elle consiste en une mesure de l’état de désordre d’un système d’atomes ou de molécules. L’entropie augmente lorsque le système évolue vers un état de plus grand désordre, et inversement.

La question à se poser est donc à quoi correspond l'entropie dans le cadre de la cryptographie?

Nous allons d’abord définir ce qu’est l'entropie au sens probabiliste (voir PDF joint), puis l’entropie d’un texte, et voir en quoi cela mesure la densité d’information du texte en question.

Entropie mathématique

Initialement, on considère une variable aléatoire E qui peut prendre plusieurs valeurs possibles. E = {e1, e2, ... , eN} où N est le nombre de résultats possibles pour E. On cherche donc à déterminer l'entropie de E comme une fonction de cette varaible aléatoire, sachant qu'elle est censée représenter un "désordre mathématique", au sens probabiliste, c'est à dire une quantité caractérisant l'incertitude du résultat.

L'entropie mathématique possède donc quelques proporiétés évidentes et intuitives:

  • L'entropie est nulle pour N = 1
  • L'entropie, pour des expériences équiprobables, est une fonction croissante de N
  • L'entropie est maximale, à N fixé, pour une expérience équiprobable
De ces trois assertions, une fonction qui répond à ces critères trouve sa légitimité: le logarithme. Mais quelle base choisir pour ce logarithme? Le cas le plus naturel estde choisir la base à 2, pour se ramener à des problèmes binaires, avec équiprobabilité d'apparition du 0 ou du 1. Ainsi, toute expérience aléatoire sera décrite par décomposition de sous-expériences aléatoires binaires.

Par exemple, on considère un tirage d'une boule numérotée parmi 16 boules, et on cherche à récupérer le numéro de cette boule juste par des questions "binaires" (oui ou non) :

  • Le numéro est-il inférieur à 8?
  • Oui. Est-il inférieur à 4?
  • Non. Est-il inférieur à 6?
  • Non. Donc est-ce le numéro 6?
  • Non. Donc c'est le 7.
Ici, il est nécessaire d'avoir 4 informations "binaires" pour accéder à la valeur observée de la variable aléatoire.

Finalement, la formule de l'entropie qui résume ceci (voir PDF) est la suivante: H(X) = - E[log_2 (P(X))]

Entropie d'un texte

La principale idée est que plus un texte a un contenu dense, plus il est difficile de le remplacer par un texte court qui contient la même quantité d’information. Si l’on enregistre un texte sous format numérique, l’information est contenue sous forme d’une suite binaire de 0 et de 1. Chacune de ces unités d’information est appelée un bit. Le nombre de bits total pourrait alors être considéré comme représentant la quantité d’information contenue dans le texte. L'entropie d'un texte correspond donc à ce nombre.

Systèmes cryptographiques et théorie de l’information

La problématique est celle de la cryptanalyse : dans quelle mesure la connaissance d’un message chiffré donne de l’information sur le message clair, en supposant que le système utilisé est connu. On sait que plus l’entropie d’un système est élevée, plus celui-ci est difficile à briser. Afin de ramener le problème à un modèle mathématique et probabiliste plus simple, on suppose que l'on étudie un système cryptographique comme un ensemble de messages clairs, un ensemble de messages codés, et un ensemble de clés tels que chaque message codé soit fonction d'un message clair et d'une clé. Mais cette relation n'est pas injective: plusieurs couples de message clair et de clé peuvent donner un même message codé.

Pour mesurer la qualité du cryptosystème, on procède donc à des calculs d'entropie mathématique sur les variables aléatoires M, C et K (voir PDF) en supposant que M et K sont indépendantes, c'est à dire que le choix d'une clé de codage se fait indépendamment du message à coder.

Par des calculs détaillés dans le PDF, on montre qu'un système cryptographique est parfaitement sûr ou parfait, si l'entropie conditionnelle de M par rapport à C est égale à l'entropie de M, ce qui signifie que la connaissance du message codé n'apporte aucune information sur le message clair.

En pratique, H(M|C) est inférieur à H(M), donc on cherchera à faire tendre cette entropie conditionnelle vers H(M).

Comments