Implementazioni di algoritmi/RSA

Wikibooks, manuali e libri di testo liberi.
Indice del libro

In crittografia l'acronimo RSA indica un algoritmo di crittografia asimmetrica, utilizzabile per cifrare o firmare informazioni.

Nel 1976 Whitfield Diffie e Martin Hellman, crittologi americani, hanno ipotizzato la creazione di un cifrario "asimmetrico" composto da "chiavi pubbliche". Il sistema di crittografia si basa sull'esistenza di due chiavi distinte, che vengono usate per cifrare e decifrare. Se la prima chiave viene usata per la cifratura, la seconda deve necessariamente essere utilizzata per la decifratura e viceversa. La questione fondamentale è che le due chiavi siano indipendenti l'una dall'altra, in modo che se anche si è a conoscenza di una delle due chiavi, non si possa risalire all'altra, garantendo in questo modo l'integrità della crittografia.

Per poter realizzare con il cifrario asimmetrico un sistema crittografico pubblico è importante che un utente si crei autonomamente entrambe le chiavi, denominate "diretta" ed "inversa", e ne renda pubblica una soltanto. Così facendo si viene a creare una sorta di "elenco telefonico" a disposizione di tutti gli utenti, che raggruppa tutte le chiavi dirette, mentre quelle inverse saranno tenute segrete dagli utenti che le hanno create, ottenendo in questo modo i presupposti necessari alla sicurezza del sistema.

Implementazione in Java[modifica]

/**Implementa la suddivisione in blocco di un messaggio.
 * @param byte[] msg, rappresenta il messaggio;
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * Determina il numero di blocchi utilizzando lo schema PKCS#5, ovvero:
 * Supponiamo che la grandezza del blocco sia di 64 bytes ed il messaggio sia di 125 bytes. 
 * In condizioni normali avremmo un blocco completo da 64 bytes, più uno
 * incompleto composto da soli 61 byte, facendo rimanere scoperti 3 bytes. 
 * Per far fronte a questo inconveniente aggiungeremo in coda tre volte il numero 3 
 * (in binario ovviamente).
 * Es.
 *      Messaggio      Padding
 *      ... ... ... 00000011 00000011 00000011
 *  
 * Con questa tecnica il messaggio risulta essere suddiviso perfettamente in blocchi.
 * Inoltre ciò significa che ogni cifrario che usa tale metodo risulta essere efficace
 * limitatamente ad un numero di blocchi di grandezza massima di 255 bytes.
 * @return un valore byte[], rappresentate il messaggio impacchettato.
 * */
private static byte[] pad(byte[] msg,int blockSize) {
        //Verifica che il messaggio sia adeguato per lo schema PKCS#5
        if (blockSize<1||blockSize>255) 
                throw new IllegalArgumentException("La grandezza dei blocchi deve essere compresa tra 1 e 255.");
        //Padding del messaggio
        int numberToPad=blockSize-msg.length%blockSize;
        byte[] paddedMsg=new byte[msg.length+numberToPad];
        System.arraycopy(msg,0,paddedMsg,0,msg.length);
        for (int i=msg.length;i<paddedMsg.length;i++) 
                paddedMsg[i]=(byte)numberToPad;
 
        return paddedMsg;
}//pad
 
/**Questo metodo prende in messaggio sottoposto a padding,
 * e lo converte in un array midimensionale di byte.
 *      Ogni riga in questa matrice è un blocco.
 * Il metodo di decriptaggio lavorerarà con questi due array.
 * @param byte[] msg, rappresenta il messaggio già sottoposto alla tecnica del padding;
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return una matrice byte[][], rappresentate il messaggio in due blocchi.
 * */
private static byte[][] block(byte[] msg,int blockSize) {
        //Crea un array di bytes 2D sottoposto alla tecnica del padding
        int numberOfBlocks=msg.length/blockSize;
        byte[][] ba=new byte[numberOfBlocks][blockSize];
        for (int i=0;i<numberOfBlocks;i++)
                for (int j=0;j<blockSize;j++)
                        ba[i][j]=msg[i*blockSize+j];
 
        return ba;
}//block
 
/**Questo metodo spacchetta il messaggio; Ciò avviene dopo l'operazione di criptaggio o decriptaggio.
 * Questi riceve in input un array 2D di bytes e lo riconverte in un array lineare di bytes.
 * Nell'applicare tale metodo bisogna avere accortenza nel verificare che
 * la trasformazione di cifratura o decifratura possa produrre un numero intero inferiore alla 
 * dimensione del blocco stesso.
 * In tal caso, si provvederà a riempire la parte finale del blocco.
 * @param byte[][] ba, rappresenta una matrice nella quale è memorizzato il messaggio n due blocchi.
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return un array byte[], dove memorizzare il codice decifrato
 * */
private static byte[] unBlock(byte[][] ba,int blockSize) {
 
        //Crea un array byte[], dove memorizzare il codice decifrato
        byte[] m2=new byte[ba.length*blockSize];
        //Pone i blocchi in un array 1D
        for (int i=0;i<ba.length;i++) {
                int j=blockSize-1;
                int k=ba[i].length-1;
                while (k>=0) {
                        m2[i*blockSize+j]=ba[i][k];
                        k--;
                        j--;
                }//while
        }//for
 
        return m2;
}//unBlock
 
/**
 * Questo metodo rimuove il padding dal messaggio. 
 * Esamina il valore numerico dell'ultimo blocco ed in base
 * a tale valore ne elimina una quantità pari di blocchi 
 * aggiunti durante la fase di padding.
 * 
 * @param byte[] msg, rappresenta il messaggio con padding.
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return un array byte[], sprovvisto di blocchi di padding.
 * */
private static byte[] unPad(byte[] msg,int blockSize) {
        /*Determina la quantitù di blocchi, testando il valore memorizzato
        nell'ultimo blocco*/
        int numberOfPads=(msg[msg.length-1]+256)%256;
        //Elimina i blocchi di padding
        byte[] answer=new byte[msg.length-numberOfPads];
        System.arraycopy(msg,0,answer,0,answer.length);
        return answer;
}//unPad
 
/**
 * Cripta secondo il sistema RSA
 * @param msg di tipo byte[], rappresenta il messaggio in chiaro espresso in byte
 * @param e di tipo BigInteger, rappresenta la chiave pubblica
 * @param n di tipo BigInteger, rappresenta il modulo
 * @return un array di byte
 * */
public static byte[] RSAEncipher(byte[] msg,BigInteger e,BigInteger n) {
 
        //Determina la grandezza in blocchi del testo in chiaro
        int blockSize=(n.bitLength()-1)/8;
        byte[][] ba=block(pad(msg,blockSize),blockSize);
        //Avvia il processo di crittazione
        for (int i=0;i<ba.length;i++) 
                ba[i]=getBytes(new BigInteger(1,ba[i]).modPow(e,n));
 
        //il blocco cifrato è di una dimensione maggiore di byte rispetto al testo in chiaro.
        return unBlock(ba,blockSize+1);
}//RSAEncipher
 
/**
 * Decripta secondo il sistema RSA
 * @param msg di tipo byte[], rappresenta il messaggio criptato espresso in byte
 * @param d di tipo BigInteger, rappresenta la chiave privata
 * @param n di tipo BigInteger, rappresenta il modulo
 * @return un array di byte
 * */
public static byte[] RSADecipher(byte[] msg,BigInteger d,BigInteger n) {
 
        //Calcola la grandezza del blocchi criptati
        int blockSize=(n.bitLength()-1)/8+1;
        byte[][] ba=block(msg,blockSize);
        //Avvia la decrittazione
        for (int i=0;i<ba.length;i++) 
                ba[i]=getBytes(new BigInteger(1,ba[i]).modPow(d,n));
 
        //spacchetta il testo
        return unPad(unBlock(ba,blockSize-1),blockSize-1);
}//RSADecipher