Enigma, była jak na swoje czasy bardzo zaawansowaną maszyną szyfrującą. Bazowała ona na prostych podstawieniach, dodając do nich jeden drobny element – zmianę klucza, co pozwoliło na szyfrowanie które nie dało się złamać poprzez analizę statystyki poszczególnych znaków. Ta sama litera, w zależności od położenia w tekście szyfrowanym mogła być zakodowana jako dowolna z pozostałych liter. Osiągnięto to, poprzez zmianę podstawienia, ale na początek popatrzmy na stojącą za tym wszystkim matematykę.

Jeśli mamy zbiór N elementów, to na ile sposobów możemy te elementy ułożyć w kolejności? Popatrzmy na sprawę systematycznie. Jeśli zbiór nie ma żadnych elementów albo ma jeden element – to mamy tylko jedną możliwość ułożenia elementów w kolejności. Jeśli dołożymy drugi – to może on spocząć na dwóch miejscach – przed pierwszym albo za nim. Mamy dwie możliwości kolejności. A ile będzie przy trzech? Trzeci element możemy ustawić na początku, w środku albo na końcu a więc na trzy sposoby, ale tego do czego dostawiamy też są dwie możliwości. Mamy więc 1*2*3=6 różnych kolejności. Jeśli dołożymy czwarty? To oczywiste – liczbę ułożeń trzech elementów musimy pomnożyć przez 4. Ogólnie – jeśli zbiór ma N elementów – dopuszczalnych kolejności, albo jak mawiają matematycy – permutacji – jest N! – czyli 1*2*3*4*…*N. Dla dwudziestu sześciu liter liczba wszystkich uporządkować wynosi ponad 4*10²⁶.

Rozważmy zbiór wszystkich permutacji danego zbioru i przyjmijmy jedną z nich za naturalny porządek. Dla liter – jest to porządek alfabetyczny, dla liczb – rosnący. Każdą inną permutację możemy traktować jako przeszeregowanie owego porządku naturalnego – swego rodzaju – funkcję (różnowartościową, a więc odwracalną – co dość istotne dla szyfrów).

Zauważmy, że pojawia się możliwość składania permutacji, i w wyniku – dostajemy także permutację tego samego zbioru. Możemy także permutację przesuwać w prawo lub w lewo – i także otrzymamy w wyniku permutację tego samego zbioru.

Czy może nam to pomóc przy tworzeniu szyfru?

O tym za chwilę, teraz warto zauważyć, że jeśli potraktujemy permutację jak sposób szyfrowania – będziemy mogli zaszyfrować dowolną wiadomość poprzez podstawianie znaków. Ma to niestety swoje wady. Po pierwsze, trzeba przekazać klucz szyfrujący w postaci dokładnego opisu permutacji. Po drugie – statystyki występowania poszczególnych znaków są zachowane. Dlatego jeśli znamy język w jakim przekazywany jest komunikat – możemy kilka liter od razu przyporządkować a potem zgadywać i próbować.

Dobrze byłoby więc co jakiś czas zmieniać klucz, na przykład po każdym znaku. I jeszcze, żeby cały proces szyfrowania i deszyfrowania można było zautomatyzować, bo próba zapanowania nad ilością permutacji przyprawia o zawrót głowy.

Jeśli w typowym liczniku mechanicznym, który będzie zliczał zakodowane litery, każdy z bębnów byłby jakąś permutacją, a obrót bębna by ją rotował. Permutacje na poszczególnych bębnach składałyby się na tą – która byłaby kluczem kodowym dla kolejnej litery. Ponieważ kolejna permutacja zależy od ustawienia wszystkich kół licznika, każdą kolejną literę komunikatu będziemy kodować innym kluczem. Można nawet, dobierając odpowiednio permutacje, doprowadzić do sytuacji, w której kodowanie litery na każdej innej literze będzie równie prawdopodobne – i przekaz zakodowany – będzie wyglądał jak szum.

Dokładnie na takie zasadzie działała niemiecka Enigma. Kod początkowy ustawiano na kołach licznika, a potem wprowadzano literę po literze. Maszyny miały 4 i więcej bębny kodujące co pozwalało na ustawienie ponad pół miliona różnych kluczy.

To znacznie mniej niż wszystkich możliwych kodowań. To dlatego, że zastosowano w maszynie szyfrującej kilka specjalnych permutacji które dowolnie złożone tworzyło szyfr różnowartościowy i symetryczny. To znaczy, że litery są zamieniane parami i aby rozszyfrować wiadomość wystarczy użyć tego samego klucza.

Obecnie ten sposób kodowania nie jest specjalnym problemem. Współczesne komputery potrafią wykonywać miliardy operacji na sekundę, i zgadnięcie klucza nie stanowi problemu. Po prostu trzeba wykorzystać wszystkie kombinacje i sprawdzić kiedy wychodzi coś sensownego. Oczywiście musimy znać system kodowy – owe bazowe permutacje z których tworzymy klucz szyfru. Bo sprawdzenie wszystkich permutacji w ogóle, raczej nie jest możliwe ze względu na brak czasu. Przypomnijmy – liczba wszystkich permutacji – jest rzędu 10²⁶. To przy miliardzie sprawdzeń na sekundę – daje czas 10¹⁷ sekund – to mniej więcej 10¹⁰ lat. Trochę długo.

Zastosowanie permutacji do szyfrowania metodami podobnymi do Enigmy – doprowadziły do rozwoju całej gałęzi matematyki zajmującej się przestrzeniami permutacji