Imitation Game - Tesina

The imitation game

Dalla disfatta della macchina Enigma al concetto di codice

Daniele Gatti

Di matematica

Il funzionamento della macchina Enigma

Introduzione al calcolo combinatorio

Il numero dei rotori – Disposizioni semplici

La posizione dei rotori – Disposizioni con ripetizione

Il pannello di commutazione – Combinazioni semplici

Il risultato finale

Cos’è Enigma…

• È una macchina utilizzata per cifrare e decifrare i messaggi in codice
• Fu utilizzata a partire dal 1924 dall’esercito tedesco per cifrare le proprie comunicazioni

…e come funziona

Pannello di

Pannello di

Tastiera commutazi Rotori Riflettore

Tastiera commutazi Rotori Riflettore

one

one Pannello di

Pannello di

Pannello

Pannello commutazi

commutazi Rotori

Rotori

luminoso

luminoso one

one Pannello di

Pannello di

Pannello commutazi

commutazi Rotori

Rotori

luminoso

luminoso one

one

Quante sono le possibili impostazioni di Enigma?

Le possibili impostazioni dipendono da tre fattori:

• Il numero dei rotori
• La posizione iniziale dei rotori
• La configurazione del pannello di commutazione

Il calcolo combinatorio

Per questo tipo di operazione è necessario l’utilizzo del calcolo combinatorio: esso stabilisce il numero totale dei raggruppamenti che si possono formare con gli n elementi di un insieme

Il numero dei rotori

Le macchine utilizzate dall’esercito tedesco avevano tre dischi rotanti che potevano essere estratti e cambiati. C’erano in totale cinque rotori tra cui sceglierne tre.

Il numero di modi possibili per posizionare i rotori è dunque una disposizione semplice:

3 !

� = =60

5,3 (5 −3)!

Le disposizioni semplici

Le disposizioni semplici di n elementi distinti di classe k (con k ≤ n) sono tutti i gruppi di k elementi scelti fra gli n, che differiscono per

� !

� =

� ,� �)!

(� − almeno un elemento o per l’ordine degli elementi

La posizione dei rotori

Una volta scelto l’ordine dei rotori, quante sono le possibili posizioni iniziali? Poiché ci sono 26 lettere nell’alfabeto, ci sono 26 possibili posizioni iniziali per ciascun rotore. Il calcolo è dato dalla disposizione con ripetizione:

� 3

� =26 =17.576

26,3

Le disposizioni con ripetizione

Le disposizioni con ripetizione di n oggetti distinti di classe k sono tutti i gruppi di k elementi, anche ripetuti, scelti fra gli n, che differiscono

� �

� =�

� ,� per almeno un elemento o per l’ordine degli elementi

Il pannello di commutazione

Sul pannello di commutazione erano inseriti 10 cavi che collegavano fra loro le lettere a 2 a 2. Ci sono modi di scegliere una coppia di lettere per il primo cavo, modi per il secondo… Il risultato di ciò è:

ma ogni cavo può essere sostituito con un altro, per cui bisogna dividere per i 10! modi di permutare tra loro i cavi:

26 !

10

(2 )

6!

26 ! =150.738.274 .937.250

10

(2 )

6! 10!

Le combinazioni semplici

Le combinazioni semplici di n elementi distinti di classe k (con k ≤ n) sono tutti i gruppi di k elementi scelti fra gli n, che differiscono per

� !

( )

�

� = = almeno un elemento (ma non l’ordine)

�, � ( )

� �! � −� !

Il risultato finale

Eseguendo il prodotto dei fattori trovati finora, troviamo che il numero totale di possibili