Szachownica Polibiusza

Szachownica Polibiusza

Szachownica Polibiusza – rodzaj szyfru monoalfabetycznego wymyślony w starożytności przez greckiego historyka Polibiusza.

Szachownica klasyczna

Szyfr ten przypisuje każdej literze liczbę, według następującej tabeli:

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	I/J	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

Cyfry oznaczają położenie danej litery w tabeli – pierwszą cyfrą jest numer wiersza, a drugą – kolumny. Tak na przykład tekst:

ŚCIŚLE TAJNE

po zaszyfrowaniu (nie uwzględniając polskich znaków) przyjmuje postać:

43 13 24 43 31 15 44 11 24 33 15

Szachownica z rozwidlaniem

Klasyczna szachownica Polibiusza jest kwadratową tabelą, w której pierwszy wiersz zawiera współrzędne pionowe (kolumn), a pierwsza kolumna współrzędne poziome (wierszy). Metoda rozwidlania polega na dodaniu (jako drugiego od góry) wiersza bez współrzędnej poziomej. Do komórek tego wiersza wpisuje się słowo-klucz, które może zawierać najwyżej 8 liter. Pozostałe pola tego wiersza pozostawia się niewypełnione. Cyfry będące współrzędnymi pionowymi niewypełnionych komórek wpisuje się jako współrzędne poziome wierszy od trzeciego w dół. Powstaje tabela, która ma 10 kolumn, a liczba wierszy zależy od długości słowa-klucza. Następnie wypełnia się powstałą szachownicę pozostałymi literami alfabetu (z pominięciem liter z klucza) i ewentualnie innymi znakami. Można to robić najprościej – wierszami alfabetycznie lub według metody ustalonej między osobami, które będą używać tabeli. Liczba znaków, które można w zmieścić w takiej tabeli można opisać wzorem:
liczba znaków w tabeli = 10 × liczba wierszy ze współrzędnymi liczba znaków słowa-klucza.
Jak widać 8 znaków to logiczne maksimum długości klucza, ponieważ przy 9 powstaje tablica z liczbą pól mniejszą, niż długość najprostszego alfabetu.

Poniżej przykład szachownicy z rozwidleniem. Słowem-kluczem jest ESTONIA.

	1	2	3	4	5	6	7	8	9	0
	E	S	T	O	N	I	A
8	Ą	B	C	Ć	D	Ę	F	G	H	J
9	K	L	Ł	M	Ń	Ó	P	R	Ś	U
0	W	X	Y	Z	Ż	Ź	.	,	sp.	L/C

Jak widać zmieściły się w niej nie tylko polskie znaki, co umożliwia szyfrowanie tekstu bez ryzyka pomyłek-przejęzyczeń, ale także podstawowe znaki interpunkcyjne, a nawet kod dla spacji (sp.). Umieszczono w niej również znacznik L/C. Był on praktycznie standardowo stosowany przez agentów używających szachownicy, a oznaczał początek i koniec zapisu liczby. Osoba odszyfrowująca tekst po odczytaniu znaku L/C wiedziała, że następujące po nim cyfry nie są kodami liter, tylko elementami liczby. Dopiero następne pojawienie się znacznika L/C oznaczało powrót do zaszyfrowanych liter.

W procesie szyfrowania jako odpowiednik litery zawartej w słowie-kluczu podaje się pojedynczą cyfrę stojącą nad nią w pierwszym wierszu. Odpowiednikami pozostałych liter/znaków tekstu jawnego są współrzędne (wiersz-kolumna) pól szachownicy zawierających te znaki. Zaszyfrowany przy użyciu tej tabeli przykład:

ŚCIŚLE TAJNE

przyjmie postać:

99 83 6 99 92 1 09 3 7 80 5 1

Rozwidlenie szachownicy daje następujące korzyści.
1. W klasycznej szachownicy każdej literze tekstu jawnego odpowiadają dwie cyfry w tekście zaszyfrowanym. Rozwidlenie powoduje, że niektóre litery są zastępowane jedną cyfrą, co (po opuszczeniu spacji) znacznie utrudnia kryptoanalizę w oparciu o częstotliwość występowania znaków.
2. W klasycznej szachownicy kolumn i wierszy może być do 10, czyli można stworzyć tabelę zawierającą do 100 pól. Jednak jeżeli szachownica zawiera ich mniej, wiąże się to z rezygnacją z niektórych cyfr. Dla kryptoanalityka może to być wskazówka co do użytej metody szyfrowania. Przy zastosowaniu metody rozwidlenia można zmieniać liczbę pól szachownicy zmieniając długość słowa-klucza, ale w tekście zaszyfrowanym zawsze występują wszystkie cyfry od 0 do 9.
3. Przy użyciu odpowiedniego słowa-klucza można zmniejszyć wielkość tekstu zaszyfrowanego nawet o 30%. Jest to możliwe, jeżeli słowo-klucz będzie zawierało litery występujące najczęściej w języku, w jakim został napisany tekst jawny (w przykładzie wykorzystano słowo ESTONIA, które zawiera większość liter pojawiających się najczęściej w tekstach pisanych po polsku). Tekst ŚCIŚLE TAJNE zaszyfrowany klasyczną tabelą zawierał 22 znaki. Dzięki rozwidleniu mimo użycia polskich znaków i spacji tekst zaszyfrowany ma tylko 18 cyfr. Przy wysyłaniu zaszyfrowanych tekstów dzielono je na pięciocyfrowe grupy. Jeżeli ostatnia grupa była krótsza uzupełniano ją dowolnymi cyframi do pełnych pięciu. Po poddaniu takiej operacji (dla przejrzystości do uzupełnienia użyto tylko cyfry 9) tekst z tablicy podstawowej będzie się składał z 5 grup:
43132 44331 15441 12433 15999
a tekst zaszyfrowany tablicą z rozwidleniem – z czterech:
99836 99921 09378 05199

Idea ulepszenia szachownicy Polibiusza przez stworzenie wiersza tabeli bez współrzędnej bocznej pojawiła się jeszcze w XVI wieku ale popadła potem w zapomnienie i wróciła w szyfrach opracowywanych w I połowie XX wieku przez kryptologów radzieckich. Zachowując podstawowe zasady rozwidlania szachownicy modyfikowali ją albo przez skomplikowane zasady wypełniania pól tabeli znakami albo przez zmianę kolejności cyfr-współrzędnych w pierwszym wierszu. Szachownica z rozwidleniem była częścią trzech najsłynniejszych radzieckich szyfrów z połowy XX wieku: szyfru używanego przez Czerwoną Orkiestrę, szyfru Ramsaya i szyfru VIC – najdoskonalszego szyfru ręcznego w historii kryptologii.

Bibliografia

• David Kahn: Łamacze kodów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2004. ISBN 83-204-2746-0. Brak numerów stron w książce