Il contenuto di questa pagina non è stato perfezionato: da usare con cura!

Introduzione alla crittografia

1. Sicurezza
   1. Confidenzialità
   2. Autenticazione
   3. Integrità dei dati
   4. Non ripudio
2. Terminologia fondamentale
3. Proprietà di un cifrario
4. Crittografia simmetrica
   1. Pro e contra
5. Cifrari (simmetrici) a scorrimento
   1. Il cifrario di Cesare
      1. Il cifrario di Cesare è sicuro?
      2. Se anziché K = 3, si considera una generica traslazione K delle lettere del testo in chiaro, il cifrario diventa sicuro?
   2. I «pizzini» di Provenzano
6. Attaccare un cifrario [1]: Brute forcing
7. Regole per un buon cifrario [1]
8. Il principio di Kerckhoffs
9. Cifrari (simmetrici) a sostituzione monoalfabetici
   1. Un cifrario a sostituzione monoalfabetico è sicuro?
10. Attaccare un cifrario [2]: KPA
11. Attaccare un cifrario [3]: COA
    1. Esempio di COA contro un cifrario a sostituzione monoalfabetico
12. Cifrari (simmetrici) a sostituzione polialfabetici
    1. Quante sono le possibili chiavi di un cifrario a sostituzione polialfabetico?
    2. Il cifrario di Vigenère
13. Cifrari a trasposizione (o a permutazione)
    1. Cifrario a trasposizione: pro e contra
14. Regole per un buon cifrario [2]
15. Perfect secrecy
16. Il cifrario simmetrico moderno: AES
    1. AES
    2. AES: come funziona?
17. ChaCha20
    1. Origini e contesto di ChaCha20
    2. Struttura interna del cifrario
    3. Sicurezza e vantaggi
18. Crittografia asimmetrica
    1. Crittografia asimmetrica: un po’ di storia
    2. Cosa accadde nel 1976?
    3. Crittografia asimmetrica: chiavi
    4. Cifratura asimmetrica e confidenzialità
    5. Cifratura asimmetrica e autenticazione
19. Come si implementa tutto questo?
20. RSA
    1. RSA: come funziona
    2. RSA: come usarlo
    3. RSA con OpenSSL
21. Scambio delle chiavi Diffie-Hellman
    1. DF: come funziona
22. Fonti

Sicurezza

Le proprietà di sicurezza fondamentali ottenibili attraverso un sistema crittografico sono:

• Confidenzialità
• Autenticazione
• Integrità dei dati
• Non ripudio

La confidenzialità è la proprietà più nota, nonché la base per ottenere le altre.

Confidenzialità

La confidenzialità, o segretezza, o riservatezza, è la proprietà di un sistema crittografico che rende un messaggio illeggibile per tutti, tranne che per i destinatari del messaggio stesso.

Autenticazione

L’autenticazione, o autenticità, è la proprietà che definisce l’identità della controparte. Risponde alle domande:

• Chi è la controparte?
• La controparte è chi dice di essere?

Il termine autorizzazione si riferisce invece alle azioni permesse a un utente già precedentemente autenticato.

Integrità dei dati

L’integrità dei dati garantisce che i dati non siano stati manomessi.

Possibili manipolazioni dei dati includono:

• Inserzione: informazioni estranee sono inserite nella comunicazione;
• Sostituzione: l’informazione originale è sostituita, interamente o parzialmente, con informazione estranea;
• Rimozione: una parte dell’informazione originale è rimossa.

Non ripudio

Il non ripudio, o non repudiation, è la proprietà che impedisce a un’entità di negare azioni compiute nel passato.

Terminologia fondamentale

Per capire i fondamenti della crittografia, bisogna fissare dei concetti chiave.

• Alfabeto: un alfabeto A è un insieme finito di simboli. I computer, ad esempio, usano l’alfabeto binario A = {0, 1}.

• Spazio dei messaggi: è un insieme M di stringhe su un alfabeto. Ogni elemento di M è chiamato testo in chiaro, o plaintext.

• Spazio dei testi cifrati: è un insieme C di stringhe su un alfabeto, il quale può essere diverso da quello dello spazio dei messaggi. Ogni elemento di C è chiamato testo cifrato, o ciphertext.

• spazio delle chiavi: è un insieme K di stringhe, dette chiavi.

• funzione di cifratura: data una chiave e ∈ K, si chiama funzione di cifratura E_e: M → C una funzione che associa ogni testo in chiaro di M a un testo cifrato di C, attraverso la chiave e.

• funzione di decifratura: data una chiave d ∈ K, si chiama funzione di decifratura D_d: C → M una funzione che associa ogni testo cifrato di C a un testo in chiaro di M, attraverso la chiave d.

• cifrario, o crittosistema: un cifrario è un oggetto definito da una sestupla: <A, M, C, K, {E_e: e ∈ K}, {D_d: d ∈ K}>

Proprietà di un cifrario

Un cifrario ideale gode delle seguenti fondamentali proprietà:

• Correttezza: è possibile ottenere un messaggio in chiaro da un messaggio criptato solo attraverso la corretta chiave di decifratura.

• Efficienza e forza: le funzioni di cifratura e decifratura devono essere veloci da calcolare, dati i valori corretti delle chiavi, e impossibili da calcolare senza tali chiavi. In altri termini, le funzioni E e D, pur essendo di fatto biunivoche, devono comportarsi come fossero one-way functions.

Crittografia simmetrica

Si parla di cifrario a crittografia simmetrica o a crittografia a chiave segreta quando le funzioni di cifratura e di decifratura del cifrario usano la stessa chiave.

Un cifrario a crittografia simmetrica può garantire confidenzialità, integrità, autenticazione alla comunicazione. Non può garantire il non ripudio.

I cifrari a crittografia simmetrica sono suddivisi in due gruppi principali:

• Cifrari a blocco: operano su testi (in chiaro o cifrati) di lunghezza fissata. Esempi di cifrari a blocco: AES (Advanced Encryption Standard), 3DES2, BlowFish

• Cifrari a scorrimento: operano su testi (in chiaro o cifrati) di lunghezza arbitraria. Esempi di cifrari a scorrimento: RC4, Trivium, A5/3

Pro e contra

I vantaggi della crittografia simmetrica:

• Superiore efficienza computazionale rispetto a un cifrario a crittografia asimmetrica

Gli svantaggi della crittografia simmetrica:

• La chiave segreta deve essere scambiata su un canale di comunicazione sicuro e separato, prima dell’inizio dello scambio di informazioni

Cifrari (simmetrici) a scorrimento

In un cifrario a scorrimento:

• dato un alfabeto A, ogni elemento è identificato da un numero. La chiave del cifrario è un numero compreso tra 0 e len(A) – 1.
• la funzione di cifratura sostituisce ogni lettera del testo in chiaro con una lettera posta k posizioni più in là: c = p + k mod(len(A))
• la funzione di decifratura sostituisce ogni lettera del testo cifrato con una lettera posta k posizioni indietro: c = p - k mod(len(A))

Il cifrario di Cesare

Notoriamente Gaio Giulio Cesare, inviando comunicazioni qua e là per il futuro impero, cifrava i suoi messaggi. In particolare, sostituiva ogni lettera con la lettera posizionata 3 posizioni oltre.

Ad esempio, C diventa F; Z diventa C; M diventa P.

Per decifrare il messaggio, è sufficiente sostituire ogni lettera con quella posizionata 3 posizioni addietro. La chiave k = 3 è utilizzata sia per la cifratura sia per la decifratura, perciò il cifrario di Cesare è un esempio di cifrario a crittografia simmetrica . Inoltre, dato il suo funzionamento, è un esempio di cifrario a scorrimento.

Esercizio: utilizzando il cifrario di Cesare, come cifreresti il tuo nome e il tuo cognome?

Il cifrario di Cesare è sicuro?

No. Nota la chiave K = 3, decifrare i messaggi di Cesare è un gioco da ragazzi.

Se anziché K = 3, si considera una generica traslazione K delle lettere del testo in chiaro, il cifrario diventa sicuro?

No. Infatti, dato un alfabeto di N lettere (nel caso del nostro alfabeto, N = 26), esistono solo N possibili valori per K. A meno che l’alfabeto sia enorme, è sufficiente tentare N chiavi diverse per essere certi di scovare il testo in chiaro.

I «pizzini» di Provenzano

Un rudimentale sistema di cifratura basato sul cifrario di Cesare è stato usato anche da Bernardo Provenzano per proteggere informazioni rilevanti scritte nei suoi famosi pizzini, i piccoli foglietti di carta con i quali il boss della mafia, durante la sua latitanza, riceveva informazioni e impartiva ordini.

Il sistema scelto da Provenzano era abbastanza semplice: si trattava di sostituire ad ogni lettera il numero corrispondente alla posizione nell’alfabeto sommato a 3 e di comporre così un singolo, lungo numero.

Ad esempio, i numeri “512151522 191212154” nascondono il nome di “Binnu Riina”: infatti, 5 = 2 (posizione della B) più 3; 12 = 9 (posizione della I) più 3; ecc..

Esercizio: utilizzando il metodo di Provenzano, come cifreresti il tuo nome e il tuo cognome?

Attaccare un cifrario [1]: Brute forcing

Provare tutte le possibili chiavi di un cifrario è un’operazione detta brute-forcing .

Se è possibile trovare la chiave di un messaggio cifrato attraverso un attacco brute forcing (come nel caso dei cifrari a scorrimento), allora il cifrario è insicuro.

Regole per un buon cifrario [1]

Fare un attacco brute forcing deve essere reso difficile. Ovvero: bisogna che il numero di possibili chiavi sia gigantesco .

Avere un insieme K delle chiavi molto numeroso è quindi il primo passo per la realizzazione di un buon crittosistema. Come vedremo, si tratta di una condizione necessaria, ma per nulla sufficiente.

Il principio di Kerckhoffs

L’insieme dei testi in chiaro, l’insieme dei testi cifrati e i dettagli delle funzioni di cifratura e decifratura sono noti a priori.

Questo significa che non bisogna basare la sicurezza di un crittosistema sulla segretezza del suo funzionamento. Assumendo che il funzionamento del cifrario sia noto a tutti, esso deve comunque essere sicuro.

Il cifrario di Cesare, per esempio, non rispetta in alcun modo il principio di Kerckhoffs: Cesare basava la sicurezza (…) del suo cifrario sull’ignoranza del suo funzionamento da parte di persone che non fossero i suoi comandanti.

L’unico segreto è sempre la chiave di decifratura: tutto il resto deve essere ritenuto noto.

Cifrari (simmetrici) a sostituzione monoalfabetici

Un cifrario a sostituzione monoalfabetico è una generalizzazione di un cifrario a scorrimento.

‘A sostituzione’, perché ogni carattere del testo in chiaro è sostituito con un carattere dell’alfabeto di C.

‘Monoalfabetico’ è fuorviante. Non si riferisce all’utilizzo di un stesso alfabeto per M e C, bensì, più in generale, all’utilizzo di alfabeti composti dallo stesso numero di elementi. È perciò possibile definire la funzione di cifratura come corrispondenza biunivoca tra gli elementi dei due alfabeti.

La chiave del cifrario a sostituzione monoalfabetico definisce una mappatura tra l’alfabeto di M e l’alfabeto di C. Ad esempio:

Esercizio: utilizzando la tabella di sostituzione qui sopra, come cifreresti il tuo nome e il tuo cognome?

Un cifrario a sostituzione monoalfabetico è sicuro?

Anzitutto, bisogna chiedersi: quante sono le possibili chiavi di un cifrario di questo genere?

Sia N la lunghezza dell’alfabeto. Ebbene, alla prima lettera di M possiamo associare N diverse lettere di C; alla seconda lettera di M possiamo associare N - 1 lettere di C… con qualche nozione di matematica, si intuisce che un cifrario di questo tipo ha un numero di diverse chiari possibili pari a:

Ad esempio, se N = 26, ci sono 26! = 2⁸⁸ = 403291461126605635584000000 chiavi possibili.

2⁸⁸ è un numero gigantesco, che rende un cifrario a sostituzione monoalfabetico resistente ad attacchi a forza bruta. Wow! Questo potrebbe far pensare che un cifrario a sostituzione monoalfabetico sia sicuro. Non lo è.

Attaccare un cifrario [2]: KPA

Un attacco a testo in chiaro noto (known plaintext attack, KPA) consiste nel tentativo di scoprire la chiave di decifratura, conoscendo coppie di testi in chiaro/testi cifrati tutte ottenute utilizzando la stessa chiave.

Se si conosce un testo in chiaro e un corrispondente testo cifrato, ottenuto con un cifrario a sostituzione monoalfabetico, risalire alla mappatura tra alfabeto di M e alfabeto di C è banale: osservo una lettera nel testo in chiaro e osservo con quale lettera essa è stata sostituita nel testo cifrato. Ripeto il procedimento per tutte le lettere del testo in chiaro e ho completato la decifratura.

Attaccare un cifrario [3]: COA

Un attacco con solo testo cifrato (ciphertext only attack, COA) consiste nel tentativo di scoprire una chiave, conoscendo un certo numero di messaggi cifrati tutti ottenuti utilizzando la stessa chiave .

Come fare un attacco COA contro un cifrario a sostituzione monoalfabetico?

Sostituendo una lettera con un’altra, la frequenza di quella lettera nel testo cifrato rimane la stessa della corrispondente lettera nel testo in chiaro. Perciò, calcolando le frequenze di ogni carattere nel testo cifrato e confrontandole con le corrispondenti frequenze dei caratteri nell’alfabeto di M, si possono ottenere tantissime informazioni. A tal punto da rompere il cifrario.

Esempio di COA contro un cifrario a sostituzione monoalfabetico

Cifrari (simmetrici) a sostituzione polialfabetici

Un cifrario a sostituzione polialfabetico è una generalizzazione di un cifrario a sostituzione monoalfabetico.

• ‘a sostituzione’, perché ogni carattere del testo in chiaro è sostituito con un carattere dell’alfabeto di C.
• ‘polialfabetico’ poiché ciascun carattere del testo in chiaro è sostituito con un altro carattere di un altro alfabeto, come nei cifrari monoalfabetici. MA qui, in più, è possibile utilizzare molteplici alfabeti per sostituire le lettere, non uno soltanto.

La chiave di un cifrario a sostituzione polialfabetico definisce:

• Gli alfabeti da usare
• Una politica per la sotituzione di ciascuna lettera del testo in chiaro

Ad esempio, la chiave di un cifrario a sostituzione polialfabetico può essere:

Alfabeti:

• Alfabeto 1: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
• Alfabeto 2: N M L K J I H G F E D C B A Z Y X W V U T S R Q P O

Politica: utilizza in maniera alternata Alfabeto 1 e Alfabeto 2

Quante sono le possibili chiavi di un cifrario a sostituzione polialfabetico?

Sia L il numero di alfabeti utilizzati. Sia N la lunghezza di tali alfabeti. Allora, il numero di possibili chiavi distinte è pari a:

Si tratta di un numero troppo grande per avere successo con un attacco brute force . Tuttavia, come accenneremo, anche questo tipo di cifrario è vittima di attacchi KPA e COA.

Il cifrario di Vigenère

Il cifrario di Vigenère è un esempio di cifrario a sostituzione polialfabetico. Può essere considerato una generalizzazione del cifrario di Cesare.

Invece di spostare ciascuna lettera del testo in chiaro di un numero fisso di posti, le lettere del testo in chiaro sono spostate di un numero variabile di posti. Cioè?

Esempio: scegliamo come chiave la parola ABACO. Nell’alfabeto da noi utilizzato:

• La lettera A è in posizione 0
• La lettera B è in posizione 1
• La lettera C è in posizione 2
• La lettera O è in posizione 14

Sia “MAMMA” il testo in chiaro. Sia “ABACO” la chiave. Utilizzando il cifrario di Vigenère, dovremo:

• Sostituire la prima M di MAMMA con la lettera 0 posizioni più avanti —> M
• Sostituire la prima A di MAMMA con la lettera 1 posizioni più avanti —> B
• Sostituire la seconda M di MAMMA con la lettera 0 posizioni più avanti —> M
• Sostituire la terza M di MAMMA con la lettera 2 posizioni più avanti —> O
• Sostituire la seconda A di MAMMA con la lettera 14 posizioni più avanti —> O

Il testo cifrato ottenuto sarà: MBMOO

Ok, ma come fare quando il testo in chiaro è più lungo della chiave?

Si ripete la chiave tutte le volte che è necessario 🙂

Testo in chiaro: IRONMANMUORE

Chiave: ABACO

IRONMANMUORE <— testo in chiaro
ABACOABACOAB <— chiave
ISOPAAOMWCRF <— testo cifrato

Cifrari a trasposizione (o a permutazione)

Un cifrario a trasposizione funziona in maniera totalmene diversa rispetto a un cifrario a sostituzione.

Tutti i cifrari visti finora – cifrari a scorrimento, cifrari monoalfabetici, cifrari polialfabetici - sono cifrari a sostituzione.

I cifrari a trasposizione sono basati sulla permutazione delle lettere del testo in chiaro.

Per costruire la chiave di un cifrario a trasposizione:

1. Si sceglie la lunghezza L della chiave
2. Si costruisce una tabella, di lunghezza L, che fissa le posizioni da permutare.

Ad esempio, scegliendo L = 5, la seguente è una possibile tavola di permutazione:

Come si cifra un messaggio, usando un cifrario a permutazione?

Dopo aver scelto la chiave, si divide il messaggio in chiaro in frammenti lunghi quanto la chiave. Poi, all’interno di ciascun frammento, si scambiano le posizioni dei caratteri basandosi sulla tavola di permutazione (ovvero, basandosi sulla chiave).

Ad esempio, sia “funcrypto” il messaggio da cifrare. Sia la seguente la chiave di cifratura:

1. Dividiamo il testo in chiaro in frammenti lunghi quanto la chiave (aggiungiamo caratteri P per ottenere frammenti lunghi quanto la chiave):

funcr yptoP

1. Applichiamo la tavola di permutazione, ovvero la chiave, a ciascun frammento:

nfcur tyopP

1. Il testo cifrato è ottenuto allineando i frammenti ottenuti:

nfcurtyopP

Nota bene: un cifrario a trasposizione non è equivalente a un cifrario a sostituzione. Infatti, nei cifrari a trasposizione, ciascuna lettera del testo in chiaro può corrispondere a differenti lettere del testo cifrato, a seconda della posizione.

Cifrario a trasposizione: pro e contra

Pro:

• Lo spazio delle chiavi può essere molto grande: $L!$ —> resistenza ad attacchi brute force

• Le frequenze delle sequenze di caratteri cambiano passando dal testo in chiaro al testo cifrato —> resistenza ad attacchi ciphertext only come quelli di cui sono vittima i cifrari polialfabetici

Contra:

• La frequenza delle singole lettere non cambia.

• Un attacco known plaintext può essere efficace, quando L è ragionevolmente piccolo

Regole per un buon cifrario [2]

Un buon cifrario deve resistere ad attacchi KPA e COA, ovvero:

• Deve essere pressocché impossibile risalire alla chiave di cifratura, note delle coppie di testo in chiaro/testo cifrato (resistenza a KPA);
• Deve essere pressocché impossibile ottenere delle informazioni utili studiando le frequenze dei caratteri nel testo cifrato (resistenza a COA).

Perfect secrecy

È possibile creare un cifrario che non fornisca alcuna informazione utile al decifratore? Un cifrario che sia impossibile da rompere, a prescindere dallo sforzo computazionale compiuto?

Sì. Tuttavia, un simile cifrario avrebbe almeno tre difetti:

• ogni chiave dovrebbe essere usata una volta sola;
• ogni chiave dovrebbe avere la stessa lunghezza del testo in chiaro considerato;
• ogni chiave dovrebbe essere generata in maniera completamente casuale.

Non potendo usare il cifrario perfetto, ci basta un cifrario computationally secure , ovvero in grado di resistere ad attacchi di ogni tipo portati avanti con la potenza di calcolo oggi disponibile. Si ipotizza, realisticamente, che nessuno disponga di una potenza di calcolo illimitata.

Saltando a pié pari una definizione rigorosa di computationally secure e scansando anni di sviluppo di cifrari a chiave simmetrica, arriviamo a…

Il cifrario simmetrico moderno: AES

AES (Advanced Encryption Standard) è l’algoritmo di crittografia simmetrica oggi più diffuso.

Il suo funzionamento è pubblico. È stato il vincitore di un contest internazionale del NIST (Nation Insitute of Standards and Technologies) nel 2001.

Esso è anche noto come algoritmo Rijndael (è fiammingo, si pronuncia tipo: “rèin-daal”), dai nomi dei crittografi belgi che lo hanno ideato: Vincent Rijmen e Joan Daemen.

AES

Anzitutto, AES è un cifrario a blocchi , ovvero lavora su blocchi di informazione di lunghezza predefinita (128 bit).

Come già detto, è un cifrario simmetrico, perciò la chiave di decifratura e quella di decifratura coincidono.

La chiave può essere lunga 128, 192, oppure 256 bit. A seconda della lunghezza della chiave, si parla di AES-128, AES-192 o AES-256. Sottolineo che, a prescindere dalla lunghezza della chiave, la dimensione del blocco è sempre pari a 128 bit.

Esistono 2¹²⁸ chiavi da 128 bit. Se queste sono generate casualmente, non esiste attacco brute force in grado di scovare la chiave. Tanto meno per AES-192 e AES-256.

AES è stato progettato per resistere agli attacchi visti finora: brute-forcing , known plaintext, ciphertext only. AES resiste anche ad altri attacchi da noi non studiati: attacchi di crittoanalisi lineare, differenziale, …

Se e quando esisteranno computer quantistici, il numero di tentativi da effettuare per completare un attacco brute force sarà ridotto da 2ⁿ a 2^n/2, grazie all’algoritmo di Grover¹. Oggi (2025) si riescono a effettuare circa 2⁸⁰ tentativi in circa un’ora². Si ritiene che un algoritmo, per essere sempre considerato sicuro, debba richiedere almeno 2¹²⁸ tentativi per scovare la chiave.

Di seguito una tabella che riassume la situazione di sicurezza delle tre versioni di AES. Il termine quantum resistant indica che un algoritmo continuerà a essere considerato sicuro anche dopo l’eventuale creazione di computer quantistici.

AES: come funziona?

AES si basa su concetti di algebra lineare e aritmetica modulare. Può sembrare spaventoso, ma è sufficiente visitare la pagina di Wikipedia per avere una idea del suo funzionamento.

Oppure, potete recarvi a pagina 131 di questo libro qui.

Noi insieme, però, non studieremo il funzionamento esatto di AES: per quanto molto interessante, sia da un punto di vista informatico, sia da un punto di vista matematico, richiederebbe molte, troppe lezioni. Chi vorrà, lo studierà per sé o in università!

ChaCha20

Per migliorare la comprensione della lezione, consiglio vivamente di procurarsi immagini e/o video esplicativi.

Origini e contesto di ChaCha20

• Chi ha progettato ChaCha20? In che anno?
• Da quale algoritmo deriva?
• Quali miglioramenti introduce ChaCha20 rispetto al suo predecessore?
• Perché è diventato così popolare?
• Cos’è un cifrario a flusso (stream cipher) e in cosa differisce da un cifrario a blocchi?
• Quali problemi avevano i vecchi stream cipher, come RC4?
• In che modo la semplicità del design può essere un punto di forza?

Struttura interna del cifrario

• Quali sono gli elementi di input di ChaCha20?
• Cosa si intende per stato interno di ChaCha20?
• Quante parole contiene la matrice di stato e di quanti bit ciascuna?
• Cos’è una quarter-round function?
• Quali operazioni elementari usa ChaCha20?
• Cosa rappresenta l’output finale di ChaCha20?
• In che modo il keystream viene combinato col plaintext per cifrare?

Sicurezza e vantaggi

• Quali debolezze aveva RC4 che ChaCha20 evita?
• Perché l’uso di un nonce unico per ogni messaggio è fondamentale?
• Cosa significa avalanche effect e come si manifesta in ChaCha20?
• Quali sono i vantaggi in termini di prestazioni e sicurezza rispetto ad AES?
• Quali errori pratici comprometterebbero la sicurezza di ChaCha20?

Crittografia asimmetrica

Si parla di cifrario a crittografia asimmetrica o crittografia a chiave pubblica quando la chiave di cifratura è pubblica, mentre la chiave di decifratura è segreta.

Crittografia asimmetrica: un po’ di storia

Fino al 1976, la crittografia asimmetrica è stata un’idea balenata qua e là tra varie menti umane, oppure un segreto di stato americano.

Nel 1874, ad esempio, il signor William Stanley Jevons scriveva in un suo libro:

«Può il lettore dire quali sono i due numeri moltiplicati tra loro che produrranno il numero 8616460799? Penso che sia improbabile che qualcuno ci riesca, a parte me stesso»

Jevons aveva appena colto uno dei problemi sui quali oggi si basa la crittografia asimmetrica: la fattorizzazione di un numero.

P.S.: oggi potete scrivere uno script in qualsiasi linguaggio e il vostro potentissimo computer troverà i fattori primi di 8616460799 (a patto che scriviate una soluzione sufficientemente efficiente. Provateci.)

Cosa accadde nel 1976?

Nel 1976, i signori Whitfield Diffie e Martin Hellman pubblicarono lo schema di un protocollo a cifratura asimmetrica, oggi noto come «scambio di chiavi di Diffie-Hellman». Fu l’inizio della crittografia asimmetrica.

Nel 1977, i signori Ronald Rivest, Adi Shamir e Leonard Adleman inventarono l’algoritmo di crittografia RSA, che più tardi cercherò di mostrarvi.

Crittografia asimmetrica: chiavi

Quando si utilizza un protocollo a cifratura asimmetrica, ogni attore dispone di due chiavi:

• una chiave pubblica, la quale può essere comunicata a chiunque;

• una chiave segreta, la quale deve essere tenuta segreta.

Dalla chiave segreta è possibile derivare la chiave pubblica. Dalla chiave pubblica deve essere impossibile risalire alla chiave segreta. La generazione di queste chiavi si basa su dei problemi matematici di cui parlerò più tardi.

Cifratura asimmetrica e confidenzialità

In un protocollo a crittografia asimmetrica, chiunque (Bob) può criptare un messaggio utilizzando la chiave pubblica di Alice. Solo Alice può decrittare il messaggio utilizzando la propria chiave segreta.

Cifratura asimmetrica e autenticazione

In un protocollo a crittografia asimmetrica, solo Alice può criptare un messaggio con la propria chiave privata, e chiunque (Bob) può decrittare il messaggio usando la chiave pubblica di Alice. Bob è certo che il mittente del messaggio sia Alice, perché solo lei conosce la chiave segreta associata alla sua chiave pubblica. Questa è la base della firma digitale.

Come si implementa tutto questo?

Anche la crittografia asimmetrica ha una solida base matematica.

L’idea è di sfruttare un problema complesso, ovvero un’operazione matematica semplice da eseguire, ma difficilissima da invertire.

I «problemi complessi» oggi sfruttati sono:

• La fattorizzazione di un numero (provo a spiegarvelo)
• Il calcolo del logaritmo discreto (non provo a spiegarvelo)
• Curve ellittiche su campi finiti (non provo a spiegarvelo)
• altri problemi matematici che non sono mai riuscito a comprendere

RSA

RSA è un algoritmo di crittografia a chiave pubblica, basato sulla difficoltà del problema di fattorizzazione di un numero.

Se volete unirvi alla sfida, rimangono 31 numeri RSA da fattorizzare .

Adesso proverò a spiegarvi il funzionamento di RSA. Come in ogni algoritmo di crittografia, c’è tanta matematica.

RSA: come funziona

1. Si scelgono a caso due numeri primi, p e q, abbastanza grandi per la sicurezza dell’algoritmo. I numeri primi si scelgono usando dei test di primalità.
2. Si calcola il loro prodotto: n = pq , chiamato modulo. Si ritiene che la fattorizzazione di n sia segreta, ovvero che solo chi ha scelto i due numeri primi p e q sia in grado di fattorizzare n.
3. Si calcola il prodotto $\varphi (n)=(p-1)(q-1)$, dove $\varphi (n)$ è la funzione toziente.
4. Si sceglie un numero e, chiamato esponente pubblico, coprimo con $\varphi (n)$ e minore di $\varphi (n)$.
5. Si calcola il numero d, chiamato esponente privato, tale che il suo prodotto con e sia congruo a 1 modulo $\varphi (n)$, cioè:

Fatto.

• la chiave pubblica è (n, e)
• la chiave privata è (n, d)

RSA: come usarlo

RSA con OpenSSL

Utilizzando il software OpenSSL, è possibile giocare con RSA.

Generare, nella cartella corrente, una chiave privata RSA nel file private.key:

openssl genrsa -out private.key

leggere la chiave privata custodita nel file private.key, in formato human-readable:

openssl rsa -text -in private.key

Utilizzando il software OpenSSL, è possibile giocare con RSA.

ottenere la chiave pubblica associata alla chiave privata salvata nel file private.key e scriverla nel file public.key:

openssl rsa -in private.key -pubout -out public.key

leggere la chiave pubblica custodita nel file public.key, in formato human-readable:

openssl rsa -text -pubin -in public.key

Scambio delle chiavi Diffie-Hellman

Lo scambio di chiavi Diffie-Hellman (DF key exchange) è un protocollo crittografico che consente a due entità di stabilire una chiave segreta condivisa utilizzando un canale di comunicazione insicuro, senza la necessità che le due parti si siano incontrate in precedenza.

Una volta scambiata una chiave segreta, questa può essere utilizzata per instaurare una comunicazione sicura attraverso un protocollo a chiave simmetrica.

Lo sicurezza dello scambio di chiavi Diffie-Hellman si basa sul problema del logaritmo discreto. In sintesi e in maniera imprecisa, l’idea è che, se conosco il risultato del logaritmo m = g * a (mod p), è pressocché impossibile risalire all’esponente a con l’operazione a = log(base g) m (mod p).

DF: come funziona

Fonti

• Nigel Smart, Introduction to cryptography
• Gerardo Pelosi, slide introduttive al corso magistrale «Cryptography and architectures for computer security»
• Stefano Bregni, lezioni del corso triennale «Sicurezza delle reti»
• Wikipedia
• OpenSSL quick reference guide
• Extra: DH with OpenSSL
• Gli ottimi corsi di crittografia del professor Alfred Menezes, disponibili suo suo sito