Cryptographie pour les néophytes : cryptographie asymétrique

| 26 November 2013 | Cryptographie | 3 Comments

www.hellopro.fr

Ah le RSA, le DSA, El-gamal et toutes ces joyeusetés ! Dans la suite de nos articles sur la cryptographie, voici un article qui va en intéresser plus d’un. Je vous parlerais ici, du pourquoi et du comment de la cryptographie asymétrique. Nous considérons comme asymétrique les cryptosystèmes nécessitant un ou des éléments privés associés à un ou des éléments publiques.

Il faudra, comme vus dans les fondamentaux, se poser régulièrement la question : Où est le secret ?

Niveau Manager et Législation : Petit défi intellectuel
Niveau Technique : Petite base en math…

 La question clé !

Nous l’avons vu précédemment, la première étape lors du chiffrement symétrique est le partage de clé entre Alice et Bob. Et tout le problème est là ! Comment Alice peut-elle envoyer de manière sécurisée son secret à Bob ? Cela revient à la fameuse énigme de Tristan et Iseult :

Iseult souhaite envoyer une lettre d’amour à Tristan qui est resté au fin fond de la forêt du Morrois. Elle ne veut pas que cette lettre soit interceptée sous peine d’être condamnée par le roi.
Elle met donc la lettre dans un coffre et fait appel à un messager (elle ne peut bien évidemment pas lui faire confiance).
Iseult possède un coffre et un cadena dont, elle seule détient la clé.
Tristan possède un autre cadena dont lui seul possède la clé.
Comment font Tristan et Iseult pour s’échanger leur lettre d’amour sans que le coffre ne puisse être ouvert par le messager ?

Réponse :

  1. Iseult met sa lettre dans le coffre et le ferme avec son cadena
  2. Le messager transporte le coffre fermé à Tristan
  3. Tristan n’ayant pas la clé, ne peut ouvrir le coffre
  4. Tristan met son cadena en plus de celui d’Iseult
  5. Le messager ramène le coffre à Iseult
  6. Iseult enlève son cadena
  7. Le messager apporte le coffre fermé par le cadena de Tristan à Tristan
  8. Tristan ouvre le coffre

Tristan_Iseult_Crypto

Diffie-Hellman…Hell yeah !

C’est dans cet esprit que les deux mathématiciens  Whitfield Diffie et Martin Hellman ont conçu leur système d’échange de clé. Le processus est le suivant :

  1. Alice et Bob se mettent d’accord sur l’anneau et le générateur employé
  2. Alice génère un secret “a“
  3. Bob génère un secret “b“
  4. Alice calcule une valeur publique A et l’envoie à Bob
  5. Bob calcule sa valeur publique B et l’envoie à Alice
  6. Chacun élève la clé publique reçue à la puissance de sa clé secrète

Diffie_Hellman

Alice et Bob viennent de calculer une clé de session équivalente sans jamais faire passer en clair les secrets a ou b , uniquement les valeurs publique A et B.

La faille !!

Car si, effectivement, personne ne peut retrouver le secret dans un temps raisonnable, cela n’empêche pas un(e) pirate, que nous nommerons Charlie, de faire une attaque d’homme du milieu (man in the middle). Ainsi Charlie se fait passer pour Bob auprès d’Alice et pour Alice auprès de Bob. La parade est donc de prouver l’identité de chaque intervenant et cela se fait grâce à la signature des clés A et B.

Un peu de math pour les curieux

Parce que, chez nous, la curiosité est une excellente qualité, voici une petite explication vulgarisée sur l‘anneau et le générateur. Un anneau est un ensemble d’éléments possédant :

  • une relation + (plus)
  • une relation * (multiplier)
  • un élément neutre e pour * (e*x = x)

Par exemple (Z32, +, *) représente tout les entiers de 0 à 31…et il est où le 32 ?? Et bien,  Z32 est cyclique, cela veut dire qu’une fois qu’on est arrivé à 32, on revient à 0. C’est le modulo ! Ainsi 33 dans l’ensemble Z32 s’exprime sous la forme 33 mod32 = 33[32] =1 + 32[32] =  1 + 0 = 1.

Un générateur est un chiffre ou un nombre qui permet de générer tous les éléments de l’anneau par la relation +. Un petit exemple sur Z7 pour mieux comprendre :

5[7]=5
+5=10[7]=3
+5=15[7]=1
+5=20[7]=6
+5=25[7]=4
+5=30[7]=2
+5=35[7]=0

J’ai bien reconstitué mon ensemble {0,1,2,3,4,5,6}. 5 est un générateur de l’anneau (Z7,+,*)
C’est aussi pour cela que l’on vous demande de choisir entre “g2” ou “g5” dans un VPN : c’est le générateur employé 2 ou 5.

Rivest Shamir et Adleman

Nous pouvons à présent “échanger” une clé symétrique entre deux partenaires grâce à Diffie-Hellman (DH). Mais deux problèmes se posent ! Le premier est le fait de ne pas pouvoir authentifier les participants de l’échange. Le second est lors des échanges à plusieurs partenaires… C’est un peu comme partout : plus on est, plus ça se complique. En effet si j’essaye de faire une conversation à 3, il me faudra 2 clés différentes (une par partenaire), si je monte à N, il m’en faudra N-1.

Heureusement, Adleman est un prof ouvert et participe à une grosse fête étudiante pendant laquelle il se murge sévèrement…et conçoit l’idée d’une cryptographie asymétrique. Il en fait alors part à ses deux amis Rivest et Shamir et ils créent, à 3, le fameux Rivest, Shamir et Adleman : le RSA.

Ce qui rend cet algorithme si élégant, c’est sa simplicité. La recette ? Et bien je prends un anneau de taille n et je choisi e et d tel que e*d = 1 [φ(n)]. Du coup, pour un message M :

M c'est mon Message, 
e c'est ma clé publique, 
d c'est ma clé privée.
Je chiffre avec ma clé publique:
C = Me [n]
Et je déchiffre avec ma clé privée:
Cd[n]= Me*d [n] = M1 [n]= M

C’est simple et efficace.

Le petit plus

Les observateur auront noté le φ(n), c’est l’indicatrice d’Euler qui représente le nombre de nombres premiers à n et inférieurs à lui.  Par exemple, pour un nombre premier p, p≡1φ(p) (Fermat bonsoir) et φ(p) = p-1 puisque il est premier avec tout le monde sauf lui même et qu’il y a p-1 nombre avant lui. Ici, n=p*q, du coup : φ(n) = φ(p)*φ(q)=(p-1)(q-1).

Mais comment ça marche Jamie ?

RSA est un algorithme de chiffrement, je vais donc garder ma clé privée (d) pour moi et diffuser ma clé publique (e) à touuuut le monde.

Dans le cas d’un échange de clé, je vais utiliser les clés publiques de mes n partenaires et chiffrer une clé de session K. Nous utiliserons ensuite tous la même clé K pour communiquer. Ce sera notre clé de groupe finalement.

Pour la signature, je vais réaliser un hash du message et le chiffrer avec ma clé privée d. Ainsi toutes les personnes qui auront ma clé publique e pourront vérifier que c’est bien moi qui ai signé le message.

C’est ce qui est utilisé dans un échange SSL ! Voilà comment ça se déroule lors d’une authentification -uniquement serveur :

  1. Je met L’URL du site que je souhaite joindre dans mon navigateur
  2. Le site m’envoie
    1. un certificat avec sa clé publique
    2. une signature réalisée avec sa clé privée
  3. Je vérifie que le certificat contient bien l’URL que j’ai rentrée
  4. Je vérifie la signature avec la clé publique du certificat
  5. Je crée une clé de session K
  6. Je chiffre ma clé de session avec la clé publique du site
  7. Je communique avec le site sous l’égide de ma clé K

echange_ssl

Ce qu’il faut retenir…

Bon ça a l’air compliqué comme ça, et je vous ai fait grâce des vérifications du certificat, donc laissez moi mettre un éclairage particulier sur les points importants !

1 – RSA est un algorithme de chiffrement

2 – Avec RSA, je peux faire du chiffrement et de la signature

3 – Pour chiffrer, je chiffre le message avec la clé publique de mes partenaires

4 – Pour signer, je chiffre le hash du message avec ma clé privée

5 – Pour partager un message chiffré, je le chiffre avec une clé de session K et je chiffre K avec les clés publiques de mes partenaires

 Petit note sur DSA

A l’époque ou RSA était encore breveté, le NIST (National Institute of Standard and Technology) publia un algorithme pour la signature numérique très solide. Il se base sur deux valeurs publiques s1, la valeur de vérification, et s2, la valeur de calcul contenant le hash du message à vérifier et signé avec le secret s. Je pourrais vous expliquer le détail du wiki si vous le souhaitez mais, afin que les compétences mathématiques de chacun soit respectées,  je ne le ferais pas ici.

L’important est de savoir que cet algorithme ne fait que de la signature. Rien d’autre…même si c’est déjà pas mal.

Courbe épilep..elliptique

La courbe elliptique ou ECC (Eliptic Curve Cryptography) n’est pas un algorithme!! C’est un moyen mathématiques pour définir les ensembles de calcul. Ainsi on applique un algorithme de cryptographie asymétrique à un ensemble, défini par la courbe elliptique.

Ce que ça change ? Mais tout messieurs dames, tout !
Vous définissez un nouveau groupe et les relations qui vont avec. Grossièrement, dites vous que la relation * (multiplier) devient + (plus)…Impressionnant, non?! Cela accélère fortement les calculs, surtout si l’on considère la taille réduite des clés nécessaire en ECC.
En effet, pour assurer la même sécurité qu’une clé publique de 256 bits en EC-RSA, il nous faudrait un couple de clés calculées sur 3072 bits en RSA basique. Ceci est du aux propriétés des courbes elliptiques, optimales pour les problèmes de logarithme discret.

C’est donc pour les matériels ayant peu de ressources de calcul que l’EC-RSA (ou DSA, ou El-Gamal, ou que sais je encore) va être particulièrement utilisé. Les cartes à puces, les PDA, les systèmes basés sur les antennes, etc.

Related Posts