Le système d'ElGamal
1. Le cryptosystème
Il est basé sur le problème du logarithme discret, dont la formulation générale est la suivante : étant donnés un (grand) groupe cyclique \(G\) et un générateur \(g\) de \(G\), retrouver \(x\) à partir de \(y=g^x\).
La page en anglais de Wikipedia donne plus de détails.
Les clefs se construisent à partir d'un grand nombre premier \(p\) et d'un générateur \(g\) d'un grand sous groupe (d'ordre \(q\)) de \(({\mathbb Z}/p{\mathbb Z})^*\).
Chaque utilisateur choisit un entier \(x\) (sa clef secrète) et publie \(y=g^x \mod p\).
Pour chiffrer un message \(m\) (représenté par un entier modulo \(p\), on tire un entier aléatoire \(k\) et on calcule $$ (c_1, c_2) = (g^k, m\cdot y^k)$$
Le destinataire déchiffre avec sa clef secrète en calculant $$ m = \frac{c_2}{c_1^x}$$
Il y a des clefs faibles. Il faut que le problème du logarithme discret soit difficile dans \({\mathbb Z}_p^*\). Ce n'est par exemple pas le cas si \(p-1\) est un produit de petits facteurs premiers (l'algorithme de Pohlig-Hellman permet de casser la clef).
Les clefs les plus résistantes sont celles pour lesquelles \(p\) est un nombre premier sûr, c'est à dire de la forme \(p=2q+1\) avec \(q\) premier (on dit alors que \(q\) est un nombre premier de Sophie Germain). Ces nombres sont rares, et le calcul des clefs est long. On recommande ensuite de choisir pour \(g\) un générateur du sous groupe des carrés, qui est d'ordre \(q\) premier. Le problème du logarithme discret est supposé être le plus difficile dans les groupes d'ordre premier.
On peut utiliser d'autres groupes, par exemple les groupes multiplicatifs des autres corps finis \({\mathbb F}_q\) (très utilisés pour la construction de codes correcteurs d'erreurs), ou mieux, les groupes associés aux courbes elliptiques sur les corps finis. Ces derniers systèmes, plus complexes et dépendant de mathématiques très sophistiquées, permettent d'avoir des clefs plus courtes à sécurité équivalente, et sont bien adaptés aux environnements embarquées comme les cartes à puces.
2. Le schéma de signature
Comme dans la plupart des schémas de signature numérique, un utilisateur signe un document en chiffrant un hachage \(h\) avec sa clé secrète, et tout le monde peut alors vérifier la signature au moyen de sa clé publique. De manière précise, pour signer un entier \(0\le h\lt p-1\), on tire au hasard un entier \(k\) dans ce même intervalle, premier avec \(p-1\), et on calcule $$r=g^k \mod p,$$puis $$s=(h-xr)k^{-1}\mod p-1.$$ La signature est le couple \((r,s)\).
Pour vérifier une signature avec la clé publique \(y\), on vérifie $$(1)\quad 1\le r\lt p,$$et $$(2)\quad g^h\equiv r^sy^r\mod p.$$
La condition (1) est très importante. Si un programme omet de la vérifier, on peut lui faire accepter de fausses signatures sur n'importe quelle valeur de hachage \(h'\) pourvu qu'on connaisse une signature valide. On calcule \(u=h'h^{-1}\mod p-1\). Alors, $$g^{h'}\equiv g^{hu}\equiv y^{ru}r^{su}\mod p$$ et on peut prendre \(s'=su\mod p-1\). Ensuite, par le théorème des restes chinois, on peut trouver \(r'\) tel que \(r'\equiv ru\mod p-1\) et \(r'\equiv r\mod p\). Si la condition (1) n'est pas testée, \((r',s')\) sera accepté comme une signature valide de \(h'\).
Un autre problème est lié à la présence de canaux subliminaux. Si l'entier \(k\) n'est pas choisi de manière totalement aléatoire, il peut servir à dévoiler des informations sur le signataire (par exemple sa clé secrète) à l'insu de celui-ci. Un bon exemple, où un patch de deux lignes sur le code source de GPG suffit à compromettre le système, est décrit ici.
3. ElGamal en Python
Voici un exemple minimal avec pyCrypto (la documentation est essentiellement inexistante, il faut regarder le code source). En particulier il faut un générateur de hasard (randfunc, prise dans les sources). On demande une clé de 1024 bits (le nombre premier \(p\)). Les autres attributs sont un générateur \(g\) d'un grand sous-groupe (taille non précisée), l'exposant secret \(x\), et \(y=g^x\). On peut chiffrer, déchiffrer, signer, et vérifier une signature.
from Crypto.PublicKey
import ElGamal
from Crypto
import Random
randfunc =
Random.new().read
EG =
ElGamal.generate(1024,randfunc)
print "p
= ", EG.p
print "g
= ", EG.g
print "x
= ", EG.x
print "y
= ", EG.y
# g n'est pas
toujours primitif dans cette version ...
M ='Le
cheval de mon cousin ne mange du foin que le dimanche.'
C =
EG.encrypt(M, 4567)
print C
D
= EG.decrypt(C)
print D
s
= EG.sign(M, 4567)
print s
v
= EG.verify(M,s)
print v
Avec un exemple réel sous les yeux, on peut maintenant envisager de coder un ElGamal à partir de zéro (ou presque). Un problème à résoudre est celui des clés faibles. On utilisera donc des nombres premiers sûrs. Pour les construire, on tire un entier aléatoire \(u\) dans l'intervalle voulu. S'il est pair, on l'incrémente. Ensuite on teste si \(u\) ou \(2u+1\) est divisible par un petit nombre premier. Si c'est le cas, on l'incrémente de 2. Sinon, on fait un seul test de Fermat en base 2 sur \(2u+1\). En cas de succès, on fait un test de Miller-Rabin sur \(u\)...
Voici une ébauche de programme (utilisant encore quelques fonctions du ent.py de W. Stein) :
#
-*- coding: utf-8 -*-
# ElGamal avec
p sûr
from random
import randint
from ent
import *
#
On utilise un p sûr (p=2q+1, q premier)
#
q est un premier de Sophie Germain
#
On ne doit pas avoir q = (r-1)/2 mod r (r petit permier)
#
sinon p serait divisible par r
# La
borne 2**16 est recommandée par Wiener
small_primes =
primes(2**16)[1:]
def small_test(u):
for v
in small_primes:
a
= u%v
if a
== 0 or a == (v-1)/2:
return False
return True
def gen_SG_prime(nbits):
u
= randint(2**(nbits-2), 2**(nbits-1)-2**(nbits/2))
if u%2
== 0:
u
+=1
while not small_test(u):
u+=2
while u
< 2**(nbits-1):
if powermod(2,u-1,u)
== 1:
p
= 2*u+1
if powermod(2,p-1,p)==1:#
si u est SG,
suffit
if miller_rabin(u):
print "OK"
return p
u
+= 2
while not small_test(u):
u
+= 2
return None
#
Pas plus de 1024 bits en un temps raisonnable ...
#
On prend un générateur du sous-groupe des
#
carrés, qui est d'ordre q premier
def gen_key(nbits):
p
= gen_SG_prime(nbits)
q = (p-1)/2
g
= randint(2,p-1)
g = powermod(g,2,p)
x
= randint(2,q-1)
y =
powermod(g,x,p)
return ((p,q,g,y),x)
def encrypt(m,
pub_key):
(p,q,g,y) = pub_key
k
= randint(1,q-1)
u = powermod(g,k,p); v =
m*powermod(y,k,p)
return (u,v)
def decrypt(c,x,p):
u,v
= c
w =
inversemod(u,p)
return powermod(w,x,p)*v
% p
#K =
((122623979655276773311833466355134730317919125207345460587141457198707840069424754839275480872399964741922207101871881996351252863861105629711439713449199823611286136758833854543491819868734309340764670248871556864039107910615671369497019188352612420443703336812271460511573098173988879632933216593831803718899L,
61311989827638386655916733177567365158959562603672730293570728599353920034712377419637740436199982370961103550935940998175626431930552814855719856724599911805643068379416927271745909934367154670382335124435778432019553955307835684748509594176306210221851668406135730255786549086994439816466608296915901859449L,
19650728731309751102018287247254899926466961147067801856162941521154186405084666185825009436963298363909895177396019285132350064704177913693510813130581029993174510425968691328604202624791540071725216006541822267219401188609369682869236528567431806069652008303254036711494700339435968026947052909322719523084L,
91284257596663654444985426060358069631610965300175832290186058917848996981558216785805281766071419369239989509062552020575521600837403140281221530162886589985462892723222205090422373753073913198059805861235280842079998968719972813085651294298213486639747113129293124723895376972505380021332302945637275505038L),
55527076173712430417534965627584148031730438068478149034854242250661636297345240057642533048719525321090511805353306218867277689752588136785651284699739228341690303070143201028055472883415790638484321068538264442547825352533388394712046730430867594340482170687446909325325106088831602231905557195386184247314L)
K
= gen_key(1024)
print "Key:
"
print K
m
= randint(2**255,2**256)
print m
c
= encrypt(m, K[0])
print c
d
= decrypt(c, K[1], K[0][0])
print d
4. L'algorithme de Pohlig-Hellman et l'attaque de Bleichenbacher
On pourra partir du petit programme de démonstration ci-dessous pour tester l'attaque de Bleichenbacher sur le schéma de signature d'ElGamal (décrite dans la section 3 de cet article). Elle fonctionne quand \(p-1=bw\) où \(b\) n'a que de petits facteurs premiers (on dit qu'il est lisse, smooth en anglais). On peut alors trouver \(z\) tel que \(g^{wz}\equiv y^w\mod p\) par l'algorithme de Pohlig-Hellman. On peut ensuite trouver \(k\) et \(r\) tels que \(r\equiv g^k\equiv cw\mod p\) pour un \(c\) entre 0 et \(b\). On peut ensuite,sans connaître la clé secrète, forger des signatures sur tout hachage \(h\) vérifiant \(h\equiv xr \mod k\wedge(p-1)\). En particulier, si \(g\) est lisse et divise \(p-1\), on peut signer tout \(h\) si \(p\equiv 1\mod 4\) et la moitié des hachages possibles sinon.
#
-*-
coding: utf-8 -*-
#
Algorithme de Pohlig-Hellman pour le logarithme discret
#
Suppose que p-1 n'ait que de *petits* facteurs premiers
#
Version de démonstration non optimisée ...
from ent
import *
def pohlig_hellman (p,
alpha, beta, q, c):
a = [0 for i
in range(0,c)]
omega
= inversemod(alpha,p)
gamma =
[powermod(alpha, (p-1)*i/q, p) for i
in range(q)]
for j
in range(c):
delta
= powermod(beta, (p-1)/q**(j+1), p)
a[j]
= gamma.index(delta)
beta
= beta*powermod(omega, a[j]*q**j, p) % p
return sum([a[j]*q**j
for j
in range(len(a))])
def solve_chinese(yy,mm):
assert len(yy)
== len(mm), "Arguments
must have same length."
k
= len(yy); m = reduce(lambda x,y:x*y,
mm); x=0
for i
in range(k):
u
= reduce(lambda x,y:x*y,
[mm[j] for j
in range(k)
if j!=i])
v
= inversemod(u,mm[i])
x
= (x + yy[i]*v*u) %
m
return x
def discrete_log(beta,alpha,p):
ff
= factor(p-1)
ph =
[pohlig_hellman(p,alpha,beta,q,c) for q,c
in ff]
return solve_chinese(ph,[f[0]**f[1]
for f
in ff])
#print
discrete_log(18,2,29)
#print
discrete_log(9451,5,10007)
#
Test avec un p de 64 bits tel que p-1 n'ait que de petits facteurs
premiers
#
On en trouve un avec SAGE
#
Cet exemple prend environ 22 minutes (instantané avec SAGE)
#
53 10281500672050559975
#
Tue Dec 14 15:59:47 2010
#
Computing ...
#
123456789
#
Tue Dec 14 16:21:51 2010
#
>>>
p=12214595251480930577
alpha=53
beta
= powermod(alpha,123456789,p)
print alpha,
beta
import time
print time.asctime()
print "Computing
..."
print discrete_log(beta,alpha,p)
print time.asctime()
5. Cryptosystèmes à courbes elliptiques
Le système d'ElGamal peut a priori être défini à partir de n'importe quel groupe suffisamment grand. On peut par exemple remplacer \(({\mathbb Z}/p{\mathbb Z)})^*\) par le groupe multiplicatif d'un corps fini plus général \({\mathbb F}_q\), mais cela ne conduit pas à des calculs fondamentalement différents. Il existe une autre source de grands groupes finis utilisables de cette manière. Pour en avoir l'idée, il fallait connaître des mathématiques beaucoup plus sophistiquées que celles nécessaires à l'invention du RSA ou du ElGamal de base. En effet, les notions requises d'arithmétique modulaire (Euclide, Bezout, Fermat, Euler, reste chinois) serait enseignables au lycée (et l'ont même été à une certaine époque), alors que les courbes elliptiques relèvent de l'analyse complexe et de la géométrie algébrique, et ne sont actuellement enseignées que dans des masters spécialisés de mathématiques pures.
On trouvera un bon résumé sur Wikipédia. À titre d'introduction, voici quelques éléments pour comprendre le contexte.
De quoi sont les courbes elliptiques ?
Pour faire court, ce sont, du troisième degré, les courbes planes non singulières, autrement dit, les courbes définies par une équation \(P(x,y)=0\), où \(P\) est un polynôme de degré 3 en au moins une des variables, et qui admettent en chaque point une tangente unique (ce qui exclut par exemple le folium de Descartes \(x^3+y^3 = 3axy\) (un point double : cubique nodale) ou la parabole semi-cubique \(y^2-x^3=0\) (une tangente double au point anguleux), ainsi que toutes le courbes qui se décomposent en une droite et une conique.
La classification des courbes planes du troisième degré est assez compliquée. Pour simplifier les choses, les mathématiciens leur rajoutent deux sortes de points : les points imaginaires et les points à l'infini. La définition des points imaginaires est naturelle : on autorise les variables \(x,y\) à prendre des valeurs complexes, et on voit donc la courbe comme un sous-ensemble de \({\mathbb C}^2\). La définition des points à l'infini est un peu plus subtile : on imagine notre plan comme étant le plan \(z=1\) dans l'espace à 3 dimensions, on remplace l'équation de la courbe par celle du cône d'origine O qui s'appuie sur elle, un polynôme homogène du troisième degré \(\hat P(x,y,z)=0\), tel que \(\hat P(x,y,1)=P(x,y)\). Par exemple, pour la courbe elliptique \(y^2+x^3+x=0\), on a l'équation (dite projective) \(y^2z+x^3+xz^2=0\). On identifie deux triplets \((x,y,z)\) et \((x',y',z')\) s'il sont proportionnels : \((x',y',z')=(ax,ay,az)\). L'ensemble des classes de triplets non nuls de nombres complexes est appelé plan projectif complexe. Ceux pour lesquels \(z\not=0\) correspondent aux points ordinaires de notre courbe. Ceux pour lesquels \(z=0\) sont nouveaux, ce sont les points à l'infini.
Pourquoi cette construction ? L'introduction des points imaginaires permet d'éliminer les discussions sur le nombre de racines des équations. Celle des points à l'infini élimine la question des asymptotes. Par exemple, la classification projective des courbes du second degré ne contient plus que trois cas. En effet, un polynôme homogène de degré 2 peut soit ne pas se factoriser (une conique), soit être un produit de deux polynômes du premier degré distincts (deux droites sécantes), soit enfin être le carré d'un polynôme du premier degré (une droite double). Au niveau projectif, il n'y a plus de distinction entre les trois types de coniques. Si on choisit une projection (par exemple le plan \(z=1\)) pour regarder la courbe, alors, elle pourra ne pas avoir de point à l'infini réel (ellipse), en avoir un (parabole) ou deux (hyperbole). On ne distingue pas non plus les droites sécantes ou parallèles (les parallèles se coupent à l'infini), etc. Donc, c'est beaucoup plus simple.
Pourquoi elliptiques ?
C'est parce qu'elles sont paramétrables par des fonctions spéciales appelées fonctions elliptiques (il restera à expliquer le nom de ces fonctions). Dans un sens, les fonctions elliptiques généralisent les fonctions circulaires. Les coniques sont paramétrables par des fonctions circulaires (ou hyperboliques), par exemple une ellipse sera \(x=a\cos\theta, y=b\sin\theta\). On ne les appelle pas pour autant courbes circulaires, car elles sont en fait paramétrables par des fonctions rationnelles : si \(t=\tan\frac{\theta}{2}\), on a \(\cos\theta =\frac{1-t^2}{1+t^2}\) et \(\sin\theta=\frac{2t}{1+t^2}\). On les appelle donc courbes rationnelles
Et les fonctions elliptiques ?
Leur nom vient du fait qu'elles peuvent être définies comme les fonctions réciproques des intégrales elliptiques, qui ont enfin quelque chose à voir avec les ellipses : si on essaie de calculer la longueur d'un arc d'ellipse, on tombe sur une intégrale elliptique. Il y a plusieurs versions de la théorie des fonctions elliptiques. La plus utilisée en physique ou en ingénierie est celle de Jacobi . Elle permet d'exprimer les solutions de nombreuses équations différentielles, comme celle des grandes oscillations du pendule, par exemple (et la période est alors donnée par une intégrale elliptique).
Mais la version qui nous intéresse pour la cryptographie est celle de Weierstrass. Sachant, par les travaux précédents, que les extensions au plan complexe des fonctions elliptiques sont doublement périodiques (elles vérifient \(f(z+n\omega_1+m\omega_2)=f(z)\) pour tous \(m,n\in{\mathbb Z}\) et tout \(z\in{\mathbb C}\) pour lequel \(f(z)\) est défini, \(\omega_1,\omega_2\) sont deux nombres complexes dont le rapport n'est pas réel), Weierstrass s'est demandé s'il existait un moyen simple de construire directement de telles fonctions doublement périodiques. Son raisonnement est bien expliqué dans l'article de Wikipédia. L'idée est de partir d'une fonction quelconque \(f\) et de former la somme infinie
$$F(z)=\sum_{m,n\in{\mathbb Z}} f(z+n\omega_1+m\omega_2)$$
Si la série converge, \(F\) sera doublement périodique. Il faut donc que \(f\) tende assez vite vers 0 à l'infini. La construction marche avec \(f(z)=z^{-3}\), mais on peut faire mieux en bricolant un peu la série associée à \(f(z)=z^{-2}\). Telle quelle, elle ne converge pas, mais en retranchant à chaque terme son équivalent asymptotique, on peut montrer que ça marche encore. Le résultat est la fameuse fonction
$$\wp(z) = {1\over z^2} + {\sum_{(n_1,n_2)\not = (0,0)}}\left[ {1\over (z+n_1\omega_1+n_2\omega_2)^2} - {1\over (n_1\omega_1+n_2\omega_2)^2}\right]$$
(le caractère \(\wp\) n'appartient à aucune police connue, il a été réalisé spécialement pour Weierstrass).
On peut maintenant rentrer dans le vif du sujet. En développant chaque terme de la série en série de puissances de \(z\), on peut montrer que la fonction \(\wp\) vérifie l'équation différentielle
$$\wp'(z)^2=4\wp(z)^3-g_2\wp(z)-g_3$$
o\`u \(g_2=60G_4\) et \(g_3=140G_6\), avec
$$G_k={\sum_{(m,n)\not=(0,0)}}{1\over (m\omega_1+n\omega_2)^k}$$
et
$$\wp(z)={1\over z^2}+\sum_{k\ge 2}(2k-1)G_{2k}(\tau)z^{2k-2}$$
Donc, \(x=\wp(t), y=\wp'(t)\) fournit directement un paramétrage de la courbe elliptique \(y^2=4x^3-g_2x-g_3\). Un peu de géométrie projective élémentaire permet de montrer que toute courbe elliptique admet une équation de cette forme dans un repère approprié. La fonction de Weierstrass fournit donc une méthode simple et élégante pour paramétrer les courbes elliptiques par des fonctions elliptiques.
Elle montre en particulier qu'on peut additionner les points d'une courbe elliptique ! Si \(P_1 = (\wp(t_1),\wp'(t_1))\) et \(P_2=(\wp(t_2),\wp'(t_2))\), on peut poser
$$P_1\oplus P_2 = (\wp(t_1+t_2),\wp'(t_1+t_2))$$
Cette opération définit une structure de groupe commutatif sur la courbe. On peut vérifier que géométriquement, la somme est le symétrique par rapport à l'axe horizontal du troisième point d'intersection de la droite passant par \(P_1,P_2\) avec la courbe (c'est souvent présenté comme la définition de l'addition sur la courbe, ce qui n'est pas franchement naturel …), et que l'élément neutre est son point à l'infini.
Il reste à la calculer (c'est le théorème d'addition pour la fonction \(\wp\)). Ce n'est pas évident, mais on aboutit à un résultat intéressant : les coordonnées de \(P_1\oplus P_2\) sont des fonctions rationnelles à coefficients entiers des coordonnées de \(P_1\) et \(P_2\). On trouvera le calcul ici
On peut donc appliquer ces formules à la courbe modulo un nombre premier \(p\), c'est à dire à l'ensemble des solutions de l'équation projective dans \(({\mathbb Z}/p{\mathbb Z})^3\). Dans les bons cas, on obtiendra un très grand groupe dans lequel le problème du logarithme discret est encore beaucoup plus difficile que dans un corps fini (à cause de la non-linéarité des fomules d'addition).
Le système proposé (indépendamment par Koblitz et Miller) est donc essentiellement un ElGamal dans le groupe d'une courbe elliptique modulo un grand nombre premier. Par rapport au RSA, il permet d'avoir des clés plus courtes à sécurité équivalente.
On notera que, si la description du RSA est relativement simple, le choix des clés n'est pas trivial. Pour les courbes elliptiques, c'est encore plus complexe. Il est donc recommandé d'utiliser les courbes proposées dans divers standards.