Wiki du cours

Rédacteur: [Gabriel Martin]

A traiter [Modifier]

• L'échange de clés de Diffie-Hellman
• Le problème de Diffie-Hellman calculatoire
• Le problème de Diffie-Hellman décisionnel
• Solution du problème de Diffie-Hellman décisionel par le couplage de Weil.

L'échange de clés de Diffie-Hellman [Modifier]

Le but de l'échange de clés de Diffie-Hellman est de permettre la création d'une clé secrète entre 2 personnes sans contact au préalable. La méthode est expliquée en vidéo [3] mais ici nous ferons un résumé de celle-ci. Un exemple avec des couleurs permet de mieux comprendre l'idée de l'algorithme:

1. Alice et Bob choisissent chacun une couleur secrète (disons a et b) et ont accès à une couleur publique (p).

2. Alice mélange sa couleur secrète avec la couleur commune (elle crée donc ap) et l'envoie à Bob.

3. Bob fait de même. (envoie bp)

4. Alice et Bob mélangent la couleur reçue avec leur couleur secrète et obtiennent ainsi la même couleur finale (abp).

Un espion qui intercepterait les messages envoyés obtiendrait comme uniques informations: p ap et bp mais ne pourrait pas obtenir directement abp en mélangeant ces informations.

De la même manière que pour le problème de la peinture au sein duquel il est facile de savoir le mélange final à partir de 2 couleurs, mais difficile de retrouver les couleurs initiales à partir du mélange final. Nous allons nous servir du problème du logarithme discret traité au chapitre 16.

En effet, dans \( G=\mathbb{Z}_{p} \) avec \(p\) premier pour toute paire de points \(a, b \in G\) avec \(a\) non nul, il existe un certain \(k\) tel que \(a^k\equiv b\) mais ce \(k\) n'est pas facile à trouver. Ce problème ne se limite pas à \( G=\mathbb{Z}_{p} \), en effet nous retrouvons également le problème du logarithme dans les courbes elliptiques. Pour des raisons pratiques nous utiliserons \( G=\mathbb{Z}_{p} \). En pratique pour \(p\) très grand, le calcul n'est quasiment plus possible à résoudre.

1. Alice et Bob choisissent le même nombre premier \(p\) et le même générateur \(a\).

2. Alice choisit une puissance secrète \(m\) et envoie le \(b_1\) obtenu via \(a^m\equiv b_1\) à Bob

3. Bob choisit une puissance secrète \(n\) et envoie le \(b_2\) obtenu via \(a^n\equiv b_2\) à Alice

4. Alice calcule \((b_2)^m\equiv c\) et obtient \(c\)

5. Bob calcule \((b_1)^n\equiv c\) et obtient le même \(c\)

Le problème de Diffie-Hellman calculatoire

On s'intéresse maintenant au cas où le groupe \(G\) est une courbe elliptique. Etant donné \(P, aP\) et \(bP\) dans \( E(\mathbb{F}_{q}) \) peut-on obtenir \(abP\)?

Si on pouvait résoudre les logarithmes discrets alors on pourrait utiliser \(P\) et \(aP\) afin d'obtenir \(a \) et ensuite calculer \(a(bP)\) et ainsi obtenir \(abP\).

Le problème est donc de savoir s'il est possible de trouver \(abP\) sans résoudre un logarithme discret.

Le problème de Diffie-Hellman décisionnel

Etant donné \(P, aP\) et\( bP\) dans \( E(\mathbb{F}_{q}) \) , et donné un point \(Q \in E(\mathbb{F}_{q}) \) est-il possible de déterminer si \(Q = abP\)?

Dans notre exemple il s'agit du cas où un informateur indiquerait la clé à l'espion mais celui ci désirerait vérifier qu'il s'agit de la bonne clé.

Solution du problème de Diffie-Hellman décisionel par le couplage de Weil

Dans certains cas, le couplage de Weil permet de résoudre le problème de Diffie-Hellman décisionnel. Supposons que l'on connaisse \(P, aP , Q\) et que l'on souhaite savoir si \(Q= abP\).

On utilise le couplage de Weil affin de savoir si \(Q\) est un multiple de \(P\). Par Lemme 5.1 \(Q\) est un multiple de \(P \Longleftrightarrow e_n (P,Q)=1\) supposons que ce soit le cas alors \(Q = tP\) pour un certain \(t\).

Nous avons donc: \(e_n(aP,bP)=e_n(P,P)^{ab} =e_n(P,abP) \) et également \(e_n(Q,P)=e_n(P,P)^t \)

Supposons que \(3 \nmid n\), alors le lemme 6.1 nous dit que \(e_n(P,P) \) est une racine n-ième de l'unité. Finalement on obtient: \(Q=abP \Longleftrightarrow t\equiv ab (mod n ) \Longleftrightarrow e_n(aP,bP)=e_n(Q,P) \)

Nous avons ainsi évité le problème du logarithme discret grâce au couplage de Weil.

Références [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 6.1
[2] Yevgeniy Dodis, Introduction to cryptography, Lecture 7
[3] Public key cryptography - Diffie-Hellman Key Exchange (full version) https://www.youtube.com/watch?v=YEBfamv-_do