Congettura di Birch e Swinnerton-Dyer

Tempo di vacanze e di riflessioni (attenti alle scottature!)

Il 2 agosto è stato il compleanno dell'ottantenne Peter Swinnerton-Dyer! Colui che insieme a Birch formulò una leggendaria congettura, decimo problema di Hilbert e definita da Andrew Wiles uno dei problemi del Millennio!

Nel blog precedente avevamo iniziato a parlarvi di curve ellittiche, mentre qui sotto il sole e lo scroscìo del mare con l'aiuto di Rosario Turco, vi proponiamo un bel articolo a prosieguo sull'argomento:

"La congettura di Birch e Swinnerton-Dyer"

Buona lettura e buone vacanze!

:-)

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);

}

Crittografia asimmetrica (RSA)

Finora abbiamo esaminato come fattorizzare due semiprimi RSA, con l'aiuto e la creazione di software con PARI/GP.

Come è noto la crittografia è detta asimmetrica perchè fa uso di due chiavi: una pubblica ed una privata; mentre la crittografia simmetrica ha una sola chiave da tener segreta.

Adesso ci poniamo il problema di come crittografare un messaggio in RSA . La teoria è nota; i passi sono:
1 Alice sceglie casualmente, col suo algoritmo, due numeri primi p e q distinti e grandi (circa trecento cifre) e calcola N = p*q;
2 si calcola la funzione di Eulero phi(N)= (p -1)(q -1);
3 l'algoritmo "butta" via p e q (sono da tenere segreti);
3 si determina la coppia KPu=(puK,N) che costituisce la chiave pubblica che Alice darà agli amici (es: Bob), che la useranno per inviare messaggi ad Alice;
4 Alice si conserva la chiave privata KPr=(N,prK);
5 puK e prK devono esser ricavate in modo da rispettare determinate regole: puK e phi(N); devono essere coprimi e puk * prK deve essere congruo 1 mod phi(N);
6 L'algoritmo di Alice a questo punto può fare a meno anche di phi(N);

Ora Bob può inviare un messaggio ad Alice usando la chiave publica che Alice ha distribuito a tutti; mentre Alice potrà decrittare i messaggi con la chiave privata che deve conservare gelosamente.

Se Bob volesse ricevere anche lui messaggi sicuri dai suoi amici dovrà creare a sua volta una coppia di chiavi proprie: quella pubblica da dare agli amici e quella privata da conservare gelosamente.

La generazione delle coppie di chiavi è fatta una sola volta.

Che c'entra la fattorizzazione? C'entra!

Alice a Bob dà N e puK ma Bob sa soltanto che N che è un composto (semiprimo RSA) con moltissime cifre e dispone del puK. Se riuscisse a fattorizzare N in tempi brevi saprebbe i due numeri primi p e q, si calcolerebbe phi(N) e di conseguenza sarebbe capace di calcolarsi prK.

Per cui i messaggi non sarebbero più segreti!

Qual è il punto di forza/punto debole del RSA?

Il problema è che "fattorizzare N" è un problema non polinomiale e in generale P è diverso da NP; il che vuol dire conosciamo bene un metodo deterministico (un algoritmo) per fattorizzare N ma per poterlo completare servono tempi tanto più elevati quanto più è la lunghezza del numero di cifre di N.

Basta uan chiave a soli 1024 bit ed è inutile solo tentare.


Nel seguito un algoritmo didattico di crittografia RSA e dei problemini che pone.

Il messaggio di partenza è convertito in numerico ottenuto dalla somma di ogni valore del carattere, nell'alfabeto scelto (A...Z di 26 caratteri), moltiplicato per la potenza di 27 della posizione del carattere nel messaggio. Qui si è scelto di partire dall'esponente 1 della potenza.

Il blocco di test conveniente da crittografare è dato da log n / log 26 circa 22 caratteri. Per cui se il testo è maggiore va suddiviso in blocchi e crittografato: ad esempio ogni blocco costituisce una riga scritta in un file. L'algoritmo didattico non prevede lettura e scrittura da file ma è facilemnte estendibile anche in tal senso.

La decrittazione usa la funzione inversa del crypting. La conversione da numero del messaggio decrittato a stringa avviene con una conversione basata su potenze di 27.

Perchè potenza di 27 e non di 26? una comodità algoritmica (è "un consentitemi di ..." informatico!)

Il problema era Z corrisponde al valore 90-64=26 e quindi si sarebbe ottenuto nell'algoritmo di seguito un valore di 26*26^weigth e nella decodifica da numero a testo avremmo avuto un errore perchè la max potenza cercata sarebbe stata maggiore di una unità rispetto al reale.

Invece con 26*27^weigth i conti tornano rapidamente e si semplifica il numero di linee di codice necessarie.

Con un pò di lavoro si può estendere l'esempio anche ad un alfabeto alf>26 caratteri, contenente anche spazi, numeri, punteggiatura, lettere minuscole, parentesi etc, ovviamente modificando iil software con potenza alf. Nell'esempio di sotto vanno invece usate solo lettere maiuscole senza spazi etc.

Esempio di messaggio da crittare: ANTONIOVAACASADELLAMICO



/*
*
* Rosario Turco
*/

createCryptRSA() = local (p,q, KP, phi);

KP=vector(3);

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

q = nextprime(random(10^35));


KP[1]=p*q; /* N */

phi = (p-1) * (q-1); /* phi N */

print("phi : ", phi);


/*
* Person A produce own private key and public key */
/* Public key = (N, puk) */
/* Private key = (N, prk) */

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

puK = random(q);

print("\nN : ", KP[1]);

while(gcd(phi,puK)!=1,puK=puK+1);

KP[2]=puK;
print("puK : ", puK);


prK = lift(Mod(puK,phi)^(-1));


KP[3]=prK;
print("prK : ", prK);


/* I verify that prk*puk is congrue con 1 mod phi */
test = (prK * puK) % phi;

if( test == 0,
error("Test NOK: It isn't congrue 1 mod phi"); );

print(" ");

return(KP);

}

/*
* External Function
*/

{get26Ascii(str) = local (MyW, weight, i, a, m);


weight = length(str);

MyW=Vecsmall(str);


m=0;

/*
I use a power of 27 otherwise char Z will have
26*26^weight and this doesn't work well
with getMsg
*/

for( i=1,weight,

a = MyW[i]-65+1;
m = a*(27^weight) + m;
weight--;
);


return(m);

}


/*
* External function
*/
{getMsg(num) = local (a=num,d=27,r=0, msgM="", amax=0);


while( d>26,

amax = maxk26k(a);
d = floor(a/(27^amax));
r = a%(27^amax);
msgM=concat(msgM,Strchr(d+64));

if( r>=26, a = r; d=27;);
if( r<26 & r!=0, msg=concat(msgM,Strchr(r+64)); d=1;);

);

return(msgM);

}

/*
* Internal function
*/

{maxk26k(n) = local (k);

k=0;

while( 27^k <= n, k++;);

return(k-1);

}

/*
* External function
*/

{cryptWordRSA(m, N, puK) = local (secret);


secret = lift(Mod(m,N)^puK);
print("\nsecret value: ", secret);
print(" ");


return(secret);


}
/*
* External function
*/

{decryptWordRSA(secret, N, prK) = local (desecret, msg);

desecret = lift(Mod(secret,N)^prK);

print("decrypt value: ", desecret);

print ("\nTest OK if decrypt value is equal to m value");

return(desecret);


}

/*
Test function

Person B transmit a message to A with public key di A
Person A decrypt with own private key

If person A transmit a message to B, A must use the public key of B

*/

{testRSA(strMyWord) = local (vec,ms,secretRSA,desecretRSA,msg);

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

ms = get26Ascii(strMyWord);
print("m : ", ms);

secretRSA=cryptWordRSA(ms, Key[1], Key[2]);


/* Now A decrypt */

desecretRSA=decryptWordRSA(secretRSA,Key[1],Key[3]);

msg = getMsg(desecretRSA);
print("\nmsg decriptato: ", msg);

return;

}