Ancient Cryptography PDF - Khan Academy

Ancient cryptography What is cryptography? Immagina che due persone, che condividono un importante segreto, debbano separarsi e continuare a comunicare informazioni private a distanza. Tuttavia, c'è un'intercettatrice chiamata Eve che vuole ottenere queste in...

Ancient cryptography What is cryptography? Immagina che due persone, che condividono un importante segreto, debbano separarsi e continuare a comunicare informazioni private a distanza. Tuttavia, c'è un'intercettatrice chiamata Eve che vuole ottenere queste informazioni e ha la capacità di intercettare i loro messaggi. Per proteggere il loro segreto, Alice decide di usare una tecnica per inviare messaggi segreti. Un'analogia utile per capire questo processo è la seguente: 1. Alice chiude il suo messaggio in una scatola, usando un lucchetto di cui solo lei e Bob conoscono la combinazione. Questo è l'equivalente della cifratura o "encryption." 2. Successivamente, Alice invia la scatola chiusa a Bob. 3. Quando Bob riceve la scatola, la apre utilizzando il codice che lui e Alice avevano precedentemente condiviso. Questa è la decifratura o "decryption." La crittografia nasce quando si abbandonano i lucchetti fisici e si utilizzano invece i cifrari, che possiamo considerare come lucchetti virtuali. I cifrari permettono ad Alice e Bob di codificare e decodificare i loro messaggi, rendendoli incomprensibili nel caso in cui Eve li intercettasse. La crittografia ha una storia antica, è stata fondamentale nelle guerre e oggi è al centro della rete di comunicazioni globale. Comprendere questa storia affascinante ci richiede di esplorare due concetti molto antichi: la teoria dei numeri e la teoria della probabilità. The Caesar cipher Il primo cifrario noto, è un cifrario a sostituzione, fu utilizzato da Giulio Cesare intorno al 58 a.C. Oggi è noto come Cifrario di Cesare. Cesare modificava ogni lettera dei suoi comandi militari, facendo apparire i messaggi incomprensibili nel caso in cui fossero intercettati dal nemico. Immagina che Alice e Bob vogliano comunicare usando il Cifrario di Cesare. Prima, dovrebbero accordarsi su uno spostamento da utilizzare, diciamo tre. Per cifrare il suo messaggio, Alice sposta ogni lettera di tre posizioni nell'alfabeto: A diventa D, B diventa E, C diventa F, e così via. Questo messaggio crittografato viene poi inviato a Bob, che sottrae semplicemente lo spostamento di tre per leggere il messaggio originale. Sorprendentemente, questo semplice cifrario è stato usato dai leader militari per centinaia di anni dopo Cesare. Tuttavia, un lucchetto è forte solo quanto il suo punto più debole. Un craccatore di lucchetti cerca difetti meccanici o raccoglie informazioni per restringere le combinazioni possibili. Lo stesso vale per i craccatori di codici. Il punto debole del Cifrario di Cesare fu svelato 800 anni dopo da un matematico arabo chiamato Al-Kindi. Egli lo infranse utilizzando un indizio basato su una proprietà importante della lingua in cui è scritto un messaggio: la frequenza delle lettere. Se analizzi un testo e conti la frequenza di ogni lettera, troverai un modello consistente. Ad esempio, in inglese, la lettera "E" è la più comune. Questo può essere considerato un impronta digitale della lingua. I craccatori di codici possono usare questa impronta per analizzare un testo cifrato. Se notano che "H" è la lettera più frequente anziché "E", possono dedurre che lo spostamento è probabilmente tre e possono invertire il cifrario per rivelare il messaggio originale. Questo metodo, chiamato analisi delle frequenze, rappresentò un colpo alla sicurezza del Cifrario di Cesare. Polyalphabetic cipher Un cifrario forte è quello che riesce a nascondere la tua impronta linguistica, cioè a rendere difficile riconoscere la distribuzione delle frequenze delle lettere. Un modo per farlo è appiattire questa distribuzione, rendendo meno evidenti le lettere più comuni. Nel XV secolo, si è sviluppata una soluzione più avanzata rispetto al Cifrario di Cesare: i cifrari polialfabetici. Immagina che Alice e Bob condividano una parola segreta che determina una sequenza di spostamenti. Alice converte questa parola in numeri, corrispondenti alla posizione delle lettere nell'alfabeto. Questa sequenza numerica viene ripetuta lungo tutto il messaggio. Poi, ogni lettera del messaggio viene cifrata spostandola di un numero differente, come indicato dalla sequenza. In questo modo, Alice utilizza più spostamenti, anziché un solo spostamento come nel cifrario di Cesare. Dopo aver cifrato il messaggio, lo invia a Bob, che può decifrarlo sottraendo gli spostamenti, dato che ha anche lui una copia della parola segreta. Se Eve, una intercettatrice, tenta di decifrare il messaggio, troverà una distribuzione più piatta delle frequenze delle lettere, cioè una "impronta" più leggera, rendendo più difficile capire il messaggio cifrato. Tuttavia, i craccatori di codici, come Eve, cercano comunque fughe di informazioni. Ogni volta che c'è una differenza nelle frequenze delle lettere, c'è una perdita d'informazioni. Nel caso del cifrario polialfabetico, questa perdita deriva dalla ripetizione della parola segreta usata per il cifrario. Per infrangere il cifrario, Eve deve prima determinare la lunghezza della parola segreta, non la parola stessa. Analizza le frequenze delle lettere a intervalli diversi e, controllando la distribuzione delle frequenze di ogni quinta lettera (per esempio), può rivelare la lunghezza del codice. A quel punto, può decifrare una serie di Cifrari di Cesare ripetuti, che è un compito più semplice. La forza aggiunta di questo cifrario sta nel tempo necessario per determinare la lunghezza della parola segreta: più lunga è la parola, più forte è il cifrario. The one-time pad Per oltre 400 anni, il problema è rimasto: come può Alice progettare un cifrario che nasconda la sua "impronta", evitando di rivelare informazioni durante la cifratura? La risposta è la casualità. Immagina che Alice lanci un dado a 26 facce per generare una lunga lista di spostamenti casuali e condivida questa lista con Bob, al posto di una parola chiave segreta. Quando cifra il suo messaggio, Alice usa questi spostamenti casuali, assicurandosi che la lista sia lunga quanto il messaggio, evitando così qualsiasi ripetizione. Bob, usando la stessa lista, può poi decifrare il messaggio. Questo crea un grosso problema per Eve, l'intercettatrice. Il messaggio cifrato ha due proprietà potenti: 1. Gli spostamenti non seguono alcuno schema ripetitivo. 2. Il messaggio cifrato presenta una distribuzione uniforme delle frequenze delle lettere, eliminando qualsiasi differenza nelle frequenze che Eve potrebbe usare per dedurre informazioni. Poiché non c'è alcuna perdita di informazioni, diventa impossibile per Eve rompere la cifratura. Questo metodo è il più forte possibile ed è conosciuto come il "one-time pad", emerso verso la fine del XIX secolo. Per visualizzare la forza del one-time pad, consideriamo l'esplosione combinatoria che si verifica. Nel Cifrario di Cesare, ogni lettera viene spostata di un numero compreso tra 1 e 26, quindi esistono 26 possibili cifrature per ogni messaggio. Questo è un numero ridotto di possibilità, facile da risolvere con la forza bruta. Ora, confrontalo con il one-time pad, dove ogni lettera è spostata da un numero diverso, compreso tra 1 e 26. Il numero di possibili cifrature diventa 26 moltiplicato per se stesso tante volte quanto la lunghezza del messaggio. Ad esempio, se Alice cifra il suo nome (5 lettere), il numero di possibili cifrature è 26⁵, quasi 12 milioni. È difficile immaginare questa esplosione combinatoria: se Alice scrivesse il suo nome su una pagina e impilasse tutte le possibili cifrature, questa pila di pagine sarebbe alta oltre un chilometro! Quando Alice utilizza il one-time pad, è come se scegliesse una pagina a caso da questa pila. Dal punto di vista di Eve, ogni messaggio cifrato è ugualmente probabile che corrisponda a qualsiasi parola in questa pila, rendendo la crittografia perfettamente segreta. Frequency stability property short film Lo scenario presentato riguarda la distinzione tra vera casualità e tentativi umani di simulare la casualità. Immagina due stanze: in una, un uomo lancia una moneta per decidere se accendere o spegnere una luce; nell'altra, una donna indovina casualmente senza una moneta. A prima vista, entrambe le sequenze di interruttori della luce possono sembrare ugualmente casuali perché il numero di "1" (acceso) e "0" (spento) apparirà probabilmente bilanciato. Tuttavia, la chiave per distinguerle sta nell'esaminare i modelli nelle sequenze piuttosto che i risultati individuali. In particolare, possiamo concentrarci sulle sequenze di interruttori consecutivi—corsi di due, tre o più. La vera casualità, come quella derivante dal lancio di una moneta, segue la proprietà di stabilità della frequenza, il che significa che ogni possibile sequenza (ad esempio, tre teste o tre croci di fila) è ugualmente probabile che si verifichi. Questa proprietà produce una distribuzione uniforme delle sequenze. Le sequenze generate dagli esseri umani, invece, tendono a mostrare pregiudizi. Le persone spesso evitano ciò che percepiscono come sequenze "sfortunate" o "non casuali"—come lunghe serie dello stesso risultato (ad esempio, cinque teste di fila). Ciò porta a modelli che favoriscono certe sequenze e creano distribuzioni irregolari. Questo bias naturale umano è ciò che rende possibile rilevare la differenza tra una sequenza veramente casuale (lancio di moneta) e una simulata. Tende a pensare che certi risultati (ad esempio, una lunga serie di teste o croci) siano meno probabili, anche se, in realtà, ogni sequenza è ugualmente probabile quando si lancia una moneta equa. The Enigma encryption machine Nel 1857 fu posato un cavo sottomarino lungo 4.300 chilometri che collegava la Gran Bretagna con l'America, segnando l'inizio di una nuova era nelle comunicazioni globali. Questo cavo permetteva di trasmettere informazioni in modo quasi istantaneo, rivoluzionando le comunicazioni commerciali, come la trasmissione dei dati di borsa e i trasferimenti di denaro, che Western Union sfruttò per potenziare le relazioni sociali ed economiche tra le due sponde dell'Atlantico. Durante la Seconda Guerra Mondiale, le potenze dell'Asse, ovvero Germania, Italia e Giappone, si trovarono in una situazione di svantaggio numerico rispetto agli Alleati. Perciò, la loro strategia di vittoria dipendeva dalla capacità di lanciare attacchi a sorpresa su vasta scala. Per garantire la sicurezza delle loro comunicazioni segrete, la Germania fece largo uso della macchina crittografica Enigma, un'invenzione elettromeccanica sviluppata dopo la Prima Guerra Mondiale. Questa macchina utilizzava una serie di rotori, che modificavano la configurazione delle lettere ogni volta che veniva inserita una nuova lettera, garantendo un altissimo livello di complessità nella crittografia. Con tre rotori che potevano generare 17.576 combinazioni di lettere, e la possibilità di cambiare l'ordine dei rotori, le chiavi crittografiche generate erano numerose e variabili. Nonostante l'apparente invulnerabilità dell'Enigma, una serie di errori umani e di progettazione ne compromisero la sicurezza. Gli operatori tedeschi, spesso esausti, tendevano a scegliere le posizioni iniziali dei rotori con poca variabilità, riducendo la casualità necessaria per mantenere la crittografia robusta. Inoltre, un errore di progettazione dell'Enigma impediva che una lettera si crittografasse su se stessa, offrendo agli Alleati un indizio fondamentale per decifrare i messaggi. Grazie a questi punti deboli, i criptoanalisti alleati riuscirono a creare una macchina chiamata Bombe, che poteva testare rapidamente migliaia di configurazioni dell'Enigma sfruttando gli indizi forniti dalle "cribs", ovvero parole comuni che si sapeva fossero presenti nei messaggi, come "meteo". Con la Bombe, gli Alleati riuscirono a decifrare i messaggi tedeschi in tempi molto brevi, permettendo loro di anticipare le mosse nemiche. Questo vantaggio si rivelò cruciale per la strategia militare degli Alleati e, di fatto, cambiò il corso della guerra. Se la casualità nelle impostazioni iniziali dei rotori fosse stata migliore e se la macchina Enigma fosse stata progettata diversamente, la sua sicurezza sarebbe stata molto più solida, rendendo impossibile per gli Alleati decifrare i messaggi in modo così rapido. Tuttavia, le debolezze presenti ridussero lo spazio delle chiavi crittografiche, portando a una svolta fondamentale nel conflitto. Perfect secrecy Il video presenta un gioco ideato per illustrare il concetto di "segretezza perfetta" nella crittografia, sviluppato da Claude Shannon nel 1945. La situazione del gioco è la seguente: Bob entra in una stanza vuota con delle serrature, una scatola e un mazzo di carte. Eve, che osserva da fuori, dà istruzioni a Bob affinché scelga una carta dal mazzo e la nasconda, rispettando delle regole: non può portare niente fuori dalla stanza, e può mettere al massimo una carta nella scatola. Vince se Eve non riesce a indovinare la carta. Inizialmente, Bob considera l'idea di nascondere la carta nella scatola e usare una serratura, ma si rende conto che le carte rimanenti sul tavolo potrebbero rivelare la sua scelta, perché una carta mancherebbe dal mazzo. Le serrature si rivelano essere una distrazione, e la soluzione migliore non è separare la carta dal mazzo. Così, Bob rimette la carta nel mazzo e decide di mescolarlo. Mescolando, rende impossibile per Eve capire quale carta abbia scelto, poiché ogni carta ha la stessa probabilità di essere quella scelta. Questo principio riflette l'idea di "segretezza perfetta": anche se Eve avesse un'infinita potenza di calcolo, non potrebbe fare altro che indovinare, perché non rimane alcuna informazione sulla carta scelta da Bob. Il concetto chiave è stato formalizzato da Claude Shannon, che dimostrò matematicamente come il "one-time pad" (una tecnica di cifratura) garantisce segretezza perfetta. Nel contesto crittografico, Shannon pensava ai messaggi come una serie di possibili combinazioni di lettere. Se Alice invia un messaggio a Bob, questo può essere pensato come la scelta di una pagina da uno spazio di messaggi, che rappresenta tutte le possibili combinazioni di lettere di quella lunghezza. Per cifrare il messaggio, Alice applica una chiave, che è una sequenza di numeri casuali che determina lo spostamento delle lettere del messaggio originale. Il risultato è un testo cifrato, che potrebbe essere una qualunque combinazione di lettere, senza fornire alcun indizio sul messaggio originale. Secondo Shannon, la dimensione dello spazio dei messaggi, delle chiavi e dei testi cifrati deve essere la stessa per garantire che ogni possibile messaggio abbia la stessa probabilità di corrispondere al testo cifrato. Questo rende ogni tentativo di decifrare il messaggio solo sulla base del testo cifrato inutile, poiché ogni messaggio è equiprobabile. Il problema principale del "one-time pad" è la necessità di condividere preventivamente chiavi molto lunghe. Per risolverlo, Shannon propose di rilassare la definizione di segretezza, introducendo il concetto di "pseudo-casualità" per migliorare la gestione delle chiavi crittografiche. Pseudorandom number generators Questo video spiega la differenza tra numeri generati casualmente e numeri pseudocasuali, oltre al concetto di pseudorandomness, che permette di simulare l'apparenza di casualità attraverso metodi algoritmici. Quando osserviamo il mondo fisico, notiamo che le fluttuazioni casuali sono ovunque. Questi fenomeni, noti come rumore, possono essere misurati per generare numeri realmente casuali, come osservare la corrente elettrica di una TV sintonizzata su un canale statico. Questa sequenza casuale può essere visualizzata come una "camminata casuale", in cui ogni mossa è imprevedibile e non segue alcun pattern. Al contrario, le macchine sono deterministiche, il che significa che il loro funzionamento è prevedibile e ripetibile. Nel 1946, John von Neumann, coinvolto nello sviluppo della bomba all'idrogeno, si trovava ad affrontare il problema di calcolare processi complessi, che richiedevano numeri casuali ripetibili ma senza abbastanza memoria per immagazzinarli. Per risolvere il problema, sviluppò il metodo dei "quadrati centrali", un algoritmo per generare numeri pseudocasuali. Il processo prevede di scegliere un numero iniziale casuale, chiamato "seme", e utilizzarlo per eseguire un calcolo: si moltiplica il seme per sé stesso e si prelevano le cifre centrali del risultato per generare il numero successivo, che diventerà il nuovo seme per la generazione successiva. Questo metodo, pur essendo utile, ha dei limiti: la sequenza pseudocasuale generata ripeterà inevitabilmente lo stesso ciclo, definito "periodo", quando il seme iniziale verrà riutilizzato. La lunghezza del periodo è determinata dalla lunghezza del seme: un seme di due cifre potrà produrre al massimo 100 numeri prima di ripetersi, uno di tre cifre potrà generarne 1.000, e così via. Più grande è il seme, più lunga sarà la sequenza prima che si ripeta, ma rimane comunque pseudocasuale, non veramente casuale. La vera differenza tra numeri casuali e pseudocasuali risiede nel fatto che con numeri pseudocasuali ci sono molte sequenze che non possono essere generate. Ad esempio, se Alice genera una sequenza casuale di 20 numeri, ha accesso a un numero astronomico di possibili combinazioni. Se, invece, usa un seme pseudocasuale di quattro cifre, potrà generare solo 10.000 sequenze, una frazione infinitesimale del totale. La pseudorandomness, sebbene non garantisca la stessa sicurezza perfetta dei numeri casuali, è sufficientemente sicura per l'uso pratico. Questo concetto è simile all'uso di un lucchetto: anche se qualcuno potrebbe tentare tutte le combinazioni, il tempo richiesto per farlo renderebbe il sistema abbastanza sicuro da considerarlo affidabile per un certo periodo di tempo. Infine, la pseudorandomness permette a due persone, come Alice e Bob, di condividere solo un piccolo seme casuale e generare indipendentemente la stessa sequenza pseudocasuale, evitando la necessità di scambiare l'intera sequenza in anticipo. Tuttavia, rimane la domanda su come possano condividere questo seme se non riescono mai a incontrarsi di persona. Public key cryptography: What is it? Dopo la Seconda Guerra Mondiale, con gran parte dell'Europa devastata, crebbe la tensione tra l'Unione Sovietica e gli Stati Uniti. Era evidente che la prossima superpotenza mondiale avrebbe dovuto essere in grado di lanciare e difendersi da attacchi nucleari tramite missili balistici intercontinentali. Per il Nord America, il punto più vulnerabile a un attacco era sopra il Polo Nord. Così, nel 1958, Stati Uniti e Canada avviarono uno sforzo congiunto, creando il NORAD, ovvero il Comando di Difesa Aerospaziale del Nord America. Un elemento chiave di difesa era il sistema semi-automatico di rilevamento a terra, composto da oltre 100 radar a lungo raggio distribuiti in tutto il Nord America. Questi radar erano collegati a stazioni di rilevamento computerizzate che trasmettevano i dati tramite linee telefoniche o onde radio. Tutte queste informazioni radar venivano inviate a un centro di allerta primaria situato in una montagna a un miglio di profondità, a Cheyenne Mountain, Colorado. Grazie a questa comunicazione automatica tra macchine, gli operatori potevano prendere decisioni in frazioni di secondo utilizzando i dati elaborati dai computer. L'idea di essere "online" fu presto adottata e perfezionata dalle università, che compresero il potenziale del networking tra computer. Questo concetto di rete non solo metteva in comunicazione i lavoratori distanti geograficamente, ma permetteva loro di accedere costantemente a una base di informazioni condivisa. Ciò rivoluzionò la pianificazione, l'organizzazione e l'esecuzione di molte attività intellettuali. Tra le applicazioni crescenti di queste reti, ci furono i trasferimenti di denaro, che richiedevano crittografia per garantire la sicurezza. Con la crescita di internet, un problema emerse: la crittografia richiedeva che due parti condividessero una chiave segreta, un numero casuale, ma come potevano due persone che non si erano mai incontrate accordarsi su una chiave segreta senza che un terzo (Eve) la intercettasse? Nel 1976, Whitfield Diffie e Martin Hellman trovarono una soluzione ingegnosa. Per spiegare come funziona, possiamo usare l'esempio dei colori. Alice e Bob devono accordarsi su un colore segreto senza che Eve lo scopra. La chiave del trucco sta nel fatto che, sebbene sia facile mescolare due colori per ottenerne un terzo, è difficile invertire il processo e risalire ai colori originali. Questo concetto è alla base della crittografia a senso unico. Il procedimento funziona così: prima Alice e Bob scelgono pubblicamente un colore di partenza, ad esempio il giallo. Poi, ciascuno di loro sceglie un colore privato e lo mescola con il giallo. Alice invia la sua miscela a Bob, e Bob invia la sua ad Alice. Ora, ciascuno aggiunge il proprio colore privato alla miscela ricevuta dall'altro, ottenendo così un colore segreto condiviso. Eve, anche se intercetta le miscele, non può risalire al colore segreto poiché non conosce i colori privati di Alice e Bob. Questo principio di mescolamento dei colori si traduce nei numeri con l'uso di funzioni matematiche che sono facili da eseguire in un senso, ma difficili da invertire. Modern cryptography The fundamental theorem of arithmetic Immagina di vivere in tempi preistorici e di dover tenere traccia del tempo senza l'uso di un orologio. Come facevamo? Tutti gli orologi si basano su qualche schema ripetitivo che suddivide il flusso del tempo in segmenti uguali. Per trovare questi schemi, si osservavano i cieli, con il ciclo più evidente del sole che sorge e tramonta ogni giorno. Tuttavia, per monitorare periodi di tempo più lunghi, ci si rivolgeva alla luna. Il ciclo della luna, che cresce e diminuisce gradualmente, dura circa 29 giorni. Questo numero è alla base del concetto di mese. Ma se proviamo a dividere 29 giorni in parti uguali, ci accorgiamo che è impossibile. Questo perché 29 è un numero primo, ovvero un numero che non può essere suddiviso se non in unità. I numeri che possono essere suddivisi in parti uguali più grandi di uno sono chiamati numeri composti. Ora, se ci chiediamo quanti numeri primi esistono e quanto grandi possono diventare, possiamo fare una distinzione tra numeri primi e composti. Elencandoli, si nota un'alternanza senza un pattern evidente. Per vedere l'insieme dei numeri primi in un modo più chiaro, possiamo usare la spirale di Ulam. Disponendo tutti i numeri in una spirale crescente e colorando i numeri primi, emerge una distribuzione apparentemente caotica. Questa disposizione dei numeri primi non è ancora completamente compresa e rappresenta uno dei grandi misteri della matematica. Avanzando fino al 300 a.C., il filosofo greco Euclide scoprì che ogni numero può essere diviso fino a un gruppo di numeri più piccoli, che sono sempre numeri primi. Questa intuizione porta al Teorema Fondamentale dell'Aritmetica: qualsiasi numero composto può essere scomposto in un insieme unico di numeri primi. Questo processo si chiama fattorizzazione, e ogni numero ha una combinazione unica di fattori primi. Ad esempio, prendiamo il numero 30. Scomponendolo, otteniamo i fattori primi 2, 3 e 5. Moltiplicando questi fattori una sola volta, otteniamo nuovamente 30 (2 × 3 × 5 = 30). Questo è l'unico modo per costruire il numero 30 con i numeri primi, e ogni numero ha una fattorizzazione unica. Un'analogia utile è pensare a ogni numero come a una serratura e alla sua fattorizzazione come a una chiave: ogni serratura ha una chiave unica, e nessuna serratura condivide la stessa chiave.  The discrete logarithm problem Nel video viene spiegato l'utilizzo dell'aritmetica modulare come base per una procedura numerica che è facile in un senso, ma difficile da invertire, e quindi adatta alla crittografia. L'aritmetica modulare, o aritmetica a orologio, è descritta come un processo in cui si prende un numero e lo si "avvolge" attorno a un modulo per trovare il resto. Ad esempio, per calcolare 46 \mod 12, si avvolge una corda lunga 46 attorno a un orologio con 12 unità (il modulo). Il punto in cui finisce la corda è il risultato, cioè 10. Questo è facile da calcolare. Per creare una funzione crittografica, viene utilizzato un modulo primo, come 17, e una radice primitiva di questo modulo, in questo caso il numero 3. Una radice primitiva ha la proprietà che, se elevata a diversi esponenti, i risultati si distribuiscono uniformemente attorno al modulo. Il numero 3 viene quindi chiamato generatore. Se si eleva 3 a un qualsiasi esponente x, il risultato sarà un numero uniforme tra 0 e 17. La parte difficile del processo è l'inversione: dato un risultato come 12, trovare a quale esponente 3 deve essere elevato per ottenere 12. Questo problema è noto come problema del logaritmo discreto. Invertire questa operazione richiederebbe tentativi e errori. Anche se con numeri piccoli è semplice, con un modulo primo di centinaia di cifre il processo diventa impraticabile, anche disponendo di tutta la potenza di calcolo sulla Terra. Potrebbe richiedere migliaia di anni. Quindi, la forza di una funzione a senso unico dipende dal tempo necessario per invertire l'operazione, e questo concetto è alla base della sicurezza crittografica. Diffie-hellman key exchange In questa parte del video viene spiegato come Alice e Bob possano scambiarsi un segreto condiviso utilizzando un trucco basato sull'aritmetica modulare, senza che Eve, l'osservatore indesiderato, possa decifrare la comunicazione. Procedura: 1. Alice e Bob concordano pubblicamente un modulo primo (17) e un generatore (3). 2. Alice sceglie un numero casuale privato, ad esempio 15, e calcola inviando il risultato (6) pubblicamente a Bob. 3. Bob sceglie a sua volta un numero casuale privato, ad esempio 13, e calcola inviando il risultato (12) pubblicamente ad Alice. 4. Passaggio chiave: - Alice prende il risultato pubblico di Bob (12) e lo eleva alla potenza del suo numero privato ottenendo il segreto condiviso (10). - Bob fa lo stesso con il risultato pubblico di Alice (6) e lo eleva al suo numero privato ottenendo anche lui il segreto condiviso (10). Anche se gli esponenti sono usati in ordine diverso, il risultato finale è lo stesso. Questo è perché l'ordine degli esponenti in questo caso non cambia il risultato. Sicurezza: Eve, senza conoscere i numeri privati di Alice o Bob, si trova di fronte al problema del logaritmo discreto, che è difficile da risolvere con numeri grandi. Quindi, anche con tutta la potenza di calcolo disponibile, impiegherebbe un tempo irragionevole per risolvere il problema, rendendo l'encryption praticamente sicura. Questo metodo risolve il problema dello scambio delle chiavi e può essere usato insieme a un generatore pseudocasuale per criptare messaggi tra persone che non si sono mai incontrate. RSA encryption: Step 1 Fino agli anni '70, la crittografia si basava esclusivamente su chiavi simmetriche, dove il mittente e il destinatario usavano la stessa chiave per criptare e decriptare i messaggi. Questo richiedeva però che Alice e Bob condividessero una chiave identica, il che diventava complicato quando non potevano incontrarsi fisicamente o dovevano usare un metodo come lo scambio di chiavi Diffie-Hellman, che comportava un overhead aggiuntivo di comunicazioni. Un problema ancora maggiore si verificava quando Alice (ad esempio una banca) doveva comunicare con molte persone diverse: doveva gestire chiavi separate per ciascun interlocutore, complicando enormemente la gestione delle chiavi. Nel 1970, l'ingegnere britannico James Ellis ebbe un'idea rivoluzionaria basata su una crittografia non segreta. Il concetto era semplice ma geniale: le operazioni di blocco e sblocco sono inversi tra loro. Ellis immaginò un sistema dove Alice poteva creare un lucchetto, tenere la chiave per sé e inviare il lucchetto aperto a Bob. Bob avrebbe potuto usarlo per bloccare un messaggio e poi restituirlo ad Alice, senza che fosse necessario scambiare alcuna chiave. Questo sistema avrebbe permesso ad Alice di pubblicare il lucchetto pubblicamente, permettendo a chiunque di usarlo per inviarle un messaggio, mentre lei avrebbe dovuto gestire solo una singola chiave per decriptare tutti i messaggi. Tuttavia, Ellis non riuscì a sviluppare una soluzione matematica per implementare la sua idea, sebbene avesse un'intuizione chiara. Il concetto si basava sulla divisione di una chiave in due parti: una per criptare e una per decriptare, dove la chiave di decriptazione avrebbe eseguito l'operazione inversa rispetto a quella di criptazione. Esempio con i colori: - Alice sceglie un colore privato, ad esempio il rosso. - Usando una "macchina segreta", calcola il colore complementare del rosso, cioè il ciano, e lo invia a Bob come chiave pubblica. - Bob desidera inviare un messaggio segreto (giallo) e lo mescola con il ciano di Alice, inviando il risultato ad Alice. - Alice aggiunge il suo colore privato (rosso) al messaggio ricevuto, annullando l'effetto del ciano, ottenendo così il colore originale di Bob (giallo). In questo esempio, Eve (l'intercettatore) non ha modo di scoprire il colore di Bob, poiché le manca la chiave privata di Alice (rosso). Tuttavia, per far funzionare tutto in pratica, era necessaria una soluzione matematica. Internet Security Hash Algorithm Gli algoritmi di hashing sono algoritmi a senso unico, il che significa che, una volta criptato un messaggio, non è possibile decriptarlo. In realtà, l'hashing non cripta il messaggio, ma genera un digest o una "impronta digitale" del file, chiamata hash. Quando un messaggio viene elaborato con un algoritmo di hashing, passa attraverso una serie di calcoli matematici che producono un risultato di dimensioni fisse, indipendentemente dalla lunghezza del messaggio iniziale. Una domanda comune è: qual è l'utilità di un algoritmo che non permette di decriptare un messaggio? La risposta sta nel fatto che l'hashing non è progettato per garantire la riservatezza del messaggio, ma per verificarne l'integrità. Quando si invia un messaggio a qualcuno utilizzando un algoritmo di hashing, si calcola l'hash del messaggio e lo si invia insieme al messaggio originale. Il destinatario può quindi utilizzare lo stesso algoritmo di hashing per generare l'hash del messaggio ricevuto. Se l'hash calcolato corrisponde a quello inviato, il destinatario può essere sicuro che il contenuto del messaggio non è stato alterato. Un'altra caratteristica importante degli algoritmi di hashing è che producono un risultato di dimensioni fisse, indipendentemente dalla lunghezza dell'input. Quindi, che si tratti di una singola pagina o di un intero libro, l'output sarà sempre della stessa lunghezza. Esistono diversi tipi di algoritmi di hashing. Uno dei più popolari e diffusi è l'MD5 (Message Digest 5), che genera un hash di 128 bit. Tuttavia, con il tempo sono emerse vulnerabilità in MD5, e così è stato sviluppato l'algoritmo SHA-1, che produce un hash di 160 bit. Anche SHA-1 ha mostrato alcune debolezze, e successivamente è stato introdotto SHA-2, che genera hash di lunghezze variabili, da 224 bit a 512 bit. Più recentemente, è stato sviluppato SHA-3, che rappresenta la versione più sicura della serie SHA. Un altro algoritmo di hashing importante è il RIPEMD (Race Integrity Primitives Evaluation Message Digest), creato da un'organizzazione affiliata all'Unione Europea. Questo algoritmo, come gli altri, genera hash di diverse dimensioni. Oltre a questi, esistono altri algoritmi di hashing, ma quelli descritti sono tra i più comuni e utilizzati. Gli algoritmi di hashing sono fondamentali per garantire l'integrità dei dati, specialmente in ambito digitale, dove l'accuratezza e la sicurezza dei messaggi sono cruciali.  Digital Signature La firma digitale è un concetto che funziona in modo simile alla firma che utilizziamo nella vita quotidiana, ma fornisce un livello di garanzia molto più alto sull'identità del mittente. Nella crittografia asimmetrica, si utilizza una coppia di chiavi: una chiave privata e una chiave pubblica. La chiave privata è mantenuta segreta dal mittente, mentre la chiave pubblica è condivisa con tutti. Se un messaggio viene criptato con una delle due chiavi, può essere decriptato solo con l'altra chiave corrispondente. Ad esempio, se Alice ha una coppia di chiavi e vuole inviare un messaggio a Bob, può fornire a Bob la sua chiave pubblica e chiedergli di criptare il messaggio con essa. Solo Alice, che possiede la chiave privata, potrà decriptarlo. In questo caso, il messaggio è reso riservato poiché solo Alice può accedervi. Tuttavia, se Alice decidesse di criptare un messaggio utilizzando la sua chiave privata, chiunque con la sua chiave pubblica, compreso Bob, potrebbe decriptare il messaggio. In questo scenario, la riservatezza non è più la preoccupazione principale: l’obiettivo è garantire che il messaggio provenga realmente da Alice, proprio come una firma autentica su un documento. Bob non si preoccupa del fatto che altre persone possano leggere il messaggio; il suo interesse è sapere con certezza che il messaggio proviene da Alice. Questo concetto è analogo a quando si firma un assegno: la banca non si preoccupa di chi ha visto l'assegno, ma della corrispondenza tra la firma sull'assegno e quella che hanno registrato. Se corrispondono, la banca sa che l’assegno è autentico. La firma digitale funziona allo stesso modo: quando Alice cripta un messaggio con la sua chiave privata, chiunque con la sua chiave pubblica può decriptarlo, ma solo Alice poteva aver creato il messaggio. Se qualcuno provasse a manipolare il messaggio e a criptarlo nuovamente con la chiave pubblica di Alice, Bob non sarebbe in grado di decriptarlo correttamente con la stessa chiave pubblica, indicando che il messaggio è stato alterato o non proviene da Alice. In sintesi, la firma digitale garantisce che il mittente sia autentico e che il messaggio non sia stato alterato durante la trasmissione. Si basa sulla crittografia asimmetrica, dove la chiave privata serve per creare la firma e la chiave pubblica per verificarla. Anche se esistono algoritmi specifici per le firme digitali, l'importante è capire che questo processo fornisce un metodo sicuro per autenticare l'identità del mittente.  Digital Certificate Un certificato digitale è una tecnologia che collega l'identità di un utente alla sua chiave pubblica, risolvendo il problema della verifica dell'autenticità delle chiavi pubbliche. Ad esempio, quando Alice vuole inviare un messaggio a Bob utilizzando una firma digitale, invia la sua chiave pubblica a Bob affinché quest'ultimo possa verificare l'autenticità del messaggio. Tuttavia, un malintenzionato come Tom potrebbe intercettare e sostituire la chiave pubblica di Alice con la propria, ingannando Bob e permettendogli di modificare il messaggio. Per evitare questo scenario, entra in gioco il certificato digitale. Un certificato digitale garantisce che la chiave pubblica che Bob riceve appartenga effettivamente ad Alice, perché viene emesso da un'autorità di certificazione fidata (CA, Certificate Authority), una terza parte che associa l'identità dell'utente alla chiave pubblica. Il processo è simile a come accettiamo una patente di guida come prova d'identità perché è rilasciata da un'agenzia governativa fidata. Quando Alice desidera un certificato digitale, invia una richiesta di firma del certificato alla CA, includendo informazioni come il suo sito web, il nome dell'attività, il paese, l'indirizzo email e la chiave pubblica. La CA verifica tutte le informazioni e, se tutto è corretto, genera un certificato digitale contenente il nome di Alice, la sua chiave pubblica, il nome della CA, una firma digitale della CA, un numero di serie e una data di scadenza. Il certificato digitale funziona in modo simile a una firma digitale. Quando Alice invia il certificato a Bob, Bob può verificare la firma digitale utilizzando la chiave pubblica della CA per decriptare l'hash del certificato. Se l'hash corrisponde ai dati del certificato, Bob sa che il certificato è valido e che la chiave pubblica appartiene davvero ad Alice. Un esempio pratico dell'uso di certificati digitali è durante lo shopping online. Quando accedi a un sito come Amazon, il tuo browser riceve un certificato digitale dal server di Amazon. Cliccando sull'icona del lucchetto accanto all'URL, puoi vedere che la connessione è sicura e visualizzare i dettagli del certificato, come il nome del sito, l'autorità di certificazione che lo ha emesso e la validità temporale del certificato. Il tuo browser verifica automaticamente il certificato, garantendo che la comunicazione con Amazon sia sicura.