Storia della crittografiaCifrari monoalfabeticiCifrari polialfabetici
Liste involutorie o reciproche
Atbash

Nel gergo crittografico si chiama lista involutoria o reciproca una funzione simmetrica di un alfabeto A su se stesso, tale cioè che se ad una lettera c1 corrisponde la lettera c2, allora a c2 deve corrispondere c1.

Un modo semplice per ottenere una lista involutoria è quello di dividere l'alfabeto in due sottoinsiemi di ugual numero di lettere e quindi scrivere le due metà una sotto l'altra disordinando la seconda (disordinare la prima non aggiunge nulla al numero di coppie possibili, e quindi è inutile!); in questo caso si parla di lista intervertita.

Ecco un esempio semplice ottenuto spezzando in due l'alfabeto internazionale di 26 lettere(*) (dove A si cifra con N, N si cifra con A, B con O, O con B e così via):

ABCDEFGHIJKLM NOPQRSTUVWXYZ

o meglio ancora con due liste casuali (la prima è in ordine alfabetico per quanto detto sopra):

ADEFHKMNQRTVX ZJCGIUPBYWLOS

Usando la notazione matematica la lista si riduce all'insieme di tredici coppie:

$ \{ (A, Z), (D, J), (E, C), (F, G), (H, I), (K, U), (M, P), (N, B), (Q, Y), (R, W), (T, L), (V, O), (X, S) \}$

Per evitare una lista disordinata e difficile da memorizzare si possono (vedi p.es. le cifre di G. B. Bellaso) generare liste involutorie partendo da una parola chiave scritta alternativamente all'inizio delle due righe, saltando eventuali lettere ripetute; quindi si scriveranno ordinatamente le rimanenti lettere dell'alfabeto; per esempio usando come parola chiave VENEZIA:

VNIBCDFGHJKLM EZAOPQRSTUWXY

Si tratta di un espediente comodo a livello operativo, ma che diminuisce di molto la segretezza della lista essendo ancora in parte ordinata e basata su una singola parola che deve essere difficile da immaginare; a meno di non usare una parola chiave contenente tutte o quasi tutte le lettere. Vale sempre la regola: tanto più lunga la parola chiave, tanto maggiore la sicurezza.

Crittograficamente

Liste involutorie sono state usate da diversi cifrari sia monoalfabetici come l'antichissimo Atbash, sia polialfabetici, dove questo metodo è appunto utile per generare molte liste alfabetiche, a partire dalle cifre del Bellaso, e dalla tavola Della Porta e fino alla ben nota macchina Enigma.

Una caratteristica, che può essere vista come un pregio, è che così il metodo di cifratura coincide con quello di decifratura. Tale era appunto la macchina Enigma, cifrante e decifrante allo stesso tempo.

Matematicamente

Matematicamente usare liste involutorie introduce un vincolo che riduce di molto il numero di liste possibili. Ma di quanto? Possiamo calcolarlo in due modi:

  1. Si sceglie una partizione dell'alfabeto di $2n$ lettere, che equivale a scegliere una combinazione di $n$ lettere scelte da $2n$ che in tutto sono $ 2n(2n-1)(2n-2) ...(n+1) = \frac{(2n)!}{n! \times n!}$; poi per ogni lettera della prima metà si deve sceglierne una delle $n$ rimanenti quindi in totale $n!$; in totale quindi $\frac{(2n)!}{n!}$. Procedendo in questo modo però si sono considerate coppie ordinate di lettere, mentre in realtà l'ordine non ha importanza. Se A cifra N, allora N cifra A. Quindi occorre dimezzare il risultato per n volte, ovverosia per $2^n$. In definitiva il risultato è: $$ \frac{(2n)!}{2^n \times n!} $$
  2. Si comincia dalla prima lettera A, una sola possibilità, e si sceglie la sua cifra tra le $2n - 1$ rimanenti. Quindi si scende la seconda lettera disponibile, la B a meno che non sia stata scelta come cifra della A, ma non importa, anche qui c'è una sola possibilità e per questa va scelta una cifra tra le $2n-3$ lettere rimanenti. In definitiva si ottiene che il numero di liste involutorie possibili è un doppio fattoriale: $$ (2n-1)!! = (2n-1)(2n-3) ... $$ Risultato diverso? No! Infatti se si esplicita il doppio fattoriale come il fattoriale $(2n)!$ diviso per i numeri pari $ (2n)(2n-2) ...$ e cioè, raggruppando diversamente i fattori, per $ 2^n n(n-1) ... = 2^n n!$ si ottiene: $$ \frac{(2n)!}{2^n \times n!} $$ che coincide con la precedente.

Nel caso presente con $n=13$ si ha: $ \frac{26!}{2^{11} \times 11!} = 4,93 10^{15}$ numero comunque enorme, anche se circa cento miliardi di volte più piccolo di $26! = 4,03 \times 10^{26}$ .


Riferimenti bibliografici
X Naturalmente è necessario che il numero delle lettere dell'alfabeto sia pari, altrimenti avanzerebbe sempre una lettera che dovrebbe cifrarsi con se stessa.