Crittografia: Cesare, Vigenère e RSA

In quinta, nel programma di informatica e telecomunicazioni, la crittografia arriva dentro il blocco sulle reti: dopo il modello a livelli e i protocolli, il docente passa a come si protegge ciò che viaggia sulla rete. Se la verifica o l’interrogazione cade fra cinque-otto settimane, è il momento giusto per sistemare questo argomento, perché è uno di quelli dove chi ha capito il meccanismo scrive tre righe e prende il voto, mentre chi ha memorizzato lo schema si blocca alla prima variante.

La domanda tipica ha tre forme: scrivi in Python un cifrario di Cesare, spiega la differenza tra crittografia simmetrica e asimmetrica, cifra e decifra un messaggio con RSA usando numeri piccoli. Le tre cose sono collegate e le affronto in quest’ordine, come in un’ora di ripetizione.

Un’avvertenza: su informatica non c’è ancora una simulazione dedicata, quindi qui trovi solo gli esercizi svolti in fondo. Per il quadro di ciò che sta sotto (livelli, protocolli, porte) rimando al post sul modello ISO/OSI e TCP/IP; per VLAN, firewall e VPN dal lato progettazione c’è il post su sistemi e reti di quinta. Qui mi occupo solo di come funzionano i cifrari.

Il vocabolario minimo

Il testo in chiaro è il messaggio originale; il testo cifrato è quello che esce dall’algoritmo; la chiave è il parametro segreto che decide come si cifra; cifrare va dal chiaro al cifrato, decifrare torna indietro con la chiave. Chi tenta di leggere il messaggio senza la chiave fa crittanalisi.

Principio di Kerckhoffs, che i docenti citano spesso: la sicurezza deve dipendere solo dalla segretezza della chiave, non da quella dell’algoritmo.

Cifrari a sostituzione: Cesare

Nel cifrario di Cesare ogni lettera viene spostata in avanti di $k$ posizioni nell’alfabeto; la chiave è il numero $k$ . Con $k = 3$ la A diventa D, la B diventa E, e così via; in fondo l’alfabeto si richiude: X diventa A, Y diventa B, Z diventa C.

Per scriverlo bene serve il modulo. Numerando le lettere da 0 (A) a 25 (Z), la cifratura della lettera di indice $x$ è:

c = (x + k) mod 26

e la decifratura è l’operazione inversa:

x = (c - k) mod 26

Ecco il codice Python, quello che in verifica si chiede di scrivere a mano:

def cesare(testo, k):
    out = ""
    for c in testo.upper():
        if c.isalpha():
            out += chr((ord(c) - 65 + k) % 26 + 65)
        else:
            out += c
    return out

ord(c) restituisce il codice della lettera (la A vale 65), sottraendo 65 si ottiene l’indice 0-25, si somma $k$ , si riduce modulo 26 e con chr(... + 65) si torna a una lettera. Spazi e punteggiatura passano invariati.

Esempio: cesare("CIAO MONDO", 3) restituisce FLDR PRQGR. Per decifrare non serve una seconda funzione: basta chiamare cesare("FLDR PRQGR", -3) e si riottiene CIAO MONDO, perché in Python % con un numero negativo dà comunque un risultato fra 0 e 25.

Limite del codice, utile da dire se te lo chiedono: le lettere accentate passano isalpha() ma escono dall’alfabeto di 26 lettere, e upper() fa perdere la distinzione fra maiuscole e minuscole.

Perché Cesare non è sicuro. Le chiavi possibili sono solo 25 (con $k = 0$ non cambia nulla): un attacco a forza bruta le prova tutte in un istante. Ma anche senza provarle tutte esiste l’analisi delle frequenze: in italiano le lettere più frequenti sono E, A, I, O. Se nel cifrato la lettera più comune è, per esempio, H, è plausibile che H corrisponda a E e quindi $k = 3$ . Cesare è un cifrario di sostituzione monoalfabetica: ogni lettera del chiaro viene sempre sostituita dalla stessa lettera del cifrato, e questo lascia intatte le frequenze.

Vigenère: più alfabeti, stessa idea

Il cifrario di Vigenère nasce per correggere esattamente quel difetto. La chiave non è un numero ma una parola, e ogni lettera della parola dà uno spostamento diverso, usato a turno. Con la chiave LUNA gli spostamenti sono L=11, U=20, N=13, A=0, poi si ricomincia.

Cifro le prime quattro lettere di ATTACCO con la chiave LUNA (indici A=0, T=19):

A + L: $0 + 11 = 11$ , cioè L
T + U: $19 + 20 = 39$ , $39 mod 26 = 13$ , cioè N
T + N: $19 + 13 = 32$ , $32 mod 26 = 6$ , cioè G
A + A: $0 + 0 = 0$ , cioè A

Il cifrato inizia con LNGA. Notale: le due T di ATTACCO sono diventate lettere diverse (N e G). È questo il punto: il cifrario è polialfabetico, e l’analisi delle frequenze semplice non funziona più, perché la stessa lettera in chiaro finisce in lettere diverse.

Non è però invulnerabile: se la chiave è lunga $m$ lettere, il testo si può dividere in $m$ colonne e ognuna è un Cesare, attaccabile con le frequenze. Il difficile per l’attaccante è stimare $m$ . Una chiave casuale, lunga quanto il messaggio e usata una sola volta, dà il cifrario perfetto (one-time pad), ma distribuire chiavi così è impraticabile: è il problema del paragrafo successivo.

Simmetrica o asimmetrica

Cesare e Vigenère sono cifrari simmetrici: la stessa chiave serve per cifrare e per decifrare. Gli algoritmi moderni di questa famiglia (AES è quello da citare) sono molto più robusti e velocissimi, ma restano con un problema: mittente e destinatario devono già possedere la stessa chiave segreta. Se non si sono mai incontrati, come se la scambiano su una rete che non è fidata?

La crittografia asimmetrica risolve questo problema usando una coppia di chiavi: una pubblica, che si può diffondere a chiunque, e una privata, che resta al proprietario. Ciò che si cifra con una si decifra solo con l’altra.

	Simmetrica	Asimmetrica
Chiavi	una sola, condivisa	coppia pubblica/privata
Velocità	alta	bassa (calcoli su numeri enormi)
Problema principale	scambio sicuro della chiave	lentezza
Esempi	Cesare, Vigenère, AES	RSA

Nella pratica si usano insieme: l’asimmetrica per accordarsi su una chiave, la simmetrica per cifrare i dati. Lo si vede nell’HTTPS.

RSA a mano con numeri piccoli

RSA si basa su un fatto: moltiplicare due numeri primi è facile, ma ritrovare i due fattori partendo dal prodotto è difficilissimo se i numeri sono di centinaia di cifre. Qui uso $p = 5$ e $q = 11$ , che per la verifica sono più che sufficienti.

1. Generazione delle chiavi.

Calcolo il modulo:

n = p \cdot q = 5 \cdot 11 = 55

Poi la funzione di Eulero:

φ (n) = (p - 1) (q - 1) = 4 \cdot 10 = 40

Scelgo l’esponente pubblico $e$ coprimo con 40 e minore di 40: $e = 3$ va bene perché $MCD (3, 40) = 1$ .

Calcolo l’esponente privato $d$ come inverso di $e$ modulo 40, cioè tale che:

e \cdot d \equiv 1 (mod 40)

Provo: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ , quindi $d = 27$ .

Chiave pubblica: $(n, e) = (55, 3)$
Chiave privata: $(n, d) = (55, 27)$

( $p$ , $q$ e $φ (n)$ si buttano via: chi li conosce può ricalcolare $d$ .)

2. Cifratura del messaggio $m = 7$ (deve essere minore di $n$ ):

c = m^{e} mod n = 7^{3} mod 55

$7^{3} = 343$ e $343 = 6 \cdot 55 + 13$ (perché $6 \cdot 55 = 330$ ), quindi $c = 13$ .

3. Decifratura:

m = c^{d} mod n = 1 3^{27} mod 55

Non si calcola mai $1 3^{27}$ per intero: si elevano al quadrato i resti, riducendo ogni volta modulo 55.

$1 3^{2} = 169 = 3 \cdot 55 + 4 \Rightarrow 4$
$1 3^{4} \equiv 4^{2} = 16$
$1 3^{8} \equiv 1 6^{2} = 256 = 4 \cdot 55 + 36 \Rightarrow 36$
$1 3^{16} \equiv 3 6^{2} = 1296 = 23 \cdot 55 + 31 \Rightarrow 31$

Poiché $27 = 16 + 8 + 2 + 1$ :

1 3^{27} \equiv 31 \cdot 36 \cdot 4 \cdot 13 (mod 55)

Moltiplico a coppie, riducendo: $31 \cdot 36 = 1116 = 20 \cdot 55 + 16$ , quindi 16; poi $16 \cdot 4 = 64 \equiv 9$ ; infine $9 \cdot 13 = 117 = 2 \cdot 55 + 7$ , quindi 7. Il messaggio originale è tornato. Il conto torna con la regola: $e \cdot d = 81 \equiv 1 (mod 40)$ garantisce che cifrare e decifrare si annullino.

Con $n = 55$ si cifrano solo numeri fino a 54: per questo nella realtà $n$ ha migliaia di bit.

Firma digitale e hash

Si può usare la coppia di chiavi anche al contrario. Se io cifro con la mia chiave privata, chiunque con la mia chiave pubblica può decifrare, e quindi sa che solo io potevo aver prodotto quel dato: è l’idea della firma digitale. Col nostro esempio: per firmare $m = 9$ calcolo $9^{27} mod 55 = 4$ (la firma); chi la riceve calcola $4^{3} = 64 \equiv 9 (mod 55)$ e trova il messaggio atteso. Autenticità e integrità si controllano senza che la chiave privata sia mai stata rivelata.

Nella realtà non si firma l’intero documento ma il suo hash: una funzione che trasforma qualsiasi file in una stringa di lunghezza fissa. Un hash buono è a senso unico (da quell’impronta non si risale al file), è molto sensibile (cambiare una lettera cambia tutta l’impronta) ed è quasi impossibile trovare due file con lo stesso hash. Si firma l’impronta perché è corta, e il destinatario ricalcola l’hash del documento ricevuto e lo confronta con quello ottenuto dalla firma.

Dove si vede tutto questo: HTTPS e TLS

Quando il browser apre un sito in HTTPS, il protocollo TLS fa in sequenza queste cose, ed è uno schema che conviene saper raccontare:

il server presenta il suo certificato, che contiene la sua chiave pubblica ed è firmato da un’autorità di certificazione di cui il browser si fida;
il browser verifica la firma, cioè controlla che il certificato appartenga davvero a quel sito (autenticazione);
le due parti si accordano, con meccanismi di crittografia asimmetrica, su una chiave di sessione;
da lì in poi tutto il traffico viene cifrato con un algoritmo simmetrico usando quella chiave, perché è molto più veloce.

Lo stesso principio è dietro le VPN di cui si parla nel post sulle reti di quinta.

Errori tipici

Dire che RSA cifra tutto il traffico HTTPS. Non è vero: serve solo per l’accordo sulla chiave; il traffico è cifrato in modo simmetrico.
Confondere chi usa quale chiave. Per cifrare un messaggio riservato si usa la chiave pubblica del destinatario; per firmare si usa la propria chiave privata. Mai il contrario.
Scegliere $e$ non coprimo con $φ (n)$ . Se $MCD (e, φ (n)) \neq = 1$ l’inverso $d$ non esiste.
Calcolare $m^{e}$ per intero invece di ridurre a ogni passo: a mano diventa ingestibile.
Dimenticare il modulo in Cesare: il codice va oltre la Z e produce caratteri strani.
Dire che l’hash si “decifra”. L’hash non si inverte; si ricalcola e si confronta.
Chiamare “crittografia” anche la codifica (Base64, ASCII): non c’è nessuna chiave, quindi non protegge nulla.

Tre esercizi svolti

Esercizio 1. Decifra EHOOR, sapendo che è un Cesare con chiave sconosciuta e che il messaggio è una parola italiana di cinque lettere.

Provo $k = 3$ : sottraggo 3 a ogni lettera. E diventa B, H diventa E, O diventa L, O diventa L, R diventa O: BELLO. Ha senso, quindi la chiave è 3. (In un esercizio vero si provano le chiavi in ordine e ci si ferma alla prima che dà una parola sensata.)

Esercizio 2. RSA con $p = 3$ , $q = 11$ . Determina le chiavi, cifra $m = 4$ e decifra il risultato.

$n = 33$ , $φ (n) = 2 \cdot 10 = 20$ . Scelgo $e = 3$ (coprimo con 20). Cerco $d$ con $3 d \equiv 1 (mod 20)$ : $3 \cdot 7 = 21 = 20 + 1$ , quindi $d = 7$ .

Cifro: $4^{3} = 64 = 33 + 31$ , quindi $c = 31$ .

Decifro: $3 1^{7} mod 33$ . Nota che $31 \equiv - 2 (mod 33)$ , quindi $3 1^{7} \equiv (- 2)^{7} = - 128$ . Per riportare $- 128$ nell’intervallo da 0 a 32 aggiungo $4 \cdot 33 = 132$ : $- 128 + 132 = 4$ . Il risultato è 4, il messaggio originale.

Esercizio 3. Un Vigenère con chiave di 4 lettere viene usato su un testo di 100 lettere. Quante chiavi diverse esistono e perché non conviene provarle tutte a mano? E quante lettere del testo vengono cifrate con la stessa lettera della chiave?

Ogni posizione della chiave ha 26 scelte, quindi le chiavi sono $2 6^{4} = 456976$ : troppe a mano, ma pochissime per un calcolatore (per questo la forza bruta non basta come difesa, e conta la lunghezza della chiave). Ogni lettera della chiave viene usata a turno: $100/4 = 25$ volte ciascuna, quindi 25 lettere del testo per ogni lettera della chiave, ed è su queste 25 lettere (un Cesare) che un attaccante lavorerebbe con le frequenze.

Prima della verifica

Per la verifica: riscrivi da solo la funzione cesare senza guardare, poi rifai l’RSA con $p = 5$ , $q = 11$ e un altro messaggio. Se il codice Python ti dà ancora problemi di base parti da programmazione Python da zero; per ragionare su quanto costa provare tutte le chiavi c’è il post sulla complessità degli algoritmi. Il quadro della materia è nella pagina informatica. Se vuoi che guardi come imposti il conto modulare o il codice, scrivimi su contatti per una diagnosi gratuita.

Crittografia: Cesare, Vigenère e RSA spiegati