Partage de secret

Comment se partager un secret alors que tout le monde nous espionne ? Le protocole Diffie-Hellman est une solution à ce problème, aidé par le fait que l'on ne sait pas tout faire en algorithmie.

Protocole Diffie-Hellman

Protocole Diffie-Hellman

Dans le domaine public :

  • $p$ premier
  • $g < p$ un générateur du groupe cyclique $(\mathbb{Z}/p\mathbb{Z}^{\star}, \cdot)$
  1. Échange de la première partie des clés
    • Alice choisit un nombre $a$ et envoie à Bob $A = g^a \bmod p$
    • Bob choisit un nombre $b$ et envoie à Bob $B = g^b \bmod p$
  2. Constitution des clés :
    • Alice construit le secret $k = B^a \bmod p = g^{ab} \bmod p$
    • Bob construit le secret $k = A^b \bmod p = g^{ab} \bmod p$

Au final, Alice et Bob partagent un nombre $k$ compris entre $0$ et $p-1$.

Pourquoi ça marche

  1. si $n$ est premier, $(\mathbb{Z}/p\mathbb{Z}^{\star}, \cdot)$ est un groupe cyclique
  2. il est très facile de faire l'exponentiation modulaire dans le cas général et encore plus rapide en notation binaire
  3. le logarithme discret est une opération coûteuse

Existence

Comme $g$ est un générateur d'un groupe cyclique, on peut donc avoir tout le monde en temps que $g^a$

$ab$ permet bien d'obtenir tout nombre $q$ entre $0$ et $p-1$ car :

Problème du logarithme discret

Trouver $a$ à partir de $g^a$ n'est pas évident. On ne sait pas faire efficacement, alors que l'exponentiation va très vite.

TBD https://fr.wikipedia.org/wiki/Baby-step_giant-step

TBD taille clé 4096b actuellement

TBD : https://math.mit.edu/classes/18.783/2022/LectureNotes9.pdf et https://www.lix.polytechnique.fr/~morain/MPRI/2013/lecture1.pdf

TBD montre l'algo baby step giant step qui fait partie des algos ou on échange du temps contre de la mémoire.

Attaque

TBD beaucoup de types d'attaque diff (qui marchent).

TBD algo, authentification, side channel

Brute force

La meilleure attaque connue est l'attaque brute force en utilisant l'algorithme du crible général qui est une méthode de factorisation.

Pour un nombre premier de 2058bit, l'attaque brute force en utilisant le crible général prend de l'ordre de $2^{90}$ opérations. Comme on en veut au moins $2^{128}$ pour être en sécurité : on préconise au moins 3000b actuellement.

Voir ce doc p35.

Man in the middle

TBD : pb d'authentification faire le dessin.

Side channel attack

L'exponentiation indienne peut s'écrire de façon binaire en utilisant le principe MULTIPLY and SQUARE.

expo(x, y):
  r = 1
  pour chaque i de 0 à n-1:
    si y[i] == 1:
      r = r * x      # MULTIPLY
    x = x * x        # SQUARE
  rendre r

On remarque qu'il y a deux fois plus de travail lorsque $y[i]$ vaut 1 que lorsqu'il vaut 0.

TBD le temps est aussi double puisque c'est des multiplications. dnc si on connait le temps mis pour que des 0 ou que des 1 on sait combien de 1 à la clé.

Mais on peut faire mieux en mesurant le courant !

Utilisation de courbes elliptiques

TBD On a besoin que de l'exposant. Cela peut donc se faire dans tout groupe pas obligé d'être dans Z/pZ. TDB exemple avec courbe elliptique.

Un des intérêt du protocole de Diffie-Hellman est qu'il peut s'écrire sous la forme de courbes elliptiques, ce qui permet de réduire la taille de la clé tout en évitant l'attaque brute force.

https://fr.wikipedia.org/wiki/Échange_de_clés_Diffie-Hellman_basé_sur_les_courbes_elliptiques

TBD taille clé 256b actuellement (courbe de Bernstein)

Renvoyer à Courbes elliptiques pour la def et les propriétés basiques d'une courbe elliptique.