Tesi Crittografia - Macchine cifranti giapponesi

Università degli Studi di Brescia

Dipartimento di Ingegneria dell'Informazione

Corso di Laurea in Ingegneria Informatica

RELAZIONE FINALE

La Macchina Cifrante Purple

Laureando:Nicolas Vermi

Matricola:705524

Relatore:Prof. Luca Giuzzi

Anno Accademico 2016/2017

1.3 Il disco cifrante di Alberti

In crittografia il disco cifrante di Leon Battista Alberti, descritto nel De cifris intorno al 1467, è il primo sistema di cifratura polialfabetica. L’apparecchio si compone di due dischi concentrici, rotanti uno rispetto all’altro, contenenti un alfabeto ordinato per il testo in chiaro e un alfabeto disordinato per il testo cifrato. Permette la sostituzione polialfabetica con periodo irregolare. Lo scorrimento degli alfabeti avviene per mezzo di lettere chiave inserite nel corpo del crittogramma. I quattro numeri possono anche servire per sopracifrare 336 frasi di codice. Ci sono tre metodi di cifratura proposti dall’Alberti nel suo trattato e questi sono più i sofisticati e sicuri:

• Mittente e destinatario concordano una lettera minuscola (esempio k) come chiave segreta; il mittente ruota il disco mobile fino a portare k sotto una maiuscola (esempio B) che viene scritta come prima lettera del cifrato, dopo di che si cifrano alcune lettere con la lista risultante, poi si ruota il disco interno a caso di alcune posizioni, ottenendo una nuova lista. Il cambio di lista viene segnalato scrivendo la maiuscola sotto la quale si trova ora la k; e così via ad ogni cambiamento di lista.

Figura 1.1: Disco di Alberti

Esempio: volendo cifrare il messaggio

"INVIARE RINFORZI DOMANI"

con il disco interattivo qui a sopra, si inseriscono a casaccio alcune nulle, poi si cifra cambiando lista, sempre a caso, 3 volte. Quindi aggiungendo le nulle abbiamo:

INVIA RE2R1NF10 RZID 30MANI

e poi cifrando:

BegchycoLciopclcaPpmly1Zlhcsla

La decifratura procede a rovescio: il destinatario legge a inizio cifrato B, porta k sotto B e decifra con questa lista fino alla prossima maiuscola, in questo esempio L; allora porta k sotto L decifra i seguenti caratteri secondo la nuova lista fino alla prossima maiuscola e così via. La segretezza si basa quindi sui dischi dei quali i due corrispondenti devono possedere due copie identiche e sulla lettera minuscola concordata.

• Il secondo metodo è un’evoluzione del primo in quanto le lettere maiuscole costituiscono un aiuto anche per il nemico, perciò per aumentare la sicurezza Alberti suggerisce di fissare come chiave una maiuscola (esempio D) e di scrivere a inizio messaggio la minuscola corrispondente (esempio k) e di usare poi le quattro cifre non più come nulle ma per segnalare il cambio di alfabeto; la lettera minuscola corrispondente al numero sarà la nuova chiave e la si porterà sotto B;

macchina RED, utilizzava un semi-rotore, importato dal crittografo svedese Arvid G. Damm, che utilizzava una tecnica più rozza, rispetto al metodo proposto da Enigma, per la criptazione e la creazione delle corrispondenze tra input ed output. In questo meccanismo, vengono sistemati 26

Figura 2.1: Schema macchina cifrante RED

collegamenti, strutturati a coppie, uno situato sulla faccia sinistra del rotore, l'altro collegato sulla faccia destra del rotore. L'OCP evidenziato in figura, è il link dedicato alla creazione dell'output, direttamente connesso al rotore e dove il contatto in ingresso è rimpiazzato da quello che in figura è chiamato Slip ring, che costituisce l'interfaccia rotante, situato lungo un’asta attaccato al corpo del rotore. Ogni lettera in ingresso è collegata ai 26 anelli. Il meccanismo prevedeva la rotazione di questi anelli e il movimento dell'asta ad esso collegata. Tale tipo di collegamento implica che ogni lettera è sempre l'opposto della corrispondente lettera appartenente alla faccia di sinistra del rotore, qualunque sia la posizione del rotore.

Figura 2.2: Rotore RED

In figura vediamo come il processo di cifratura della lettera in chiaro Y, venga effettuato durante

Capitolo 3

Purple Cipher Machine

3.1 Introduzione

Nel dicembre 1938 venne intercettato e decifrato un messaggio cifrato con la RED che autorizzava a mettere in servizio un nuovo tipo di macchine cifratici di 'TIPO B', che gli americani poi chiamarono Purple, le quali dovevano sostituire le RED per la decifrazione dei messaggi tra le varie ambasciate giapponesi nel mondo. La purple entrò effettivamente in gioco il 20 febbraio 1939. La purple cipher machine costituisce un'evoluzione ben più sofisticata della macchina RED. Il nome è derivato dal colore dei contenitori usati per contenere il cifratore. I giapponesi usarono questo tipo di macchinario per criptare tutte le conversazioni diplomatiche fino alla fine della guerra. A differenza di Enigma, della Purple non vennero ritrovati esemplari e per la sua decriptazione ci si dovette affidare unicamente alla crittoanalisi.

Figura 3.1: Parte della macchina Purple ricostruita dagli americani

La macchina Purple era un dispositivo a sostituzione, composto da 2 macchine da scrivere (una per l'input e una per l'output) in cui veniva sostituito ogni testo in chiaro con un testo cifrato. La

3.3 Indice di coincidenza di Friedman

A questo punto sembra che decriptare un messaggio purple sia una cosa da nulla, ma tutto ciò si basa un'ipotesi fondamentale, ovvero quella di conoscere la lingua in cui è stato scritto il messaggio. Ma come capire qual è la lingua del plaintext? Ora descriveremo un metodo per farlo, questo fu sviluppato da William Friedman per analizzare crittosistemi con multipelci sostituzioni. Noi abbiamo un messaggio y ∈ Aⁿ di m lettere da un alfabeto A così c = #A lettere. Ogni lettera e ∈ A ricorre un numero t_a di volte in y, tale che ∑_a∈A t_a = n. Nota che in questo caso non è la prima lettera dell'alfabeto, ma una variabile arbitraria. L'indice di coincidenza c(y) di y è la probabilità con cui 2 lettere in y sono uguali. Ci sono t_a(t_a-1)/2 paia di posizioni in y con la stessa lettera a ∈ A, e n(n-1)/2 paia di posizioni in y. Così

c(y) = ∑_a∈A t_a(t_a-1)/k² = ∑_a∈A t_a(t_a-1)/n(n-1)

In altre parole ci sono

n(n-1)/2

combinazioni in y. Se noi consideriamo y: 1, Idols, n λ come una funzione hash. Noi adesso cerchiamo una situazione dove y é random o prodotto dal cifrario di Vigenere, e cercheremo una notevole differenza tra i valori di c in questi due casi. Quando y é random cn é grande abbastanza noi abbiamo

t_a ≈ n/c

per ogni lettera a. Allora

c(y) = ∑_a∈A t_a(t_a-1)/n(n-1) ≈ n/c . n/c = n/c = 1/n/c ≈ 1/c = c_rand

Questo é il più semplice caso di ripetizioni, dove x = a é un monogramma di lunghezza l = 1. Se y é generato con la frequenza p_a per ogni lettera a ∈ A di ogni lingua, allora f_a ≈ np_a, e cosi

c(y) ≈ ∑_a∈A np_a(np_a 1)/n(n 1) ≈ ∑_a∈A p_a(p_a - 1/p_a 1) ≈ ∑_a∈A p²_a

Quest'ultimo valore dipende solamente dalla lingua, e una semplice sostituzione non cambia questo valore. Ora assumiamo che y é il testo cifrato di un plainText inglese: x = (x₀, ..., x_n - 1). Non conosciamo ne m ne le sostituzioni, le y_k = y_n in y sono di 2 tipi: generate dalla stessa permutazione, come y_k = π_i(x_k) = x_k per qualunque i < n con π_k = π_i, ł ∈ k. in Z_mc oppure 2 diverse permutazioni, y_k = π_i(x_k) = π_i(x) con i ≠ j é i/b ≠ i/km/m. Per il primo tipo noi consideriamo alcune sostituzioni π_i con i < m. Ci sono circa n/m lettere cifrate con π é circa

n/m (n/m -1)/2 = t_(n/m-m)² m

paia di lettere cifrate sotto π_i. Supponendo che la probabilità di ripetizione é c_Eng e n siano le sostituzioni, noi ci aspettiamo

m ⋅ c_Eng t_(n/m-m) n/2m²

ripetizioni del primo tipo. Mentre ci sono invece