Crittografia: curve ellittiche - il logaritmo discreto - algoritmo di El Gamal

Crittografia: curve ellittiche - il logaritmo discreto - algoritmo di El Gamal

Nella crittografia asimmetrica, ovvero a chiave pubblica e privata, esistono anche altri algoritmi interessanti, basati ad esempio sulla teoria delle curve ellittiche e che fanno leva sulla grossa difficoltà di risolvere in tempi brevi un "problema di fattorizzazione discreta" noto anche come problema del logaritmo discreto.

Qui addirittura le chiavi pubbliche scambiate tra Alice e Bob, come vedremo, hanno anche maggiori informazioni rispetto ad una tecnica RSA.

Supponiamo che Alice compia i seguenti passi:
1 sceglie randomicamente un numero primo p>1 a molte cifre, poi un intero g compreso tra 1 e p ed un intero a compreso tra 1 e p.
2 calcola il valore g^amodp
3 crea la propria chiave pubblica KpuA=(p, g, g^a) e la da ai suoi amici (es: Bob)
4 la propria chiave privata è Kpr=a

Bob, ricevuta KpuA da Alice farà i seguenti passi:
1 genera un proprio intero b: b appartenga a Zp (ovvero tra 1 e p)

2 costruisce la propria chiave pubblica KpuB=(p, g, g^b) e la da ad Alice

3 custodisce la propria chiave privata KprB=b

4 sceglie un messaggio M apaprtenente a Zp


Bob adesso cripta M e lo trasmette ad Alice. Bob esegue il crypting nel seguente modo:

Mc = M(g^a)^bmod p

Alice conosce KpuB, quindi g^b.

Da qui calcola (g^b)^amod p

A questo punto Alice è in grado di decriptare il messaggio Mc perchè:

Mc(g^b)^a)^(-1)=M(g^a)((g^b)^a)^-1=M

Fattorizzazione

Cosa c'entra il logaritmo e perchè è discreto?

Alice conosce la chiave pubblica di Bob in cui c'è p e g^b o meglio g^b mod p; per cui per sapere la chiave privata di Bob dovrebbe ricavarsi b da g^b mod p. In pratica g è la base e b l'esponente dell'elevazione a potenza. L'operazione inversa di ricavare l'esponente (b) a cui elevare la base (g) per ottenere l'argomento è il logaritmo! Solo che lavoriamo in aritmetica modulo ecco perchè si parla di logaritmo discreto!

Ebbene l'operazione di ricavarsi il logaritmo discreto, tenendo conto che sia g che b sono a molte cifre, è banale ma richiede molto tempo. Ed è questo il punto di forza di questa crittografia.

Un algoritmo noto per affrontare il logaritmo discreto è quello di Fermat.

Curve ellittiche
Cosa c'entrano le curve ellittiche? Studiando le curve ellittiche e, ad esempio il problema del millennio di Birch, Swinnerton e Dyer, si scopre che, per poter trattare l'infinito numero di punti a valore razionale Q, è conveniente far riferimento alla aritmetica modulo. Ma questo lo affronteremo un'altra volta e con calma.


Software didattico

Segue un esempio di algoritmo didattico su EL GAMAL, dove alcune funzioni sono comuni con il blog precedente del RSA e che troverete lì facilmente.

Inoltre vine mostrato anche un algoritmo per affrontare il problema del logaritmo discreto.

La libreria invece è disponibile su INTERNET grazie all'autore.

/*
* EL GAMAL
*
* External function
*
*/

{createCryptElG() = local (KPEG, p, g, a, b, ga, gb);

KPEG=vector(6); /* It's Public Key of El Gamal */

p = nextprime(random(10^40));

g = random(p);

a = random(p); /* It's Private Key of El Gamal user A */

b = random(p); /* It's Private Key of El Gamal user B */

ga=lift(Mod(g,p)^a);
gb=lift(Mod(g,p)^b);


/* I put them in a vector KPEG for convenience in the test*/

KPEG[1]=g;
KPEG[2]=a; /* a for user A and b for user B */
KPEG[3]=ga; /* ga for user A and gb for user B */
KPEG[4]=p; /* p is shared */
KPEG[5]=b;
KPEG[6]=gb;


return(KPEG);

}

/*
* External function
*/

{cryptWordElG(mc, p, a, gb) = local (msecret);


msecret = lift(mc*Mod(gb,p)^a);
print("\nsecret value: ", msecret);
print(" ");


return(msecret);


}

/*
* External function
*/

{decryptWordElG(secretElG, p, b, ga) = local (desecretElG, msg);


desecretElG = lift(secretElG*(Mod(ga,p)^b)^-(1));

print("decrypt value: ", desecretElG);

return(desecretElG);


}

{testElG(strMyWordTest) = local (msc,Msecret,Mdesecret,msgs);

/* B has got a KeyPub and transmit to A a message */
Key=vector(6);

Key=createCryptElG();

/* B tx to A */
msc = get26Ascii(strMyWordTest);
print("msc : ", msc);


Msecret=cryptWordElG(msc, Key[4], Key[2],Key[6]);

/* A decrypts */
Mdesecret=decryptWordElG(Msecret,Key[4],Key[5],Key[3]);

print("Decodifica\n");
msgs = getMsg(Mdesecret);
print("\nmsg decriptato: ", msgs);


return;


}

/*
********************************************************
* Quadratic Sieve Factoring
*
* x^2 = a^2 mod N
* x^2 = a^2 + k*N (k=0, k=1)
*
* Variant of Fermat's algorithm
* This method is good for odd numbers
*
* Rosario Turco
********************************************************
*/

{qsfRSA(n) = local (col, vecOut, xq, a, x1, x2);

if( n<2>1"));

col = bigomega(n);

/* trivial solution: 1 and n it is a prime*/
if( col == 1, print1("qsfRSA: It's a prime number: ", n); return(););

vecOut=vector(col);

if( col != 2, print1("qsfRSA: It isn't a RSA number. You must insert a RSA number"); return(););

/* if it is a even number ... */
if( Mod(n,2)==0, vecOut[1]=2; vecOut[2]=floor(n/2); return(vecOut););

xq=0; /* xq = x^2 */
a=0;

while( (!ispower(xq,2) | xq == 0), a++; xq=a^2+n;
);

x1=a;
x2=floor(sqrt(a^2+n));

vecOut[1]=x2-x1;
vecOut[2]=x2+x1;

/* if n is a perfect square */
if( x2-x1==1 & x2+x1==n, vecOut[1]=floor(sqrt(n)); vecOut[2]=vecOut[1];);

return(vecOut);

}