Cifrario a sostituzione
# Cifrario a sostituzione

In crittografia un cifrario a sostituzione è un metodo di cifratura in cui ogni unità del testo in chiaro è sostituita con del testo cifrato secondo uno schema regolare; le "unità" possono essere singole lettere (il caso più comune), coppie di lettere, sillabe, mescolanze di esse, ed altro. Il destinatario decifra il messaggio applicando una sostituzione invertita.

I cifrari a sostituzione sono simili ai cifrari a trasposizione con la differenza che questi ultimi operano ricombinando le unità del testo in chiaro in un ordine differente e di solito più complesso ma lasciandole comunque inalterate. Nei cifrari a sostituzione, invece, le unità del testo in chiaro sono riallocate nel testo cifrato nella stessa sequenza ma vengono però alterate.

Esistono diversi tipi di cifrari a sostituzione: se il cifrario opera su singole lettere, è detto cifrario a sostituzione semplice; se opera su gruppi di lettere più grandi è detto cifrario poligrafico. Un cifrario monoalfabetico utilizza sostituzioni fisse sull'intero messaggio mentre un cifrario polialfabetico usa invece differenti schemi di sostituzione ed ogni lettera del testo in chiaro è trattata con un differente alfabeto secondo uno schema stabilito dalla chiave segreta.

## Sostituzione semplice

La sostituzione operante su singole lettere, detta sostituzione semplice, si applica utilizzando un altro alfabeto scritto con le lettere disposte in un certo ordine detto alfabeto per la sostituzione. Questo può essere preparato ruotando od invertendo l'alfabeto (creando così, rispettivamente, il cifrario di Cesare ed il cifrario Atbash) oppure mescolando le lettere secondo un ordine prestabilito: in quest'ultimo caso si parla di alfabeto mescolato o alfabeto squilibrato. Tradizionalmente gli alfabeti mescolati sono creati scrivendo prima una parola chiave, eliminando le sue lettere ripetute e poi scrivendo tutte le lettere rimanenti dell'alfabeto.

### Esempi

Utilizzando questo sistema, la parola chiave "zebra" dai seguenti alfabeti:

| Alfabeto del testo in chiaro: | abcdefghijklmnopqrstuvwxyz |
| - | - |
| Alfabeto del testo cifrato: | ZEBRACDFGHIJKLMNOPQSTUVWXY |

Un messaggio quale

viene cifrato come

Tradizionalmente il testo cifrato è scritto in blocchi di lunghezza prefissata, omettendo i segni di punteggiatura e gli spazi, per evitare errori trasmissione e per non far capire i confini delle parole del testo in chiaro. Questi blocchi sono detti "gruppi" e, talvolta, viene anche fornito un "contatore di gruppi" (cioè il numero dei gruppi) come controllo addizionale. Il numero di lettere più usato nella creazione dei gruppi è 5, un'usanza nata quando i messaggi venivano inviati tramite telegrafo. L'esempio precedente diventa quindi:

Se la lunghezza del messaggio non è divisibile per 5, si aggiungono alla fine del caratteri nulli, caratteri che, decifrati, non abbiano senso in modo che il destinatario li riconosca e li possa scartare.

L'alfabeto del testo cifrato può alle volte differire da quello del messaggio in chiaro. Ad esempio, nel cifrario massone il testo cifrato è composto da un insieme di simboli derivati da una griglia:

Tuttavia, ai fini della sicurezza l'uso di simboli al posto delle lettere fa poca differenza: si può utilizzare qualunque insieme di simboli che, ritrascritti con le lettere dell'alfabeto, possono poi essere gestiti nella solita maniera.

Nei listini e nei cataloghi di vendita spesso si utilizza per i prezzi una semplice forma di cifratura per rimpiazzare le cifre numeriche con le lettere:

| Cifre in chiaro: | 1234567890 |
| - | - |
| Alfabeto del testo cifrato: | MAKEPROFIT |

Esempio: MAT sarebbe la rappresentazione di 120.

### Sicurezza dei cifrari a sostituzione semplice

Uno svantaggio di questo metodo operativo è che le ultime lettere dell'alfabeto (che sono in genere le meno frequenti) tendono a raggrupparsi alla fine. Un modo più robusto di costruire un alfabeto mescolato è quello di effettuare una trasposizione colonnare dell'alfabeto ordinario utilizzando una parola chiave: nonostante l'aumento della sicurezza del cifrario che si ottiene, questo stratagemma non è però utilizzato molto spesso.

Anche se lo spazio delle chiavi è molto vasto (26!, ≈ $2^{88,4},$ o circa 88 bit), questo cifrario non è molto robusto e si rivela facile da violare. Dato un messaggio di lunghezza ragionevole (vedi sotto), mediante crittanalisi si può dedurre il probabile significato della maggior parte dei simboli più comuni analizzando la distribuzione di frequenze dell'analisi delle frequenze del testo cifrato. Ciò permette la formazione di parole parziali, che possono essere completate per tentativi, espandendo progressivamente la soluzione parziale. In alcuni casi, le parole cifrate possono essere determinate dal modello delle loro lettere: ad esempio, attract ed osseous sono le uniche parole della lingua inglese che corrispondono al modello ABBCADB. Molte persone risolvono questo tipo di cifrari per divertimento nelle rubriche di enigmistica dei giornali (sono i cosiddetti crittogrammi).

Stando alla distanza di unicità della lingua inglese, per violare un cifrario a sostituzione semplice con alfabeto mescolato sono richieste 27,6 lettere di testo cifrato. In pratica, però, ne occorrono in media 50, anche se alcuni messaggi possono essere violati con un numero inferiore se si presentano modelli inusuali nel testo. In altri casi, il testo in chiaro può essere manipolato per avere una distribuzione della frequenza delle lettere più piatta, ma ciò comporta il dover avere testi in chiaro più lunghi.

## Sostituzione omofonica

Un primo tentativo di aumentare la difficoltà degli attacchi ai cifrari a sostituzione basati sull'analisi delle frequenze si ebbe cercando di mascherare la frequenza delle lettere dei messaggi in chiaro con l'omofonia: in questi cifrari le lettere del messaggio in chiaro possono essere sostituite da più di un simbolo cifrato. In genere, più un simbolo del testo in chiaro ha una frequenza elevata e più sono i simboli cifrati corrispondenti: in questo modo la distribuzione delle frequenze viene appiattita, rendendo l'analisi più difficoltosa.

Dato che in questo modo occorrono più delle 26 lettere dell'alfabeto per formare tutti i caratteri dell'alfabeto cifrato, viene fatto in genere ricorso a diverse soluzioni per la creazione dei simboli mancanti: la soluzione più semplice è quella di utilizzare un "alfabeto" a sostituzione numerica, mentre un altro metodo consiste nell'uso di semplici varianti dell'alfabeto esistente (caratteri maiuscoli, minuscoli, dall'alto in basso, ecc.). Alcune soluzioni più stravaganti, anche se non necessariamente più sicure, utilizzano alfabeti completamente inventati e costituiti da simboli di fantasia (esempi sono il manoscritto Voynich ed il cifrario illustrato nel racconto Lo scarabeo d'oro di Edgar Allan Poe).

### I nomenclatori

Una variante più interessante è il nomenclator, o nomenclatore, così detto dal pubblico ufficiale che annunciava i titoli dei dignitari in visita alle corti reali: questo cifrario combinava un piccolo libro codice con grandi tabelle di sostituzione omofoniche. Originariamente il cifrario fu ristretto ai nomi di persone importanti, da cui il suo nome; ma nel corso degli anni arrivò ad includere molte parole di uso comune e nomi di luoghi noti. I simboli per queste parole (o nomi in codice) e queste lettere (o cifrari) non erano distinguibili nel testo cifrato. Il Grande Cifrario del Rossignol, usato da Luigi XIV di Francia ne è un esempio: i messaggi scritti con questo cifrario rimasero inviolati per diversi secoli.

I nomenclatori furono usati dall'inizio del XV secolo fino alla fine del XVIII secolo nella corrispondenza diplomatica, nello spionaggio e nelle cospirazioni politiche, nonostante molti di essi erano e rimasero crittograficamente poco sofisticati. Anche se dalla metà del XVI secolo i crittanalisti cominciarono a violare i nomenclatori ed altri sistemi più sicuri si erano già diffusi a partire dal 1467 (come il disco cifrante dell'Alberti), i loro utilizzatori continuavano a fidarsi di questi cifrari e rispondevano alla loro perdita di sicurezza semplicemente allargando le tabelle di sostituzione: alla fine del XVIII secolo, quando cessarono di essere utilizzati, alcuni nomenclatori avevano raggiunto la ragguardevole cifra di 50.000 simboli.

Nonostante ciò, non tutti i nomenclatori sono stati violati e la crittanalisi dei testi cifrati archiviati rimane un'area molto proficua della ricerca storica.

I libri codice e le scacchiere a diffusione (o straddling checkerboard in inglese) sono tipici esempi di cifrari omofonici.

## Sostituzione polialfabetica

I cifrari a sostituzione polialfabetica furono descritti per la prima volta nel 1467 da Leone Battista Alberti, che li utilizzò per i suoi celebri dischi cifranti. Johannes Trithemius, nel suo libro Steganografia, che greco antico significa "scrittura nascosta" (scritto all'incirca nel 1499 ma pubblicato solo nel 1606) presentava un cifrario basato sull'uso di "tabule", o tabelle di sostituzione, idea poi ripresa ed ampliata nel 1516 quando ideò la sua tabula recta, più nota però come tavola di Vigenère perché ripresa dall'omonimo matematico francese per il suo ben più noto cifrario . Una versione più sofisticata di questo tipo di cifrario, basato sull'uso di più cifrari, fu presentata da Giovanni Battista della Porta nel 1563 descrivendola nel suo libro De Furtivis Literarum Notis.

In un cifrario polialfabetico vengono utilizzati più cifrari alfabetici. Per facilitare la cifratura, tutti gli alfabeti sono scritti in genere in una grande tabella, tradizionalmente chiamata tabula, le cui dimensioni sono in genere di 26×26 caselle, così che siano disponibili 26 alfabeti di testo cifrato completi. Il metodo per riempire la tabula e per scegliere la successione degli alfabeti definisce il particolare cifrario polialfabetico. Tutti questi cifrari sono molto più facili da violare di quanto si creda se gli alfabeti a sostituzione sono ripetuti per messaggi in chiaro sufficientemente lunghi.

Uno dei più popolari fu quello ideato da Blaise de Vigenère. Pubblicato per la prima volta nel 1585, fu considerato inviolabile fino al 1863, e per questo definito "il cifrario indecifrabile". Nel cifrario di Vigenère la prima riga della tabula viene riempita con una copia dell'alfabeto in chiaro mentre le successive righe sono create ruotando semplicemente di un carattere a sinistra la riga soprastante (questo tipo di tabula corrisponde matematicamente alla somma tra il testo in chiaro e le lettere della chiave modulo 26). Per scegliere l'alfabeto da usare per cifrare il testo si usa una parola chiave: ogni lettera della parola chiave viene usata a turno, ripetendo la selezione dall'inizio. Ad esempio, se la parola chiave è "SALE", la prima lettera del messaggio in chiaro è cifrata con l'alfabeto "S", la seconda con l'alfabeto "A", la terza con l'alfabeto "L", la quarta con l'alfabeto "E", la quinta nuovamente con l'alfabeto "S", la sesta nuovamente con l'alfabeto "A" e così via. Le chiavi dei cifrari di Vigenère sono spesso frasi molto lunghe onde evitare il problema della ripetizione degli alfabeti con una frequenza molto alta.

Nel 1863 Friedrich Kasiski pubblicò un metodo crittanalitico (in realtà scoperto anni prima da Charles Babbage ma mai da quest'ultimo pubblicato) che permetteva di calcolare la lunghezza della parole chiave usata nel cifrario di Vigenère. Una volta ottenuto questo dato, le lettere del messaggio segreto che erano state cifrate utilizzando lo stesso alfabeto potevano essere isolate ed attaccate separatamente come costituenti di un certo numero di semplici cifrari a sostituzione semi-indipendenti, situazione complicata dal fatto che per ogni alfabeto le lettere erano separate e non componevano parole complete ma semplificata dall'uso di una più semplice tabula recta.

Un cifrario di Vigenère sarebbe in teoria molto difficile da violare se si ricorresse ad alcuni stratagemmi, quali l'uso di alfabeti mescolati nella tabula, l'uso di parole chiave casuali e se la lunghezza del messaggio cifrato fosse inferiore a 27,6 volte la lunghezza della parola chiave (questo a causa della distanza di unicità). Questi requisiti erano però raramente rispettati per cui i messaggi cifrati con il cifrario di Vigenère erano in pratica molto meno sicuri di quanto in teoria si credeva.

Quelli appena descritti non sono gli unici cifrari polialfabetici ma solo quelli più famosi. Altri cifrari sono:

* il cifrario Gronsfeld: è identico al Vigenère eccettuato il fatto che utilizza solo 10 alfabeti e che la parola chiave è numerica;
* il cifrario Beaufort: questo cifrario è in pratica un cifrario di Vigenère in cui la tabula è sostituita da una tabella invertita, matematicamente equivalente a testo cifrato = chiave - testo in chiaro. Questa operazione è auto-invertibile: la stessa tabella può essere utilizzata sia per la cifratura che per la decifratura.
* il cifrario ad autochiave: questo cifrario, sempre inventato da Vigenère, mescola il testo in chiaro con una chiave per evitare la periodicità;
* il cifrario a chiave continua, dove la chiave usata, molto lunga, è tratta da un passaggio estratto da un libro o da altro testo similare.

I moderni cifrari a flusso possono essere considerati un'evoluzione dei cifrari polilafabetici in cui si sfrutta per la cifratura un keystream il più lungo ed imprevedibile possibile.

## Sostituzione poligrafica

In un cifrario a sostituzione poligrafica le lettere del testo in chiaro sono sostituite a gruppi invece che singolarmente. Uno dei vantaggi di questo metodo è che la distribuzione della frequenza è molto più piatta che operando su lettere individuali (anche se non è del tutto piatta nel caso di linguaggi reali: ad esempio, in italiano "CH" è molto più frequente di "QU"). Un altro vantaggio è che l'ampio numero di simboli utilizzati rende necessario utilizzare molti più testi cifrati per avere un'analisi delle frequenze che sia valida.

Per la sostituzione di coppie di lettere sarebbe necessario ricorrere ad un alfabeto sostitutivo composto da 676 simboli ($26^{2}=676$): nel De Furtivis Literarum Notis su menzionato, lo stesso Della Porta proponeva un tale sistema, con una tabula di dimensioni 20 x 20 (per le 20 lettere dell'alfabeto latino che usava) composta da 400 glifi unici. Tale sistema era complesso da mettere in pratica e forse non fu mai neanche usato.

### Cifrari bigrafici

Il primo cifrario bigrafico (sostituzione a coppie) noto fu il cosiddetto cifrario Playfair, inventato da Charles Wheatstone nel 1854: esso era costituito da una griglia 5 x 5 composta dalle lettere dell'alfabeto in ordine sparso (due lettere occupavano una stessa casella, in genere la "I" e la "J"). Veniva poi effettuata una sostituzione bigrafica usando un ipotetico rettangolo costruito utilizzando le lettere della coppia da cifrare per indicare due suoi vertici: gli altri due vertici indicavano le lettere da usare per comporre la coppia di testo cifrato. Esistevano delle regole speciali per trattare le lettere doppie oppure le coppie di lettere che ricadevano in una stessa riga o colonna.

Il Playfair fu usato in campo militare nel periodo compreso fra la seconda guerra boera e la seconda guerra mondiale.

Nel 1901 Felix Delastelle inventò altri cifrari poligrafici, inclusi il cifrario bifido, il cifrario a quattro quadrati (entrambi bigrafici) ed il cifrario trifido (probabilmente il primo cifrario trigrafico usabile realmente).

### Cifrario di Hill

Il cifrario di Hill, inventato nel 1929 da Lester S. Hill è un cifrario a sostituzione poligrafica che può unire contemporaneamente più gruppi di lettere utilizzando l'algebra lineare. Ogni lettere è trattata come un numero in base 26: A è uguale a 0, B è uguale ad 1, e così via (esisteva una variante in cui venivano aggiunti tre ulteriori simboli per rendere la base prima). Un blocco n di lettere è quindi considerato come uno spazio vettoriale di dimensione n, e moltiplicato per una matrice n x n, modulo 26. L'intera matrice è considerata la chiave del cifrario e deve essere casuale, a patto che sia invertibile in $\mathbb {Z} _{26}^{n}$ (per assicurare che la decrittazione sia possibile). Incredibilmente, fu implementato meccanicamente un cifrario di Hill di dimensione 6.

Sfortunatamente il cifrario di Hill risultava vulnerabile ad un attacco con testo in chiaro noto perché completamente lineare per cui deve essere combinato con qualche funzione non lineare per poter resistere a questo attacco. La combinazione di schemi deboli ma con buone capacità di diffusione, come il cifrario di Hill, con schemi a sostituzione non lineare ha portato alle reti a sostituzione e permutazione, come ad esempio il cifrario di Feistel: estremizzando, è possibile considerare i moderni cifrari a blocchi come un'evoluzione dei cifrari a sostituzione poligrafica.

## Cifrari a sostituzione meccanici

Nel periodo che intercorse fra la prima guerra mondiale e la diffusione dei primi computer (approssimativamente tra gli anni cinquanta e gli anni sessanta per alcuni Governi, negli anni settanta per alcune grandi aziende e circa dal 1975 presso la popolazione), erano molto usate le implementazioni meccaniche dei cifrari a sostituzione polialfabetica. Molti inventori ebbero idee similari all'incirca nello stesso periodo: nel 1919 furono infatti brevettate 4 macchine cifranti a rotori, la più importante e nota delle quali fu senz'altro la macchina Enigma, specialmente nelle versioni utilizzate dalle Forze Armate Tedesche a partire dal 1930. Gli Alleati svilupparono anch'essi delle macchine a rotori, quali la SIGABA e la Typex.

Tutte queste macchine operavano in maniera molto simile, nel senso che le lettere cifrate venivano scelte elettricamente fra le tantissime possibili combinazioni ottenibili dalla rotazione di diversi dischi letterali: dato che uno o più dischi erano ruotati meccanicamente ad ogni lettera del testo in chiaro cifrata, il numero di alfabeti utilizzati era sostanzialmente astronomico. Le prime versioni di queste macchine furono, inevitabilmente, violabili: William F. Friedman del Signal Intelligence Service (SIS) americano trovò delle vulnerabilità nella macchina a rotori di Hebern mentre Dillwyn Knox del GCHQ, il servizio britannico per la sicurezza delle telecomunicazioni, decifrò alcuni messaggi inviati con le prime versioni della macchina Enigma, quella senza il pannello degli spinotti, ben prima che la seconda guerra mondiale avesse inizio. Tutti i messaggi cifrati dalle forze militari tedesche con le prime macchine Enigma, quelle usate nei primi anni trenta, furono decifrati dai crittanalisti degli Alleati: di questi, i più famosi furono quelli che operarono a Bletchley Park, tra cui uno dei più importanti fu il matematico polacco Marian Rejewski. Verso la fine degli anni trenta i tedeschi variarono le macchine Enigma, rendendo più arduo il lavoro dei crittanalisti: fu modificata soprattutto la versione della macchina a disposizione della marina tedesca, rinforzando i suoi schemi di sicurezza mediante l'adozione di quattro rotori scelti fra un gruppo di 8. La marina tedesca era, nel complesso, la forza armata più pericolosa: i suoi U-Boot, i famosi sommergibili, davano molto filo da torcere nelle acque dell'Oceano Atlantico. Nel 1941 fu approntato un piano (l'Operazione Primrose) da parte della marina britannica per catturare un U-Boot ed entrare in possesso di una macchina Enigma completa. L'operazione ebbe successo e la macchina, con tutti i manuali di funzionamento ed il gruppo completo dei rotori, fu spedito a Bletchley Park, dove aiutò il gruppo di crittanalisti a decifrare i messaggi delle ultime versioni di Enigma.

Non si ha notizia, invece, di nessun messaggio protetto con le macchine SIGABA e Typex che sia stato decifrato.

## I cifrari "one-time pad"

Il cifrario one-time pad, letteralmente maschera monouso, è un tipo di cifrario a sostituzione molto speciale. Fu inventato verso la fine della prima guerra mondiale dagli americani Gilbert Vernam e Joseph Mauborgne e fu dimostrato matematicamente inviolabile da Claude Shannon nel 1949. Nella più comune delle sue implementazioni, l'one-time pad può essere considerato solo in parte un cifrario a sostituzione: esso infatti prevede che le lettere del testo da cifrare siano combinate, e non sostituite, con quelle della chiave utilizzando un determinato schema (generalmente lo XOR).

I cifrari one-time pad non sono facilmente implementabili nella realtà dato che si basano su alcuni principi difficili da mettere in pratica: la chiave deve essere lunga quanto il testo in chiaro e deve essere veramente casuale, va utilizzata una ed una sola volta, va tenuta segreta a tutti eccezion fatta per il mittente e per il destinatario. Quando anche una di queste condizioni viene violata, anche solo marginalmente, il cifrario one-time pad non è più sicuro. I messaggi cifrati con sistemi one-time pad spediti dagli Stati Uniti d'America dalle spie sovietiche verso la fine della seconda guerra mondiale furono in parte decifrati dai crittanalisti americani verso la fine degli anni quaranta (vedi Progetto Venona) perché erano state utilizzate chiavi non casuali.

Sono state anche create delle implementazioni meccaniche dei sistemi one-time pad, come il ROCKEX usato dai governi di Gran Bretagna e Canada. Si ha notizia anche di una tale macchina utilizzata per cifrare le comunicazioni fra Mosca e Washington durante la crisi dei missili cubani.

## I cifrari a sostituzione nella crittografia moderna

I cifrari a sostituzione, così come descritti fin qui, specialmente i vecchi cifrari da carta e penna, non sono più utililzzati nel campo della sicurezza. Nonostante ciò, il concetto crittografico della sostituzione vive ancor oggi: analizzando i moderni cifrari a blocchi che lavorano su bit di informazione, quali il DES o l'AES, si può astrarre questi cifrari a cifrari a sostituzione che operano su enormi alfabeti binari. In aggiunta, i cifrari a blocchi includono spesso delle piccole tabelle di sostituzione chiamate S-box, abbreviativo di substitution box (vedere anche rete a sostituzione e permutazione).

## I cifrari a sostituzione nella cultura di massa

* Sherlock Holmes viola un cifrario a sostituzione nel racconto "L'avventura degli omini danzanti"
* Il linguaggio Al Bhed di Final Fantasy X è in pratica un cifrario a sostituzione in cui però la traduzione (e la pronuncia) varia in base alla lingua da cui il termine deriva. Ad esempio, "mare" è tradotto come "Syna" se il giocatore è italiano, oppure "Cay" se il giocatore è inglese.
* L'Uryuomoco, la lingua inventata del fumetto web "El Goonish Shive", è un cifrario a sostituzione derivato dall'inglese
* L'alfabeto dei Minbari, una razza aliena della serie televisiva Babylon 5, è anch'esso un cifrario a sostituzione derivato dall'inglese.
* La lingua parlata dai nativi Sauriani e dal personaggio Kystal nel videogioco Star Fox Adventures: Dinosaur Planet è sempre un cifrario a sostituzione derivato dall'inglese.
* In World of Warcraft i personaggi parlano diverse lingue a seconda della razza e dalla fazione a cui appartengono. Tutte le lingue che i personaggi parlano sono rese in inglese o nella lingua del server se questo non è inglese, ma i linguaggi che un personaggio non parla sono resi attraverso un cifrario a sostituzione. Ad esempio, se un appartenente all'Orda dice "lol", ogni appartenente all'Alleanza vedrà "[Orchesco]: kek"
* In Yu-Gi-Oh! Zexal, l'alfabeto del Mondo Astrale è un cifrario del katakana giapponese. Analogamente, quello del Mondo Bariano è un cifrario del rōmaji.
