Bozza in revisione: il testo non è ancora stato approvato.

La matematica di Enigma

Ogni componente di Enigma fa la stessa cosa: riceve una lettera e ne restituisce un’altra, senza mai mandare due lettere diverse nella stessa. In matematica una regola di questo tipo si chiama permutazione dell’alfabeto. Con poche idee sulle permutazioni si dimostrano, una volta per tutte, le due proprietà che le lezioni precedenti hanno visto su un modello e su qualche esempio: Enigma è reciproca, e non cifra mai una lettera in sé stessa. Sono le idee con cui Marian Rejewski, matematico del servizio cifra polacco, alla fine del 1932 ricostruì il cablaggio dei rotori militari.

Le permutazioni

Una permutazione si può scrivere come una tabella a due righe: sopra le lettere che entrano, sotto quelle che escono. Per il rotore I in posizione A:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
EKMFLGDQVZNTOWYHXUSPAIBRCJ

La A va in E, la B in K, la C in M, e così via. Le permutazioni possibili delle 26 lettere sono $26! = 26 \times 25 \times \cdots \times 1$, circa $4{,}03 \times 10^{26}$.

C’è un modo più compatto di scriverle. Si parte da una lettera e la si segue: nel rotore I la A va in E, la E in L, la L in T, e dopo dieci passi si torna alla A. Si ottiene un ciclo, che si scrive fra parentesi. Ogni permutazione si scompone in cicli che non hanno lettere in comune; per il rotore I:

(AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S)

La S forma un ciclo da sola: è un punto fisso, una lettera che il rotore lascia com’è. Le lunghezze dei cicli, qui dieci, quattro, quattro, tre, due, due e uno, formano la struttura in cicli della permutazione.

Composizione e inversa

Il segnale attraversa i componenti uno dopo l’altro, quindi la sostituzione complessiva è la composizione delle singole permutazioni. La scriviamo come le funzioni, da destra a sinistra: $YX$ vuol dire «prima $X$, poi $Y$». L’ordine conta. Se $X$ scambia la A con la B e $Y$ manda la A in B, la B in C e la C in A, allora con $YX$ la A va in C, mentre con $XY$ la A torna in A.

L’inversa $X^{-1}$ è la permutazione che annulla $X$: si ottiene leggendo la tabella dal basso verso l’alto, e $X^{-1}X$ lascia ogni lettera al suo posto. È l’identità, che indichiamo con $\mathrm{id}$. Al ritorno dal riflettore la corrente attraversa i rotori nel verso opposto, quindi subisce le loro inverse.

Il rotore che gira: il coniugio

Quando un rotore avanza, il cablaggio resta lo stesso ma si sposta rispetto alla carcassa, e con lui si spostano i cicli.

Il ciclo (AELTPHQXRU) diventa (DKSOGPWQTZ), cioè (ZDKSOGPWQT) scritto a partire da un’altra lettera: ogni lettera è andata un posto indietro, e la lunghezza è rimasta dieci. Lo stesso vale per tutti i cicli e in tutte le posizioni: le lettere cambiano, le lunghezze restano dieci, quattro, quattro, tre, due, due e uno.

Chiamiamo $\rho$ lo spostamento di un posto, che manda la A in B, la B in C e la Z in A. Un rotore con cablaggio $R$, spostato di $k$ posti, opera la permutazione

cioè prima sposta i contatti di $k$ posti, poi attraversa il cablaggio, infine torna indietro di $k$. Una permutazione della forma $T^{-1} X T$ si dice coniugata di $X$, e le coniugate hanno sempre la stessa struttura in cicli: $T$ cambia il nome delle lettere, non la lunghezza dei cicli. Nel rotore che gira $T = \rho^{k}$, e il nuovo nome di ogni lettera è la lettera $k$ posti più indietro.

Rejewski si servì di questa proprietà per separare i rotori dal pannello a spine. Dai messaggi di un giorno ricavava permutazioni i cui cicli avevano lunghezze che dipendevano dalla posizione dei rotori e non dai cavi del pannello, che cambiavano solo i nomi delle lettere. Come costruì quelle permutazioni lo racconta la lezione Rejewski e la teoria dei cicli.

Involuzioni e reciprocità

Il riflettore scambia le lettere a coppie, quindi applicarlo due volte riporta ogni lettera al suo posto: $U^2 = \mathrm{id}$, cioè $U = U^{-1}$. Una permutazione così si chiama involuzione. Il riflettore B è fatto di 13 cicli di lunghezza due, senza punti fissi:

(AY) (BR) (CU) (DH) (EQ) (FS) (GL) (IP) (JX) (KN) (MO) (TZ) (VW)

Anche il pannello a spine con i cavi normali è un’involuzione, ma con punti fissi: le lettere senza cavo.

Chiamiamo $P$ il pannello e $R$ il tratto che va dalla ruota d’ingresso al riflettore, rotori compresi. Con la macchina ferma in una certa posizione, la lettera accesa è data da

cioè $E$ è coniugata di $U$ con $T = RP$. Le coppie della macchina, nella lezione sul riflettore, erano le coppie del riflettore viste attraverso i rotori: ora sono le coppie di $U$ rinominate da $RP$. Ne seguono le due proprietà. La prima è la reciprocità:

La seconda è che nessuna lettera si cifra in sé stessa: $E$ ha la stessa struttura in cicli di $U$, quindi 13 scambi e nessun punto fisso. I due ragionamenti non usano il cablaggio dei rotori, e nemmeno il fatto che $P$ sia un’involuzione: valgono anche con l’Uhr, che all’andata opera una permutazione e al ritorno la sua inversa.