El criptosistema ElGamal
Artur Travesa
(versió 2021-04)

Introducció general

L'origen d'aquestes notes es remunta a diferents cursos d'Aritmètica o de Criptografia, a càrrec de l'autor, per a estudiants de Matemàtiques o d'Informàtica de la Universitat de Barcelona.

La idea bàsica és descriure algunes aplicacions importants de l'Aritmètica bàsica (diguem, de nivell de primer curs) a les transmissions xifrades d'informació.

En cap cas es tracta d'un curs de Criptografia, que caldria encabir en espais més amplis de coneixements, que haurien d'incloure, probablement, parts de teoria de la comunicació, de complexitat algorítmica o computacional, d'aprenentatge automàtic, o d'estudi de teories de compartició de secrets, entre d'altres.

El format triat per a la presentació és el d'un notebook de Mathematica, per la facilitat que té aquest programari per a poder desenvolupar els càlculs no trivials de manera prou senzilla i entenedora, d'una banda, i per a permetre fer una presentació escrita prou raonable des del punt de vista de material escrit, de l'altra. En particular, la possibilitat d'incloure els càlculs dins del text de manera natural en fan una bona eina comunicativa i, alhora, facilita molt el càlcul amb exemples no trivials.

A fi de veure tot el contingut del notebook convé executar-lo. Això es pot fer de cop o bé, més recomanable, cel·la a cel·la a mesura que s'avança en la lectura i comprensió dels diferents continguts. 
Observació: Per al cas en què no es disposi del programari, hi ha la versió executada del notebook en format pdf.

Amb la finalitat doble d'una banda, de no fer textos molt llargs o amb molts continguts, i de l'altra de poder ampliar de manera senzilla els continguts que s'hi tractin, el material s'ha dividit en diferents notebooks, que desrivim a continuació, en l'apartat de referències.

Referències

[Cripto-1]: Criptografia bàsica (1).
Travesa, A.: CriptografiaBasica-1; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una iniciació a la codificació de missatges. El criptosistema de Cèsar. El criptosistema de Vigenère.

[Cripto-2]: Criptografia bàsica (2). 
Travesa, A.:CriptografiaBasica-2; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Els criptosistemes lineals. Els criptosistemes afins. Sufixació de missatges. Farciment de missatges.

[Eratostenes]: Un garbell d'Eratòstenes.
Travesa, A.: Eratostenes; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Un garbell d'Eratòstenes.

[Cripto-3]: Primeritat. Construcció de primers. 
Travesa, A.: ConstruccioDePrimers; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Test de primeritat de Solovay-Strassen. Test de primeritat de Miller-Rabin. Un  certificat congruencial de primeritat. Construcció certificada de nombres primers de mida prefixada. Aplicació al càlcul de claus RSA. Aplicació (exercici) al càlcul de claus ElGamal.

[Cripto-4]: Factorització. 
Travesa, A.: Factoritzacio; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Un garbell d'Eratòstenes. Tests de primeritat de Solovay-Strassen i de Miller-Rabin. Un certificat congruencial de primeritat. Un algoritme bàsic de divisó per nombres primers petits. Un algoritme bàsic de divisó per nombres petits. El mètode de factorització de Fermat. El mètode de factorització p-1 de Pollard. El mètode de factorització rho de Pollard.

[RSA]: Criptosistemes de tipus RSA. 
Travesa, A.: RSA; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una descripció bàsica dels criptosistemes de tipus RSA: les claus; xifratge; desxifratge; observacions sobre la seguretat.

[ElGamal]: El criptosistema ElGamal. 
Travesa, A.: ElGamal; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Logaritmes discrets. Una descripció bàsica del criptosistema ElGamal: el grup cíclic; les claus; xifratge i desxifratge.

[D-H]: Diffie, W.; Hellman, M.E.: New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), p. 644-654.

[ElGamal-1]: ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31 (1985), p. 469-472.

[DSS-Standard]: FIPS PUB 186-4: Digital Signature Standard (DSS). Federal Information Processing Standards Publication. National Institute of Standards and Technology, 2013.

[Tr-1]: Travesa, A.: Aritmetica. Edicions de la Universitat de Barelona, col·lecció UB, n. 25. Barcelona, 1998. ISBN:84-8338-031-5.

Introducció

El criptosistema ElGamal és basat en el mateix principi que el protocol Diffie-Hellman per a intercanvi de claus en canals públics; el va inventar Tahe ElGamal, que el va descriure en un article en 1984 (cf. [D-H], [ElGamal-1] a les referències). És la base d'un dels estàndards actuals (DSA) de signatura digital (cf. [DSS-Standard, cap. 4]).

La seguretat del criptosistema ElGamal es basa en la dificultat (conjectural) de calcular logaritmes discrets arbitraris. En efecte, donats un nombre primer p, un element g invertible mòdul p, i un nombre natural x, el càlcul de la potència, h=(g^x) (mod p) es pot fer en temps polinòmic en la longitud en bits de p i x; en canvi, no es coneix cap algoritme tal que, donats p, g i h, trobi el nombre x en temps polinòmic en la longitud en bits de p (com en el cas de la factorització, el millor algoritme que es coneix actualment és subexponencial).

En farem una descripció i, simultàniament, un exemple.

1. Logaritmes discrets

En general, suposem que disposem d'un grup qualsevol, G, i d'un element g∈G d'ordre finit, q. Escriurem multiplicativament l'operació del grup i ens fixarem en el subgrup cíclic de G generat per g. Aquest subgrup, (Subscript[C, g]), és format per les potències h=(g^x), per a 1≤x≤q, ja que q és l'ordre de g; notem, també, que (g^0)=(g^q)=1 és l'element neutre del grup G i, per tant, també del grup (Subscript[C, g]).

Definició

Amb les notacions anteriors, i per analogia amb els logaritmes reals o complexos, x s'anomena el logaritme discret de h en base g. Notem que x és un nombre enter, que està definit mòdul l'ordre q de g en G; per tant, podem pensar x com un element de ℤ/qℤ.

Obervació 1

Així, l'assignació x → (g^x) defineix un isomorfisme (de grups) entre el grup additiu ℤ/qℤ i el grup multiplicactiu (Subscript[C, g]): l'exponencial de base g.

Exemple

Considerem un nombre natural primer p, i sigui G el grup dels elements invertibles mòdul p. En G, podem considerar qualsevol element g com a base dels logaritmes discrets. Si anomenem q l'ordre de g, tenim que el grup (Subscript[C, g]) és format per les potències h=(g^x), per a 1≤x≤q. També tenim que, en virtut del petit teorema de Fermat, q és un divisor de p-1.

Observació 2

En general, donats p, g, i (g^x) (mod p), el càlcul de x no se sap fer en temps polinòmic respecte de la mida en bits de p (ni tan sols, conegut q).

Observació 3

Notem que si en lloc de considerar el grup multiplicatiu dels elements invertibles mòdul n, considerem tot el grup additiu de les classes residuals mòdul n, i g és una classe qualsevol, la potència (g^x) de més amunt es correspon ara amb el producte g·x, de manera que el càlcul del logaritme discret es redueix a la resolució de la congruència lineal g·x=h (mod n); i aquesta es pot resoldre (mitjançant l'algoritme d'Euclides, per exemple) en temps polinòmic en la longitud en bits de n. Per tant, hi ha grups cíclics per als quals el problema del logaritme discret és polinomic.

2. La base del criptosistema ELGamal

El grup cíclic

De manera similar a com en els criptosistemes de tipus RSA la base del mètode és el càlcul de potències mòdul un nombre enter N, així també en el criptosistema ElGamal la base és aquest mateix tipus de càlcul.

Cada usuari U del criptosistema tria un nombre primer senar p i un nombre enter g no divisible per p i tal que l'ordre multiplicatiu de g en (ℤ/pℤ)* sigui un nombre primer senar q. (Moltes vegades, tots els usuaris U del criptosistema utilitzen el mateixos valors de p i g i, per tant, tots coneixen també el valor de q.)

En particular, es té que p-1=2·k·q, on k és un nombre enter. D'aquesta manera, el subgrup G de (ℤ/pℤ)* generat per g és cíclic, d'ordre primer, q, i és format pels elements (g^x), 1≤x≤q, de (ℤ/pℤ)*.

Observació 4

A fi que aquesta tria sigui útil per al criptosistema ElGamal cal que el problema del logaritme discret en el grup G sigui computacionalment intractable, encara que aquesta condició no és l'única que cal per a G. (A la pràctica, si no es fa servir tot (ℤ/pℤ)* en lloc de G, i una arrel primitiva mòdul p en lloc de g, és per a satisfer la necessitat d'aquesta condició.)

Observació 5

En l'actualitat (abril de 2021), sembla prou segur utilitzar nombres primers p tals que l'ordre de G, posem q, sigui un nombre d'un miler de bits, aproximadament. En el nostre exemple, prendrem com a p un nombre primer de 1024 bits i tal que p-1 sigui divisible per un primer q de 1000 bits. D'aquesta manera, el nombre enter k:=((p-1)/(2·q)) serà un nombre de, com a màxim, 24 bits, o sigui, relativament petit.

Observació 6

El càlcul de nombres p, q i k en aquestes condicions no és especialment complicat, i es pot fer a partir d'algoritmes probabilístics. Per exemple, es pot consultar la referència [Cripto-3].

Observació 7

D'altra banda, la tria d'un element de (ℤ/pℤ)* d'ordre q no presenta dificultats. En efecte, si (Subscript[g, 0]) és una arrel primitiva mòdul p, l'element ((Subscript[g, 0])^(2·k)) és d'ordre q, i tots els elements de (ℤ/pℤ)* d'ordre q són de la forma ((Subscript[g, 0])^(2·k)), per a alguna arrel primitiva mòdul p, (Subscript[g, 0]). Per tant, és suficient calcular una arrel primitiva mòdul p i elevar aquesta a la potència 2·k, mòdul p.

Exercici 1

(a) Es demana calcular un nombre primer p de 1024 bits de manera que p-1 sigui el producte d'un nombre primer q de 1000 bits per un nombre enter parell 2·k.
(b) Es demana calcular un element g de (ℤ/pℤ)* d'ordre q, per als valors p, q de l'apartat (a).

3. Les claus

Les claus

Quan l'usuari U disposa de p, q, k i g, tria a l'atzar un nombre enter x, 1≤x≤q-1, i calcula h:=(g^x) (mod p). D'aquesta manera, h és un element de G.

Definició.

La clau pública de U és (p, q, g, h); la clau privada de U és (p, q, g, x). Notem que l'única diferència és en h i x, mentre que els paràmetres p, q i g són comuns; en particular, tots els usuaris del criptosistema poden usar els mateixos p, q, i g.

Observació 8

Els nombres h i x de les claus juguen un paper molt diferent. Així com h és un element de G, i actua com a tal en el procés de xifratge, x és un nombre natural, i actua com a tal en el procés de desxifratge. En conseqüència, x i h no són intercanviables, en contraposició a les claus pública i privada del criptosistema RSA, que sí que són intercanviables.

Observació 9

Cal notar que calcular x a partir de p, q, g i h vol dir calcular el logaritme discret mòdul p, de base g, per a l'element h; per tant, si no podem resoldre aquest problema de logaritme discret, no sabem calcular la clau privada de U a partir de la seva clau pública.

Exercici 2

Es demana crear, a partir dels nombres p, q i g de l'exercici 1, una parella de claus pública (p, q, g, h) i privada (p, q, g, x) per al criptosistema ElGamal. Les anomenarem ClauElGamalPublica i ClauElGamalPrivada.

4. Xifratge i desxifratge

Xifratge

Les unitats de missatge que es poden xifrar amb el criptosistema ElGamal són els elements de ℤ/pℤ. En particular, el conjunt d'unitats de missatge vàlides és diferent per a cada usuari si cadascun treballa en un anell diferent, però el mateix si tots els usuaris treballen amb el mateix valor de p; és per això que és còmode usar el mateix valor de p per a tots els usuaris del criptosistema.

Notem que el conjunt de missatges que poden ser xifrats és més gran que el grup que fem servir per a xifrar; de fet, el grup G és un subgrup de (ℤ/pℤ)* que, alhora, és un subconjunt de ℤ/pℤ.

Suposem que la unitat de missatge que es vol xifrar és un element m de ℤ/pℤ, on p és el nombre primer de la clau de U. L'usuari V que vol enviar el missatge m a U, tria a l'atzar un nombre y de l'interval 1≤y≤q-1 i calcula els dos nombres (Subscript[c, 1])=(g^y) (mod p) i (Subscript[c, 2])=m·(h^y) (mod p), amb 0≤(Subscript[c, 1])≤p-1, 0≤(Subscript[c, 2])≤p-1. El missatge xifrat associat a m és la parella de nombres naturals ((Subscript[c, 1]), (Subscript[c, 2])).

Observació 10

Cal notar que tant (Subscript[c, 1]) com (Subscript[c, 2]) són nombres de, com a màxim, 1024 bits, perquè p és de 1024 bits.

Desxifratge

Per a desxifrar el missatge, l'usuari U calcula el producte (Subscript[c, 2])·((Subscript[c, 1])^(-x)) (mod p); pot calcular-ho perquè coneix el valor secret x, i això produeix el missatge m.

Demostració.

En efecte, es té que (Subscript[c, 2])·((Subscript[c, 1])^(-x)) (mod p)=m·(h^y)·((((g^y)))^(-x)) (mod p)=m·((((g^x)))^y)·((((g^y)))^(-x)) (mod p)=m (mod p), perquè ((((g^x)))^y)·((((g^y)))^(-x))=1 (mod p). □

Observació 11

Cal notar que les potències de g són elements de (ℤ/pℤ)*, de manera que la multiplicació per ells (i pels seus inversos) és possible a tot ℤ/pℤ, i no cal restringir-se a G.

Exemple

La funció següent pren com a entrades una llista d'unitats de missatge i una clau pública ElGamal i produeix una llista d'unitats de missatge xifrades amb aquesta clau pública.

ElGamalX0[mc_,claupublica_]:=Module[{l,p,q,g,h},
l=Length[mc];
{p,q,g,h}=claupublica;Table[Module[{y},y=RandomInteger[{1,q-1}];{PowerMod[g,y,p],Mod[mc[[i]] PowerMod[h,y,p],p]}],{i,1,l}]]

Observem que, un cop hem resolt l'exercici 2, ja disposem d'una parella de claus pública i privada per al criptosistema ElGamal. Suposem que la clau pública és en una llista anomenada ClauElGamalPublica i que la clau privada és en una llista anomenada ClauElGamalPrivada. (Per si encara no s'ha resolt l'exercici 2, aquí disposem d'una parella de claus pública i privada de 1024 bits per al criptosistema ElGamal.)

ClauElGamalPublica0={,,,};

ClauElGamalPrivada0={,,,};

pe0=ClauElGamalPublica0[[1]]

Ara, ens inventem un missatge.

m1=Table[RandomInteger[{0,pe0-1}],{i,1,5}]

I el xifrem amb la clau pública.

x1=ElGamalX0[m1,ClauElGamalPublica0]

Exercici 3

Es demana definir una funció, ElGamalDx0, per a desxifrar missatges xifrats amb la funció ElGamalX0. Notem que cal produir, a la sortida, el missatge codificat en forma d'una llista d'elements de ℤ/pℤ, on p és el nombre primer de la clau privada. Per a comprovar que funciona bé, es pot provar de desxifrar el missatge x1.

ElGamalDX0[mx_,clauprivada_]:=Module[{l,p,q,g,x},
l=Length[mx];
{p,q,g,x}=clauprivada;Table[Mod[mx[[i,2]] PowerMod[mx[[i,1]],-x,p],p],{i,1,l}]]

dx1=ElGamalDX0[x1,ClauElGamalPrivada0]

dx1==m1