Wiki du cours

Rédacteur: [Benjamin Carrel]

A traiter [edit]

Ce sujet a pour but de présenter différents protocoles cryptographiques. Il ne présente pas de difficulté mathématique, mais requiert quelques recherches bibliographiques.

• Chiffrement, composé de 3 algorithmes: création de clé, chiffrement, déchiffrement. [2]
• Chiffrement symétrique (cryptographie à clé secrète). [2]
• Chiffrement asymétrique (cryptographie à clé publique). [2]
• Signature, composé de 3 algorithmes: création de clé, signature, vérification. [3]
• Echange de clés (description informelle)

Types de chiffrements [edit]

La problématique est la suivante : deux parties souhaite s'échanger des informations de manière confidentiel. Naturellement, on peut penser à un texte que l'on va chiffrer d'une manière bien définie de telle sorte qu'un inconnu ne puisse pas comprendre ce texte, mais que les deux parties soient capables de retrouver le texte original, c'est à dire déchiffrer le message. Nous allons voir deux façons de faire ce chiffrement, et nous allons ensuite donner la définition formelle de tels procédés.
Prenons deux individus, Alice et Bob, qui souhaite communiquer de manière confidentielle ; ainsi qu’un pirate, Eve, qui essai de connaître le message entre Alice et Bob.

Chiffrement symétrique

1. La création de clé. Alice et Bob doivent se partager une clé secrète \(S\), que Eve ne connaît pas.
2. Le chiffrement. Bob souhaite envoyer un message \(m\) à Alice. Bob et Alice se fixent préalablement une méthode utilisant la clé \(S\) suffisamment complexe pour qu'Eve ne puisse pas retrouver le message facilement, mais réalisable en un temps raisonnable avec la clé \(S\). Bob utilise la clé \(S\) pour chiffrer \(m\). On note cette opération \(c=E_S(m)\). Le message chiffré \(c\) est appelé cryptogramme. Bob peut maintenant envoyer \(c\) à Alice en toute sécurité.
3. Le déchiffrement. Alice reçoit le message chiffré \(c\) de Bob. Avec la clé \(S\), elle déchiffre \(c\) pour retrouver le message original \(m\). On note cette opération \(m=D_S(c)=D_S(C_S(m))\). Ainsi, Alice a reçu le message original de Bob.
   Avec ce procédé, le seul message qu'Eve peut récupérer est le cryptogramme \(c\). Ne connaissant pas la clé, elle est en incapable de retrouver le message original \(m\) en un temps raisonnable.

Remarque : En informatique, on utilise souvent les mots facile ou difficile pour désigner un problème qui est respectivement rapide (seconde/jours) ou très long (millions, voir milliards d'années) à résoudre avec le meilleur algorithme connu. Voici une indication plus rigoureuse sur la complexité d'une problème :

Notation : Soit un algorithme A. On note \(A(1^k)\) pour indiquer que le paramètre de sécurité \(k\) est la taille en bits des clés utilisées. Instinctivement, \(k\) représente dans une certaine échelle le coût en temps de l'algorithme \(A\).

Définition : On dit d’un algorithme qu’il est PPT (probabilistic polynomial time) si son coût en temps est polynomial et que son résultat est le bon avec une certaine probabilité non-nulle.

Définition formelle : Un chiffrement à clé symétrique est un triplet d’algorithme PPT \(\varepsilon = (G,E,D)\) tel que :

1. \(G\) est l’algorithme de création de clé. Le résultat de \(G(1^k) \longrightarrow (S,\mathcal{M})\) avec \(S\) la clé, et \(\mathcal{M}\) l’espace dans lequel vit le message. On peut choisir le paramètre de sécurité \(k\) comme on le souhaite.
2. \(E\) est l’algorithme de chiffrement. Le résultat de \(E_S(m) \longrightarrow c\) est le cryptogramme, avec \(m \in \mathcal{M}\). (En fonction de la méthode utilisée, on peut ajouter un paramètre \(r\) tiré aléatoirement. On note alors \(E_S(m,r)\).)
3. \(D\) est l’algorithme de déchiffrement. Le résultat de \(D_S(c) \longrightarrow m̃ \in (invalid) \cup \mathcal{M}\), appelé message déchiffré. Le résultat peut être invalide dans le cas où le message chiffré et la clé ne correspondent pas.
   Ces trois algorithmes doivent vérifier la condition de cohérence suivante : \(\forall m \in \mathcal{M}, m̃=m, D_S(E_S(m))=m\)

Remarque à propos de la sécurité : Le but ici n'est pas d'avoir une définition formelle de la sécurité. [Voir Dodis Lecture 1 Définition 5 pour celle-ci]. On peut néanmoins expliquer cette notion rapidement. Si \(k\) incarne le paramètre de sécurité, alors Eve ne doit être capable de déchiffrer le message avec une probabilité négligeable en \(k\), c'est à dire qui tend vers 0 en \(k\) plus rapidement que polynômialement. Concrètement, la sécurité du chiffrement est assuré par le temps que met Eve à "probablement" déchiffrer le message.

Exemple : Chiffrement césar (Décalage constant de l'alphabet), affine, Enigma (voir le film The Imitation Game), ...

Chiffrement asymétrique

Pour le chiffrement asymétrique, le principe est le même. Cependant, Alice possède maintenant deux clés : une publique \(PK\) et une secrète \(SK\). Tout le monde a accès à \(PK\), et on s’en sert pour chiffrer un message à envoyer à Alice. Seulement Alice connaît \(SK\), qui lui sert à déchiffrer les messages reçus.
Dans cette configuration, Alice peut seulement recevoir des messages. Si elle souhaite répondre à Bob, il devra avoir sa propre paire de clé.

Définition formelle : Un chiffrement asymétrique (à clé publique) est un triplet d’algorithme PPT \(\varepsilon = (G,E,D)\) tel que :

1. \(G\) est l’algorithme de création de clé. Le résultat de \(G(1^k) \longrightarrow (PK, SK, \mathcal{M})\), avec \(PK\) la clé publique, \(SK\) la clé secrète et \(\mathcal{M}\) l’espace du message. De nouveau, \(k\) représente le paramètre de sécurité.
2. \(E\) est l’algorithme de chiffrement. Le résultat de \(E_{PK}(m) \longrightarrow c\) est le cryptogramme, avec \(m \in \mathcal{M}\). (Comme avant, on peut ajouter un paramètre \(r\) tiré aléatoirement. On note alors \(E_{PK}(m,r)\).)
3. D est l’algorithme de déchiffrement. Le résultat de \(D_{SK}(c) \longrightarrow m̃ \in (invalid) \cup \mathcal{M}\), appelé message déchiffré.
   Ces trois algorithmes doivent vérifier la condition de cohérence suivante : \(\forall m \in \mathcal{M}, m̃=m, D_{SK}(E_{PK}(m))=m\)

Remarque : Bien que Eve connaisse elle aussi la clé publique, celle-ci ne lui donne normalement aucune information sur la clé secrète. De ce fait, la sécurité de cette méthode est toujours assurée par le temps que devrait mettre Eve pour "probablement" déchiffrer le message.

Exemple : Chiffrement RSA qui repose sur la difficulté à factoriser un nombre entier quelconque en nombres premiers.

Echange de clés

Un protocole d'échange de clés a pour but d'échanger des clés secrètes en vue de l'établissement d'un protocole de cryptographie symétrique. Un moyen de mettre en contact deux parties dans ce but et d'utiliser un chiffrement asymétrique. Une autre possibilité est le protocole de Diffie-Hellman dont on parlera dans le sujet suivant.

Utiliser la cryptographie symétrique plutôt qu'asymétrique est intéressante en pratique car moins coûteuse et potentiellement plus sûre. C'est pourquoi le protocole d'échange de clé est important.

Signature [edit]

Admettons maintenant que Bob reçoive un cryptogramme. Il peut le déchiffrer avec sa clé secrète, mais comment connaître l’origine du message ? Comment être certain que ce soit Alice, et non Eve, qui a écrit ce message ? C’est pour répondre à cette problématique que l’on introduit les signatures. Comme dans la vie courante, le principe d’une signature (visible par tout le monde) est d’identifier quelqu’un, en étant sûr que sa signature ne puisse être reproduite parfaitement. Voici une formalisation de ce principe.

Définition formelle : Une signature à clé publique est un triplet d’algorithme PPT \((Gen,Sign,Ver)\) avec :

1. \(Gen\) est l’algorithme de génération d’une clé secrète et d’une clé publique (de vérification) : \(G(1^k) \longrightarrow (SK,VK)\)
2. \(Sign\) est l’algorithme permettant de signer un message : \(Sign_{SK}(m) \longrightarrow \sigma\), avec \(m \in \mathcal{M}\)
3. \(Ver\) est l’algorithme de vérification, permettant de vérifier que la signature est correcte : \(Ver_VK(m,\sigma) \in (accepte, rejete)\)
   Ces trois algorithmes doivent vérifier la condition de cohérence suivante : \( \forall m, Ver_{VK}(Sign_{SK}(m))=accepte\)

Définition : Une signature à clé publique est dite sécurisée si un adversaire a une probabilité négligeable d'arriver à créer une signature valide. [La définition formelle est donné ici : Dodis Lecture 12 Définition 4]

Références [edit]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 6.1
[2] Yevgeniy Dodis, Introduction to cryptography, Lecture 2
[3] Yevgeniy Dodis, Introduction to cryptography, Lecture 12, 5.1
[4] Le problème du logarithme discret en cryptographie
[5] Morten Tyldum, The Imitation Game, Film-biographie d'Alan Turing