Cifrario a trasposizione

In crittografia un cifrario a trasposizione è un metodo di cifratura in cui le posizioni occupate dalle unità di testo in chiaro (che in genere sono lettere o gruppi di esse) sono cambiate secondo un determinato schema, così che il testo cifrato costituisca una permutazione del testo in chiaro. Matematicamente parlando viene utilizzata una funzione di corrispondenza biunivoca sulle posizioni dei caratteri durante l'operazione di codifica e una funzione inversa durante quella di decodifica.

Quelle che seguono sono alcune implementazioni di cifrari a trasposizione.

Cifrario a staccionata

Il cifrario a staccionata è un tipo di cifrario a trasposizione che deve il suo nome al modo in cui il testo in chiaro viene cifrato: esso viene trascritto lettera per lettera su righe ideali, diagonalmente verso il basso e poi risalendo una volta arrivati alla riga più bassa e viceversa arrivati alla riga più in alto, disegnando ipotetiche traverse di un'immaginaria staccionata. Il messaggio cifrato si ottiene, alla fine, leggendo le lettere così posizionate riga per riga. Ad esempio, utilizzando 3 righe e il messaggio "PIANTARE IL CAMPO DIETRO LA COLLINA", la trasposizione sarà:

P . . . T . . . I . . . M . . . I . . . O . . . O . . . N .
. I . N . A . E . L . A . P . D . E . R . L . C . L . I . A
. . A . . . R . . . C . . . O . . . T . . . A . . . L . . .

Che sarà cifrato come:

PTIMI OONIN AELAP DERLC LIAAR COTAL

(Il cifrante ha diviso il testo cifrato in blocchi di 5 lettere così da ridurre gli errori di trascrizione)

Cifrario a percorso

In un cifrario a percorso il testo in chiaro viene prima scritto in una griglia di dimensioni prefissate e poi letto seguendo uno schema dato dalla chiave. Ad esempio, usando lo stesso testo in chiaro utilizzato per l'esempio precedente, potremmo avere:

P A C D O L
I R A I L L
A E M E A I
N I P T C N
T L O R O A

La chiave potrebbe specificare di "leggere in spirali concentriche, in senso antiorario, partendo dall'angolo in alto a destra".Otterremmo perciò il seguente testo cifrato:

LODCAPIANTLOROANILLIAREIPTCAEM

I cifrari a percorso possono avere molte più chiavi di quelli a staccionata. Infatti, per messaggi di una certa lunghezza il numero di possibili chiavi è potenzialmente troppo grande anche essere provate dai moderni computer. Nonostante ciò, non tutte le chiavi sono ugualmente valide: i percorsi scelti malamente possono lasciare troppi blocchi di testo in chiaro o possono semplicemente invertire il testo, dando così ad un crittanalisita informazioni sui percorsi usati.

Una variante interessante del cifrario a percorso fu l'Union Route Cipher, il cifrario a percorso dell'Unione, utilizzato dalle forze dell'Unione durante la Guerra di secessione americana. Esso era un normale cifrario a percorso ma che operava su intere parole piuttosto che sulle singole lettere. A causa di questo modo di operare, alcune parole di importante significato venivano prima codificate tramite un codice. A volte venivano anche inserite parole inutili al senso del discorso al solo scopo di confondere le acque o per rendere il testo cifrato di senso compiuto^[1].

Trasposizione colonnare

Nella trasposizione colonnare il messaggio è scritto lungo le righe di una griglia di dimensioni prefissate e poi letto lungo le colonne, secondo un ordine particolare delle stesse. Sia la lunghezza delle righe che la permutazione delle colonne sono definite da una parola chiave. Ad esempio, la parola VETRINA è lunga 7 lettere, così le righe saranno anch'esse di lunghezza 7, e la permutazione è definita dall'ordine alfabetico delle lettere della parola chiave. In questo caso l'ordine sarebbe "7-2-6-5-3-4-1" perché l'ordine alfabetico delle lettere di VETRINA è A-E-I-N-R-T-V, e le loro posizioni sono quindi A=1, E=2, I=3, N=4, R=5, T=6 e V=7, per cui V-E-T-R-I-N-A corrisponde proprio a 7-2-6-5-3-4-1.

Nei cifrari a trasposizione colonnare regolari le posizioni vuote alla fine dell'ultima riga vengono riempite con caratteri casuali, mentre in quelli irregolari sono lasciati bianchi. Alla fine, il messaggio è letto sulle colonne secondo l'ordine specificato dalla parola chiave. Ad esempio, supponendo di usare la parola chiave VETRINA e il messaggio PIANTARE IL CAMPO DIETRO LA COLLINA, in una trasposizione colonnare regolare avremmo una griglia così composta:

V E T R I N A
- - - - - - - 
7 2 6 5 3 4 1
- - - - - - - 
P I A N T A R
E I L C A M P
O D I E T R O
L A C O L L I
N A D V Y I Q

Con le ultime cinque lettere insignificanti (DVYIQ). Il testo cifrato è così letto:

RPOIQ IIDAA TATLY AMRLI NCEOV ALICD PEOLN

Nel caso di una trasposizione colonnare irregolare, invece, la griglia sarebbe così creata:

7 2 6 5 3 4 1
P I A N T A R
E I L C A M P
O D I E T R O
L A C O L L I
N A

E il messaggio cifrato sarebbe il seguente:

RPOII IDAAT ATLAM RLNCE OALIC PEOLN

Per decifrarlo, il destinatario risale alla lunghezza delle colonne dividendo la lunghezza del messaggio per quella della parola chiave. Poi può scrivere il messaggio riorganizzandolo in colonne e poi riordinare le colonne in base alla parola chiave.

I cifrari a trasposizione colonnare sono oggi usati solo come giochi enigmistici o per utilizzi dilettantistici: alcuni gruppi di scout, ad esempio, utilizzano un cifrario a trasposizione colonnare regolare per rendere illeggibili semplici comunicazioni^[2].

Trasposizione doppia

Una trasposizione colonnare singola sarebbe violabile indovinando la possibile lunghezza delle colonne e provando a scrivere il messaggio in esse (ma nell'ordine sbagliato, dato che la parola chiave non è ancora nota) e poi cercando possibili anagrammi. Per rendere questo tipo di cifrario più robusto si usa spesso una trasposizione doppia, che essenzialmente è una trasposizione colonnare applicata due volte. Si può utilizzare la stessa chiave per entrambe le trasposizioni, oppure si possono utilizzare due chiavi differenti.

Operando, ad esempio, sul risultato della precedente trasposizione colonnare irregolare, e applicando una seconda cifratura con una chiave differente, ad esempio PORTALE (da cui si ottiene la permutazione 5-4-6-7-1-3-2) otteniamo la seguente griglia: RPOII IDAAT ATLAM RLNCE OALIC PEOLN

5 4 6 7 1 3 2
R P O I I I D
A A T A T L A
M R L N C E O
A L I C P E O
L N

Da cui è facile calcolare il testo cifrato:

ITCPD AOOIL EEPAR LNRAM ALOTL IIANC

Impieghi bellici

Durante la prima guerra mondiale i militari tedeschi utilizzavano un cifrario a trasposizione colonnare doppia: il sistema era però regolarmente violato dall'esercito francese, che lo aveva battezzato Übchi: gli analisti transalpini recuperavano le nuove parole chiave nel giro di pochi giorni. Questi successi ebbero un così vasto risalto che fu addirittura pubblicato un articolo sul giornale Le Matin: dopo tale pubblicazione, i Tedeschi adottarono il 18 novembre 1914 un nuovo sistema di cifratura^[3].

Nella seconda guerra mondiale i cifrari a trasposizione colonnare doppia furono utilizzati dai gruppi di resistenza all'invasione tedesca olandesi e francesi (i maquis) e dai corpi di sabotaggio inglesi SOE (SOE), che operarono in clandestinità in buona parte dell'Europa^[4]. Questi cifrari furono utilizzati anche dai servizi strategici americani, che crearono un reparto simile al SOE britannico^[5], e come cifrario di emergenza dall'esercito e dalla marina tedeschi.

I cifrari a trasposizione doppia sono stati considerati, almeno fino all'avvento del cifrario VIC, tra i cifrari più complicati che un agente segreto poteva utilizzare per operare in condizioni di sicurezza precarie.

Trasposizione di Myszkowski

Una variante della trasposizione colonnare è la trasposizione di Myszkowski, così detta perché proposta nel 1902 da Émile Victor Théodore Myszkowski. Nelle altre trasposizioni, se nella parola chiave ci sono delle lettere ripetute, queste vengono sostituite da quelle che seguono nell'alfabeto: ad esempio, la parola chiave "PATATA" genera la permutazione numerica "4-1-5-2-6-3" (da "PATBUC"). Nella trasposizione di Myszkowski, invece, le lettere ripetute generano permutazioni identiche, per cui la parola chiave "PATATA" restituisce la permutazione "2-1-3-1-3-1".

Costruendo la griglia con la solita frase degli esempi precedenti si ottiene:

2 1 3 1 3 1
P I A N T A
R E I L C A
M P O D I E
T R O L A C
O L L I N A

Per ottenere il testo cifrato si prendono le colonne identificate da numeri unici e si trascrivono dall'alto in basso, mentre le colonne con numeri ripetuti sono trascritte per righe procedendo da sinistra a destra. Per cui dalla griglia precedente prima si opera sulle colonne "1" da sinistra a destra e dall'alto in basso, poi si trascrive la colonna "2" operando invece dall'alto in basso, infine si trascrivono le colonne "3" sempre da sinistra a destra e dall'alto in basso, ottenendo:

INAEL APDER LCLIA PRMTO ATICO IOALN

Trasposizione disturbata

Nella trasposizione disturbata alcune posizioni della griglia sono lasciate volutamente vuote e non sono usate quando la griglia viene riempita con le lettere del messaggio in chiaro. In questa maniera si va ad alterare la regolarità dei riempimenti e ciò rende il lavoro del crittanalista più difficile.

Griglie

Lo stesso argomento in dettaglio: Cifrario a griglia.

I cosiddetti cifrari a griglia sono un'altra forma dei cifrari a trasposizione: come si evince dal nome, essi utilizzano, invece che algoritmi matematici, vere e proprie maschere, in genere di carta, in cui sono ritagliate delle finestrelle. Questi cifrari possono produrre trasposizioni altamente irregolari in relazione al periodo specificato dalla dimensione della griglia ma richiedono che i destinatari dei messaggi conservino materialmente una chiave segreta. Le griglie comparvero per la prima volta nel 1550 e furono usate per lungo tempo; esse erano ancora impiegate per cifrare le corrispondenze militari durante i primi mesi della Prima Guerra Mondiale.

Investigazione e crittanalisi

Dato che la trasposizione non modifica la frequenza delle singole lettere, una trasposizione semplice può essere facilmente individuata con l'analisi delle frequenze. Se un testo cifrato manifesta una distribuzione delle frequenze molto simile a quella di un testo in chiaro, il più delle volte esso risulta proprio una trasposizione che può essere risolta semplicemente anagrammandolo: si prendono piccole parti del messaggio da posizioni casuali e si combinano insieme osservando se il testo ottenuto presenta la comparsa di porzioni che sembrano anagrammi di parole di senso compiuto, e poi si risolvono questi anagrammi. Una volta che sono stati risolti, questi anagrammi rivelano informazioni sulla regola utilizzata per la trasposizione e il metodo può essere conseguentemente esteso al resto del messaggio.

Le trasposizioni più semplici soffrono inoltre del fatto che parole chiave molto simili a quella utilizzata per la cifratura rivelano spesso lunghe porzioni di testo leggibile intervallato da sequenze di caratteri senza senso. La conseguenza è che tali cifrari risultano vulnerabili agli algoritmi ottimizzati per la ricerca dei dati, come gli algoritmi genetici.

Combinazioni

La trasposizione è spesso combinata con altre tecniche. Ad esempio, un semplice cifrario a sostituzione combinato con una trasposizione colonnare elimina le debolezze di entrambi gli schemi. Il rimpiazzo di simboli nel testo cifrato ad elevata frequenza con lettere del testo in chiaro ad elevata frequenza non rivela porzioni del testo in chiaro grazie proprio alla trasposizione. L'anagrammare di una trasposizione non funziona, invece, a causa della sostituzione.

La tecnica della combinazione risulta particolarmente potente se combinata con il frazionamento (vedi sotto). Uno svantaggio di questi schemi di cifratura sta nel fatto che diventano più laboriosi e suscettibili di errori rispetto ai cifrari più semplici.

Frazionamento

La trasposizione risulta particolarmente efficiente quando viene abbinata al frazionamento, cioè un passaggio preliminare che divide ogni simbolo del testo in chiaro in più simboli di testo cifrato. Ad esempio, l'alfabeto del testo in chiaro potrebbe essere trascritto in una griglia in cui ogni lettera del messaggio potrebbe essere rimpiazzata dalle sue coordinate (vedi il quadrato di Polibio). Un altro metodo di frazionamento è la semplice conversione del messaggio in codice Morse, con un simbolo per gli spazi, uno per i punti e uno per le linee.

Quando un tale messaggio frazionato viene trasposto, le sue singole lettere vengono ben separate nel messaggio ottenendo nel contempo la diffusione teorizzata da Claude E. Shannon: il cifrario bifido, il cifrario trifido, il cifrario ADFGVX e il cifrario di VIC sono tutti esempi di cifrari che combinano il frazionamento e la trasposizione.

Un'altra soluzione consiste nel rimpiazzare ogni lettera con la sua rappresentazione binaria, trasporre questa e poi convertire la nuova stringa binaria nel corrispondente carattere ASCII. Per rendere più difficile la violazione del cifrario è possibile effettuare più volte la conversione della stringa binaria prima di convertire il risultato in un carattere ASCII: molti cifrari a blocchi moderni si rifanno a questa idea applicando forme di trasposizione più complesse.

Note

1. Esempio di Union Route Cipher Archiviato il 1º maggio 2009 in Internet Archive.
2. I cifrari a trasposizione - Saggio pubblicato sul Tangram anno VII n° 19 (2008)
3. Kahn, pagg. 301-304.
4. Kahn, pagg. 535 e 539.
5. Kahn, pag. 539

Bibliografia

• Kahn, David. The Codebreakers: The Story of Secret Writing. Rev Sub. Scribner, 1996.

Voci correlate

• Cifrario a permutazione
• Cifrario a sostituzione
• Crittografia

Collegamenti esterni

• (EN) Gustavus J. Simmons, transposition cipher, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) route cipher, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia