Sujet 24: Elliptic curve digital signature algorithm (ECDSA) et ECIES

ECDSA est un algorithme de signature digitale, basé sur le problème du logarithme discret sur les courbes elliptiques. Il est notamment utilisé par le Bitcoin pour s'assurer que seuls les propriétaires véritables des fonds peuvent les dépenser.

Supposons qu'Alice veut signer un entier m qu'elle envoie à Bob, où m est message, ou plus souvent le résultat d'une fonction de hachage appliquée au message. Voici comment on procède pour signer avec ECDSA.

Génération des clefs

Alice choisit les paramètres suivants :
\( \quad \quad E\) une courbe elliptique
\( \quad \quad \mathbb{F}_q\) un corps, tel que \( |E(\mathbb{F}_{q})|=fr \), où \(r\) est un premier grand, et \(f \in \mathbb{N} \) petit (souvent \(1\), \(2\), ou \(4\))
\( \quad \quad G \in E(\mathbb{F}_q) \) un point d'ordre \(r\)
\( \quad \quad a \in \mathbb{N}\) un entier secret qu'on utilise pour calculer \(Q=aG\)

Elle publie ensuite les valeurs suivantes :
\( \quad \quad (E, \mathbb{F}_q , r, G, Q) \)
L'entier \(a\) doit rester secret, et le \(f\) peut être déduit des valeurs données (il ne nous intéresse pas).

Signature

L'algorithme choisit aléatoirement un \( 1 \leq k < r \) et Alice calcule :

\( \space R=kG=(x,y)\)
\( \space s = k^{-1}(m+ax) \) mod \(r\) et donc \( k=s^{-1}(m+ax) \)

La signature d'Alice sur le message m est alors :
\( \quad \quad (m, R, s) \)

Vérification

Bob vérifie la signature d'Alice de la manière suivante. Il calcule d'abord :
\( \quad \quad u_1 = s^{-1}m \) mod \(r\)
\( \quad \quad u_2 = s^{-1}x \) mod \(r\)
\( \quad \quad V = u_1 G + u_2 Q\)

Puis il valide la signature si \(V=R\).

On peut montrer que la vérification fonctionne. Supposons qu'on a une signature valide, en utilisant \(1\) et \(2\) on obtient :
\( \quad \quad V=u_1 G + u_2 Q\)
\( \quad \quad \quad = s^{-1}mG + s^{-1}xQ \)
\( \quad \quad \quad = s^{-1}mG + s^{-1}xaG \)
\( \quad \quad \quad = s^{-1}(m+xa)G \)
\( \quad \quad \quad = kG = R \)
Une signature valide est donc bien validée.

ECIES [Modifier]

ECIES est un algorithme de chiffrement basé sur le problème du logarithme discret sur les courbes elliptiques. Il utilise une clef publique pour créer une clef symétrique privée entre deux parties, avec une étape d'authentification pour se protéger contre certains types d'attaques.

Supposons qu'Alice veut envoyer un message m à Bob. Il faut d'abord se mettre d'accord publiquement quant à quelles fonctions de hachages \(H_1\) et \(H_2\) on utilise, ainsi que sur l'algorithme de chiffrement symétrique \(E_k\) dépendant d'une clef \(k\).

\(Notations \) : Soient \(m, n \in \mathbb{N}\), on note \(m||n\) pour "m suivi de n". Par exemple pour \(m=0110\) et \(n=1010\), on a \(m||n=01101010\)

Génération des clefs

Bob établit ses clefs publiques et privées, en choisissant les paramètres suivants :
\( \quad \quad E\) une courbe elliptique sur un corps fini \( \mathbb{F}_q\)
\( \quad \quad A \in E(\mathbb{F}_q) \) un point d'ordre \(N\) avec \(N\) un premier grand
\( \quad \quad s \in \mathbb{N} \) un entier secret, et il calcule \(B = sA\)

La clef publique de Bob est :
\( \quad \quad (q, E, N, A, B) \)

Chiffrement

Alice chiffre son message en faisant les choses suivantes :

Acquérir la clef publique de Bob
Choisir \(k \in \mathbb{N} \) avec \( 1 \leq k < N \)
Calculer \( R=kA\) et \(Z=kB\)
Calculer \( k_1||k_2 = H_1(R,Z)\) (où \(k_1\) et \(k_2\) ont des longueurs spécifiques)
Calculer \(C = E_{k_1}(m) \) le message chiffré, et \(t = H_2(C, k_2) \) le paramètre de vérification
Elle envoie finalement (R, C, t) à Bob

Déchiffrement

Bob reçoit (R, C, t) et applique la méthode suivante pour le déchiffrement :

Calculer \( sR = skA = ksA = kB = Z\)
Calculer \(k_1||k_2 = H_1(R,Z) \)
Calculer \(H_2(C, k_2)\)
Vérification si \(H_2(C, k_2)=t\) alors Bob continue. Sinon, Bob rejette le texte chiffré.
Calculer \(m = D_{k_1}(C)\), où \(D_{k_1}\) est tel que \( D_{k_1}(E_{k_1}(m))=m \)

Les fonctions de hachage sont ici utilisées comme méthode d'authentification, mais on pourrait utiliser d'autres méthodes d'authentification.

Sécurité

L'étape \(4.\) est cruciale pour se protéger contre les attaques dites à cryptogramme choisi. Pour ce type d'attaque, Charlie envoie à Bob des faux textes chiffrés, qui ne correspondent pas à un texte en clair mais qui sont bien pratiques pour déduire des informations sur la clef s, afin que Bob les déchiffre et les lui renvoie. (On choisit intelligemment des faux textes pour pouvoir déduire des informations sur la clef.)
Cependant, le schéma de chiffrement de ECIES permet d'identifier les faux textes chiffrés avant de les déchiffrer. Ainsi, on ne fournit aucune information à l'attaquant.
En effet, supposons qu'un attaquant cherche à produire un texte chiffré :

Il choisit \(C\) et \(k_2'\)
Il pose \( t'=H_2(C, k_2') \)

Bob, pour déchiffrer, va obtenir \(k_2\) en calculant \(H_1(R, Z)\). Or Charlie ne connaît pas \(Z\), donc il sera très peu probable que le \(k_2'\) proposé par Charlie corresponde au \(k_2\) calculé par Bob.
Par conséquent, avec une forte probabilité on aura :

\( \quad \quad t'=H_2(C, k_2') \neq H_2(C, k_2) = t \)

On voit donc que Bob ne va pas au-delà de l'étape \(4.\) si on lui propose un texte chiffré choisi, qui ne correspond pas à un message clair.

Comparaison avec El Gamal [Modifier]

Les algorithmes de signature ECDSA et El Gamal se ressemblent beaucoup. Leur différence principale réside dans l'étape de la vérification de la signature. Pour El Gamal, on doit calculer :
\( \quad \quad f(R)B + sR = mA \)
où \(A, B, R\) sont des points d'une courbe elliptique. Tandis que pour ECDSA, on doit calculer :
\( \quad \quad V = u_1G + u_2Q \)
où \(G, Q\) sont des points d'une courbe elliptique. La multiplication d'un point d'une courbe elliptique par une constante est une opération coûteuse. De ce fait, si on s'attend à faire de nombreuses vérifications de signatures, alors ECDSA sera préféré car plus efficace. En effet il effectue cette opération seulement deux fois, contrairement à El Gamal qui la fait trois fois.

ECIES est également plus rapide qu'El Gamal pour le chiffrement. En effet, avec ECIES le message n'est pas représenté par un point sur une courbe elliptique, contrairement au système El Gamal. De plus, dans ECIES l'algorithme de chiffrement est symétrique, et n'utilise pas les courbes elliptiques. Comme on n'a pas besoin de faire de nouveaux calculs sur les courbes elliptiques pour chaque bloc de message, on gagne en efficacité.

Références [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Sections 6.6, 6.7