Marek Grajek KURS KRYPTOLOGII
Szyfry podstawieniowe
Przypomnijmy prosty szyfr stanowiący część nomenklatora, z którym zetknęliśmy
się w poprzednim wykładzie. Miał on postać:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
QWERTYUIOPASDFGHJKLZXCVBNM
Zaszyfrujmy nim tekst SZYFRYPODSTAWIENIOWE - otrzymujemy szyfrogram:
LMNYKNHGRLZQVOTFOGVT
Ale przy tym samym tekście jawnym i tym samym, choć wyrażonym w odmiennym
alfabecie szyfrowym kluczu szyfrogram może przybrać formę
*[ó! 9ó41.*$7ś6;861ś;
dla alfabetu szyfrowego użytego w opowiadaniu Allana Edgara Poe  Złoty żuk lub
dla alfabetu Braille a, wreszcie
dla alfabetu szyfrowego  tańczących sylwetek zaczerpniętego z jednego z
opowiadań Conan Doyle a o Sherlocku Holmesie.
Adept kryptologii nie powinien lekceważyć literatury pięknej. Dowodzi tego
historia ówczesnego porucznika Wojska Polskiego, Jana Kowalewskiego, który w
połowie 1919 roku, w czasie wojny polsko-bolszewickiej, został poproszony przez
swego przyjaciela ze sztabu o zastąpienie go na nocnym dyżurze; siostra kolegi
brała właśnie ślub, a ten, chcąc zatańczyć na jej weselu, musiał znalez
ć
zastępcę. Problem w tym, że kolega był pracownikiem sekcji radiowywiadu, a
znajomość szyfrów u Jana Kowalewskiego, jak sam przyznał w spisanych po latach
wspomnieniach, ograniczała się ówcześnie do lektury  Złotego żuka Allana
Edgara Poe. Wyniesiona z niej wiedza o szyfrach, połączona z dociekliwością i
systematycznością okazały się wystarczające - jeszcze przed rankiem Kowalewski
złamał szyfr bolszewików. Był to początek wielkiego wyczynu polskiego
radiowywiadu, który pod koniec wojny łamał większość używanych przez
przeciwnika szyfrów i kodów w ciągu kilku godzin. Polskie zwycięstwo nad
bolszewikami w sierpniu 1920 roku zyskało póz
niej miano  cudu nad Wisłą .
Jeżeli rzeczywiście był to cud, zdziałali go wyłącznie kryptolodzy polskiej
armii, dostarczając swoim dowódcom precyzyjnej i punktualnej informacji o
wszystkich zamiarach przeciwnika.
Wspólną cechą wszystkich szyfrów, o których będziemy mówić w dzisiejszym
wykładzie, jest ich struktura; w miejsce każdego znaku alfabetu jawnego
podstawia się znak alfabetu szyfrowego. W rezultacie cała rodzina podobnie
©A
AMACZE SZYFRÓW 1 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
skonstruowanych szyfrów zyskała nazwę szyfrów podstawieniowych, lub też, z
łaciny, szyfrów substytucyjnych. Przez kilkaset lat autorzy różnych systemów
szyfrowych usiłowali onieśmielać kryptoanalityków wymyślając coraz bardziej
fantazyjne alfabety szyfrowe, jednak podstawowa zasada ich konstrukcji -
substytucja znaków alfabetu jawnego przez znaki alfabetu szyfrowego -
pozostawała bez zmiany. Zauważyliśmy w poprzednim wykładzie, że elementy dwóch
alfabetów 26-znakowe można przyporządkować sobie wzajemnie na 26! sposobów, co
wydaje się tworzyć bezpieczny system. Wspomnieliśmy jednak także, że dla
większości tradycyjnych systemów kryptologicznych opracowano drogi na skróty, a
szyfr podstawieniowy był bodaj pierwszy na tej liście. Nie wiemy, kto i kiedy
opracował uniwersalny sposób jego łamania. Najstarszy zachowany sygnał tego
wynalazku pochodzi z rękopisu pióra arabskiego uczonego z IX wieku, Al-
Kindiego, który pisał:
 Jeden sposób na odczytanie zaszyfrowanej wiadomości, gdy wiemy w jakim języku
została napisana, polega na znalezieniu innego tekstu w tym samym języku, na
tyle długiego, by zajął mniej więcej jedną stronę, i obliczeniu, ile razy
występuje w nim każda litera. (...) Następnie bierzemy tekst zaszyfrowany i
również znajdujemy najczęściej występującą w nim literę, zastępując go
najczęściej występującą literą innego tekstu (...)
Abu Jusuf Jakub ibn Ishak al-Kindi i strona z traktatu opisującego łamanie szyfrów przez badanie
częstotliwości występowania liter w tekście.
Resztę przepisu na złamanie szyfru podstawieniowego opiszmy operując
współczesną terminologią. Uczeni arabscy zauważyli, że poszczególne znaki
alfabetu występują w tekstach z charakterystyczną częstotliwością. W tekstach
arabskich najczęściej występuje znak alif, po nim - lam. W innych językach
struktura częstotliwości występowania znaków będzie odmienna, ale pewne cechy
charakterystyczne dla danego języka będą zawsze zachowane. Zauważmy, że ścisłe
wyznaczenie częstotliwości występowania poszczególnych znaków w danym języku
©A
AMACZE SZYFRÓW 2 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
jest niemożliwe; po pierwsze - nikt jeszcze nie opracował słownika obejmującego
wszystkie zwroty języka; po drugie - rzeczywista częstotliwość występowania
znaków jest zależna od wielu czynników, w tym tematu tekstu i indywidualnego
stylu autora. Z pewnością jednak strukturę częstotliwości występowania znaków
można wyznaczyć w sposób wystarczająco precyzyjny, by była użyteczna dla celów
praktycznych. Jeżeli jest to możliwe, zawsze warto próbować wyznaczyć
częstotliwości odniesienia występowania liter w oparciu o próbkę tekstu o takim
samym charakterze, jak podejrzewamy w szyfrogramie.
Charakterystyczną częstotliwość występowania znaków w języku angielskim i
polskim (w procentach) wyznaczoną dla długich próbek tekstu przedstawiono w
poniższych tabelach.
a b c d e f g h i j k l
8,2 1,5 2,8 4,3 12,7 2,2 2 6,1 7 0,2 0,8 4
m n o p q r s t u v w x y z
2,4 6,7 7,5 1,9 0,1 6 6,3 9,1 2,8 1 2,4 0,2 2 0,1
język angielski
a ą b c ć d e ę f g h i j k l ł
9,3 1,2 1,8 3,8 0,5 3,2 7,7 1,7 0,2 1,4 1,0 8,8 2,3 3,5 2,2 2,6
m n ń o ó p r s ś t u w y z z
ż
3,3 5,2 0,1 7,0 0,8 3,1 3,8 4,3 0,8 3,4 2,3 4,0 3,7 5,8 0,1 1,1
język polski
Poniższy wykres przedstawia częstotliwość występowania znaków w języku
angielskim. Warto zwrócić uwagę zarówno na naturalne  szczyty wykresu,
przypadające na litery E, T, A, O, I, N, jak i widoczne  doliny pomiędzy
znakami I oraz L jak również O i R.
©A
AMACZE SZYFRÓW 3 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Przedstawiane dalej przykłady będą zawierać teksty w języku angielskim, co
najmniej z dwóch powodów. Po pierwsze - prawdziwy kryptoanalityk niezwykle
rzadko analizuje szyfry we własnym języku. Po drugie - struktura języka
angielskiego stawia na
drodze poczÄ…tkujÄ…cego
kryptologa nieco niższe
przeszkody. Wystarczy rzut
oka na tabelÄ™
częstotliwości
występowania znaków w
języku polskim by upewnić
się, że kluczowe dla
łamania szyfru samogłoski
(za wyjÄ…tkiem U) sÄ… w nim
statystycznie praktycznie
nierozróżnialne.
Załóżmy, że przejęliśmy
szyfrogram, którego z
ródło
nadania pozwala
podejrzewać, że został w
oryginale napisany w języku angielskim. Zgodnie z zasadami preparowania tekstów
jawnych szyfrogramów zakładamy, że z tekstu jawnego zostały usunięte wszystkie
odstępy pomiędzy wyrazami oraz znaki interpunkcyjne. Gdyby w tekście jawnym
zachowano odstępy musielibyśmy uwzględnić, że w języku angielskim typowa
częstotliwość występowania spacji jest nieco wyższa od najczęściej występującej
litery E - ale w naszym przykładzie wykluczamy taką możliwość. Zakładamy też,
że treść przejętego szyfrogramu ma związek z kryptologią. Przejęta depesza ma
treść:
HFTHOQGTTKMDATNQETQGHPNSNTPQHYMTKQTYAIGTMNNQMHFLTMQGKFNAEIDTNSRNQAQSQAHFV
KNQHYMTKQTYAIGTMQKRDTNVGAYGGKPEHMTQGKFHFTNSRNQAQSQTOHMTKYGDTQQTMKFPVGAYGG
KPKPPAQAHFKDNSRNQAQSQTNOHMFKETNQGKQVHSDPRTYHEEHFDXSNTPRTYKSNTHOQGTNALFAOA
YKFYTLAUTFQHIMHITMFKETNQGTNTNXNQTENVTMTYKDDTPFHETFYDKQHMNNHETHOQGTTKMDXFH
ETFYDKQHMNVTMTOKAMDXSFNHIGANQAYKQTPQGTNSRNQAQSQTNOHMQGTDTQQTMREALGQRTQGTD
TQQTMEHMQGTPALAQOHSMVMAQQTFAFNTUTMKDPANQAFYQAUTNQXDTNKFPQGTFQGTNSRNQAQSQT
NOHMYEALGQRTQGTDTQQTMFHMQGTPALAQOAUTKLKAFVMAQQTFAFPANQAFYQAUTNQXDTNQGSNKY
MXIQKFKDXNQVADDAFLQHQMXKNAEIDTLSTNNVHSDPHFDXFTTPQHNHDUTKYKTNKMYAIGTMKNAEI
DTNSRNQAQSQAHFVGTMTQGTKDIGKRTQANETMTDXPANIDKYTPAFNQTKPHORTAFLQGHMHSLGDXNY
MKERDTPAFNQTKPHOOKYAFLQGTOSDDIMHRDTEHOOAFPAFLNSRNQAQSQTNOHMQGTOSDDNTQHONX
ERHDNAFPAUAPSKDDXHFTAFLTFAHSNEHPTMFETQGHPHOIMHPSYAFLKGHEHIGHFAYYAIGTMYKDD
TPQGTLMKFPIMTYAIGTMAFUHDUTNYGHHNAFLQTFQTFDTQQTMVHMPNVGAYGYKFRTHMPTMTPNHQG
KQQGTAMOAMNQDTQQTMNOHMEKFTDTUTFQGQTFDTQQTMVHMPKFPVGAYGYHDDTYQAUTDXAFYDSPT
KDDQVHNAWDTQQTMNHOQGTKDIGKRTQQGTYHDSEFNAFIHMQKNPAKLMKEKDDYHFQKAFYGKMKYQTM
NMTDKQTPAFNGKITQGANEKCTNAQTKNATMQHDHHCSIKNXERHDRSQKDNHLAUTNKVKXAFOHMEKQAH
FHFTVKXQHMTQKAFQGTKPUKFQKLTHOTKNADXOAFPAFLKNXERHDRSQVAQGHSQLAUAFLKVKXAFOH
MEKQAHFQHQGTYMXIQKFKDXNQANADDSNQMKQTPAFQGTPAKLMKEKRHUT
Zaczynamy jej analizę od sporządzenia wykresu częstotliwości występowania
poszczególnych znaków, otrzymując:
©A
AMACZE SZYFRÓW 4 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Gdyśmy nie wiedzieli, że szyfrogram został zaszyfrowany z użyciem szyfru
monoalfabetycznego, powyższy rozkład częstotliwości dostarcza silnego argumentu
potwierdzającego ten fakt; bardziej złożone szyfry z reguły dają w efekcie
bardziej wyrównany rozkład częstości występowania poszczególnych znaków.
Widzimy, że najczęściej występują znaki T i Q, a ich częstotliwość występowania
odpowiada w przybliżeniu teoretycznym wartościom odpowiednio dla znaków E i T.
W języku angielskim jednym z najczęściej występujących trygramów (trójek liter)
jest trygram THE, korzystamy więc z identyfikacji prawdopodobnych odpowiedników
znaków T oraz E i szukamy w szyfrogramie wystąpień Q i T oddzielonych jedną i
zawsze tą samą literą. Znajdujemy liczne wystąpienia trójki QGT, sugerujące, że
literze H tekstu jawnego może odpowiadać litera G w szyfrogramie.
Innym często występującym ciągiem wyrazów języka angielskiego jest THAT, z
którego dysponujemy już trzema elementami; poszukujemy zatem ciągów QG?Q, w
których znakiem zapytania oznaczyliśmy nieznaną literę odpowiadającą A.
Znajdujemy dwa wystÄ…pienia ciÄ…gu QGKQ; zaledwie dwa wystÄ…pienia nie sÄ… silnÄ…
przesłanką, ale z drugiej strony - częstotliwość występowania K w szyfrogramie
jest zbliżona do częstotliwości występowania A w języku angielskim; zaryzykujmy
założenie, że litera K w szyfrogramie odpowiada literze A tekstu jawnego.
Spróbujmy sięgnąć teraz po inną przesłankę; alfabet tekstu jawnego nie zawiera
cyfr. Jeżeli w szyfrogramie występują liczby, zgodnie z często przyjmowaną
konwencją mogły zostać zapisane w postaci podobnej do tej, jaką posługujemy się
podając numer telefoniczny, np. 221 jako  dwadwajeden . Jeżeli tak się stało,
interesująca z kryptologicznego punktu widzenia jest słowna postać jedynki,
ONE, która zawiera trzy znaki należące do najczęściej występujących. Zakładamy,
że już znamy odpowiednik E. Spośród innych często występujących w szyfrogramie
znaków nie bierzemy pod uwagę litery K, odpowiadającej A w tekście jawnym. Inne
często występujące litery szyfrogramu, to H, N i F. Spróbujmy dopasować do
szyfrogramu ciÄ…gi HNT, HFT, NHT, NFT, FHT i FNT. Znajdujemy jedno wystÄ…pienie
trygramu FNT i kilka wystąpień trygramu HFT, co uprawnia nas do założenia, że
HFT odpowiada ONE, zatem O w tekście jawnym jest zastępowane przez H, a N przez
F.
Z diagramu teoretycznej częstości znaków języka angielskiego wnioskujemy, że
ostatnią spośród często występujących liter, której odpowiednika jeszcze nie
zdołaliśmy ustalić, jest litera I o częstotliwości występowania około 7%.
Przeszukując wykres częstości występowania znaków w szyfrogramie zwracamy uwagę
na literę A, której odpowiednika do tej pory nie określiliśmy, lecz ok. 8%
częstotliwość występowania wskazuje na poszukiwaną literę I.
©A
AMACZE SZYFRÓW 5 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Podsumujmy nasze dotychczasowe ustalenia:
A E H I N O T w tekście jawnym odpowiadają prawdopodobnie znakom
K T G A F H Q w szyfrogramie.
Znalez
liśmy już prawdopodobnie szyfrowy odpowiednik frazy THAT, jesteśmy też
gotowi do odnalezienia jej bliz
niaczej frazy THIS. SzukajÄ…c odpowiadajÄ…cych jej
czwórek o strukturze QGA? znajdujemy jedno wystąpienie frazy QGAN, które
sugeruje, że odpowiednikiem znaku S w tekście jawnym może być N. Ponownie -
zaledwie jedno wystÄ…pienie poszukiwanej frazy nie stanowi wystarczajÄ…cej
przesłanki, ale porównanie częstości występowania obu znaków w tekście jawnym i
szyfrogramie utwierdza hipotezę, że S zostało przekształcone w N.
Nasza następna hipoteza będzie odważna, ale zgodna z wcześniejszymi
założeniami, zgodnie z którymi treść szyfrogramu ma związek z kryptologią. Może
warto poszukać słowa CIPHER (szyfr)? Wydaje się, że znamy trzy spośród
występujących w nim liter: I, H oraz E. Gdyby udało nam się dopasować słowo do
szyfrogramu, otrzymalibyśmy ważną premię - literę R o wysokiej częstotliwości
występowania. Poszukując wzorca ?A?GT? otrzymujemy liczne wystąpienia frazy
YAIGTM, zbyt liczne, by mogło to być wyłącznie wynikiem przypadku. Wydaje
się, że odpowiednikiem litery C tekstu jawnego jest litera Y w
szyfrogramie, a R w tekście jawnym jest zastępowane przez M.
Zważywszy, że zdołaliśmy dotąd zebrać hipotezy dotyczące znaków o
najwyższej częstotliwości występowania, powinniśmy dysponować już
fragmentami obejmującymi znaczącą część tekstu jawnego. Spróbujmy
spojrzeć na efekty naszej dotychczasowej pracy zastępując w szyfrogramie
odpowiednikami litery, dla których sformułowaliśmy już hipotezy, a
pozostałe, nieznane litery - znakiem myślnika.
ONEO-THEEAR-IEST-ETHO-S-SE-TOCREATECI-HERSSTRON-ERTHANSI---ES--STIT-TION-
ASTOCREATECI-HERTA--ES-HICHHA--ORETHANONES--STIT-TE-OREACH-ETTERAN--
HICHHA-A--ITIONA-S--STIT-TES-ORNA-ESTHAT-O----ECO--ON---SE--ECA-SEO-
THESI-NI-ICANCE-I-ENTO-RO-ERNA-ESTHESES-STE-S-ERECA--E-NO-ENC-ATORSSO-EO-
THEEAR--NO-ENC-ATORS-ERE-AIR---NSO-HISTICATE-THES--STIT-TES-ORTHE-ETTER--
I-HT-ETHE-ETTER-ORTHE-I-IT-O-R-RITTENI-ERA--ISTINCTI-EST--ESAN-THENTHES--
STIT-TES-ORC-I-HT-ETHE-ETTERNORTHE-I-IT-I-EA-AIN-RITTENIN-ISTINCTI-EST--
ESTH-SACR--TANA--ST-I--IN-TOTR-ASI---E--ESS-O---ON--NEE-TOSO--EACAESARCI-
HERASI---ES--STIT-TION-HERETHEA--HA-ETIS-ERE---IS--ACE-INSTEA-O--EIN-
THORO--H--SCRA---E-INSTEA-O--ACIN-THE-----RO--E-O--IN-IN-S--STIT-TES-
ORTHE----SETO-S---O-SIN-I-I--A---ONEIN-ENIO-S-O-ERN-ETHO-O--RO--CIN-AHO-
O-HONICCI-HERCA--E-THE-RAN--RECI-HERIN-O--ESCHOOSIN-TENTEN-ETTER-OR-S-
HICHCAN-EOR-ERE-SOTHATTHEIR-IRST-ETTERS-OR-ANE-E-ENTHTEN-ETTER-OR-AN--
HICHCO--ECTI-E--INC---EA--T-OSI--ETTERSO-THEA--HA-ETTHECO---NSIN-ORTAS-
IA-RA-A--CONTAINCHARACTERSRE-ATE-INSHA-ETHIS-A-ESITEASIERTO-OO---AS---
O---TA-SO-I-ESA-A-IN-OR-ATIONONE-A-TORETAINTHEA--ANTA-EO-EASI---IN-IN-
AS---O---T-ITHO-T-I-IN-A-A-IN-OR-ATIONTOTHECR--TANA--STISI---STRATE-
INTHE-IA-RA-A-O-E
©A
AMACZE SZYFRÓW 6 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Początek otrzymanego tekstu narzuca uzupełnienie do postaci:
ONEOFTHEEARLIESTMETHODSUSEDTOCREATECIPHERSSTRONGERTHANSIMPLE,
a po rozbiciu na poszczególne słowa otrzymujemy:
 One of the earliest methods used to create ciphers stronger than simple&  .
InteresujÄ…ce, wszystkie hipotezy dotyczÄ…ce liter tekstu jawnego i ich
szyfrowych odpowiedników potwierdziły się w otrzymanym tekście (pół)jawnym.
Pamiętajmy, że formułowanie hipotez wyłącznie na podstawie częstotliwości
występowania jest rozsądnym rozwiązaniem jedynie dla znaków o najbardziej
charakterystycznych wartościach częstości wystąpień. Jednak połączenie
przesłanek wynikających z częstotliwości występowania i struktury języka z
reguły pozwala na trafne domysły co do zestawienia par znaków. Słuchaczom
biegłym nie tylko w kryptologii, ale i w języku angielskim pozostawiamy
uzupełnienie reszty tekstu oraz odnalezienie słowa kluczowego, użytego przy
generacji alfabetu szyfrowego.
A teraz do rzeczy. Nasz radionasłuch przejął przedstawiony poniżej szyfrogram.
Okoliczności nadania go wskazują, że język angielski jest językiem tekstu
jawnego, a depesza dotyczy kryptologii.
NFMPQCAQQAMPNJMDSHACAVAHQRQAHCAQQAMWJMGSHGWRFEREJCCAEQFVACYFHECUGASCCQWJPFXCAQQ
AMPJNQRASCKRSTAQQRAEJCUDHPFHKJMQSPGFSOMSDSCCEJHQSFHERSMSEQAMPMACSQAGFHPRSKAQRFP
DSBAPFQASPFAMQJCJJBUKSPYDTJCTUQSCPJOFVAPSWSYFHNJMDSQFJHJHAWSYQJMAQSFHQRASGVSHQS
OAJNASPFCYNFHGFHOSPYDTJCTUQWFQRJUQOFVFHOSWSYFHNJMDSQFJHQJQRAEMYKQSHSCYPQFPFCCUP
QMSQAGFHQRAGFSOMSDSTJVARSVAPFDFCSMPYDTJCPSMMSHOAGSCJHOQRAGFSOJHSCPJNQRAGFSOMSDS
HGUPADFXAGSCKRSTAQPSCJHOQRAAGOAPWRFCASGFOMSKRFEPYDTJCEFKRAMFPPJDAQRFHOQRSQFPHQQ
JJKMSEQFESCPFDFCSMQAERHFLUAPRSVATAAHUPAGNJMPDSCCEJGAERSMQPQJDSBAQRADKMSEQFESCSH
GPAEUMAPYPQADSQFEDAQRJGPJNAHEFKRAMFHOPAVAMSCCAQQAMPSQJHEAWFQRJUQPFDKCYUPFHOSVAM
YCSMOAQSTCAWFCCTAJUQCFHAGFHWRSQNJCCJWPNMSEQFJHSQFJHCAHGPFQPACNQJDSHYEJDKCFESQAG
SHGTFZSMMAGAVACJKDAHQPSNAWJNWRFERWFCCTAFCCUPQMSQAGQRAMARJKANUCCYSCCQRAAXSDKCAPQ
RSQWFCCTAEJHQSFHAGFHQRANJCCJWFHOKSOAPWFCCKMJVASPQSMQFHOKJFHQNMJDWRFERYJUESHCAQY
JUMFDSOFHSQFJHMUHWFCGNMSEQFJHSQFJHSCQRJUORSKJWAMNUCQAERHFLUARSPPACGJDTAAHUPAGFH
KSKAMSHGKAHEFCEFKRAMPTAESUPAFQFPQJJEJDKCFESQAGSHGKMJHAQJAMMJM
Poniżej zamieszczamy wykres częstotliwości znaków w szyfrogramie.
©A
AMACZE SZYFRÓW 7 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Zadanie brzmi:
1.Zaszyfruj szyfrem podstawieniowym o kluczu lamaczeszyfrow kolejno imiona i
nazwiska trzech matematyków - łamaczy szyfrów Enigmy porządkując je
alfabetycznie wg. Nazwisk
2.Przedstawić pierwszych 50 znaków tekstu jawnego szyfrogramu.
3.Przedstawić słowo kluczowe, użyte do wygenerowania alfabetu szyfrowego.
Powodzenia.
©A
AMACZE SZYFRÓW 8 www.lamaczeszyfrow.pl