RSA.

RSA (Rivest-Shamir-Adleman) è un algoritmo di crittografia asimmetrica tra i più utilizzati al mondo. Sviluppato nel 1977, si basa sulla difficoltà matematica di fattorizzare grandi numeri primi.

Generazione delle Chiavi RSA

1. Generazione numeri primi: Si generano 2 numeri primi distinti, molto grandi, denominati p e q.

2. Calcolo del modulo: Si calcola il valore del modulo, condiviso fra le chiavi, con la formula n = p * q.

3. Funzione di Eulero: Rappresentata con il simbolo φ(n) o con la lettera m, indica quanti numeri interi positivi sono coprimi con n nell'intervallo [1, n-1]. Si calcola con la formula φ(n) = (p-1) * (q-1).

4. Esponente pubblico: È un qualsiasi numero intero che rispetti le condizioni 1 < e < φ(n) e M.C.D.(e, φ(n)) = 1. Deve quindi essere coprimo con φ(n).

5. Esponente privato: È un qualsiasi numero intero, indicato con k, che rispetti la condizione (e * k) mod φ(n) = 1. Può anche essere rappresentato con d.

6. Chiavi RSA: Sono così composte: Kpub(e, n) - Kpr(k, n).

Suggerimento di sicurezza

Per ambienti di sviluppo, le chiavi di lunghezza inferiore a 2048 bit sono considerate poco sicure. Utilizza una dimensione maggiore, come ad esempio 3072, per un buon compromesso fra sicurezza e velocità di calcolo.

Calcolo delle funzioni RSA

• Cifratura: x = m^e mod n
• Decifratura: m = x^k mod n

Essendo i valori di RSA molto grandi, anche fino a 600 cifre, effettuare calcoli diretti sarebbe molto oneroso per il computer. Viene quindi applicato l'algoritmo di Esponenziazione modulare, illustrato di seguito.

Esponenziazione modulare

L'esponenziazione modulare è l'operazione matematica che permette di calcolare rapidamente grandi potenze riducendole in potenze minori, e con le proprietà dell'algebra modulare semplificare le operazioni. È il fondamento matematico dell'algoritmo RSA e di gran parte della crittografia asimmetrica.

Riproponiamo l'algoritmo implementato nella nostra app:

java
package app.cryptea.utils;

import java.math.BigInteger;

public class EspMod {
    
    public static BigInteger doIt(BigInteger a, BigInteger b, BigInteger n) {
        BigInteger result = BigInteger.valueOf(1);
        
        // 1. Calcolo il primo modulo della produttoria
        a = a.mod(n);

        // 2. Avvio il ciclo while per effettuare tutti i prodotti
        // mentre b > 0 (true = 1)
        while (b.compareTo(BigInteger.ZERO) == 1) {
            if (b.getLowestSetBit() == 0) {
                // se è dispari (ultimo bit uguale a 1)
                result = (result.multiply(a)).mod(n);
            }

            // 3. Calcolo la successiva potenza
            a = (a.multiply(a)).mod(n);

            // 4. Divido per 2 b
            b = b.shiftRight(1);
        }

        return result;
    }
}
Espandi

La classe BigInteger di Java già implementa questo algoritmo con il metodo .modPow().