Crittografia asimmetrica e algoritmo RSA. Parte II
22 December 2009 da Francesco
In questa seconda parte dell’articolo vedremo come implementare l’algoritmo RSA di cui si era precedentemente discusso in quest’altro articolo solamente in linea teorica. Il linguaggio di programmazione usato sara’ Java, poiche’ fornisce nativamente una classe BigInteger per il supporto di numeri interi di dimensione arbitraria, che useremo per manipolare gli enormi numeri primi necessari alla generazione delle chiavi, impossibili da gestire con tipi di dati primitivi. Non mi soffermero’, ovviamente, su questioni sintattiche relative al linguaggio; inoltre non commentero’ tutto il codice ma solo le parti piu’ importanti, mentre potrete leggere il resto scaricando l’archivio in fondo all’articolo. La prima funzione necessaria al funzionamento della classe e’ quella relativa alla generazione delle chiavi. Come avevamo visto nel precedente articolo, per generare le chiavi si segue una procedura standard che e’ facilmente implementabile usando la classe BigInteger di Java.
BigInteger p = BigInteger.probablePrime(keyLength/2, new SecureRandom()); // Generiamo un numero "probabilmente" primo, p
BigInteger q = BigInteger.probablePrime(keyLength/2, new SecureRandom()); // Generiamo un numero "probabilmente" primo, q
// Calcoliamo n e phi
BigInteger n = p.multiply(q);
BigInteger phi = p.subtract(new BigInteger("1")).multiply(q.subtract(new BigInteger("1")));
// publicKey conterra' l'esponente pubblico e,
// scegliendo e come il primo numero primo successivo a
// p, esso sara' anche coprimo con phi (come richiesto nell'algoritmo)
this.publicKey = p.nextProbablePrime();
this.privateKey = publicKey.modInverse(phi);
this.n = n;
}
Una precisazione sulla funzione probablePrime() e nextProbablePrime(): esse restituiscono un numero che probabilmente e’ primo, utilizzando dei test di probabilita’ probabilistici. Il margine di errore e’ molto basso: per essere precisi, la probabilita’ che un numero restituito da queste due funzioni sia composto e’ sempre minore di 2^-100 e la velocita’ dell’algoritmo lo rende preferibile ad uno deterministico nella generazione delle chiavi. Una volta generate le chiavi, si possono gia’ creare le due funzioni di base per criptare/decriptare un numero intero. Ecco il codice:
public BigInteger encrypt(BigInteger m) {
return m.modPow(publicKey, n); // (m^publicKey) % n
}
public BigInteger decrypt(BigInteger m) {
return m.modPow(privateKey, n); // (m^privateKey) % n
}
Dovrebbe essere abbastanza chiaro. La funzione modPow(e, n) restituisce semplicemente this ^ e % n e ci risparmia un po di calcoli. Con queste due semplici funzioni possiamo pero’ criptare unicamente numeri interi; per poter usare l’algoritmo su un testo piu’ o meno lungo dobbiamo creare altre due funzioni che processano il testo in maniera tale da essere compatibile con l’algoritmo, i passi principali saranno questi:
- aggiungere del padding (casuale) al testo in modo da renderlo divisibile in blocchi di uguali dimensioni. la dimensione di ogni blocco sara’ la lunghezza della chiave.
- processare ogni blocco, convertire il testo in un intero e cifrarlo
Per il processo inverso, invece:
- dividere il testo nel numero di blocchi in base alla chiave.
- decriptare ogni blocco e convertire gli interi nel testo corrispondente
- rimuovere il padding.
Ecco il codice con alcuni commenti esplicativi:
public String encrypt(String m) {
/* Per comodita' (piu' sotto si vedra' perche') convertiamo i
* caratteri del messaggio nel loro codice ASCII (esadecimale)
*/
String mHex = "";
for (int i = 0; i < m.length(); i++) {
mHex += Integer.toHexString(m.charAt(i));
}
/* Calcoliamo quanto padding e' necessario, chiamiamolo N, e poi concateniamo al messaggio
* N-1 bytes di padding casuale. L'ultimo non deve essere casuale ma deve contenere appunto
* il numero N, cosi' da poter poi rimuovere la giusta quantita di padding nella funzione decrypt().
*/
int padding = blockSize - (mHex.length()/2)%blockSize;
for (int i = 0; i < padding-1; i++) { // Prima generiamo N-1 byte casuali
int randomPadding = (int)(10*Math.random());
mHex += randomPadding < 10 ? "0" + Integer.toHexString(randomPadding) : Integer.toHexString(randomPadding);
}
// Ultimo byte di padding
mHex += padding < 10 ? "0" + Integer.toHexString(padding) : Integer.toHexString(padding);
int numBlocks = (mHex.length()/2)/blockSize; // Numero di blocchi in cui dividere il messaggio
String result = "", currentBlock = "";
for (int b = 0; b < numBlocks; b++) {
currentBlock = mHex.substring(b*blockSize*2, (b+1)*blockSize*2);
/* Il blocco corrente, essendo una stringa in formato esadecimale,
* quindi un numero, puo' essere criptato con le due funzioni che abbiamo gia'
* creato precedentemente che accettano come argomento un BigInteger.
*/
// Questo costruttore accetta una stringa, e la base come secondo argomento
BigInteger r = encrypt(new BigInteger(currentBlock, 16));
/* Puo' accadere che la string che otteniamo come risultato abbia un byte in meno,
* in questo caso, per non avere problemi nel decriptare il messaggio, aggiungiamo
* uno zero iniziale che non cambia niente, ma la rende della dimensione corretta.
*/
if (r.toString(16).length() == blockSize*4) {
result += r.toString(16);
} else {
result += ("0" + r.toString(16));
}
}
return result;
}
public String decrypt(String m) {
int numBlocks = (m.length()/2)/(blockSize*2);
String temp = "", currentBlock = "";
/* Questo ciclo, quasi uguale a quello della funzione encrypt(), scorre ogni
* blocco, lo decripta e concatena il risultato in una nuova stringa.
*/
for (int b = 0; b < numBlocks; b++) {
currentBlock = m.substring(b*blockSize*4, (b+1)*blockSize*4);
BigInteger r = decrypt(new BigInteger(currentBlock, 16));
temp += r.toString(16);
}
/* Il padding e' uguale all'ultimo byte della
* stringa, come avevamo precedentemente impostato.
*/
int padding = Integer.parseInt(temp.substring(temp.length()-2), 16);
int actualLength = temp.length() - padding*2;
// Rimuove il padding
temp = temp.substring(0, actualLength);
String result = "";
// Riconverte la stringa da esadecimale a testo
for (int i = 0; i < temp.length(); i+=2) {
result += (char)Integer.parseInt(temp.substring(i,i+2), 16);
}
return result;
}
Tutto il codice e’ contenuto in questo archivio disponibile per il download.
Tags: chiave pubblica, crittografia, crittografia asimmetrica, Java, RSA
Pubblicato in Informatica | Commenti (0)
No comments yet