Szyfry przestawieniowe

Marek Grajek KURS KRYPTOLOGII

Podstawienia bigraficzne - szyfr Playfaira

Wszystkie szyfry, z którymi zapoznaliśmy się do tej pory, miały wspólną
właściwość: należały do rodziny podstawień monograficznych. Innymi słowy, jeden

znak tekstu jawnego był przekształcany na jeden znak szyfrogramu. Na
zakończenie kursu poznamy najbardziej znanego reprezentanta rodziny szyfrów

bigraficznych - szyfr Playfaira.

Podstawienia bigraficzne mają starą, sięgającą starożytności historię. Autorem

najwcześniejszego podstawienia bigraficznego, o którym wiadomość dotarła do
naszych czasów, był Grek, Polibiusz, który żył w II wieku p.n.e. Pisząc o

zagadnieniach wojskowych usiłował nie tyle zaprojektować szyfr, ile rozwiązać
problem porozumiewania się pomiędzy oddziałami wojska oddalonymi od siebie na

tyle, by głos nie docierał, jednak widzącymi się nawzajem. Zaproponował, by
utworzyć tabelę o rozmiarach 5 x 5 znaków, a znakom alfabetu greckiego wpisanym

w jej komórkach przyporządkować odpowiedniki liczbowe w postaci pary (numer
wiersza, numer kolumny), jak na rysunku poniżej.

Polibiusz (ok. 200-118 p.Chr.) oraz tablica Polibiusza

Dzięki temu można było zapisać przykładowo literę π jako parę (4, 1) i przesłać

ją na odległość np. podnosząc cztery flagi w prawej ręce i jedną w lewej.
Wystarczy jednak zamienić alfabetyczne uporządkowanie znaków w tabeli na inny,

jednoznaczny porządek, byśmy otrzymali odmianę szyfru.

Jeden z najbardziej znanych i popularnych szyfrów biograficznych w historii,

szyfr Playfaira, wziął swoją nazwę od lorda Playfaira, który jednak nie był
jego wynalazcą. W istocie użycie szyfru zaproponował po raz pierwszy w 1854

roku Charles Wheatstone, prezentując swoją koncepcję zaprzyjaźnionemu lordowi.
Wkrótce potem lord Playfair przedstawił koncepcję szyfru w trakcie spotkania, w

którym uczestniczyli m.in. małżonek królowej Wiktorii, książę Albert, oraz lord
Palmerstone, przyszły premier Wielkiej Brytanii. Z ich zachowanej

korespondencji wiemy, że kiedy Palmerstone wybrał się w podróż do Irlandii,
wymieniał z pozostałymi uczestnikami spotkania listy zaszyfrowane nowym

systemem. W ten sposób praktycznie potwierdzono, że szyfr wynaleziony przez
Wheatstone’a (choć zapamiętany pod nazwiskiem Playfaira) jest łatwy zarówno do

opanowania, jak i użycia. Dzięki tym swoim cechom szyfr Playfaira stał się

©ŁAMACZE SZYFRÓW

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

jednym z najpopularniejszych systemów szyfrowania zarówno w drugiej połowie
XIX, jak i w pierwszej połowie XX wieku. Był używany rutynowo przez brytyjskie

oddziały w czasie wojny krymskiej oraz w okopach I i II wojny światowej. W
jednym z historycznych epizodów pozwolił uratować życie człowieka, którego

przeznaczeniem było stać się jednym z najbardziej popularnych prezydentów USA.
Ale zanim opowiemy ten fragment jego życia, musimy przedstawić sam szyfr.

Lord Playfair i Charles Wheatstone

Podobnie jak system Polibiusza szyfr Playfaira wykorzystuje tablicę o
rozmiarach 5 x 5 znaków. W tablicy zapisuje się 25 znaków alfabetu łacińskiego,

w którym utożsamia się znaki I oraz J. Tabela, do której wygenerowania użyto
słowa kluczowego PREZYDENT, przyjmuje postać:

PREZY
DNTAB
CFGHI
KLMOQ
SUVWX

Tekst jawny należy przed zaszyfrowaniem spreparować usuwając zeń wszelkie znaki

niewystępujące w tabeli (np. literując liczby i znaki interpunkcyjne oraz
zastępując literę

znakiem

), oddzielając wszystkie wystąpienia tej samej

litery np. znakiem X oraz dzieląc tekst na pary znaków (dopełniając tekst

ślepym znakiem na końcu w przypadku nieparzystej liczby liter). Dla przykładu,
tekst jawny

FOLLOWFIRSTBATALLION.

przyjmie po preparacji (kropkę zastąpiono angielskim słowem

PERIOD

) postać

FO LX LO WF IR ST BA TA LX LI ON PE RI OD

©ŁAMACZE SZYFRÓW

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

Szyfrowaniu podlegają pary znaków, a proces szyfrowania opisany jest przez trzy
proste reguły:

1. Jeżeli oba znaki w parze tekstu jawnego leżą w tej samej kolumnie tabeli,

są w szyfrogramie zastępowane przez znaki leżące bezpośrednio poniżej

(przy czym za znak leżący bezpośrednio poniżej ostatniego znaku w kolumnie
uważa się jej pierwszy znak).

2. Jeżeli oba znaki w parze leżą w tym samym wierszu tabeli, są zastępowane

przez znaki leżące bezpośrednio po prawej (przy czym za znak leżący

bezpośrednio po prawej ostatniego znaku w wierszu uważa się jego pierwszy
znak). Np. para znaków PE w tekście jawnym powyżej jest zastępowana parą

RZ.

3. Jeżeli znaki w parze leżą w różnych wierszach i kolumnach, są zastępowane

przez znaki znajdujące się w przeciwległych wierzchołkach kwadratu
wyznaczonego przez znaki tekstu jawnego, począwszy od znaku znajdującego

się w wierszu zawierającym pierwszy znak pary tekstu jawnego. Np. para
znaków FO w tekście jawnym powyżej jest zastępowana parą HL.

Po zastosowaniu opisanych reguł wobec przykładowego tekstu jawnego i tabeli

klucza otrzymujemy szyfrogram:

HL QU MQ UH FY VD DB AB QU QF LA RZ YF KA

Przy deszyfrowaniu tekstu stosujemy odwrotność procedury, tj. bierzemy znaki

stojące powyżej, po lewej i po przeciwnej przekątnej prostokąta od znaków
reprezentujących pary szyfrogramu. Po wprowadzeniu do teorii możemy powrócić do

historycznego przykładu. W czasie II wojny światowej Australijczycy instalowali
na wyspach Pacyfiku, także opanowanych przez armię japońską, tzw. obserwatorów

wybrzeży (ang. coast watchers), których zadaniem było informowanie przez radio
o wydarzeniach na morzu przylegającym do wyspy. 2 sierpnia 1943 roku por.

Arthur Evans, rezydujący na wyspie Kolombangara w archipelagu Wysp Salomona,
odebrał depeszę o treści:

KXIEYUREBEEWEHEWRYTUHEYFSKREHEGOYFIWUQUTQYOMUQYCAIPOBOQTZKNOBOTFRBDS
VYWZABYCDOBNQLNSSZTURZOKZVYOUZSKRE

Por. Evans używał w łączności z dowództwem szyfru Playfaira z kluczem
generowanym w oparciu o frazę

ROYALNEWZEALANDNAVY

. Znajomość funkcjonowania

szyfru uprawnia nas do postawienia w tym miejscu pierwszego zadania w trakcie

dzisiejszego wykładu: jaki był numer okrętu (łodzi patrolowej), o której los
niepokoiło się dowództwo (należy odpowiedzieć dokładną frazą tekstu jawnego,

określającą numer jednostki)?

Por. Evans dowiedział się wkrótce, że załoga jednostki pod dowództwem por.
Johna Kennedy’ego, przyszłego prezydenta USA, wylądowała po zniszczeniu swojej

jednostki na Wyspie Budyniu Śliwkowego (Plumpudding Island), skąd po kilku
dniach przeniosła się na wyspę Gross, gdzie została odnaleziona przez dwóch

tubylców, którzy powiadomili o jej losach Australijczyków. Cała korespondencja
związana z poszukiwaniem zaginionej załogi, a potem organizacją ekspedycji

ratunkowej, odbywała się drogą radiową, a depesze były szyfrowane systemem
Playfaira. Na szczęście dla przyszłego prezydenta japońscy kryptoanalitycy nie

wykazali się kunsztem w swoim fachu i nie wykryli, gdzie ukrywają się
rozbitkowie. Spróbujmy wspólnie ocenić, czy depesze wymieniane pomiędzy

©ŁAMACZE SZYFRÓW

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

obserwatorami wybrzeża i ich odległym dowództwem rzeczywiście były nie do
złamania... Oto jedna z depesz:

XE LW AO HW UW YZ MW IH OM NE OB TF WM IE IP IE AN WL EO TO KN EB FC
MF EX BL OL UC GR PI HB KY AO SB PM BN AS CW OS YB SN VN KC EL IL UE
UM LU HX BY BT NK AL TB OE MP KE EI HB KG CW FV EK BA

Szyfrogram w systemie Playfaira ma następujące własności:

1. Zawsze zawiera parzystą liczbę liter.
2. Jest szyfrem podstawieniowym, w którego alfabecie szyfrowym występuje

jedynie 25 różnych znaków.

3. Możliwe powtórzenia występują w szyfrogramach w regularnych odstępach o

długości wymiernej w parzystej liczbie znaków. Z reguły powtarzające się
fragmenty także są parzystej długości.

4. Występują liczne odwrócenia bigramów, np. ER - RE, TH - HT itd.

Własności wymienione powyżej ułatwiają rozpoznanie użycia szyfru Playfaira.
Własności szyfru opisane poniżej ułatwiają jego złamanie:

1. Żaden znak tekstu jawnego nie jest szyfrowany jako ten sam znak.

2. Każdy znak może być reprezentowany jako 5 różnych znaków i reprezentować 5

różnych znaków.

3. Żaden znak tekstu jawnego nie może reprezentować znaku występującego w

tabeli szyfru na tej samej przekątnej.

4. Prawdopodobieństwo, że dwa znaki dowolnej pary są wierzchołkami prostokąta

jest dwukrotnie większe, niż ich występowanie w tym samym wierszu lub

kolumnie.

5. Jeżeli ustaliliśmy, że znak w ramach jednej pary reprezentuje pewną literę

tekstu jawnego, mamy 20% prawdopodobieństwo, że w innych parach
reprezentuje tę samą literę.

Powyższe zależności ułatwiają poszerzenie zakresu włamania do szyfru, jednak

pierwszym krokiem jest z reguły odgadnięcie fragmentu tekstu jawnego.
Załóżmy, że w przejętym szyfrogramie występuje słowo ELEVENSURVIVORS

(jedenastu rozbitków), poczynając od siódmej litery szyfrogramu. Otrzymujemy
następujące wzajemne dopasowanie prawdopodobnego tekstu jawnego i

szyfrogramu:

EL EV EN SU RV IV OR S
XE LW AO HW UW YZ MW I

Konstrukcja systemu Playfaira powoduje, że siedem par odpowiadających sobie
znaków tekstu jawnego i szyfrogramu może w tabeli klucza występować w

następujących konfiguracjach:

EL = XE

EV = LW

EN = AO

LEX

ELVW

EANO

V EL

N EA

W WV

O ON

©ŁAMACZE SZYFRÓW

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

SU = HW

RV = UW

IV = YZ

OR = MW

SHUW

RUVW

IYVZ

OMRW

U SH

V RU

V IY

R OM

W WU

W WV

Z ZV

W WR

Wykorzystując wspólne litery w powyższych hipotezach dotyczących zależności w
tabeli klucza możemy łączyć je logicznie i sukcesywnie rekonstruować jej coraz

większe fragmenty, każdorazowo sprawdzając, które hipotezy pozwalają na
zachowanie spójności logicznej i zgodności z naturą szyfru Playfaira. Np.

łącząc ze sobą hipotezy oznaczone powyżej numerami 1, 2 i 5 otrzymamy
następujący fragment tabeli:

LEX
RUVW

Dodając zależności ujęte w tabelach 4 i 6 otrzymujemy:

Y I
H S

LEX
RUVWZ

W kolejnym etapie rekonstrukcji tabela klucza przybiera następującą formę:

Y I

H S
ALEX

MN O
RUVWZ

Nawiasem mówiąc, przedstawiony sposób rekonstrukcji tabeli klucza powinien

nasunąć czytelnikowi jednoznaczne skojarzenie z zasadą symetrii pozycji
Kerckhoffsa, zaprezentowaną w poprzednich wykładach. Uwzględniając zależności w

tabeli powyżej możemy zrekonstruować dalsze fragmenty tekstu jawnego:

XE LW AO HW UW YZ MW IH OM NE OB TF WM IE IP IE AN WL EO TO KN
EL EV EN SU RV IV OR S OA RO HA VE SE

EB FC MF EX BL OL UC GR PI HB KY AO SB PM BN AS CW OS YB SN VN
LE E EN EH E HO U

KC EL IL UE UM LU HX BY BT NK AL TB OE MP KE EI HB KG CW FV EK
LA YX WA RN AV A A ES X

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

Znajomość języka angielskiego pozwala dostrzec w końcówce drugiego i początku
trzeciego wiersza powyżej zarys frazy WITHOUTDELAY. Podpiszmy prawdopodobny

tekst jawny pod szyfrogram, otrzymując następujące pary znaków:

OS YB SN VN KC EL IL
EW IT HO UT DE LA YX

Pierwsza z nich (OS-EW) pozwala ustalić, że dwa pierwsze wiersze w
zrekonstruowanej do tej pory tabeli klucza stanowią w istocie fragmenty tego

samego wiersza:

HYSI
ALEX

MN O
RUVWZ

Uwzględnienie pozostałych, świeżo uzyskanych par pozwala na rekonstrukcję

tabeli klucza w postaci:

HYSI
CALEX

MNTOB
K

RUVWZ

Od tego punktu można zastosować dwa podejścia. W pierwszym rekonstruujemy
dalsze pary znaków tekstu jawnego, a wpisując je pod szyfrogramem uzyskujemy

kolejne zależności pomiędzy parami tekstu jawnego oraz szyfrogramu, które
uwzględniamy przy rekonstrukcji tabeli klucza. W drugim podejściu skupiamy

uwagę na samej tabeli klucza, która została dotąd zrekonstruowana w stopniu
umożliwiającym dokończenie pracy w oparciu o znajomość samej zasady tworzenia

tabeli. Zauważmy, że począwszy od litery B kolejne znaki w tabeli występują w
kolejności alfabetycznej. Oznacza to, że znak O stanowi zapewne ostatnią literę

przeniesioną ze słowa kluczowego, które posłużyło do wygenerowania tabeli.
Pierwszy wiesz tabeli i początek drugiego nie pozostawiają większych

wątpliwości, że fraza kluczowa rozpoczyna się od słowa PHYSICAL. Uzupełniając
dalszy ciąg frazy kluczowej w tabeli o znaki, które wystąpiły w słowie PHYSICAL

otrzymujemy bez trudu jej drugą część - słowo EXAMINATION. Pełna tabela klucza
ma zgodnie z naszymi ustaleniami postać:

PHYSI

CALEX
MNTOB

DFGKQ
RUVWZ

Odczytanie całości depeszy pozostawiamy jako ćwiczenie dla zainteresowanych

historią.
Zdołaliśmy stosunkowo łatwo złamać depeszę zaszyfrowaną w systemie Playfaira, z

którą nie poradzili sobie kryptoanalitycy armii japońskiej, dzięki czemu por.
Kennedy i jego ludzie zostali uratowani. Przy opisanej okazji John Kennedy dał

próbkę twardego charakteru, który w przyszłości pozwolił mu, już jako

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

prezydentowi USA, rozwiązać kryzys kubański bez wywoływania III wojny
światowej. Chyba dobrze się stało, że japońscy kryptolodzy nie stanęli na

wysokości zadania...

Po wstępie teoretycznym i zaczerpniętym z historii przykładzie przejdźmy do
zadania. Nasz radiowywiad przejął szyfrowaną depeszę o treści:

RTTXQFIWGSILXNXNNQIUENLIXFBPDRGPFQYHPENIBLUHXSDVFCRVTNNLNCPOLSERNULBSFPGB
RUCQPXUOVDVNEMINUUMGVNCMIGETNNLZNDVFKPEGEFLTVCKENTNNLXQXFTNECGNBZTRFXYWPQ
HLVTABUNTNNLUYGVTXGNGSONBLQFMXLNPVITBPQPXSDVFCRVUENIIGXFBPDRGPYQNQYU

Z szyfrogramów złamanych wcześniej wiemy, że przeciwnik używa szyfru Playfaira,
ma zwyczaj umieszczania na początku tekstu jawnego frazy określającej adresata,
np.

DOSZTABUDYWIZJISTOP

DOSZTABUARMIISTOP

itp. Wiemy także, że nadawcą

przejętej depeszy było dowództwo nieprzyjacielskiej dywizji, co wskazuje, że
jego odbiorcą był korpus, w którego skład dywizja wchodzi. Nasi kryptoanalitycy

twierdzą, że powyższe wskazówki powinny wystarczyć do szybkiego złamania
depeszy. Czy mają rację?

Przypomnijmy, że w dzisiejszym wykładzie postawiliśmy już jedno pytanie:

1. Jaki był numer łodzi patrolowej, której losem niepokoiło się amerykańskie

dowództwo na Wyspach Salomona?

Pozostałe dwa pytania brzmią:

2. Jakie oznaczenie liczbowe na mapach przeciwnika nosi wzgórze ostrzeliwane

przez nasze oddziały (podać tekst zgodnie z brzmieniem w szyfrogramie)?

3. Jakiej frazy użyto do wygenerowania klucza do szyfru?

www.lamaczeszyfrow.pl

Document Outline