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;

}