Equivocations for transposition ciphers

In a transposition cipher the message sequence is subdivided into blocks of equal length and each block is shuffled according to a chosen key. To evaluate the performance of a transposition cipher we take a Shannon-theoretic standpoint and compute relevant equivocations. It is wellknown that transposition ciphers are strongly ideal for memoryless stationary sources (key and cryptogram are independent). We consider also message equivocation and key-appearance equivocation and do not assume that the length of the intercepted cryptogram is a multiple of the block-length. The index of coincidence of the source statistics is shown to be a relevant parameter, at least asymptotically.

---

Riassunto Il principio della trasposizione è uno dei più antichi in crittografia, ma non è obsoleto: i cifrari a trasposizione vengono adoperati come blocchi costitutivi di alcuni dei più autorevoli cifrari attualmente in uso, come il DES dell'IBM che è stato adottato dal National Bureau of Standards americano. Il messaggio in chiaro che si vuol cifrare viene spezzato in blocchi di ugual lunghezza e ciascun blocco viene «trasposto» (anagrammato) secondo una permutazione fissa e segreta (la chiave del cifrario). In questo lavoro le prestazioni dei cifrari a trasposizione vengono valutate dal punto di vista della teoria di Shannon, calcolando certe «equivocazioni» pertinenti: tali equivocazioni quantificano l'incertezza di una spia che abbia intercettato il crittogramma; dopo l'intercettazione le equivocazioni a priori si trasformano in equivocazioni a posteriori secondo un meccanismo di tipo bayesiano. Se la sorgente dei messaggi è data da un processo stocastico stazionario senza memoria, è ben noto che per quanto concerne la chiave le equivocazioni a priori e a posteriori coincidono: i cifrari a trasposizione sono in questo caso «fortemente ideali».Noi consideriamo anche l'equivocazione sul messaggio e quella sulla «comparsa della chiave» (quest'ultima è significativa nel caso di «attacchi con testo in chiaro»). L'equivocazione sul messaggio si ottiene da quella sulla chiave, che è una costante indipendente dalla lunghezza del crittogramma intercettato, al modo seguente: si somma un contributo periodico che si annulla solo quando tale lunghezza è un multiplo della lunghezza di blocco, e si sottrae una correzione infinitesima (pari all'equivocazione sulla comparsa della chiave) la cui velocità di convergenza è asintoticamente determinata dall' «indice di coincidenza» della distribuzione di probabilità che regola la sorgente dei messaggi.

---

---

Questo lavoro è parte del programma di ricerca del GNIM-CNR. È incluso nel programma dell'International Symposium of Information Theory, Brighton (Inghilterra), giugno 1985.