Cryptographie à l’ère quantique

Par Jérémie Gagnon-Bischoff et Olivier Rousseau

Il devient de plus en plus évident que l’avènement des technologies quantiques changera l’approche cryptographique qui prévaut depuis de nombreuses années. En effet, l’information quantique introduit de nombreuses possibilités, certaines portant atteinte à la sécurité des protocoles utilisés de nos jours et d’autres ouvrant la porte à de nouveaux protocoles cryptographiques plus sophistiqués et sécuritaires. Ce sujet est d’une importance cruciale; par exemple, lorsque nous utilisons Internet, des algorithmes de cryptographie sont utilisés à tout moment pour établir des connexions sécurisées, que ce soit pour accéder à notre compte bancaire ou envoyer des renseignements personnels.

Le texte suivant vise à vulgariser les enjeux de quatre axes de cette thématique. Simultanément, cette page sert aussi d’introduction à une série de notebooks Python développée par CyberQuébec afin d’aborder les aspects techniques de ces quatre axes. Pour ce faire, les notebooks alternent textes et capsules de code. Significativement plus techniques que ce texte, ils sont écrits pour un auditoire spécialisé, ayant un bagage en mathématiques et en programmation.

Liste de notebooks selon les quatre axes:

• les algorithmes cryptographiques standards utilisés à l’heure actuelle
  • RSA (Factorisation de grands nombres entiers).
  • Générations de grands nombres premiers
  • ECC (Cryptographie par courbe elliptique)
  • AES (Cryptographie symétrique par blocs)
  • SHA-256 (Fonction de hachage cryptographique)
• les algorithmes quantiques qui mettent en jeu la sécurité des algorithmes cryptographiques standards
  • Algorithme de Shor (Factorisation de nombres)
  • Algorithme de Grover (Algorithme quantique de recherche)
• les algorithmes cryptographiques post-quantiques proposés pour faire face à l’émergence de l’informatique quantique
  • Algorithme de base (GGH) (Cryptographie par treillis)
  • NTRU (Polynômes tronqués)
  • Notebook sur le problème LWE (Apprentissage avec erreurs, problème de base)
  • CRYSTALS-KYBER & SABER (LWE avec des polynômes tronqués) – Notebook en cours de construction
  • McEliece (Cryptographie par code correcteur d’erreur) – Notebook en cours de construction
• la cryptographie par distribution de clés quantiques (QKD)
  • Protocole BB84 (2D)

Note: Dans chaque notebook, on présente des rudiments de théorie et des exemples de programmes qui les mettent en pratique, dans un but pédagogique. Les cellules de code sont des implémentations “maison” des algorithmes et des preuves de concept. Il ne s’agit pas d’avoir l’implémentation la plus efficace ou la plus réaliste, mais simplement de montrer les mécanismes derrière le sujet discuté. Dans chaque notebook, vous pouvez modifier le code et l’exécuter pour faire des essais (ceci requiert un compte Google). Vous pouvez également faire des copies des notebooks dans votre suite Google pour les modifier à votre guise.

Ce travail est en constante évolution. Par conséquent, les différents notebooks peuvent contenir des erreurs et pourraient bénéficier de compléments d’information. S’il-vous-plait, faites-nous part de vos commentaires! Pour rapporter toute erreur/coquille ou pour envoyer des commentaires/suggestions, écrire à l’adresse courriel [email protected].

Introduction

Pour bien comprendre les enjeux entourant cette situation, il faut faire la distinction entre deux types d’algorithmes cryptographiques: les algorithmes symétriques et les algorithmes asymétriques (ou à clé publique). Dans un algorithme symétrique, les deux entités voulant communiquer ont en leur possession une clé secrète commune qui est utilisée par l’une d’elle pour chiffrer le message et par l’autre pour le déchiffrer une fois reçu. Le hic, c’est que pour utiliser un tel protocole, les deux parties doivent connaître cette clé secrète. Ainsi, à moins de l’avoir échangée à l’avance en personne, il faut un moyen sécurisé de s’envoyer la clé pour ensuite utiliser un tel protocole.

Entrent alors en jeu les algorithmes asymétriques. Dans un tel protocole, une entité A divulgue une clé publique qui peut être connue de tous, et garde une clé privée associée qu’elle ne divulgue pas. Une entité B peut alors utiliser cette clé publique pour crypter une information. Elle renvoie alors cette information à A sur un canal public, et A décrypte l’information à l’aide de sa clé privée. En général, un tel protocole n’est pas efficace pour envoyer un message arbitraire; son utilité est plutôt de communiquer une clé secrète commune entre deux parties voulant communiquer. C’est la méthode la plus commune: deux entités s’envoient une clé secrète à l’aide d’un algorithme asymétrique, et elles utilisent par la suite cette clé commune dans un algorithme symétrique pour s’envoyer l’information confidentielle.

Dans un algorithme asymétrique, la clé publique et la clé privée sont liées. Ainsi, en théorie, la diffusion de la clé publique donne à tous une certaine information sur la clé privée. En pratique, la sécurité de ces algorithmes vient du fait qu’ils sont conçus tel que le lien entre la clé publique et la clé privée est un problème mathématique très difficile à résoudre, à un tel point que même les ordinateurs les plus puissants ne peuvent les résoudre dans un temps réaliste à l’échelle humaine.

Ainsi, toute la sécurité des algorithmes asymétriques, et par conséquent la méthode standard de communication sécurisée, repose sur le fait que la technologie actuelle n’est pas assez puissante pour résoudre certains problèmes mathématiques dans un temps réaliste.

L’information quantique, un domaine en pleine effervescence, vient changer la donne. En effet, des démonstrations théoriques montrent que les ordinateurs quantiques peuvent résoudre certains problèmes mathématiques de manière significativement plus rapide que les ordinateurs classiques auxquels nous sommes habitués. De plus, il se trouve que les calculs entrant en jeu dans les algorithmes asymétriques standards figurent justement sur cette liste. Ainsi, l’existence d’ordinateurs quantiques assez puissants compromettrait fortement la sécurité de la cryptographie actuelle.

Jusqu’à récemment, la fabrication d’ordinateurs quantiques d’une telle puissance semblait être un défi technologique qui ne serait pas réalisé dans un futur proche. Toutefois, les avancées techniques des dernières années démontrent que ces ordinateurs sont plus proches qu’on l’avait pensé. Ces avancées ont poussé l’institut des standards américain (NIST) à lancer en 2017 un concours pour trouver de nouveaux algorithmes asymétriques résilients à l’informatique quantique, qui seront appelés à remplacer les algorithmes actuels. Ces algorithmes utilisent des problèmes mathématiques pour lesquels on n’entrevoie pas à ce jour une méthode rapide de résolution, même sur des ordinateurs quantiques.

Un tour du sujet ne serait pas complet sans mentionner la distribution de clé quantique (QKD). Contrairement aux ordinateurs quantiques, cette technique utilise les principes de la mécanique quantique pour développer de nouvelle méthode de cryptographie pour envoyer de manière sécurisée des clés secrètes. De manière simplifiée, elle représente une alternative quantique “supérieure” aux algorithmes asymétriques pour la transmission de clés secrètes utilisées dans les algorithmes symétriques.

Algorithmes cryptographiques standards utilisés à l’heure actuelle

Symétrique vs asymétrique

Un grand nombre d’algorithmes existent pour chiffrer des transferts d’informations. Ils se déclinent en deux grands types :

• algorithme de chiffrement symétrique
• algorithme de chiffrement asymétrique (clé publique)

Dans un algorithme symétrique, lorsque deux entités A et B échangent des informations, ils ont une connaissance commune d’une même clé permettant d’encrypter et de décrypter le message.

Dans un algorithme asymétrique, A possède une clé publique et une autre qui est privée. B peut se servir de la clé publique, qui est visible de tous, pour encrypter son message. Une fois encrypté, seulement A peut le décrypter avec sa clé privée.

Une analogie fréquente est la suivante. Dans un algorithme d’encryption symétrique, A et B ont chacun la clé d’un même cadenas. A ou B peut fermer le cadenas sur une boîte et envoyer la boîte à l’autre qui pourra l’ouvrir avec sa clé. Dans un algorithme asymétrique, seul A possède une clé et il envoie à B un cadenas ouvert que seule sa clé peut ouvrir. B ferme la boîte avec le cadenas et la renvoie à A.

Les algorithmes symétriques sont les plus robustes à la casse et sont très efficaces en terme de temps d’exécution, en comparaison aux algorithmes asymétriques qui sont plus lents et moins adaptés à l’encryption de grandes quantités d’informations.

La principale difficulté d’utilisation d’un algorithme symétrique est le fait que A et B doivent partager une clé secrète. S’ils pouvaient se rencontrer au préalable en personne et échanger l’information sur la clé verbalement, le problème ne se poserait pas, mais comme tous les transferts de clés se font via des réseaux où n’importe qui peut intercepter l’information, l’encryption à clé publique est la façon privilégiée de faire ce transfert de clé.

Les algorithmes asymétriques fonctionnent tous selon le même principe : il se basent sur une opération mathématique qui est simple à faire dans une direction avec une information donnée (la clé publique), mais pour laquelle il est difficile de revenir en arrière, sauf si on a une information privilégiée (la clé secrète).

Prenons par exemple le protocole RSA (du nom de ses inventeurs Rivest, Shamir et Adleman), l’un des algorithmes asymétriques les plus connus. Ce protocole est basé sur le problème de la factorisation de grand nombres. Pour un nombre N=pq, le produit de deux nombres premiers p et q, factoriser N est le processus de retrouver les valeurs de p et q à partir de N. Il n’y a pas de procédé “efficace” connu pour réaliser ce calcul sur un ordinateur classique: pour de très grandes valeurs de N, les méthodes connues sont extrêmement lentes. Cette complexité est à la base du protocole RSA, où la clé publique est reliée à la clé privée par la factorisation d’un nombre. Toute la sécurité du protocole vient donc du fait qu’il est extrêmement difficile d’un factoriser un grand nombre.

Les différents algorithmes

Les principaux algorithmes symétriques sont :

• AES
• DES
• 3DES
• HMAC
• …

Les principaux algorithmes asymétriques sont :

• RSA : factorisation de grands nombres.
• ECC : problème de logarithme discret sur les courbes elliptiques.

Notebooks liés à ce sujet

• AES
• RSA
• Notebook discutant la génération de grands nombres premiers, qui est essentielle à l’algorithme RSA.
• ECC
• SHA-256 (Fonction de hachage cryptographique, concept qui n’est pas encore inclus dans ce texte de vulgarisation)

Algorithmes quantiques mettant en jeu la sécurité des algorithmes cryptographiques standards

La croyance populaire est qu’un ordinateur quantique serait beaucoup plus puissant et qu’il remplacera éventuellement les ordinateurs conventionnels. En fait, il se trouve qu’il est très compliqué de gérer des bits quantiques (qbits). Les ordinateurs ainsi créés auront très certainement un nombre de qbits très inférieur à un ordinateur conventionnel. De plus, dans un ordinateur quantique, il est plus difficile d’accéder à l’information, à cause des propriétés quantiques.

Par contre, pour certains problèmes spécifiques, les propriétés spéciales des qbits peuvent être utilisées pour résoudre un problème très difficile dans le cas classique. Ainsi; les ordinateurs quantiques sont plus adaptés à résoudre des problèmes très précis que pour un usage général. Il est donc probable que les ordinateurs quantiques ne soient utilisés que par de grandes entreprises ou états.

Il se trouve que l’un des problèmes que l’ordinateur quantique pourrait résoudre efficacement est la factorisation de grand nombres. L’algorithme quantique le plus connu, l’algorithme de Shor, sert à résoudre ce problème. Il doit sa popularité au fait qu’il fut le premier algorithme proposé permettant à des ordinateurs quantiques de résoudre un problème plus efficacement que les ordinateurs classiques. De plus, sa publication a été la première preuve concrète que les ordinateurs quantiques représentent une menace à la sécurité de certains algorithmes asymétriques standards. En effet, dans son article pionnier de 1996, Shor a également démontré qu’une variante de son algorithme résout le calcul des logarithmes discrets, ce qui brise aussi le protocole ECC.

Un autre problème où l’ordinateur quantique excelle est la recherche de solutions dans un espace de recherche (comme une base de données) sans structure. Pour résoudre cette question, la meilleure option pour un ordinateur classique est de parcourir l’espace de recherche en essayant les solutions une à la suite de l’autre. Éventuellement, cet algorithme tombera assurément sur la solution, mais cette méthode n’est vraiment pas efficace. À l’opposé, un ordinateur quantique peut utiliser l’algorithme de Grover pour arriver à la solution beaucoup plus rapidement. À terme, ceci pourrait causer un problème à la cryptographie symétrique puisqu’un tel ordinateur améliorerait drastiquement les attaques par force brute, qui correspondent à essayer toutes les clés secrètes possibles.

En bref, lorsque les défis technologiques à la fabrication d’ordinateurs quantiques de taille raisonnable seront surmontés, ceux-ci briseront les méthodes standards de cryptographie actuelles utilisées à grande échelle. Il est toutefois important de noter que le danger posé par les ordinateurs quantiques est beaucoup plus grand du côté de la cryptographie asymétrique actuelle. Dans des cas comme RSA et ECC, l’algorithme de Shor pourrait rapidement calculer la clé privée à partir de la clé publique. À l’opposé, le danger posé par les ordinateurs quantiques à la cryptographie symétrique est pour l’instant plutôt faible: l’accélération de la puissance calculatoire par l’algorithme de Grover, bien que significative, ne sera pas suffisante pour briser en un temps raisonnable les plus grandes clés cryptographique utilisées à ce jour, comme AES-256. Ainsi, les efforts pour protéger la cryptographie de la menace quantique visent surtout les algorithmes asymétriques.

Notebooks liés à ce sujet

• Factorisation à l’aide de l’algorithme de Shor
• Recherche de solutions dans un ensemble de données avec l’algorithme de Grover

Algorithmes cryptographiques post-quantiques proposés pour faire face à l’émergence de l’informatique quantique

Le développement d’ordinateurs quantiques progresse relativement rapidement. Alors qu’il y a quelques années, les scientifiques doutaient encore de la possibilité de construire de tels ordinateurs dans un futur proche, les progrès récents nous montrent qu’il est possible que des ordinateurs quantiques de petite taille puissent faire leur apparition dans les décennies à venir. Il est donc d’une importance cruciale de modifier les méthodes actuelles de cryptographie à grande échelle en prévision de l’arrivée des ordinateurs quantiques d’une puissance significative.

Concours NIST

Aux États-Unis, NIST (National Institute of Standards and Technology) donne les balises cryptographiques aux institutions et celles-ci sont utilisées partout à travers le monde.

NIST a un document sur tous les standards cryptographiques et sur les façons de les utiliser : Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms

Les spécialistes évaluent qu’il faut s’attendre à ce qu’il y ait en 2030 des ordinateurs quantiques assez puissants pour briser RSA ou ECC (avec leurs paramètres actuels). NIST a donc lancé un concours international dans le but de trouver des remplaçants à ces deux algorithmes asymétriques. L’idée est de concevoir des techniques d’encryption à clé publique en faisant usage de problèmes mathématiques qui ne sont pas simples à résoudre même sur un ordinateur quantique.

En 2017, 59 algorithmes ont été soumis et après 3 tours de sélection, il reste maintenant 4 finalistes :

• Cryptographie de réseau (lattice-based cryptography), sous trois variantes :
  • NTRU
  • CRYSTALS-KYBER
  • SABER
• Code based : McEliece

Mais ils ont aussi identifiés certains candidats éliminés qui pourraient être quand même d’intérêt:

• Lattice : FrodoKEM, NTRU Prime
• Code-based : BIKE, HQC
• Supersingular Elliptic Curve Isogeny : SIKE

Voici le lien vers l’article officiel du NIST à ce sujet.

Notebooks liés à ce sujet

Lattice-based cryptography :

• Algorithme de base (GGH)
• NTRU

Les KYBER et SABER sont aussi “lattice-based”, mais utilisent plutôt le problème “Module learning with errors (MLWE)”.

• Notebook sur le problème plus simple LWE.
• CRYSTALS-KYBER & SABER – Notebook en cours de construction
• McEliece – Notebook en cours de construction

Cryptographie par distribution de clés quantiques (QKD)

La distribution de clé quantique (QKD – abrégé de Quantum Key Distribution) est une technique de cryptographie quantique. Elle consiste en une utilisation ingénieuse des lois de la mécanique quantique pour échanger une clé secrète entre deux observateurs. Sa force vient du fait qu’elle permet aux deux observateurs de vérifier avec une quasi-certitude si un imposteur a pu intercepter la transmission. Si c’est le cas, aucun mal n’a encore été causé: ils savent que la clé échangée n’est pas sécuritaire et donc il ne l’utilisent pas pour envoyer de l’information confidentielle. Autrement, ils possèdent une clé secrète commune qu’ils peuvent utiliser pour envoyer de l’information confidentielle sur un réseau publique à l’aide d’un protocole de cryptographie à clé symétrique.

Le but d’un protocole QKD est de permettre à une entité A d’envoyer à une identité B une clé sous la forme d’une suite de bits (une suite de 0 et de 1). On peut diviser le procédé en trois étapes. Tout d’abord, A envoie à B une suite de bits par l’entremise d’un canal quantique. Ensuite, A et B comparent une partie de leurs données sur un canal public pour vérifier si leur canal quantique était bel et bien sécuritaire, c’est-à-dire qu’une entité E n’y a pas intercepté la suite de bits. Ceci est possible par le fait qu’en vertu des lois de la mécanique quantique, E ne peut épier le canal quantique sans y laisser sa trace sur l’information échangée. Finalement, s’ils ont déterminé que leur échange n’a pas été intercepté, ils utilisent l’autre partie de leurs données (restée secrète) pour générer une clé secrète partagée. Cette clé peut ensuite être utilisée pour échanger confidentiellement un message sur un canal public à l’aide d’un algorithme à clé symétrique.

Plusieurs protocoles de QKD ont été inventés avec le temps (voir par exemple cette liste), utilisant des procédés de codification et des canaux quantiques différents. Le premier à avoir été proposé est le protocole BB84 (du nom de ses auteurs, Charles Bennett et Gilles Brassard, et de l’année de publication, 1984) et reste à ce jour le plus connu, vu son caractère pionnier et son utilisation simple des concepts clés du domaine.

Une question naturelle se pose: si la distribution de clé quantique est une méthode cryptographique si fiable, pourquoi n’est-elle pas plus répandue? La raison principale est qu’elle n’est pas simple à réaliser technologiquement dans un contexte arbitraire. En effet, elle nécessite un canal quantique stable et qui n’est pas sujet à un bruit (taux d’erreur de transmission de l’information) trop élevé. Dans les deux dernières décennies, de nombreuses équipes de chercheurs ont réussi à réaliser des protocoles QKD dans des contextes académiques. De plus, des dispositifs de QKD font tranquillement leur apparition dans le milieu commercial. Toutefois, cette nouvelle technologie requiert son infrastructure propre et est beaucoup plus exigeante en terme de ressources que les méthodes classiques. Ainsi, dans un futur proche, il est plutôt envisageable que cette technologie reste limitée à un usage spécialisé, tel que par des agences gouvernementales.

Notebooks liés à ce sujet

• Protocole BB84