Sujet 22: Cryptosystème de ElGamal

Il choisit une courbe elliptique \(E\) sur un corps finis \(\mathbb{F}_{q}\) tels que le problème du logarithme est difficile à resoudre pour \(E(\mathbb{F}_{q})\).
Il choisit \(P \in E\) avec un premier assez grand comme ordre.
On choisit un entier secrèt \(s\) et on calcule \(B = sP\).

Finalement, Bob optient sa clé privé \(s\) et la clé publique \((E, \mathbb{F}_{q}, B, P)\).

Algorithme de chiffrement

Pour envoyer le message à Bob, Alice suit l'algorithme suivant:

Télécharger la clé publique de Bob.
Exprimer le message à envoyer avec un point \(P \in E(F_q)\).
Choisir un entier aléatoire secrèt \(k\) et calculer \(M_1 := kP\).
Calculer \(M_2 := M + kB\).
Envoyer \(M_1,M_2\).

Algorithme de déchiffrement

Le déchiffrement se déroule en calculant \(M=M_2-sM_1\):

\(M_2-sM_1 = (M+kB)-s(kP) = M+k(sP)-skP = M\).

L'éspion Eve connaît la clé publique de Bob (en étant une information publique) et les points \(M_1,M_2\). Si Eve peut calculer le problème du logarithme, elle peut utiliser \(P\) et \(B\) pour trouver \(s\), avec lequel elle peut déchiffrer le message via le calcul \(M_2-sM_1\). Si Eve ne peut pas calculer le problème du logarithme, apparement elle ne peut pas découvrir le méssage \(M\) autrement.

Remarque C'est très importante pour Alice de changer son \(k\) aléatoire secrèt chaque fois qu'elle veue envoyer un message à Bob. Supposons quêlle utilise le même \(k\) pour les méssages \(M\) et \(M'\). Alors, Eve reconnaît le \(k\) car \(M_1=M'_1\), et après elle peut calculer \(M'_2-M_2=M'-M\). Supposons que M est un annonce de vent qui sera publié le jour après, et que Eve le découvre; alors elle peut calculer \(M'=M-M_2+M'_2\). D'où, la connessance du texte \(M\) permets à Eve de déchiffrer le texte \(M'\).

Au contraire à la signature de ElGamal (qu'on traitera just après), le système de la clé publique de ElGamal n'est pas largement utilisé.

La signature numérique de ElGamal [modifica]

Alice aimerait signer un document, comme étant un document papier. Suppsons, en tout cas, que le document est éléctroinique, comme un fichier sur un ordinateur. La solution naïfe serait de digitaliser la signature d'Alice et l'annexer au fichier contenant le document. Mais, dans ce cas, la méchante Eve peut copier la signature et l'annexer à un autre document. Par consequant, des mesures doivent être prises pour lier la signature au document de manière à ce qu'elle ne puisse plus être utilisée.

En tout cas, ça doit être possible pour quelqu'un de verifier que la signature soit valide, et ça devrait être aussi possible de montrer qie Alice soit la personne qui a vraiment signé le document.

Une solution à ce problème repose dans la difficulté du problème du logarithme discrèt. Normalement, L'algorithme a été dévéloppé pour le groupe multiplicatif d'un groupe fini; en fait, celui s'applique à n'importe quel groupe fini. On le presentera pour les courbes elliptiques sur les corps finis.

Création des clés

D'abord, Alice doit définir une clé publique:

Elle choisit une courbe elliptique \(E\) sur un corps finis \(\mathbb{F}_{q}\) telle que le problème du logarithme discrèt soit difficile pour \(E(\mathbb{F}_{q})\).
Elle choisit aussi un point \(A \in E(\mathbb{F}_{q})\); normalement on choisit \(A\) tel que son ordre \(N\) soit un premier assez grand.
Elle choisit aussi un entier secrèt \(a\) and elle calcule \(B=aA\)
Finalement, elle choisit une fonction \(f:E(\mathbb{F}_{q}) \rightarrow \mathbb{Z}\)

Exemple \(\mathbb{F}_{q} = \mathbb{F}_{p}\), alors Alice devrait utiliser \(f(x,y) = x\), où \(x\) représente un entier, \(0≤x≤p\). La fonction \(f\) n'a pas besoin de propriétés particuliaires, sauf que son image doit être grande et que seul un petit nombre d'inputs doit produire une outpoot donnée (e.g. pout \(f(x,y)=x\), au moins deux points \((x,y)\) donnent un output donné \(x\)).

L'information publique de Alice est \((E, \mathbb{F}_{q}, f, A, B)\); elle gardera l'entier \(a\) comme clé secrète. L'entier \(N\) n'est pas nécéssairement public.

Algorithme de signature

Pour signer l'algorithme, Alice doit suivre l'algorithme suivante:

Representer le document via un entier \(m\) (si \(m>N\), on choisit une courbe plus large, ou utiliser une fonction d'hachage (à suivre)).
Choisir un entier aléatoire \(k\) tel que \(gcd(k,N) = 1\) et calculer \(R = kA\).
Calculer \(s \equiv k^{-1}(m-af(R))\) (mod \(N\)).

Remarque Le message signé sera \((m,R,s)\): \(m\) et \(s\) sont des entiers, alors que \(R\) est un point en \(E\). En plus, Alice ne chèrche pas de garder le document \(m\) secrèt: si elle veut le faire, alors elle a besoin d'utiliser une forme de cryptage.

Algorithme de vérification

Bob vérifie la signature comme suit:

Télécharger l'information publié de Alice.
Calculer \(V_1 := f(R)B + sR\) et \(V_2 := mA\).
Si \(V_1=V_2\), alors la signature est déclrée valide.

Si la signature est valide, alors \(V_1=V_2\), car

\(V_1 =f(R)B+sR=f(R)aA+skA=f(R)aA+(m−af(R))A=mA=V_2\).

On utilise le fait que \(sk \equiv m-af(R)\) (mod \(N\)), d'où \(sk \equiv m-af(R) + zN\), avec \(z \in \mathbb{Z}\). Alors:

\(skA = (m−af(R))A+zNA = (m−af(R))A+ \infty = (m−af(R))A\).

Si Eve calcule le logarithme discrèt, alors elle peut utiliser \(A\) et \(B\) pour trouver \(a\). Dans ce cas, elle peut mettre la signature de Alice dans n'importe quel message. Alternativement, Eve peut utiliser \(A\) et \(R\) pour trouver \(k\). Dès qu'elle connaît \(s, R,m\), elle peut donc utiliser \(sk \equiv m-af(R)\) (mod \(N\)) pour trouver \(a\). Si \(d := gcd(f(R),N) \neq 1\), alors l'équation \(af(R) \equiv m-ks\) (mod\(N\)) possède \(d\) solutions pour \(a\). Tant que \(d\) est petit, Eve peut essayer chaque possibilité jusqu’à ce qu’elle obtienne \(B = aA\). D'où elle peut utiliser \(a\), comme avant, pour imprimer la signature de Alice sur un message arbitraire.

Remaque Comme on a vu avant, Alice doit garder \(a\) et \(k\) secrèts. En plus, elle doit utiliser un entier \(k\) different pour chaque signature. Sinon, on aurais le même problème que dans le chiffrement du message se présent si on ne change pas d'entier (et Eve arrivera découvrir le \(a\) secrèt).

Parfois, pour Eve n'est pas nécessaire de resoudre le problème du logarithme pour la signature. Tout ce que Eve a besoin de faire est arriver à \(R\) et \(s\) tels que l'équation de vérification \(V_1=V_2\) soit satisfaite; elle a besoin de trouver \(R=(x,y)\) et \(s\) tels que

\(f(R)B + sR = mA\).

Pour faire ça, Eve a besoin de reoudre le priblème du logarithme discrèt de \(sR = mA − f(R)B\) par rapport à l'entier \(s\), en choisissant un certain point \(R\). Si, par contre, elle choisit l'entier \(s\), elle devra resoudre une équation par rapport à \(R\).

Remarque D'ailleurs, personne n'est réussit à trouver une procédure qui permets de trouver \(R\) et \(s\) au même temps. Ils existent des façons pour utiliser un message signé valide pour construire un autre message signé valide. Mais malheuresement, ces messages construits sont messages significatifs.

Utilisation des fonctions de hachage pour pouvoir signer des messages de taille arbitraire [modifica]

En générale, on crois que la sécurité du système de ElGamal est très proche de la sécurité du problème du logarithme discrèt pour le groupe \(E(\mathbb{F}_{q})\). Mais le message signé \((m, R, s)\) est environ trois fois plus long que le message originale; un désavantage pour ce système.

Une méthode plus efficace est d'utiliser une fonction de hachage publique \(H\) et signer \(H(m)\).

Définition Une fonction de hachage cryptographique est une fonction qui prends des inputs de longueur arbitraire (parfois un message de milliards de bits), et sortir des valeurs de longueur fixe (par exemple 160 bits).

Propriétés Une telle fontion \(H\) devrait avoir les propriétés suivantes:

Étant donné un message \(m\), la valeur \(H(m)\) doit être calculé très rapidement.
Étant donné \(y\), c'est infaisable de calculer \(m\) tel que \(H(m)=m\) (on dit que \(H\) est résistant à la pré-image).
C'est infaisable de calculer deux messages disctincts \(m_1\) et \(m_2\) tels que \(H(m_1) = H(m_2)\) (on dit que \(H\) est fortement sans collision).

Remarque Les points 2. et 3. sont pour prévenir que Eve crée des messages avec une valeur de hachage voulu, ou deux messages avec la même valeur de hachage. Ces mesures previennent la falsification.

Exemples MD5 (valeurs en 128 bits), Secure Hash Algorithm (valeurs en 160 bits).

Si Alice utilise une fonction de hachage, le message signé est \((m, R_H, s_H\), où \((H(m), R_H, s_H)\) est une signature valide. Pour verifier que le message signé \((m, R_H, s_H\) est valide, Bob doit suivre l'algorithme suivante:

Télécharger l'information publique de Alice.
Calculer \(V_1 := f(R_H)B + s_H R_H\) et \(V_2 := H(m)a\).
Si \(V_1 = V_2\), on déclare valide la signature.

Remarque L'avantage est que un message très long \(m\), contenant de milliards de bits, possède une signature qui réquis seulement un paire de miliers de bits en plus.

Tant que le problème du logarithme discrèt est difficile à resoudre pour \(E(\mathbb{F}_{q})\), Eve ne pourra pas afficher la signature de Alice sur un autre message.

La variante de van Duin [modifica]

Une variante récente de la signature de ElGamal est le schéma fait par van Duin, très efficace dans certains aspècts. Par exemple, onarrive à calculer \(k^{-1}\), et l'algorithme de vérification a besoin juste de deux calcules du type \(nP\), où \(n \in Z\) et \(P \in E\).

Comme avant, Alice veut signer un document \(m\). Pour mettre en place le système:

Elle choisit une courbe elliptique \(E\) sur un corps finis \(\mathbb{F}_{q}\) et aussi un point \(A \in E(\mathbb{F}_{q})\); normalement on choisit \(A\) tel que son ordre \(N\) soit un premier assez grand.
Elle choisit aussi une fonction de hachage cryptographique \(H\).
Finalement, elle choisit un entier secrèt \(a\) et elle calcule \(B = aA\).

La clé publique est \((E, q, N, H, A, B)\). La clé secrète est l'entier \(a\). Pour signer \(m\), Alice devra:

Choisir un entier secrèt \(k\) mod \(N\) et calculer \(R = kA\).
Calculer \(t = H(R,m)k + a\) (mod \(N\)).

Le document signé est \(m,R,t)\).

Pour verifier la signature, Bob télécharge la clé publique de Alice et il vérifie si l'expression

\(tA = H(R,m)R + B\) est vraie.

Si elle vrai, la signature est décalrée valide; sinon, la signature sera invalide.

Références [modifica]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Sections 6.4. 6.5
[2] Yevgeniy Dodis, Introduction to cryptography, Lecture 7