Crittografia a Chiave Pubblica in C: Implementare RSA dall'Algoritmo al Codice

Perché implementare RSA in C?

La crittografia a chiave pubblica è uno dei pilastri della sicurezza informatica moderna. Ogni volta che effettui un pagamento online, accedi a un sito HTTPS o firmi digitalmente un documento, molto probabilmente stai utilizzando un algoritmo basato su chiavi asimmetriche basato sugli stessi principi che vedremo oggi. Comprendere come funziona a livello di codice, e non solo in astratto, è una competenza fondamentale per chiunque voglia fare sviluppo firmware, sistemi embedded sicuri o semplicemente voglia capire davvero come funziona Internet.

In questo articolo completiamo l’implementazione in linguaggio C dell’algoritmo RSA, partendo dalla matematica dell’esponenziazione modulare fino alla crittografia di stringhe complete. Se non hai visto la prima parte, ti consiglio di recuperarla prima di procedere: lì abbiamo scelto i parametri dell’algoritmo e posto le basi dell’implementazione.

Esempio: parametri dell’algoritmo RSA

Prima di scrivere codice, richiamiamo velocemente la struttura dell’algoritmo. Abbiamo scelto due numeri primi:

P = 13, Q = 17
N = P × Q = 221 (il modulo)
φ(N) = (P−1)(Q−1) = 192 (il toziente di Eulero)
Esponente pubblico e = 37 → chiave pubblica: (37, 221)
Esponente privato d = 109 → chiave privata: (109, 221)

Questi numeri sono volutamente piccoli per facilitare il debugging e la comprensione. In un sistema reale si usano numeri con centinaia o migliaia di cifre.

La matematica della crittografia RSA

Cifrare un messaggio

Dato un valore intero m compreso tra 0 e N-1, il testo cifrato si ottiene con:

C = m^e mod N

Per esempio, con m = 122:

C = 122^37 mod 221 = 5

Decifrare il messaggio

La decifrazione usa la chiave privata in modo analogo:

m = C^d mod N

Quindi:

m = 5^109 mod 221 = 122 ✓

La simmetria è elegante: la stessa struttura matematica, con esponenti diversi, permette di cifrare e decifrare. Il problema è implementarla correttamente in C.

Il problema dell’overflow: oerché l’implementazione naive non funziona

Il primo istinto quando si deve calcolare m^e mod N è scrivere qualcosa del tipo:

unsigned long encrypt(unsigned long m, unsigned long e, unsigned long n) {
    unsigned long result = 1;
    for (unsigned long i = 0; i &lt; e; i++) {
        result *= m;
    }
    return result % n;
}

Il problema è evidente appena si prova: anche con numeri piccoli come i nostri si va immediatamente in overflow. 122^37 è un numero astronomicamente grande, ben oltre i 64 bit di un unsigned long. Il risultato sarà completamente sbagliato.

Questo è esattamente il motivo per cui RSA richiede un approccio diverso: l’esponenziazione modulare efficiente.

Modular exponentiation: L’algoritmo memory-efficient

La soluzione si basa su una proprietà fondamentale dell’aritmetica modulare:

(A × B) mod M = ((A mod M) × (B mod M)) mod M

Questa proprietà ci permette di “tenere piccoli” i numeri durante il calcolo, applicando il modulo ad ogni passo invece di aspettare la fine.

Derivazione dell’Algoritmo

Consideriamo il caso semplice m^3 mod N:

m^3 mod N = (m^2 × m) mod N
           = ((m^2 mod N) × (m mod N)) mod N

Poiché m < N per definizione, m mod N = m. Quindi:

= (m^2 mod N) × m) mod N

Ora espandiamo m^2 mod N:

m^2 mod N = (m × m) mod N

Vediamo il pattern: ad ogni passo moltiplichiamo l’accumulatore per m e prendiamo il modulo. Questo garantisce che l’accumulatore non superi mai N-1, eliminando il rischio di overflow.

Implementazione in C

unsigned long mod_pow(unsigned long m, unsigned long exp, unsigned long n) {
    unsigned long accumulatore = (m * m) % n;
    for (unsigned long i = 2; i &lt; exp; i++) {
        accumulatore = (accumulatore * m) % n;
    }
    return accumulatore;
}

Con questa implementazione, encrypt(122, 37, 221) restituisce correttamente 5, e decrypt(5, 109, 221) restituisce 122.

Nota: Questa implementazione funziona bene per i nostri numeri di esempio. Per un sistema produttivo si userebbe l’algoritmo square-and-multiply che riduce drasticamente il numero di moltiplicazioni necessarie.

Ottimizzare il test di primalità

Prima di affrontare la crittografia di stringhe, vale la pena migliorare la funzione isPrime che abbiamo già nel codice. Due ottimizzazioni importanti:

1. Escludere i numeri pari

Eccetto il 2, nessun numero pari può essere primo:

bool isPrime(unsigned long num) {
    if (num &lt; 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;  // Ottimizzazione: escludi i pari
    
    for (unsigned long i = 3; i * i &lt;= num; i += 2) {  // Solo dispari
        if (num % i == 0) return false;
    }
    return true;
}

2. Fermarsi alla radice quadrata

Questa ottimizzazione si basa su una proprietà matematica elegante. Per qualsiasi divisore a di n, esiste un corrispondente b tale che a × b = n. Se a < √n, allora necessariamente b > √n. Questo significa che:

Se un numero ha divisori, almeno uno è ≤ √n
Se non troviamo divisori fino a √n, non ne troveremo nemmeno dopo

Invece di calcolare sqrt(num) — operazione floating point potenzialmente costosa — usiamo il confronto equivalente i * i <= num. Il risultato è identico, ma rimaniamo nell’aritmetica intera.

Queste due ottimizzazioni insieme riducono il numero di iterazioni in modo significativo, specialmente per numeri grandi.

Cifrare e Decifrare Stringhe in C

Ora che abbiamo le primitive matematiche, possiamo affrontare la crittografia di testo. La strategia è semplice:

Per ogni carattere della stringa, prendi il suo codice ASCII
Applica encrypt() al codice ASCII
Salva il risultato in un array di unsigned long

Il motivo per cui usiamo unsigned long e non char per il testo cifrato è che i valori cifrati possono essere compresi tra 0 e N-1 = 220, non necessariamente mappabili su caratteri ASCII validi. La dimensione dell’array cifrato è uguale alla lunghezza della stringa originale: ogni carattere produce esattamente un valore cifrato.

Leggere Stringhe con Spazi: fgets vs scanf

Un dettaglio pratico importante: scanf("%s", ...) si ferma al primo spazio. Per leggere stringhe con spazi usiamo fgets:

// Pulisce il buffer prima di fgets
int c;
while ((c = getchar()) != '\n' &amp;&amp; c != EOF);

// Legge la stringa
fgets(string_to_encode, STRING_LEN, stdin);

// Rimuove il newline finale catturato da fgets
string_to_encode[strcspn(string_to_encode, "\n")] = '\0';

La funzione strcspn restituisce la lunghezza del segmento iniziale che non contiene i caratteri specificati — nel nostro caso trova la posizione del \n e lo sostituisce con il terminatore \0.

Mettere tutto Insieme: un programma RSA interattivo

Con i pezzi che abbiamo costruito, possiamo assemblare un programma che:

Chiede i numeri primi P e Q all’utente
Calcola N, φ(N) e mostra i candidati per E
Chiede all’utente di scegliere E e D
Cifra e decifra stringhe arbitrarie

Testando con P = 83, Q = 97:

N = 8051
φ(N) = 7872
E scelto: 907
D calcolato: 2083

Il programma cifra e decifra correttamente qualsiasi stringa, spazi e punteggiatura inclusi. Le prestazioni rimangono buone anche con questi valori più grandi, a conferma che l’algoritmo di esponenziazione modulare è efficiente.

I Limiti di questa implementazione

È importante essere chiari sui limiti didattici di quanto abbiamo implementato:

Sicurezza: Con N = 8051 siamo ben lontani da qualsiasi standard di sicurezza reale. RSA è considerato sicuro con chiavi di almeno 2048 bit (N con circa 600 cifre decimali). La nostra N ha 4 cifre: un attacco a forza bruta richiederebbe microsecondi.

Aritmetica a precisione arbitraria: Lavorare con numeri RSA reali richiede librerie di big integer come GMP (GNU Multiple Precision Arithmetic Library). Le operazioni standard del C su unsigned long non bastano.

Hardware dedicato: Non è un caso che molti microcontrollori e SoC moderni includano un coprocessore crittograficohardware, ottimizzato specificamente per l’esponenziazione modulare su numeri grandi. Su sistemi embedded dove le prestazioni contano, implementare RSA in software puro può essere proibitivo.

Conclusioni

In questi due video abbiamo percorso un cammino completo: dalla matematica dell’algoritmo RSA — numeri primi, toziente di Eulero, chiavi pubblica e privata — fino all’implementazione funzionante in linguaggio C, con tutti i dettagli pratici che si incontrano davvero scrivendo codice.

I concetti chiave da portare a casa sono:

L’esponenziazione modulare è il cuore computazionale di RSA e richiede un approccio specifico per evitare overflow
La proprietà (A × B) mod M = ((A mod M) × (B mod M)) mod M è la chiave per mantenere i numeri gestibili
Ottimizzare isPrime con il test fino a √n è un esempio di come la matematica si traduce direttamente in efficienza computazionale
La crittografia asimmetrica in produzione richiede infrastrutture (big integer, hardware dedicato) che vanno ben oltre il linguaggio base

Con questo si chiude il modulo sulla crittografia. Nei prossimi video continueremo il corso avanzato di C con altri argomenti fondamentali per chi sviluppa firmware e sistemi embedded.