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Ä™ zaprzyjaz
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ę
©A
AMACZE SZYFRÓW 1 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ę J znakiem I), 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
©A
AMACZE SZYFRÓW 2 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
©A
AMACZE SZYFRÓW 3 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:
1 2 3
EL = XE EV = LW EN = AO
LEX ELVW EANO
E L A
X V EL N EA
W WV O ON
©A
AMACZE SZYFRÓW 4 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
4 5 6 7
SU = HW RV = UW IV = YZ OR = MW
SHUW RUVW IYVZ OMRW
H U Y M
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
BA
©A
AMACZE SZYFRÓW 5 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
©A
AMACZE SZYFRÓW 6 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 przejdz
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?
©A
AMACZE SZYFRÓW 7 www.lamaczeszyfrow.pl