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

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 :

• soit $q$ n'est pas premier et $q=ab$ avec $a$ et $b$ plus petit que $p$
• soit $q$ est premier et $p+q$ est pair, donc composé, et il existe $a$ et $b$ plus petit que $p$ tel que $ab = p + q$.

Algorithme de transmission

L'exponentiation modulaire peut s'écrire comme l'exponentiation indienne en utilisant le principe dit de "square and multiply" :

algorithme expo(x: entier, y: entier) → entier:
    r := entier
    r ← 1
    tant que y > 0:
        si y est impair:
            r ← r * x mod p     # MULTIPLY
            y ← y - 1
        x ← x * x mod p         # SQUARE
        y ← y / 2
    rendre r

En supposant que la complexité de l'addition, la multiplication et le modulo soient de complexité $\mathcal{O}(1)$, la complexité de l'algorithme est en $\mathcal{O}(\log_2(y))$ qui correspond au nombre maximum d'itérations dans la boucle.

Si $x$, $y$ et $p$ sont stockés sur $n$ bits, la complexité est polynomiale puisque $\log_2(y) \leq n$.

Problème du logarithme discret

Trouver $x$ à partir de $y=g^x \bmod p$ n'est pas évident. En effet l'algorithme naif suivant :

algorithme log(x: entier, y: entier, g: entier) → entier:
    r := entier
    r ← 1
    pour chaque i de 0 à p-1:
        si r == y:
            rendre i
        r ← r * g mod p

En supposant que la complexité de l'addition, la multiplication et le modulo soient de complexité $\mathcal{O}(1)$, la complexité de l'algorithme est en $\mathcal{O}(p)$ qui correspond au nombre maximum d'itérations dans la boucle.

Comme précédemment, si les entiers sont stockés sur $n=\log_2(p)$ bits, la complexité de l'algorithme est maintenant exponentielle par rapport à la taille $n$ de l'entrée : $\mathcal{O}( \cdot 2^{log_2(p)}) = \mathcal{O}( \cdot 2^{n})$.

Le nombre de possibilité à essayer va être rédhibitoire, même pour un algorithme très rapide.

Par exemple, l'exécution d'un algorithme faisant 1 opération en $10^{-6}$ secondes pour calculer le logarithme discret d'une clé à $64$ bits.

Il va y avoir de l'ordre de $2^{64}$ opérations. Comme $10^6 \simeq 2^{20}$ il faudra environ $2^{44}$ secondes soit plus de 6 mois.

Attention cependant, le meilleur algorithme n'est souvent pas le naif ! Regardons pas exemple cet algorithme, appelé Baby step giant step qui échange du temps contre de la mémoire.

Son principe est simple. Si $0 < m < p$, alors la division euclidienne de $x$ par $m$ donne : $x = i \cdot m + j$ avec :

• $0 \leq i \leq p/m$
• $0 \leq j < m$

Et on a que $y=g^x \mod p$ si et seulement si :

Ce qui donne :

algorithme steps(y: entier, g: entier) → entier:
    d := Dict<entier, entier>()
    c := entier
    c ← 1
    
    pour chaque i de 0 à p/m:
        d[c] = i
        c ← g * c

    si y est une clé de d:          # g^i = y  => x = i * m + 0
        rendre d[y] * m

    c ← expo(expo(g, n-2), m)       # 1/g = g ** (n-2) puisque g ** (n-1) = 1 (petit thm Fermat)

    pour chaque j de 1 à m-1:
        si y * c est une clé de d:          # g^i = y  => x = i * m + j
            rendre d[y] * m + j

La complexité de l'algorithme esr alors clairement de :

• $\mathcal{O}(m)$ en mémoire pour stocker toutes les valeurs dans le dictionnaire
• $\mathcal{O}(m + p/m)$ en moyenne pour la complexité pour parcourir les 2 boucles et les test (en moyenne du dictionnaire)

Pour ne pas favoriser une boucle plutôt qu'un autre on prend $m$ tel que $p/m = m$, c'est à dire $m = \sqrt{p}$.

On obtient alors une complexité en moyenne et en mémoire de $\mathcal{O}(\sqrt{p})$

Et tout d'un coup avec notre clé de 64b, notre algorithme n'aura plus besoin que de $2^{32}$ opérations. À raison d'une opération par microseconde, il ne faudra plus que 5 millisecondes pour résoudre le problème !

Pour une clé de 128bit et 1 opération par microsecondes :

• l'algorithme naïf prend de l'ordre de $10^{25}$ ans
• l'algorithme baby-step giant step prend de l'ordre de $584942$ ans (ce qui est encore beaucoup mais on change tout de même d'ordre de grandeur).

Les exemples précédents supposent un ordinateur avec un processeur unique et deux algorithmes non optimisés. Pour des algorithmes parallèles et optimisés on peut peut faire bien mieux.

Comme augmenter la taille de la clé augmente exponentiellement le nombre de possibilité cet la taille des clés reste toujours acceptable (doubler la vitesse d'un algorithme permet de traiter dans le même temps de clés à un bit de plus).

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

Attaque

Il existe beaucoup de types d'attaques possibles. Explicitons-en quelques unes.

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.

On préconise donc une taille de clé de 4096b 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 https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ 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-Hellmann 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.