Una ricerca esaustiva delle chiavi è efficace contro i cifrari a sostituzione?

/ / Pubblicato in Cybersecurity, Fondamenti di crittografia classica EITC/IS/CCF, Storia della crittografia, Aritmetica modulare e cifrari storici

Una ricerca esaustiva delle chiavi, nota anche come attacco a forza bruta, consiste nel provare sistematicamente ogni possibile chiave nello spazio delle chiavi di un cifrario fino a trovare la chiave corretta. L'efficacia di un simile approccio dipende in larga misura dalla dimensione dello spazio delle chiavi, che è determinata dal numero di chiavi possibili, e dalla struttura del cifrario attaccato.

I cifrari a sostituzione sono una classe di algoritmi crittografici classici in cui ogni elemento del testo in chiaro (più comunemente una lettera) viene sistematicamente sostituito con un altro elemento fisso del testo cifrato. I tipi più noti sono i cifrari a sostituzione semplici (in cui ogni lettera dell'alfabeto viene mappata su un'altra lettera) e i cifrari a sostituzione monoalfabetici, nonché i cifrari a sostituzione polialfabetici più complessi, come il cifrario di Vigenère.

Per valutare l'efficacia di una ricerca esaustiva delle chiavi rispetto ai cifrari a sostituzione, è necessario analizzare sia gli aspetti teorici che quelli pratici, tra cui la dimensione dello spazio delle chiavi, la natura delle chiavi e le caratteristiche del testo cifrato prodotto.

Spazio delle chiavi dei cifrari di sostituzione

Un semplice cifrario a sostituzione che utilizza l'alfabeto inglese a 26 lettere ha una dimensione dello spazio delle chiavi pari al numero di possibili permutazioni dell'alfabeto. Matematicamente, questo è 26 fattoriale (26!), che equivale a 403,291,461,126,605,635,584,000, ovvero circa 4 x 10^26 chiavi possibili. Per fare un confronto, il cifrario di Cesare, un tipo specifico di cifrario a sostituzione, ha uno spazio delle chiavi molto più piccolo, di sole 25 chiavi (poiché ogni lettera può essere spostata di qualsiasi valore compreso tra 1 e 25).

Un aspetto fondamentale dei cifrari a sostituzione è che la chiave non è una stringa di bit casuale, bensì una permutazione dell'alfabeto, il che influenza il modo in cui le chiavi vengono generate e testate in una ricerca esaustiva.

Ricerca esaustiva delle chiavi sui cifrari a sostituzione semplice

Il principio di una ricerca esaustiva delle chiavi prevede che per ogni possibile chiave, l'attaccante decifri il testo cifrato e verifichi se il testo in chiaro risultante sia significativo. Per i cifrari a sostituzione, in particolare quelli con ampi spazi chiave come la sostituzione monoalfabetica, questo rappresenta teoricamente un problema computazionalmente difficile, poiché esiste un numero impressionante di possibili permutazioni da testare.

Tuttavia, l'efficacia pratica della ricerca esaustiva sui cifrari a sostituzione è limitata da diversi fattori:

1. Verifica della chiave

A differenza dei cifrari moderni, in cui una chiave produce o meno il testo in chiaro corretto, con i cifrari a sostituzione l'attaccante deve decidere se l'output è un inglese valido (o la lingua del testo in chiaro prevista). Nei cifrari classici non esiste alcun indicatore o checksum, quindi l'attaccante deve verificare manualmente o automaticamente l'output. Data la ridondanza e la prevedibilità dei linguaggi naturali, questo è in genere facile da riconoscere per gli esseri umani, ma difficile da automatizzare, soprattutto dato il numero di chiavi.

2. Ridondanza nel linguaggio

Poiché le lingue naturali come l'inglese presentano una ridondanza e una struttura significative, gli output decifrati che non corrispondono a testo leggibile possono essere rapidamente scartati. Tuttavia, statisticamente, la probabilità di permutare casualmente l'alfabeto e produrre testo significativo è astronomicamente bassa, rendendo la ricerca esaustiva inefficiente.

3. Fattibilità

Sebbene lo spazio delle chiavi sia enorme, i computer moderni potrebbero, in teoria, tentare milioni o addirittura miliardi di chiavi al secondo. Ciononostante, lo spazio delle chiavi 26! è così vasto che, anche con immense risorse di calcolo, una ricerca esaustiva richiederebbe un tempo impraticabile.

Attacchi storici e pratici

Nonostante la sicurezza teorica garantita dalle dimensioni dello spazio delle chiavi, i cifrari a sostituzione non sono considerati sicuri, nemmeno contro aggressori che non dispongono delle risorse per una ricerca esaustiva delle chiavi. Il motivo principale è che questi cifrari sono vulnerabili agli attacchi analitici, in particolare all'analisi di frequenza.

Analisi di frequenza

Ogni lettera nel testo in chiaro viene sempre sostituita dalla stessa lettera nel testo cifrato, in modo da preservare le proprietà statistiche del testo in chiaro. Ad esempio, in un testo inglese, la lettera "E" è la più comune. Analizzando la frequenza delle lettere nel testo cifrato, un aggressore può dedurre quali simboli del testo cifrato corrispondono a quali lettere del testo in chiaro.

Questo metodo è molto più efficiente della ricerca esaustiva della chiave. Richiede solo una quantità moderata di testo cifrato per essere efficace e può recuperare la chiave o il testo in chiaro con uno sforzo computazionale minimo rispetto a un approccio a forza bruta.

Esempio

Supponiamo che un aggressore intercetti un testo cifrato crittografato con un cifrario a sostituzione monoalfabetica. Viene eseguito un conteggio delle frequenze, rivelando che il simbolo "Q" ricorre più frequentemente. Se l'aggressore sa che la lingua è l'inglese, è probabile che "Q" corrisponda a "E". Ripetendo questo processo per altre lettere ricorrenti (come "T", "A", "O"), l'aggressore può ricostruire la chiave di sostituzione, o almeno parte di essa, senza provare tutte le 26! permutazioni.

Recupero chiave vs. recupero testo normale

La ricerca esaustiva delle chiavi mira a recuperare la chiave in modo che qualsiasi messaggio crittografato con la stessa chiave possa essere decifrato. L'analisi di frequenza e attacchi analitici simili di solito forniscono una quantità di chiave sufficiente a recuperare il testo in chiaro, anche se la chiave completa non viene recuperata immediatamente. In pratica, questo è sufficiente a violare la sicurezza del cifrario.

Aritmetica modulare e cifrari classici

Alcuni cifrari a sostituzione, come il cifrario affine e il cifrario di Cesare, utilizzano l'aritmetica modulare nelle loro trasformazioni.

- Cesare Cipher: Ogni lettera del testo in chiaro viene spostata di un numero fisso di posizioni nell'alfabeto. Matematicamente, per lettera del testo in chiaro x, il testo cifrato viene calcolato come (x + k) \mod 26Durante la serata, k è il tasto shift.
- Cifra affine:Ogni lettera è criptata come (ax + b) \mod 26Durante la serata, a e b sono le chiavi e a e 26 devono essere coprimi.

Per questi cifrari, lo spazio delle chiavi è molto più piccolo (25 per Cesare, 312 per affine), rendendo la ricerca esaustiva delle chiavi non solo fattibile, ma anche banale. Ad esempio, un aggressore può provare tutti i 25 possibili turni di Cesare in pochi secondi. Pertanto, gli attacchi a forza bruta sono altamente efficaci contro questi cifrari.

Cifrari a sostituzione polialfabetica

I cifrari più complessi, come il cifrario di Vigenère, utilizzano una chiave ripetuta per modificare la sostituzione di ogni lettera, rendendo l'analisi di frequenza meno efficace. Tuttavia, lo spazio delle chiavi è determinato dalla lunghezza e dai possibili valori della chiave.

Se la chiave è di lunghezza ne ogni carattere può essere una qualsiasi lettera (26 opzioni), lo spazio dei tasti è 26^nPer chiavi corte, questa è ancora suscettibile di ricerca esaustiva. Ad esempio, una chiave di 5 lettere produce 11,881,376 possibili chiavi (26 ^ 5), che è alla portata dei computer moderni. Tuttavia, una chiave più lunga aumenta esponenzialmente lo spazio delle chiavi, ma l'uso pratico del cifrario di Vigenère spesso prevedeva chiavi corte, rendendolo vulnerabile ad attacchi a forza bruta e analitici.

Nel caso del cifrario di Vigenère, se la lunghezza della chiave è nota, il cifrario può essere scomposto in un equivalente di diversi cifrari di Cesare, ciascuno dei quali può essere attaccato separatamente. Metodi come l'esame di Kasiski e il test di Friedman possono aiutare a determinare la lunghezza della chiave, dopodiché l'analisi di frequenza viene applicata a ciascun sottoinsieme.

Valutazione pratica della sicurezza

L'insicurezza pratica dei cifrari a sostituzione non è dovuta solo alla dimensione del loro spazio chiavi, ma piuttosto alle debolezze strutturali che consentono attacchi analitici. La ricerca esaustiva delle chiavi è teoricamente efficace, in quanto garantisce che la chiave venga trovata alla fine, ma in pratica non è il metodo di attacco preferito a causa dell'inefficienza e della disponibilità di tecniche più efficaci.

Per i cifrari classici con spazi chiave ridotti (come i cifrari di Cesare e affini), la ricerca esaustiva delle chiavi è banalmente efficace. Per i cifrari a sostituzione monoalfabetica, lo spazio chiave è sufficientemente ampio da impedire la ricerca esaustiva anche con i computer moderni più potenti, ma questi cifrari sono comunque insicuri a causa dell'analisi di frequenza.

Valore Didattico

Studiare l'(in)efficacia della ricerca esaustiva delle chiavi rispetto ai cifrari a sostituzione offre preziose lezioni di crittografia:

- La dimensione dello spazio delle chiavi è importante, ma non è tutto:Uno spazio chiavi ampio può rendere impraticabili gli attacchi a forza bruta, ma non garantisce la sicurezza se il cifrario fa trapelare informazioni strutturali sul testo in chiaro.
- Importanza delle proprietà statistiche:I cifrari classici spesso falliscono perché preservano le caratteristiche statistiche del testo in chiaro, consentendo attacchi analitici.
- Ruolo dell'aritmetica modulare:Comprendere come le operazioni aritmetiche definiscono le trasformazioni in cifrari come quelli di Cesare e affini aiuta a capire perché i loro spazi chiave sono così piccoli e perché sono così facilmente violabili tramite forza bruta.
- Evoluzione della crittoanalisi:Il passaggio storico dagli attacchi a forza bruta a quelli analitici dimostra i progressi del settore e la necessità di cifrari che non trasmettano informazioni sul testo in chiaro o sulla chiave.

Calcolo di esempio

Supponiamo che un aggressore voglia forzare brute force un cifrario a sostituzione monoalfabetica. Se un supercomputer potesse provare 1 miliardo (10^9) chiavi al secondo, ci vorrebbero:

    \[ \frac{4 \times 10^{26}}{10^9 \text{ chiavi/sec}} = 4 \times 10^{17} \text{ secondi} \]

    \[ = \frac{4 \times 10^{17}}{60 \times 60 \times 24 \times 365} \approx 1.27 \times 10^{10} \text{ anni} \]

Si tratta di un periodo di ordini di grandezza superiore all'età dell'universo, il che rende gli attacchi basati sulla forza bruta praticamente impraticabili.

Prospettiva moderna

Nella crittografia contemporanea, gli insegnamenti tratti dai cifrari a sostituzione sono chiari. La dimensione della chiave da sola non è una misura sufficiente di sicurezza; la struttura del cifrario e la sua resistenza agli attacchi analitici e statistici sono altrettanto importanti, se non di più. I cifrari moderni, come AES, sono progettati per resistere sia alla ricerca esaustiva delle chiavi (grazie a spazi chiave astronomicamente ampi) sia a tutti gli attacchi analitici noti.

I cifrari classici, compresi i cifrari a sostituzione, sono quindi preziosi strumenti didattici per comprendere l'interazione tra spazio delle chiavi, struttura del cifrario e metodi di crittoanalisi.

Altre domande e risposte recenti riguardanti Fondamenti di crittografia classica EITC/IS/CCF:

Visualizza altre domande e risposte in EITC/IS/CCF Classical Cryptography Fundamentals

Altre domande e risposte:

Etichettato sotto: , , , , ,