Niveau :      
Résumé : RSA ; courbes elliptiques

Après vous avoir présenté les certificats, parlons de ce qui a permis la création de la notion de certificat : le chiffrement à clé publique.

Algorithme

Un algorithme de chiffrement à clé publique est un algorithme qui utilise une clé différente pour chiffrer et pour déchiffrer. Prenons un exemple simple et supposons que personne n'ait découvert la division. On choisit un algorithme à base de multiplication :

  • Créons une clé privée : 0.25
  • Et une clé publique : 4
  • Un message à chiffrer : 123
  • Chiffrons le message avec la clé publique : 123 * 4 = 492
  • On transmet le message 492
  • Déchiffrons le message avec la clé privée : 492 * 0.25 = 123

Et voila, on peut donner à tout le monde la clé publique. Personne ne sachant diviser par 4, il est impossible de retrouver la clé privée à partir de la clé publique, il est donc impossible lire un message qui a été chiffré spécialement pour vous avec votre clé publique. Par contre, en tant que possesseur de la clé privée, cachée au reste du monde, vous pourrez le lire.

Remarquez qu'on peut aussi utiliser la même technique dans l'autre sens pour faire de la signature :

  • Créons une clé privée : 0.25
  • Et une clé publique : 4
  • Un message à signer : 123
  • Signons le message avec la clé privée : 123 * 0.25 = 30.75
  • On transmet le message 123 avec sa signature 30.75
  • Vérifions la signature avec la clé publique : 30.75 * 4 = 123

Cet algorithme prouve cette fois que c'est bien la clé privée qui a été utilisée pour produire le message. En effet, personne ne sachant diviser 123 par 4, seul vous êtes capables de produire la signature à partir du message de départ. Mais attention, ça ne prouve pas que le message n'a pas été créé de toutes pièces. C'est pourquoi, en pratique, on utilise en plus une fonction à sens unique pour éviter qu'on puisse créer un message à partir de votre signature.

Bien sûr en pratique on utilise des fonctions un peu plus complexes et des nombres un peu plus grands.

RSA

Le RSA, du nom de ses inventeurs Rivest, Shamir et Adleman, est un algorithme de chiffrement à clé privée basé sur la fonction puissance modulo.

C = M^e [n]
  • M est le message à chiffrer
  • C est le message chiffré
  • n et e sont la clé publique

Pour le déchiffrer on utilise :

M = C^d [n] 
  • d est la clé privée

Et c'est tout, la méthode présentée précédemment pour chiffrer et déchiffrer est toujours valide. Il reste à créer les différents nombre proposés ici :

  • On prend p et q 2 nombres premiers choisis au hasard
  • On prend e statiquement (généralement 3 ou 65637)
  • n = p*q
  • On calcule d de façon à ce que e*d = 1 (p-1)(q-1)

Et voila on a toutes nos données. Notez que je n'ai pas prouvé que ça marche, mais d'autres l'ont fait.

La sécurité du système suppose deux choses :

  • on a besoin de p et q pour retrouver d
  • on ne connaît pas d'algorithme rapide nous donnant p et q à partir de n

Une clé RSA typique fait entre 1024 bits et 4096bits soit entre 100 et 400 chiffres.

Courbes elliptiques

Le RSA n'est pas le seul algorithme de chiffrement à clé publique, loin de là, mais c'est le plus utilisé. Le chiffrement par courbe elliptique utilise des courbes elliptiques (sisi) qui sont de la forme

y^2 = x^3 + a*x + b

Le chiffrement se base sur l'inversion de points sur cette courbe.

Je ne vous ferais pas l'affront de vous expliquer les théorèmes mathématiques qui sont derrière, je pense qu'ils sont connus de tous !
Non en fait, c'est surtout que je n'ai pas tout compris, mon niveau en mathématiques est un peu trop léger et je ne voudrais pas dire de connerie.

Ce qu'il faut savoir à propos de courbes elliptiques :

  • Les théorèmes sous-jacents sont similaires à ceux du RSA, ce qui veut dire qu'un algorithme pour casser l'un permettrait de casser l'autre
  • Les clés de chiffrement peuvent être plus petites pour une sécurité similaire, 224 bits équivaut à une clé RSA de 2048bits (attention ce n'est pas linéaire).
  • Les algorithmes de chiffrement et déchiffrement sont plus lents que pour le RSA
  • La résistance à la cryptanalyse augmente plus vite avec la taille des clés que pour le RSA