Préambule

Il y a quelques temps, 3 ans si mes souvenirs sont bons, j'ai publié des vidéos sur la cryptographie et les outils mathématiques se cachant derrière. Je ne m'étais attaqué qu'aux cryptosystèmes "traditionels" (RSA/AES/ECC) et je n'avais pas trouvé le temps de publier quelque chose à propos de la cryptographie post-quantique, oui en vrai j'ai eu la flemme.

Donc enfin voilà un contenu sur la cryptographie post-quantique. Non pas une vidéo, mais un blog-post. Je vais essentiellement me concentrer sur les mécanismes de chiffrement asymétrique, donc à clé publique, dans cet article. Je vais très peu aborder le cas des mécanismes de signatures.

Comme toujours, je ne suis ni-mathémticien, ni un super-expert du chiffrement, donc si vous voyez une boulette dites le moi. Par contre si vous voyez des simplifications, pas la peine c'est normal c'est le but de cet article !

Avertissements

Cette article a été écrit sur un "coin de table" hors heures ouvrées donc ... attendez-vous à quelques coquilles et "pétages de plombs".

Néanmoins il est là pour faire de la vulgarisation et donner quelques pistes et je pense que ça passe encore.

Je suppose tout de même que vous connaissez la base, ou au moins de loin:

  • La base de la crypto
  • RSA/ECC/DH
  • Les ensembles
  • Les vecteurs
  • Les polynômes

Agenda

  • Pourquoi la cryptographie post-quantique
  • Les grandes "familles" de cryptographie post-quantique
  • La description de ces 5 grandes familles
  • L'algorithme sélectionné par le NIST
  • Et le chiffrement symétrique ?

La cryptographie post-quantique: pourquoi ?

Comme vous le savez certainement, si vous le savez, les mécanismes de cryptographie "traditionels" à clé publique reposent sur le faite que les calculs demandé pour pouvoir eventuellement les casser sont très compliqués:

  • RSA repose sur le fait que factoriser de grands nombres est compliqué
  • ECC repose sur le fait que résoudre le problème des logarithmes discrets sur les courbes elliptiques est compliqué

Hors l'arrivée de l'informatique quantique change légèrement la donne car il semblerait que la compléxité de résolution de ces problèmes soit grandement duminuer avec les ordinateurs quantiques et certains algorithmes pouvant être utilisé sur ces derniers.

Voilà pourquoi il est nécessaire de passer à la cryptographie post-quantique.

Les grandes "familles" de cryptographie post-quantique

Nous allons voir dans cet article les grandes "familles" de la cryptographie post-quantique, à savoir:

  • Lattice-based cryptography
  • Code-based cryptography
  • Multivariate polynomial cryptography
  • Supersingular elliptic curve isogeny cryptography
  • Quantum key distribution

Allez commençons joyeusement avec la Lattice-based cryptography !

Lattice-based cryptography

Introduction

Alors déjà qu'est ce que ça veut dire lattice-based cryptography ?

Si on traduit cela en Français nous obtenons: cryptographie basée sur le treillis/les réseaux. Avec ça nous sommes bien avancés n'est-ce pas ?

Je vous rassure rien à voir avec un quelconque camouflage militaire, mais avec des maths: jetez un oeil à cette page wikipedia. Et dans le monde merveilleux de l'algèbre il va y avoir des problèmes liés aux treillis qui vont être très compliqué à résoudre pour nos chers ordinateurs quantiques.

Nous avons donc essentiellement deux gros problèmes qui peuvent être utilisé dans la lattice-based cryptography:

  • Shortest Vector Problem
  • Learning With Errors

Shortest Vector Problem

Spoiler: mes graphs sont nuls, approximatifs et moches. C'est juste pour faire passer l'idée.

Voici donc une lattice avec sa base:

Le but de SVP est de trouver le plus petit vecteur non nul dans cette lattice:

Cela paraît tout simple comme cela mais en réalité ce genre de problème ne possède pas d'algorithme réellement efficient pour trouver facilement et rapidement ce genre d'information. En soit la difficulté de calcul pour effectuer ceci est hors de portée, y compris pour un ordinateur quantique.

C'est bien beau tout cela mais comment on s'en sert ?

Alors en soit pour du SVP la procédure générale est la suivante:

  1. On génère les clés:
    1. Le choix des paramètres: en soit on choisi les dimmensions de la lattice, les modulos, quelques paramètres de sécurité et la "distribution des erreurs"
    2. On génère la lattice: donc x points sur n dimensions et des vecteurs qui la compose. Le tout est représenté sous forme de matrice (oui nous sommes en algèbre pas en géométrie)
    3. On sélectionne la base de la lattice, donc en gros un ensemble de vecteur (voir le schéma plus haut)
    4. On génère la clé publique pour cela:
      1. On choisi ce que j'apellerais "une sous-base" de notre lattice ce qui forme en soit un lattice de dimension plus petite que notre lattice originale
      2. On rajoute du "bruit", des données qui rendent la compréhension un peu plus compliqué
    5. On génère la clé privée:
      1. De même on extrait une nouvelle base mais ce coup-ci pour former une lattice de dimension plus importante
      2. On effectue quelques transformations
  2. On a nos clés donc on peut:
    1. Chiffrer
    2. Déchiffrer

Je sais cela semble encore un peu obscure sans doute.

Mais pas de panique, je vais faire un petit cas pratique dans peu de temps.

De plus je me rends compte que j'ai peut-être été un peu loin dans l'explication de SVP, mais bref, passons donc à LWE l'autre méthode des lattice-based. Et vous me dites, ce n'est pas encore clair, mais attendez un peu cela va venir.

Learning With Errors

Je vais faire beaucoup plus simple pour celui-ci.

  • On choisi des paramètres comme la dimension n de la lattice, une deviation standard
  • On choisi un secret s: un vecteur de longueur x ... oui un entier quoi :)
  • Pour la clé publique:
    • On génère une matrice A
    • On choisi un nombre premier q
    • On génère une matrice "d'erreur" e de même taille
    • On génère une matrice B avec: B[i] = (A[i] * s + e[i]) % q
    • A et B sont notre clé publique
  • Pour chiffrer des une message M on prend des"parties" de A et B (que je vais appeler Ap et Bp) et l'on fait:
    • u = SOMME(Ap) % q
    • v = (SOMME(Bp) + (q/2) * M) % q
    • (u,v) c'est notre message chiffré
  • Pour déchiffrer:
    • M = (v - su) % q

NTRUEncrypt

NTRUEncrypt est une implementation du Shortest Vector Problem.

Voici donc comment cela fonctionne:

  • Vous prenez N un nombre premier
  • Vous prenez p et q deux entiers tel que gcpd(p,q) = 1
  • On choisi deux polynômes f et g il faut que f soit inversible: je vous invite à regarder mes anciennes vidéos sur la crypto si vous avez des questions la dessus, et de même je vous passe des détails sur la sélection de f et g
  • On calcule les inverses de f modulo p et modulo q (Fp et Fq)
  • Ensuite on calcule h = p * Fq * g % q
  • Votre clé publique c'est h
  • Votre clé privée c'est (f, Fp, g)
  • Pour chiffrer un message M
    • on choisi un polynôme r (encore une fois je vous passe des détails)
    • on fait: cyphertext: C = r * h + M % q
  • Pour déchiffrer c'est un peu plus compliqué:
    • On calcule: a = f * c % q
    • On a ensuite Fp * a = M % p voilà on peut retrouver M (de même je vous ai épargné des détails)

Passons maintenant à la Code-based cryptography.

Code-based cryptography

Sur celui on va aller vite car au final, peu d'implémentation retenue sur ce dernier, mais en soit ça semble intéressant.

En soit le but dans pour ce type de chiffrement c'est d'utilisé des fonctionnalités de code correcteurs d'erreurs ... kesako ? Mais si je suis sur que vous en avez déjà entendu parler !

Et clairement là j'ai un retour de flemme :)

Rapidement en théorie, au lieu de jouer avec des vecteurs et des polynômes vous allez jouer avec des code correcteurs (Goppa, ...) en sortir une matrice, générer d'autres matrices de tailles définie et de différents formats.

Votre clé publique (P), la plupart du temps, sera le produit de ces matrices et votre secret, bah ce sont les matrices en elle-mêmes (Mgoppa, Ma, Mb).

Pour chiffrer un message M vous allez trouver un chiffre e qui correspond à un vecteur d'erreur et vous allez faire c = MP + e

Pour récupérer le message en clair il faut faire: c' = c * Mb^(-1) puis c'' = c' * Mgoppa ^(-1) -- la au fait vous faites la correction des erreurs, puis enfin M = c'' * Ma ^(-1)

Je vous laisse donc découvrir l'article wikipedia du plus connus d'entre eux et de vous faire une idée de pourquoi on ne l'utilise pas. Et c'est bien dommage mais cela a trop d'inconvénients. C'est un peu différent de ce que j'ai décrit plus haut mais l'idée reste la même

Multivariate polynomial cryptography

Alors celle-ci est déjà plus facile à décrire dans un blog-post écrit sur plusieurs sans taper trop fort sur le clavier pour ne réveiller personne (surtout pas les chiens au fait).

Alors tout ce dont je vais parler se passe dans un corps fini (j'avais déjà expliqué ça dans mes vidéos sur la crypto et vous savez ... la flemme de faire un paté sur les corps fini quoi).

La sécurité de ce type de chiffrement repose sur le fait que trouver l'inverse d'un ensemble de polynômes est très compliqué, y compris pour un orginateur quantique.

Il y a deux méthodes possibles visiblement:

P et son inverse

Donc en gros pour générer une paire de clé il vous faut: un ensemble de polynômes et leurs inverses donc:

P(x1, ...., xn) = (P1(x1,....,xn),...,Pi(x1,...,xn)) et son inverse P'

Pour chiffrer vous résolvez P(M) pour déchiffrer P(C)

La méthode TPS (je ne sais pas comment l'appeler réellement)

Pour celle-ci il vous faut :

  • Un petit polynome facilement inversable P
  • Deux transformations affines T et S
  • Votre clé privé c'est (T,P,S) ou (t^(-1),P^(-1),S^(-1)) mais bon en gros si on a T,P,S vous êtes foutus aussi
  • Votre clé publique P'=T(P(S(.)))
  • Pour chiffrer: C = P'(M)
  • Pour déchiffrer M = S^(-1)(P^(1-)(T^(-1)(C)))

Alors est-ce que c'est utilisé ?

En soit oui, surtout pour de la signature, pas de chance j'ai dis que je n'en parlerais pas, mais pas de sélection par le NIST pour ces derniers en vue :(.

Supersingular elliptic curve isogeny cryptography

Avec un nom pareil, on dirait les séries américaines quand elles sortent pleins de termes techniques les uns avec les autres pour faire classe ... Déjà tu vois le titre tu sais que ça va très mal se passer. Allez hop suivant !

Non je rigole, mais à ce moment de l'article je dois vous avouer que ce que j'avais déjà regardé depuis quelques temps concernant la crypto next-gen c'était NTRU et Quantum Key Distribution, mais bon, je me suis dit que j'allais écrire cet article donc go.

Alors en plus celui-ci est déjà utilisé dans des implémentation de Diffie-Hellman par Microsoft.

Comme toujours il repose sur la grande difficulté à résoudre certains problèmes, même pour un ordinateur quantique.

Donc ici on parle de morphisme, de courbes elliptiques et de ... supersingularité :).

Vraiment celui-ci c'est du costaud à appréhender et comme je veux faire de la pseudo-vulgarisation ce n'est vraiment pas évident: oui simplifier un concept que tu ne maitrises pas pour le coup c'est compliqué, et je dois dire que les papiers que j'ai lu sur le sujet étaient soit trop long (mais super détaillé), mais bon je fais ça à côté hein ... soit court, mais SUPER trop matheux pour moi. Si vous savez les papiers qui commencent par: donc voici 1 + 1 = 2, puis voici une courbes elliptiques (bon ça va encore) et d'un coup ça part en vrille sans échauffement. Bah cela oui je me les suis tapés.

Bref fin du pétage de plomb, c'est reparti !

En soit la solidité de ce mécanisme repose sur les caractéristiques mathématiques des courbes elliptiques supersingulières.

Mais pour simplifier, un MAX, les courbes elliptiques supersingulières ont, en autres particularités, un nombre de points fini défini sur un champ fini. L'isogeny quand à elle c'est une fonction qui prend un point sur une courbe elliptique et le mappe à un autre point sur une autre courbe elliptique, en préservant certaines propriétés.

En gros si vous avez deux courbes elliptiques E et E', il est très difficile de calculer la relation isogenie Phi entre eux. C'est sur ce principe que se repose la Supersingular elliptic curve isogeny cryptography.

Donc basé sur cela, généralement la clé privée est un entier, et la clé publique on applique la relation d'isogénie, plusieurs fois souvent, entre la valeur de la clé privée et les caractéristiques de courbes elliptiques choisies.

Du coup on s'en sert ou de ça ?

Très bonne question, en soit:

  • SIDH (Supersingular Isogeny Diffie-Hellman)
  • SIKE (Supersingular Isogeny Key Encapsulation)
  • Supersingular Isogeny Signature Scheme (SISS)

Quantum key distribution

Enfin la dernière partie "théorique" de cet article et sans doute à mes yeux la plus intéressante. Le QKD, la cryptographie quantique au fait, pas du tout poste quantique.

Alors là par contre pas de code pour l'implémentation, c'est de l'application de la physique/mécanique quantique.

Deux propritétés sont super-importantes:

En se basant sur ces faits il est impossible d'écouter un échange de ce type sans être détecté (enfin si l'installation est bien faite).

Donc si on prend Alice est Bob:

  • Alice génère des qubits (photons, état quantique particulier de certaines particules)
  • Alice envoie les informations à Bob (via fibre ou comme les chinois liaisons sattelites dédiées)
  • Bob mesure ce qu'il "reçoit"
  • Alice et Bob compare leurs résultats et peuvent ainsi détecter si quelqu'un a intercepté la communication
  • Si ce n'est pas le cas tout est bon.

L'algorithme sélectionné par le NIST

Et voici l'algorithme choisi par le NIST pour ce qui est du chiffrement à clé publique: CRYSTALS-Kyber. Et il est basé sur: lattice/LWE essentiellement.

Comment tester des algos post-quantique ?

Pour le moment très peu d'implémentation, néanmoins l'Open Quantum Safe propose un provider pour OpenSSL 3.x.

Et le chiffrement symétrique ?

Il semblerait que l'algorithme de Grover puisse mettre en danger AES-128, mais que AES-256 soit toujours safe.

Enfin du moins le AES-256 "propre" ceux ou la clé est généré à partir d'un mot de passe certaines implémentation sont peut-être à risque.

Conclusion

Quand on voit que l'on trouve encore du TLS 1.1 ou des cyphersuites dangereuses on se dit que l'on est loin de voir le post-quantique déployé partout.

De même l'informatique quantique n'est pas encore disponible à grande échelle, donc pas de panique non plus.

 

Enjoy et à la prochaine.

Legal

Voilà, ce texte est bien sûr en license CC BY-SA 4.0 (legal)

Les images de type mémes ont été générées avec memegenerator.