A.2 Cryptographie asymétrique

L’idée majeure de la cryptographie asymétrique est que les opérations publiques (le chiffrement, la vérification de signature, etc.) n’ont pas nécessairement besoin d’utiliser les mêmes clés que les opérations privées (le déchiffrement, la signature, etc.). Ainsi, la cryptographie asymétrique, telle que décrite par W. Diffie et M. Hellman [15], utilise des « clés privées », que seul un utilisateur possède et peut utiliser pour les opérations privées, et des « clés publiques », que tout le monde connaît et peut utiliser pour les opérations publiques.¹ Les clés publiques et privées sont reliées par des équations mathématiques, ces équations étant la base de problèmes que l’on croit difficiles à résoudre. Pour illustrer la notion de difficulté en pratique, une image simple est la suivante : à partir d’un pot de peinture jaune et d’un pot de peinture bleue, il est facile par simple mélange d’obtenir un pot de peinture verte. Par contre, l’opération inverse consistant à séparer les pigments jaunes des pigments bleus, sans être théoriquement infaisable, l’est en pratique. Dans cet exemple, le vert fait office d’élément public, et le bleu et le jaune sont privés : tout le monde sait que le but est de diviser le vert en bleu et jaune pour retrouver la clé privée, mais l’opération est considérée comme très difficile. De même, dans le monde mathématique, il existe de telles opérations inversibles mais asymétriques dans leur difficulté. On les appelle souvent problèmes difficiles ou asymétriques.

La plus connue de ces opérations asymétriques est la multiplication de grands nombres premiers. L’opération inverse, consistant à retrouver ces nombres à partir du résultat, est appelée factorisation ou encore décomposition en produit de facteurs premiers. Choisir deux nombres premiers de taille fixée et les multiplier est une opération facile mais, dès que la taille des entiers manipulés est suffisamment grande, aucune méthode efficace permettant de retrouver ces facteurs premiers à partir de la simple valeur de leur produit n’est connue à ce jour. Insistons sur le fait qu’une telle factorisation n’est pas impossible ; elle est mathématiquement parfaitement définie et l’on connaît des algorithmes simples permettant de la retrouver. Le problème réside dans la complexité temporelle, c’est-à-dire dans le temps de calcul nécessaire à ces méthodes pour trouver le résultat. De plus, rien ne permet de dire qu’il n’existe pas de méthode efficace. On peut tout juste affirmer qu’aucune méthode efficace de factorisation utilisant une technologie disponible n’a été rendue publique à ce jour.

Aucun détail nécessitant de lourds rappels mathématiques ne sera donné ici. Il suffira de noter simplement que ces problèmes ne deviennent réellement difficiles, et donc cryptographiquement intéressants, que pour des tailles suffisantes de certains paramètres. Ce sont ces tailles qui déterminent la sécurité intrinsèquement apportée par le problème de base à l’ensemble du mécanisme. La sécurité d’un système asymétrique s’évalue donc en fonction de la difficulté à résoudre numériquement un certain problème mathématique et non pas en fonction de la taille de l’espace des clés. Ainsi, par exemple, lorsque l’on parle de RSA-2048, ceci signifie que l’on utilise RSA avec un paramètre, appelé module, long de 2048 bits et obtenu par multiplication de deux nombres premiers de 1024 bits chacun. Il ne faut par conséquent pas s’étonner de voir apparaître en cryptographie asymétrique des paramètres ou des clés de 2048 bits ou plus alors qu’en cryptographie symétrique les clés dépassent rarement 256 bits. Les tailles de clés symétriques et asymétriques ne sont donc pas comparables.²

A.2.1 Chiffrement asymétrique

Un mécanisme de chiffrement asymétrique est spécifié par la donnée de trois algorithmes. Le premier permet de générer une bi-clé. Le second, utilisé par n’importe qui, prend en entrée un message et une clé publique, et renvoie un chiffré de ce message sous la clé publique. Enfin, le troisième algorithme est utilisé par le possesseur de la clé privée, prend en entrée cette clé ainsi qu’un chiffré et renvoie le message correspondant.

Une image classique consiste à imaginer une boîte aux lettres (physique). L’équivalent de la clé publique est la boîte à l’adresse du destinataire, adresse consultable par tous, dans un annuaire par exemple. L’équivalent de la clé privée est la clé de la boîte dont ne dispose, normalement, que le propriétaire de la boîte. Afin de transmettre un document, il « suffit » de prendre connaissance de l’adresse du destinataire et de le lui envoyer sous pli scellé. Lors de la réception, seul le destinataire peut prendre connaissance du document à la condition que lui seul possède la clé. Cette image permet en outre de comprendre le problème posé par l’authentification de la boîte du destinataire puisqu’il faut savoir relier de manière fiable le destinataire à sa boîte pour s’assurer que la bonne personne recevra le document. Pour le destinataire des documents si aucun mécanisme n’est prévu pour authentifier l’émetteur, il ne peut davantage s’assurer de l’intégrité de ce qu’il reçoit.

Il est important de noter que, contrairement au cas des mécanismes symétriques, il n’est pas ici nécessaire que les deux correspondants partagent, au préalable, une clé secrète. Ceci permet théoriquement de résoudre très élégamment les problèmes de mise en accord de clé inhérents à la cryptographie symétrique. Il se pose cependant le problème de la certification des clés publiques visant à s’assurer qu’une clé publique utilisée pour chiffrer appartient bien au correspondant à qui l’on destine le message.

Le problème apparaît plus clairement formalisé sous le diptyque confidentialité/authentification. En effet s’il est facile de comprendre que l’échange d’un secret nécessite de la confidentialité, on aurait tendance à oublier que l’authentification de l’origine du secret (c’est-à-dire à la fois la garantie de son intégrité et de l’émetteur) est cruciale. Si le chiffrement asymétrique lève le problème de la confidentialité, le problème de l’authentification reste quant à lui entier. Il est résolu par des mécanismes de certification comme cela est indiqué plus loin.

Comme dans le cas de mécanismes de chiffrement par bloc, l’utilisation de chiffrement à clé publique avec des messages de taille quelconque doit être très précisément spécifiée. Ceci implique d’être capable de formater et de compléter les messages afin d’appliquer l’algorithme de chiffrement ; on parle de « padding » ou « bourrage ». L’utilisation de données aléatoires est également nécessaire afin de rendre le chiffrement probabiliste et par conséquent d’éviter que le chiffrement du même message à deux reprises produise des chiffrés identiques. Ceci est fondamental pour des applications où l’espace des messages est restreint à un petit sous-ensemble des messages possibles.

Notons enfin que pour des raisons d’efficacité il est inutile de chiffrer de grands messages au moyen d’un mécanisme asymétrique. Une méthode bien plus efficace, désignée sous le terme de « chiffrement hybride », consiste à choisir une clé de session pour un mécanisme de chiffrement symétrique et à ne chiffrer avec le mécanisme à clé publique que cette clé de session, le message étant lui chiffré en symétrique avec la clé de session. On peut ainsi transmettre la clé de session de manière sécurisée à son interlocuteur, et un long message peut être chiffré de manière conventionnelle et très efficace.

Notions de sécurité. Il existe principalement deux notions de sécurité pour le chiffrement asymétrique. La première est la sécurité sémantique [22]. Goldwasser et Micali la définissent de la manière suivante. Un adversaire reçoit une clé publique, et choisit deux messages différents $m_{0}$ et $m_{1}$ . On lance une pièce, qui donne un résultat b = 0 ou 1, et on donne à l’adversaire un chiffré $c^{*}$ de $m_{b}$ . L’adversaire renvoie $b^{'}$ et gagne si $b = b^{'}$ . Le mécanisme de chiffrement est sémantiquement sûr si aucun adversaire n’a une probabilité de gagner non-négligeablement supérieure à $1/2$ , soit la probabilité de gagner en répondant au hasard. On trouve cette notion dans la littérature scientifique sous la dénomination IND-CPA. En particulier, cette notion implique la confidentialité des données chiffrées, un adversaire ne sachant pas quelle donnée peut se trouver sous un chiffré.

La seconde est la résistance aux attaques par chiffrés choisis et est définie similairement à ce qui précède. Le seul changement est que l’adversaire est autorisé à demander le déchiffrement de chiffrés de son choix, sauf $c^{*}$ . On trouve cette notion dans la littérature scientifique sous la dénomination IND-CCA ou IND-CCA2. En particulier, cette notion implique l’intégrité des données chiffrées. En effet, si un adversaire savait manipuler des chiffrés pour en créer de nouveaux, il pourrait gagner le jeu avec haute probabilité, en modifiant $c^{*}$ et en demandant le déchiffrement du nouveau chiffré.

D’autres notions, plus faibles ou intermédiaires, existent dans la littérature et sont principalement utilisés pour obtenir des réductions plus fines lorsque le chiffrement asymétrique est utilisé dans un autre mécanisme.

A.2.2 Encapsulation de clé

Un mécanisme d’encapsulation de clé permet de générer et de protéger en confidentialité (encapsuler) une clé de session symétrique à l’aide d’une clé publique à destination du propriétaire de la clé privée associée. Celui-ci peut la récupérer en effectuant l’opération de décapsulation à l’aide de sa clé privée. La clé de session est choisie au sein de l’algorithme d’encapsulation, qui ne prend donc en entrée que la clé publique, et est renvoyée en plus du chiffré pour permettre son utilisation par la personne appelant l’algorithme d’encapsulation.

Le lien entre ce mécanisme et le chiffrement asymétrique est fort. Un mécanisme de chiffrement asymétrique est transformé en KEM par la transformation de Fujisaki-Okamoto [20, 21], tandis qu’un KEM et un chiffrement symétrique donnent un mécanisme de chiffrement asymétrique, par la méthode du chiffrement dit hybride, à ne pas confondre avec l’hybridation dans le contexte du post-quantique.

Notions de sécurité. Il existe principalement deux notions de sécurité pour les mécanismes d’encapsulation de clé, définies similairement à celles du chiffrement asymétrique.

La première est la sécurité sémantique. On utilise la procédure d’encapsulation pour obtenir un couple (chiffré, clé) $(c, K_{0})$ et on tire uniformément aléatoirement une suite de bits $K_{1}$ de même longueur que $K_{0}$ . On lance une pièce, qui donne un résultat $b = 0$ ou $1$ , et on donne à l’adversaire la clé publique $p k$ , le chiffré $c$ ainsi que la clé $K_{b}$ . L’adversaire renvoie $b^{'}$ et gagne si $b = b^{'}$ . Le mécanisme d’encapsulation de clé est sémantiquement sûr si aucun adversaire n’a une probabilité de gagner non-négligeablement supérieure à $1/2$ , soit la probabilité de gagner en répondant au hasard. On trouve cette notion dans la littérature scientifique sous la dénomination IND-CPA. En particulier, cette notion implique la confidentialité de la clé de session symétrique, un adversaire ne sachant pas extraire d’information sur la clé à partir d’un chiffré.

La seconde est la résistance aux attaques par chiffrés choisis et est définie similairement à ce qui précède. Le seul changement est que l’adversaire est autorisé à demander la décapsulation de chiffrés de son choix, sauf $c^{*}$ . On trouve cette notion dans la littérature scientifique sous la dénomination IND-CCA ou IND-CCA2. En particulier, cette notion implique l’intégrité des données chiffrées. En effet, si un adversaire savait manipuler des chiffrés pour en créer de nouveaux, il pourrait gagner le jeu avec haute probabilité, en modifiant $c^{*}$ et en demandant le déchiffrement du nouveau chiffré.

A.2.3 Signature numérique

La signature numérique permet de garantir l’intégrité d’un message sans utiliser de clé secrète partagée entre l’émetteur et le destinataire. Elle permet également d’assurer une authentification forte de l’émetteur du message en empêchant ce dernier de nier par la suite avoir envoyé le message ; on parle de propriété de non-répudiation.

La signature est un mécanisme asymétrique qui peut donner l’impression d’avoir de nombreuses similitudes avec le chiffrement à clé publique. Signature et chiffrement ne doivent cependant surtout pas être confondus. Le principal point commun est l’emploi de bi-clés formées d’une clé privée et d’une clé publique associée. La clé privée permet de générer la signature d’un message sous la forme d’une donnée qui lui est accolée³, à la manière des MAC vus dans l’annexe A.1.2. Afin de vérifier la validité d’une signature, il suffit de disposer de la clé publique. Par conséquent, tout le monde peut potentiellement s’assurer de l’authenticité d’un message puisque la clé publique peut être librement rendue disponible. Ceci réalise donc une version électronique de la signature manuscrite classique, avec des garanties de sécurité plus fortes encore. Notons cependant qu’ici encore la certification de la clé publique est un problème crucial qui est abordé rapidement ci-dessous dans l’annexe A.4 consacrée à la gestion de clé.

Comme pour le chiffrement, la mise en forme à appliquer au message avant signature est très importante en termes de sécurité. Elle utilise souvent une fonction de hachage transformant un message de longueur quelconque en une empreinte de taille fixe et petite.

Il a pu arriver par le passé qu’on présente la signature numérique comme une sorte de réciproque du chiffrement asymétrique. Ceci provient du fait que dans le cas de RSA, souvent présenté comme illustration, chiffrement et signature sont en effet très proches, la signature d’un message s’apparentant fortement à l’opération de déchiffrement. Ce cas est cependant exceptionnel. La grande majorité des mécanismes de signature ne peuvent être utilisés à des fins de chiffrement.

Notions de sécurité. Les mécanismes de signature admettent plusieurs notions de sécurité pertinentes. La notion de base est la sécurité en contrefaçon, qui garantit qu’aucun adversaire ne peut produire une signature pour un nouveau message de son choix, en ayant accès à des couples (message, signature) de son choix ainsi qu’à la clé publique correspondante. Il existe des variantes, mais toutes restreignent l’adversaire, par exemple en lui imposant un message pour lequel contrefaire une signature, et sont par conséquent moins intéressantes.

On peut au contraire relâcher la condition précédente en autorisant un adversaire à produire une signature valide différente pour un message déjà signé. Dans ce cas, on parle de sécurité forte en contrefaçon. Cette notion est nécessaire pour éviter la rejouabilité dans de nombreux protocoles.

Une ligne de recherche récente [14, 16, 17] considère trois notions supplémentaires et orthogonales aux notions précédentes.

La notion de propriété exclusive garantit qu’aucun adversaire ne peut produire deux clés publiques différentes, une signature et un message, de telle sorte que la signature soit vérifiée pour le message sous les deux clés publiques. Cette notion participe à la non-répudiabilité de la signature, en garantissant qu’un signataire ne puisse pas blâmer quelqu’un d’autre pour une signature qu’il a produite.

La notion de signature liée au message garantit qu’aucun adversaire ne peut produire une clé publique, une signature et deux messages, de telle sorte que la signature soit vérifiée sous la clé publique pour les deux messages. Cette notion participe aussi à la non-répudiabilité de la signature, en garantissant qu’un signataire malhonnête ne peut pas interchanger le message qu’il signe avec un autre.

La notion de non-resignabilité garantit qu’aucun adversaire ne peut produire une paire (clé publique, signature) vérifiant la condition de victoire dans la situation suivante. Un message est choisi aléatoirement, puis signé. L’adversaire reçoit alors la clé secrète, la signature, mais pas le message, seulement certaines informations dessus. L’adversaire gagne si la signature qu’il produit est vérifiée pour le message caché sous la clé publique qu’il produit. Cette notion permet l’authentification du signataire d’un message, lorsque celui-ci est assimilable à un secret partagé entre deux entités.

A.2.4 Authentification asymétrique d’entités et établissement de clé

Les mécanismes de cryptographie asymétrique présentés dans les sections précédentes peuvent être utilisés dans le cadre d’authentification d’entités. Afin d’authentifier une personne dont on connaît avec certitude la clé publique, il suffit par exemple de chiffrer à son attention un message quelconque suffisamment long et de lui demander de retourner ce message clair. De même, on peut lui demander de signer un tel message et ensuite vérifier la validité de cette signature.

Il existe cependant des mécanismes spécifiquement conçus pour le cadre interactif. Ces primitives dites « à divulgation nulle de connaissance » ou « zero-knowledge », bien qu’encore peu utilisées en pratique, sont à la source de la plupart des mécanismes de signature numérique. On citera par exemple le standard de signature américain DSA (« digital signature algorithm »), qui présente une certaine parenté avec le protocole d’authentification de Schnorr.

Par ailleurs, notons qu’une variante symétrique de ce principe existe, dans lequel une première entité partageant une clé symétrique avec une deuxième entité génère un message aléatoire, l’envoie à cette dernière et lui demande de fournir un MAC valide du message sous la clé secrète.

La cryptographie asymétrique permet également de résoudre le problème de la confidentialité dans l’établissement de clé, qui consiste pour deux entités ne partageant initialement aucun secret commun à se mettre d’accord sur une valeur de clé secrète.⁴ La sécurité de l’établissement de clé est un problème délicat, car celui-ci doit se faire à l’aide d’un canal non sécurisé, c’est-à-dire potentiellement écouté voire entièrement contrôlé par un attaquant. L’article fondateur de W. Diffie et M. Hellman [15] décrivait d’ailleurs principalement une solution au problème d’établissement de clé ; le protocole résultant est ce que l’on appelle encore aujourd’hui l’« échange de clé de Diffie-Hellman ».

Techniquement, la remarque fondamentale de W. Diffie et M. Hellman est que, lorsque l’on utilise une structure mathématique dans laquelle le calcul de logarithme discret est difficile, on peut facilement choisir un grand entier secret $a$ et publier $x^{a}$ sans que $a$ ne puisse être retrouvé par quiconque. Ainsi, afin que deux interlocuteurs notés A et B se mettent d’accord sur un secret commun $K$ , il suffit que A choisisse un entier $a$ et transmette $y = x^{a}$ , que B choisisse un entier $b$ et transmette $z = x^{b}$ . A peut alors calculer $K = z^{a} = (x^{b})^{a} = x^{ab}$ et B peut faire de même en calculant la même valeur $K = y^{b}$ . Par contre, un attaquant qui écoute passivement la communication ne peut apprendre que $y$ et $z$ ; à ce jour on ne connaît pas de méthode plus efficace que le calcul de logarithme discret pour retrouver les secrets $a$ et $b$ afin d’en déduire le secret partagé $K$ .

Notons cependant que ce protocole élémentaire ne permet pas de garantir la sécurité face à des attaquants actifs pouvant modifier les communications. Il ne garantit également aucune forme d’authentification des interlocuteurs. Une attaque connue sous le nom d’attaque par le milieu permet en effet à un attaquant actif de mettre en défaut la sécurité de l’échange de clé de Diffie-Hellman.

En pratique, les mécanismes d’authentification et d’établissement de clé sont généralement utilisés de concert en pratique car, d’une part, établir une clé entre deux personnes ignorant l’identité de leur interlocuteur a peu d’intérêt et, d’autre part, une simple authentification apporte peu. Le lien entre authentification et établissement de clé doit cependant être réalisé avec soin : il est nécessaire que les deux mécanismes soient imbriqués si l’on souhaite éviter des scénarios tels que l’attaque par le milieu. Un mécanisme d’authentification totalement décorrélé de l’établissement de clé ne protégerait pas le système contre les attaques par le milieu, que ’authentification soit mise en œuvre avant l’établissement de clé ou bien après l’établissement de clé — sur un canal chiffré à l’aide des clés établies au moyen de ce dernier.⁵

A.2.5 Sécurité des primitives asymétriques

La cryptographie moderne a développé des techniques de preuve de nature mathématique afin de tenter de prouver la sécurité des primitives, notamment asymétriques. Ces preuves n’ont pas un caractère absolu mais reposent avant tout sur un modèle de sécurité formalisant les propriétés attendues de la primitive ainsi que les capacités supposées de l’attaquant contre lequel on veut se prémunir.

Ces preuves sont dites « par réduction » au sens où elles vont ramener la sécurité globale d’une primitive à une hypothèse bien identifiée telle que « factoriser des modules RSA de 2048 bits n’est pas possible⁶ ». Les preuves en clé publique n’assurent ainsi jamais une « sécurité inconditionnelle » — c’est-à-dire face à un attaquant de puissance infinie.⁷ Elles offrent au contraire le plus souvent une « sécurité calculatoire », c’est-à-dire l’assurance qu’il est impossible d’attaquer une certaine propriété du mécanisme sans résoudre un certain problème mathématique.

Afin d’illustrer l’importance mais également la difficulté de définition d’un modèle de sécurité, prenons la signature comme exemple. On peut tout d’abord considérer divers types d’attaques, selon les capacités de l’attaquant, qui peuvent aller de la simple connaissance de la clé publique de vérification de signature à la capacité d’obtenir la signature de n’importe quel message de son choix. On peut également s’interroger sur la définition même de ce que l’on entend par succès d’une attaque. Cela peut aller de la simple « contrefaçon existentielle », consistant à réussir à générer une signature valide d’un message non maîtrisé, à un « cassage total », consistant à retrouver la clé privée de signature.

Il existe deux types de sécurité, comme mis en avant la première fois par M. Bellare et Ph. Rogaway [6] : la sécurité « asymptotique » et la sécurité « exacte ». Quand la première se contente d’assurer que le mécanisme est sûr pour des paramètres « assez grands », la seconde énonce clairement des estimations de la difficulté de l’attaque en fonction de la difficulté du problème. Ainsi, il est très important de prendre en compte les résultats qu’apportent la preuve, et de ne pas s’arrêter au fait que le mécanisme est sûr pour des paramètres assez grands. Pour être plus précis, la sécurité exacte conduit à ce que l’on appelle des réductions fines (dans lesquels la difficulté du cassage du mécanisme est de l’ordre de la difficulté du problème mathématiques) et des réductions lâches (dans lesquels il est plus facile — d’un ordre de grandeur non négligeable — de casser le mécanisme que de résoudre le problème). On voit ainsi que les mécanismes à préférer sont ceux apportant les réductions les plus fines possibles, car les autres mécanismes nécessitent de plus grandes clés et paramètres pour une même garantie de sécurité. De même, s’il n’est pas possible de sélectionner un mécanisme avec une réduction fine, il faut dans ce cas utiliser les coefficients de finesse donnés par la preuve pour en déduire les tailles de paramètres et de clés adéquats. Ceci permet de conserver une signification à la garantie de sécurité offerte par la preuve.

Il est clair qu’une primitive asymétrique prouvée sûre, relativement à une hypothèse bien identifiée et raisonnable, est d’autant plus intéressante que l’on a pris en compte des attaquants puissants et des définitions de succès d’attaque modestes dans la preuve. Tout comme pour la sécurité du chiffrement symétrique, vue en annexe A.1.3, les modèles de sécurité utilisés en cryptographie moderne peuvent paraître excessifs mais l’expérience montre que c’est loin d’être le cas et qu’il est important de se placer dans ce cadre contraignant afin d’évaluer correctement les primitives.

L’usage veut que l’on réserve le terme de clé secrète aux applications symétriques et le terme de clé privée aux applications asymétriques. ↩
Ainsi, si 256 bits de clés sont largement suffisants pour la cryptographie symétrique, un module RSA de 256 bits peut être factorisé sur un simple ordinateur en moins d’une heure. ↩
Plus exactement, le mécanisme consistant à calculer une signature et à l’ajouter au message est appelé « signature avec appendice ». D’autres techniques permettant d’économiser un peu de place sont envisageables avec des mécanismes tel que RSA utilisant une permutation à trappe. Ceci n’a cependant que peu d’importance en première approche. ↩
Cette clé secrète pouvant par exemple par la suite être utilisée pour chiffrer des messages. ↩
Dans le premier cas, il suffirait en effet à un attaquant d’attendre le succès de la phase d’authentification pour mettre en œuvre une attaque par le milieu. Dans le second cas, il lui suffirait de réaliser une attaque par le milieu contre le mécanisme d’établissement de clé, puis de relayer sur les canaux chiffrés ainsi établis les messages du protocole d’authentification entre ces entités. ↩
En un temps raisonnable. ↩
La puissance étant ici la mémoire et la puissance de calcul. ↩