Sifrat ElGamal

Taher ElGamal

El procediment de sifrat/dessifrat ElGamal es referix a un esquema de sifrat basat en el problema matemàtic del logaritme discret. És un algoritme de criptografia asimètrica basat en l'idea de Diffie-Hellman i que funciona d'una forma pareguda a este algoritme discret.

L'algoritme de ElGamal pot ser utilisat tant per a generar firmes digitals com per a sifrar o dessifrar.

Va ser descrit per Taher Elgamal en 1984 i s'usa en software GNU Privacy Guard, versions recents de PGP, i atres sistemes criptogràfics. Este algoritme no està baix cap palés lo que ho fa d'us lliure.

La seguritat de l'algoritme es basa en la suposició que la funció utilisada és d'un sol sentit per la dificultat de calcular un logaritme discret.

El procediment de sifrat (i dessifrat) està basat en càlculs sobre un grup cíclico qualsevol $G$ lo que du a que la seguritat del mateix depenga de la dificultat de calcular logaritmes discrets en $G$.

L'algoritme original

Mostrem el criptosistema propost inicialment per Tahar ElGamal en el seu artícul.

Generació de la clau

Per a generar la clau, Alicia tria un número primo $p$ qualsevol tal que el logaritme discret no és soluble en un temps assumible en $Z_p^{*}$ (grup multiplicativo mòdul un primer p). Açò últim es traduïx que $p-1$ tinga un factor primer gran (lo que fa que el problema del logaritme discret siga difícil).

Ademés Alicia elegix dos números aleatoris $g$ (el generador del grup cíclico ($Z_p^{*})$) i $a$ (que actuarà com a clau privada) tal que $a\in \{0,\dots ,p-1\}$.

Alicia calcula el valor de $K=g^a(\mathrm{mod}p)$. La clau pública serà $(g,p,K)$, mentres que el valor de $a$ ho mantindrà en secret. Rebujant $a$ de l'equació $K=g^a(\mathrm{mod}p)$ obtenim la relació següent entre els components de la clau pública i la clau privada ${\log }_{g}K(\mathrm{mod}p)=a$ en lo que el criptosistema és segur sempre que siga difícil trobar el logaritme discret.

Sifrat

Supongam que Bruce té un text clar que vol enviar sifrat a Alicia. Lo primer per fer és convertir este text en un sancer m entre 1 i $p-1$ ($m\in Z_p$). Açò no és part del sifrat, sino que és una manera de codificar estàndart, coneguda per tots. Després Bruce tria arbitrariamente un número $b\in \{2,\dots ,p-1\}$ (que mantindrà secret) para finalment calcular:

$y_1=g^b(\mathrm{mod}p)$

$y_2=K^{b}m(\mathrm{mod}p)$

El mensage sifrat final correspon a la tupla $C_b(m,b)=(y_1,y_2)$

Dessifrat

Per a dessifrar aprofitem que:

$y_1^{-a}{y}_2(\mathrm{mod}p)=(g^b{)}^{-a}{K}^{b}m(\mathrm{mod}p)=g^{-ab}(g^a{)}^{b}m(\mathrm{mod}p)=(g^a{)}^{-b}(g^a{)}^{b}m(\mathrm{mod}p)=m(\mathrm{mod}p)$

Per tant per a dessifrar es té que realisar el següent càlcul:

$y_1^{-a}{y}_2(\mathrm{mod}p)$

a on $y_1^{-a}$ representa l'invers de $y_1^a$ mòdul $p$ lo que indica que per a calcular el dessifrat, és necessari conéixer $a$, que és la clau privada d'Alicia.

Pel menuda teorema de Fermat es demostra que $y_1^{-a}=y_1^{p-1-a}$ i ho podem aplicar.

Demostració: El menuda teorema de Fermat indica que $x^{p-1}(\mathrm{mod}p)=1$ en p primer i x>0 coprimo en p. Elevant a $a$ l'expressió obtenim que ${x^{p-1}}^a(\mathrm{mod}p)=1^a=1$. Per tant $x^{(p-1)\cdot a}(\mathrm{mod}p)=x^{ap-a}(\mathrm{mod}p)=x^a\cdot x^{p-1-a}(\mathrm{mod}p)=1$. Rebujant $x^{p-1-a}(\mathrm{mod}p)=x^{-a}(\mathrm{mod}p)$

Eixemples

Simple

Alicia elegix els valors:

$p=17$ (cosí aleatori i suponem que p-1=16 té un factor primer gran lo que no és cert)

$g=3$ (generador aleatori)

$a=6$ (clau privada aleatòria)

Alicia calcula

$K=g^a(\mathrm{mod}p)=3^6(\mathrm{mod}17)=15$ (valor calculat)

Per tant la clau pública serà $(g,p,K)=(3,17,15)$.

Bruce té el text clar

$m=9$ (el qual està entre 1 i p-1)

Bruce tria un $b=5$ aleatori entre 2 i p-1 Bruce calcula

$y_1=g^b(\mathrm{mod}p)=3^5(\mathrm{mod}17)=5$

$y_2=K^{b}m(\mathrm{mod}p)=15^5\cdot 9(\mathrm{mod}17)=1$.

Per lo que el text sifrat és $C_b(m,b)=(y_1=5,y_2=1)$

Per a dessifrar Alicia usa la clau privada $(a=6)$ i la Menuda Teorema de Fermat:

$m=y_1^{p-1-a}{y}_2(\mathrm{mod}p)=5^{10}\cdot 1(\mathrm{mod}17)=9$.

Complex

Vejam una aplicació més real de l'algoritme:

Alicia elegix els valors:

$p=15485863$ (cosí aleatori i per a $p-1=15485862=3*2*7^2*52673$ suponem que 52673 és sufientemente gran)

$g=7$ (generador aleatori)

$a=21702$ (clau privada aleatòria)

Alicia calcula

$K=g^a(\mathrm{mod}p)=7^{21702}(\mathrm{mod}15485863)=8890431$ (valor calculat)

Per tant la clau pública serà $(g,p,K)=(7,15485863,8890431)$.

Bruce té el text clar "HIJO"

$m=7\cdot 26^3+8\cdot 26^2+9\cdot 26+14=128688$ (el qual està entre 1 i p-1)

Bruce tria un $b=480$ aleatori entre 2 i p-1

Bruce calcula

$y_1=g^b(\mathrm{mod}p)=7^{480}(\mathrm{mod}15485863)=12001315$

$y_2=K^{b}m(\mathrm{mod}p)=8890431^{480}\cdot 1286889(\mathrm{mod}15485863)=8263449$.

Per lo que el text sifrat és $C_b(m,b)=(y_1=12001315,y_2=8263449)$ que al decodificarlo queda:

$y_1=12001315=1*26^5+0*26^4+6*26^3+21*26^2+11*26+1$=BAGVLB

$y_2=8263449=18*26^4+2*26^3+4*26^2+0*26+25$=SCEAZ

En lo que el mensage a enviar és (BAGVLB, SCEAZ)

Per a dessifrar Alicia usa la clau privada $(a=21702)$:

$y_1^{-a}{y}_2(\mathrm{mod}p)=14823281\cdot 8263449(\mathrm{mod}15485863)=128688$ ya que per la chicoteta teorema de fermat tenim

$y_1^{-a}(\mathrm{mod}p)=y_1^{p-1-a}(\mathrm{mod}p)=12001315^{15464160}=14823281$

Generalisació

Lo únic que s'utilisa de la congruència mòdul $p$ és que el conjunt $(\mathbb{Z}/p{)}^{\times }=\{x\in \mathbb{Z}:1\le x<p\}$ forma un grup en les operacions mòdul $p$ i que en dit grup el problema del logaritme discret resulta difícil.

Per lo tant, pot canviar-se en este criptosistema al grup $(\mathbb{Z}/p{)}^{\times }$ per qualsevol atre grup $G$ en el que el logaritme discret siga complicat.

Per eixemple, resulta prou efectiu utilisar com a grup una curva elíptica sobre $\mathbb{Z}/p$ (vore Criptografia de curva elíptica), ya que no es coneix un algoritme de temps subexponencial capaç de resoldre el problema del logaritme discret en curves elíptiques en general.