Principes de la cryptographie asymétrique

La cryptographie symétrique est basée sur la division de gens en "amis" et "ennemis", les "amis" étant des personnes qui partagent une clé secrète.  La cryptographie symétrique est limitée dans ses applications par deux points essentiels: le fait que des amis doivent partager une clé secrète (se qui pose la question existentielle du canal sûr par lequel ils se partagent cette clé), et le fait qu'une fois des amis partagent cette clé, ils peuvent tous faire les mêmes choses, et ne peuvent donc pas être distingués entre eux.  En d'autres termes, si un MAC est généré avec une clé secrète, alors toutes les personnes en possession de cette clé auraient pu la générer.  Nous avons vu que cependant, la cryptographie symétrique a beaucoup d'applications utiles, mais il y a aussi des applications potentielles qui seront, de principe, impossible avec les techniques de la cryptographie symétrique.

Ces deux limitations sont exactement ce que peut transgresser la cryptographie asymétrique.  L'idée de base de la cryptographie asymétrique est qu'une clé secrète n'est jamais partagée, et reste dans la seule possession de la personne qui la génère.  Ainsi, le problème de la communication sûre d'une clé secrète n'existe plus, car il ne faudra jamais communiquer une clé secrète.  Et le deuxième problème, à savoir qu'une personne qui possède une clé ne peut pas être distinguée d'une autre personne qui possède la même clé, disparaît aussi, car personne n'a la même clé secrète.  La possession d'une clé secrète devient donc une preuve d'identité unique.  On peut voir le monde, en cryptographie asymétrique, comme "un seul ami" et le reste du monde, étant des ennemis pour chaque clé secrète.

Pour mettre cette idée en oeuvre, la cryptographie asymétrique est toujours basée sur la construction d'une clé secrète et une clé dite, publique associée.  Il y a une relation bijective entre la clé secrète et la clé publique, mais de telle façon, que le calcul de la clé publique de la clé secrète est facilement faisable, et le calcul dans l'autre sens n'est pas faisable dans la pratique (même si cette relation mathématique existe).  La clé secrète est, comme l'indique son nom, gardée secrète et n'est jamais partagée avec quelqu'un (même pas un "ami").  La clé publique, elle, est rendue publique et ne doit pas être protégée.

On lit, et on dit, souvent, que ce qui rend la cryptographie asymétrique possible, c'est ce qui est appelé des "portes à sens unique": une fonction mathématique qui peut être calculée facilement dans un sens, mais qui est dans la pratique impossible à calculer dans le sens inverse.  C'est à dire, v = f(u) est facilement calculable, mais u = g(v) n'a pas d'implémentation algorithmique connue qui est utilisable dans la pratique.  Dit comme cela, c'est faux, car la cryptographie symétrique est déjà basée sur plusieurs "portes à sens unique".  Un chiffrement par bloc, X = f(C,K) peut être inversé vers C comme C = g(X,K), mais la construction est telle qu'il est pratiquement impossible de trouver un algorithme qui inverse vers K: K = k(C,X).  Une fonction de hachage d'une donnée D avec le même nombre de bits que le hash H, H = h(D) est facilement calculé, mais D = u(H) est impossible à calculer dans la pratique.  Donc la cryptographie symétrique regorge déjà de "portes à sens unique".

Ce qui rend la cryptographie asymétrique possible, c'est le fait qu'il y ait une porte à sens unique "clé publique" P = T("clé secrète" S), mais qu'en plus, il est possible de transférer cette propriété de "porte à sens unique" vers une autre fonction X = f(C,P) qui n'a pas d'inverse g tel que C = g(X,P), mais qui possède une inverse g', tel que C = g'(X,S).  En d'autres termes, en utilisant la clé publique, f est une "porte à sens unique" qui ne peut pas être inversée (avec la connaissance de P seulement), mais f est bien réversible en g' si on a la connaissance de la clé secrète.  Cette construction "d'une porte à sens unique connaissant que P, mais inversible avec la connaissance de S" est le coeur de la mise en oeuvre de la cryptographie asymétrique.  On pourrait formuler cela comme l'existence "d'une porte à sens unique avec une porte dérobée dedans".  La porte dérobée est la clé secrète.  Les fonctions à sens unique dans la cryptographie symétrique n'ont pas de porte dérobée.  Il n'y a aucune connaissance supplémentaire qui permet d'inverser une fonction de hachage par exemple.

Comment ça marche ?

Fondements mathématiques pour la cryptographie asymétrique

La base technologique pour la cryptographie asymétrique est donc une "porte à sens unique avec une porte dérobée".  Il faut donc trouver un problème mathématique tel qu'on peut construire une bijection T qui donne la clé publique à partir d'une clé secrète pour lequel il est connu que le problème inverse est un problème dur en mathématique pour lequel personne ne connaît une solution pratique et une application qui fait qu'on puisse facilement calculer quelque chose comme X = f(C,P), et C = g'(X,S), mais que C = g(X,P) n'est pas faisable. 

Il y a essentiellement deux classes de problèmes mathématiques qui sont utilisés en cryptographie asymétrique.  Il y en a quelques autres, mais qui, en ce moment, n'ont qu'un succès marginal (ce qui ne veut pas dire qu'ils n'ont pas de potentiel, mais seulement qu'ils sont beaucoup moins utilisés, étudiés, et appliqués).   Ces deux classes de problèmes sont:

  • la factorisation d'un produit de (deux) grands nombres premiers, et le théorème d'Euler
  • le problème du logarithme discret dans un groupe cyclique fini, et le fait que (ai)j = (aj)i = ai.j

Comment transformer ces principes en une vraie fonction "porte à sens unique avec une porte dérobée" est tout l'art de concevoir un système cryptographique asymétrique bien sûr, mais au coeur de tout système utilisé aujourd'hui, se trouve un de ces deux problèmes.  Le problème du logarithme discret est en fait bien plus riche en choix, car il est envisageable pour beaucoup de groupes cycliques: une classe de groupes cycliques est le groupe multiplicatif d'un champs modulaire.  Une autre classe sont les groupes cycliques basées sur des courbes elliptiques.  En fait, cette dernière classe est maintenant très prometteuse car elle semble permettre une sécurité bien plus élevée avec des clés bien plus courtes que les autres systèmes en vogue.

Le danger avec la cryptographie asymétrique est que les mathématiciens peuvent faire des progrès dans l'étude des problèmes difficiles qu'on prend comme leur base pour établir la relation entre clé publique et clé privée.  Toute l'idée est qu'il est facile de calculer la clé publique à partir de la clé secrète, mais que l'inverse pose un problème mathématique infaisable dans la pratique, même si la fonction mathématique est bien définie.  Si les gens font des progrès dans le calcul de cette fonction, cela met sérieusement en cause la sécurité du cryptosystème qui prenait cette difficulté comme sa base.   Comme certains progrès ont étés faits sur des problèmes classiques, cela implique pourquoi les longueurs de clés sont beaucoup plus grandes pour atteindre un niveau de sécurité qu'en cryptographie symétrique.  Il ne faut pas s'étonner de clés qui ont des longueurs de plusieurs milliers de bits.

Factorisation en nombres premiers: idée de base

Le système cryptographique basé sur la factorisation en nombres premiers est aussi connu sous le nom de RSA.  On va le décrire dans plus de détails dans une autre contribution, mais nous allons illustrer l'idée mathématique de base tout de suite.

L'idée est d'avoir deux grands nombres premiers p et q, qui sont "aléatoires" et donc, secrets.  Leur produit, n = p.q, est public.  Toute l'idée est que la fonction Phi de Euler du nombre n peut être facilement calculé si on connaît p et q: Phi(n) = (p-1).(q-1).  Mais pour quelqu'un qui ne connaît que n, c'est une tâche impossible.

Si nous prenons comme clé publique, n, et un nombre e, qui est un nombre premier relatif à Phi(n), donc la clé publique étant (n, e), alors un message peut être chiffré de la façon suivante:

X = Ce mod n

en utilisant (n, e).

Par contre, pour déchiffrer ce message, il faut la clé privée, qui est (p,q,e).  Effectivement, on peut calculer facilement l'inverse multiplicatif de e dans l'anneau modulaire de module Phi(n), en utilisant l'algorithme étendu de Euclide.  Ainsi, nous obtenons:

d.e = 1 mod Phi(n)

Le déchiffrement est alors:

C = Xd mod n

Effectivement, Xd = (Ce)d mod n = Cd.e mod n = C1 + k Phi(n) mod n = C using Euler's theorem.

Ceci est le coeur du système cryptographique RSA.  Toute l'idée est que si nous connaissons n, nous n'avons aucune idée comment obtenir les deux grands nombres premiers p et q qui sont ses facteurs, non pas car il y a de l'entropie (il n'y en a pas), mais parce que nous ne savons pas comment résoudre ce problème mathématique.  Ainsi, nous ne pouvons pas calculer Phi(n).  Sans Phi(n), nous ne pouvons pas calculer d de e, car pour calculer l'inverse, il faut savoir dans quel anneau il faut travailler.

Nous voyons bien les deux "portes à sens unique" dans ce schéma.  La première est "prendre le produit de deux grands nombres premiers p et q: n = p.q".  C'est facile de trouver un produit de deux nombres premiers.  Mais nous ne savons pas comment retourner, et retrouver p et q à partir de n, même si cette factorisation est bien définie.  C'est la porte à sens unique T.  La deuxième porte à sens unique est "prendre la puissance e".  Prendre la puissance e de C donne X et c'est facile, mais en connaissant e et X, nous ne savons pas comment "prendre la e-racine" même si, là encore, cette fonction est bien définie.  Seulement, il y a une porte dérobée dans "prendre la e-racine": si nous connaissons d, alors il devient possible de prendre la e-racine: c'est simplement une autre puissance qu'il faut prendre.  Prendre la puissance d d'un élément de l'anneau modulaire de module n, correspond à "défaire" l'action de "prendre la puissance e" dans ce même anneau, ce qui est exactement ce que veut dire "prendre la e-racine".  Mais sans la connaissance de d, nous ne savons pas comment prendre cette racine.  Dans la fonction à sens unique "prendre la puissance e", il y a donc une porte dérobée: connaître d.  On peut connaître d, si on connaît Phi(n), ce qui peut se connaître si on connaît les deux facteurs p et q.

Le problème du logarithme discret: idée de base

Utiliser le problème du logarithme discret pour construire directement une "porte à sens unique avec une porte dérobée" n'est pas aussi simple que dans le système RSA.  En fait, il y a quelque chose qui est simple et naturel avec le problème du logarithme discret: c'est d'établir une clé commune secrète (éphémère).  C'est l'utilisation de cette clé commune qui sera à la base de la porte à sens unique avec une porte dérobée.  L'établissement de la clé commune secrète est le coeur de ce qu'on appelle le protocole d'échange de clés Diffie-Hellman.  Nous allons étudier ce protocole en plus de détails plus tard mais ici, nous allons considérer l'idée mathématique essentielle sur laquelle se repose cet échange.

L'idée est qu'il y ait un groupe cyclique G publiquement connu, avec un générateur a, dont personne ne sait comment résoudre le problème du logarithme discret.

L'idée (étonnement simple d'ailleurs) est: une entité (personne) A choisit au hasard un élément en G: SA.  Ce sera la clé secrète de A.  Entité A calcule aussi sa clé publique: PA = aSA.

La fonction à sens unique de la clé publique est donc simplement l'exponentiation dans le groupe.  Comme le problème inverse, à savoir le logarithme discret, est considéré comme un problème difficile, ceci illustre donc l'aspect "porte à sens unique" de la fonction.  Mais comment l'utiliser ?

L'entité B fait la même chose: SB est la clé secrète de B, choisie au hasard par B, et aSB = PB est sa clé publique.

Ainsi, A et B peuvent établir une clé secrète commune entre eux, de la façon suivante.  A connaît sa propre clé secrète, SA et connaît aussi la clé publique de B: PB.  A peut calculer:

KA = (PB)SA = (aSB)SA = aSB.SA

B faisant la même chose, trouvera KB = (PA)SB = aSB.SA = KA

Ainsi, A et B peuvent établir une clé commune secrète entre eux: K = KA = KB sans le besoin d'un canal sûr.  Personne d'autre que A et B peuvent établir cette clé.

Dans l'échange de clé Diffie-Hellman, N entités ont leurs clés secrètes "fixes", et ont publiés leur clés publiques correspondantes.  En faisant cela, il y a la possibilité de générer N(N-1)/2 clés secrètes communes pour chaque pair d'entités, leur permettant de communiquer de façon secrète, en établissant des MAC entre eux, sans aucun besoin préalable de partager une clé secrète à l'avance utilisant un canal sûr.  Ce qui peut se faire en suite avec cette clé commune est fonction de l'application qu'on veut mettre en oeuvre.  L'application la plus évidente est bien sûr l'utilisation de cette clé pour un outil à cryptographie symétrique, comme AES. 

Mais on peut aussi utiliser la méthode pour établir une "clé éphémère se session".  C'est la base du schéma de chiffrement Elgamal.  C'est très proche de Diffie-Hellman, sauf que cette fois, l'émetteur n'utilise pas sa propre clé publique, mais établit juste une clé éphémère pour l'utilisation unique de cette communication.

Si l'entité A a publié sa clé publique, et l'entité B veut envoyer un message secret à A, sans qu'ils se connaissent au préalable, alors la seule chose ce dont B a besoin, c'est la clé publique de A.  B va générer une clé secrète S juste pour cette communication, et il va calculer  P = aS et K = (PA)S.  Quand cela est fait, B peut oublier S, et garder seulement P et K.    B peut maintenant chiffrer son message C (qui doit être un bloc qui rentre dans le groupe G) avec la formule simple:

X = (C . K)

et il envoie (P ; X) à A.

A reçoit (P ; X).  Il peut calculer K comme dans l'échange Diffie-Hellman.  Quand il a K, il peut calculer K-1, l'inverse de K dans le groupe G.  Alors, A peut déchiffrer le message car C = (X . K-1 ).

Si B veut envoyer plusieurs blocs (car le texte en clair est trop grand pour le groupe), alors B doit générer une nouvelle clé éphémère pour chaque bloc.

Signatures numériques

Un domaine d'application important qui s'ouvre avec la cryptographie asymétrique est la possibilité d'avoir des signatures, qui identifie une entité individuelle comme le signataire d'un document, et dont la signature peut être vérifiée par tout le monde.  Avec la cryptographie symétrique, cela n'est pas possible car pour être capable de vérifier la signature, il faut être en possession de la clé qui permet de produire la signature.  Si plus qu'une entité est capable de produire la signature, alors cette signature ne prouve plus qu'elle a été produite par une entité précise.  La propriété que seulement une entité puisse produire une signature, mais que beaucoup d'entités puissent la vérifier, ne peut être établie que par une méthode de cryptographie asymétrique.

Nous allons maintenant montrer quelles sont les idées fondamentales derrière des schémas de signature, basés sur les deux classes de problèmes de cryptographie asymétrique: la factorisation en nombres premiers, et les logarithmes discrets.

Signature numérique par factorisation en nombres premiers

Ce schéma est aussi appelé: la signature numérique RSA.  C'est en fait relativement évident comme système.  Nous nous mettons dans les mêmes conditions que le système RSA.  Un message C est signé de façon suivante:

s = Cd mod n

La signature est donnée par (e,s) et la clé publique par n.  Comme d est connue seulement par le propriétaire de la clé privé (p,q) comme nous avons vu au par avant, seulement ce propriétaire peut produire la signature.  Sans connaissance de d, on ne peut pas, en pratique, produire Cd.

Tout le monde peut vérifier la signature, cependant, en connaissant la clé publique n et e:

t = se mod n

t doit être égal à C mod n pour les mêmes raisons qu'avec le décryptage dans le système RSA.

Signature numérique basée sur le problème du logarithme discret

Dans la mesure où la signature RSA est évident comme principe, la signature avec un logarithme discret est un peu plus compliquée.

Nous allons commencer avec un groupe cyclique G avec un générateur A, d'ordre premier q.  Mais il nous faudra aussi une fonction injective du groupe G dans les nombres entiers, que nous allons appeler f.  La plupart du temps, ceci n'est pas un problème, car les éléments de G sont représentés, d'une façon ou d'une autre, par des nombres, et cette représentation nous donne une injection naturelle de G dans les nombres entiers.

Considérons que nous avons une clé secrète d, qui est un nombre entier.  La clé publique, par contre, est un élément du groupe:

B = Ad

Toute l'idée est que nous ne pouvons pas calculer d de B, car c'est justement le problème (difficile) du logarithme discret.

Considérons un jeu de données C dont nous voulons produire une signature.

Il faut d'abord générer une clé éphémère K, qui est un nombre aléatoire entre 1 et q-1.  L'élément du groupe R = AK sera calculé.  Nous allons aussi calculer sa représentation numérique: r = f(R).

Il faut ensuit calculer un autre nombre s:

s = (h(C) + d . r) . K-1 mod q

Ici, K-1 est l'inverse multiplicatif de K dans le champs modulaire de module q, et h(C) est un hash du jeu de données.

La signature de C est maintenant (r,s).

La vérification se fait ainsi, par quelqu'un qui possède la clé publique:

  • w = s-1 mod q  (opération dans le champs modulaire de module q)
  • u = w . h(C) mod q (opération dans le champs modulaire de module q)
  • v = w . r (opération dans le champs modulaire de module q)
  • P = Au . Bv (opération dans le groupe cyclique)
  • nous calculons f(P).  Si c'est égal à r, alors la signature est valide, sinon, elle ne l'est pas

La raison est que P devrait être égal à R.  Effectivement, P = Au.Bv = A1/s . h(C). (Ad)1/s . r = A1/s . (h + d.r) = AK = R  en regardant ce que vaut s.

On peut se demander pourquoi ce schéma doit être si compliqué.  La raison est qu'il faut obtenir plusieurs propriétés en même temps.  La première propriété est bien sûr que la signature ne peut être générée que par le propriétaire de la clé secrète, en utilisant d.  Ainsi, d doit apparaître quelque part.  Une deuxième propriété est qu'une empreinte du jeu de données doit être sécurisé, donc il faut que h(C) apparaisse quelque part.  Mais le grand danger de combiner d et h(C) seul, est que nous allons exposer la clé secrète d.  Si nous signons quelques textes avec la même clé secrète, il pourrait devenir possible de résoudre les équations des signatures pour la clé secrète.  C'est pour cela qu'il faut "protéger" la clé secrète avec une clé éphémère K, qui doit bien sûr aussi rester secrète.  Si on connaissait K, elle ne pourrait plus protéger d.  C'est d'ailleurs une vulnérabilité potentielle de ce schéma, qui s'est produit plusieurs fois dans la pratique: c'est la ré-utilisation (ou le manque d'entropie) de K.  Si cela se produit, alors deux signatures avec la même valeur de K sont suffisantes pour exposer la clé secrète d.

Effectivement, supposons qu'il y ait deux textes C1 et C2, signés avec la même clé éphémère K (et donc, r est la même pour les deux signatures).  Alors, cela donne:

s1 = (h(C1) + d . r ) K-1 mod q

s2 = (h(C2) + d . r ) K-1 mod q

Dans ces deux équations, il y a deux inconnues: K et d, et ces deux équations ne sont pas difficile à résoudre dans l'anneau modulaire avec module q, car elles sont essentiellement linéaires dan d.K-1 et K-1 !  Deux signatures avec la même clé éphémère exposent donc la clé secrète du signataire.  Si chaque fois, nous utilisons une nouvelle valeur de K avec beaucoup d'entropie, alors ce schéma reste sûr, par contre, mais il faut faire extrêmement attention à cette faille.

Dépendant du groupe G, ce schéma s'appelle:

  • la signature numérique Elgamal si G est le groupe multiplicatif d'un champs modulaire
  • l'algorithme DSA si G est un sous-groupe cyclique du groupe multiplicatif d'un champs modulaire
  • l'algorithme DSA à courbe elliptique si G est un sous-groupe cyclique d'une courbe elliptique

Nous n'avons qu'indiqué le principe de base de chaque schéma, et un vrai protocole de signature numérique est un peu plus compliqué.

Vue générale

La cryptographie asymétrique a ouvert beaucoup de nouvelles applications qui n'étaient pas possible avec la cryptographie symétrique.  Nous n'avons que touché aux plus évidentes.  Il y en a beaucoup d'autres, comme les signatures annulaires, les preuves à connaissance zéro,.... Cependant, cela ne veut pas dire que la cryptographie asymétrique remplace la cryptographie symétrique.  Il y a deux problèmes essentiels avec la cryptographie asymétrique qui font que la cryptographie symétrique reste préférable quand elle peut être utilisée:

  • les longueurs de clé sont très grandes en cryptographie asymétrique
  • l'effort de calcul nécessaire pour un volume à crypter est très grand vis à vis du même volume en cryptographie symétrique.  Nous parlons de plusieurs ordres de grandeur d'effort calculatoire supplémentaire nécessaire.

C'est pourquoi la cryptographie asymétrique n'est utilisée que dans ces applications essentielles où il n'y a pas de bonne solution symétrique, et que nous passons à la cryptographie symétrique dès que possible.