Szyfr Cezara
Szyfr Cezara (zwany jest też szyfrem przesuwającym, kodem Cezara lub przesunięciem Cezariańskim) – jedna z najprostszych technik szyfrowania. Jest to rodzaj szyfru podstawieniowego, w którym każda litera tekstu jawnego (niezaszyfrowanego) zastępowana jest inną, oddaloną od niej o stałą liczbę pozycji w alfabecie, literą (szyfr monoalfabetyczny), przy czym kierunek zamiany musi być zachowany. Nie rozróżnia się przy tym liter dużych i małych. Nazwa szyfru pochodzi od Juliusza Cezara, który prawdopodobnie używał tej techniki do komunikacji ze swymi przyjaciółmi.
 Szyfr Cezara zastępuje każdą literę tekstu jawnego inną, przesuniętą względem litery kodowanej o stałą liczbę pozycji w alfabecie. Na rysunku szyfr z przesunięciem równym 3, tak więc B w tekście jawnym jest podmieniane w szyfrogramie na E (rozpatrywany jest alfabet łaciński).
| |
| Rodzaj algorytmu | |
|---|---|
Algorytm szyfrowania zastosowany w kodzie Cezara bywa fragmentem bardziej złożonych systemów szyfrowania, takich jak szyfr Vigenère’a. Współcześnie szyfru Cezara używa się z przesunięciem 13 (ROT13), będącego prostym i szybkim sposobem na ukrycie treści. Obecnie szyfr Cezara, jak każda technika podmieniająca pojedyncze litery alfabetu na inne, nie oferuje żadnego bezpieczeństwa komunikacji.
Przykład
edytujSposób szyfrowania może być przedstawiony za pomocą diagramu dwóch ciągów z odpowiadającymi sobie kolejnymi literami alfabetu. Te same litery drugiego ciągu są przesunięte względem ciągu pierwszego o określoną liczbę pozycji, zwaną parametrem przesunięcia (tutaj 3) i pełniącą funkcję klucza szyfru:
Alfabet: AĄBCĆDEĘFGHIJKLŁMNŃOÓPRSŚTUWYZŹŻ Szyfr: CĆDEĘFGHIJKLŁMNŃOÓPRSŚTUWYZŹŻAĄB
Należy przy tym zauważyć, że ostatnim literom alfabetu w górnym ciągu odpowiadają początkowe litery w ciągu dolnym (alfabet został „zawinięty”). Chcąc zaszyfrować wiadomość, należy każdą jej literę zastąpić odpowiednikiem z szyfru (wiadomość w przykładzie jest zapisana wersalikami, aczkolwiek szyfr jest niewrażliwy na wielkość liter):
Tekst jawny: MĘŻNY BĄDŹ, CHROŃ PUŁK TWÓJ I SZEŚĆ FLAG Tekst zaszyfrowany: OHBÓŻ DĆFĄ, EKTRP ŚZŃM YŹSŁ L UAGWĘ INCJ
Deszyfrowanie polega na odwróceniu tej operacji.
Ujęcie matematyczne
edytujOperację szyfrowania i deszyfrowania można wyrazić w języku arytmetyki modularnej[1]. W tym celu wystarczy każdej literze alfabetu jednoznacznie przypisać jej numer według schematu A↔0, Ą↔1, B↔2, …, Ż↔31. Wygodnie jest też przyjąć, że klucz jest pewną liczbą z zakresu 0...31 (jest to numer zaszyfrowanej litery A).
Szyfrowanie można wtedy zdefiniować za pomocą kongruencji[2]:
gdzie jest numerem litery tekstu jawnego w alfabecie, – numerem litery szyfrogramu w alfabecie.
Podobnie deszyfrowanie tekstu można zapisać jako:
gdzie jest numerem litery szyfrogramu w alfabecie, – numerem litery tekstu jawnego w alfabecie.
Na podstawie własności kongruencji i tego, że są z przedziału 0...31:
- jeśli przy wyznaczaniu wartość wyrażenia przekroczy 32 – 1, to należy ją zmniejszyć o 32.
- jeśli przy wyznaczaniu wartość wyrażenia będzie ujemna, to należy ją zwiększyć o 32.
Operacje są do siebie odwrotne, bowiem przesuwanie w prawo o jest zarazem przesuwaniem w lewo o
Liczba 32 powyżej jest liczbą liter w alfabecie polskim. Dla alfabetu łacińskiego należy przyjąć liczbę 26[3].
Informacje historyczne
edytuj
Nazwa szyfru pochodzi od Juliusza Cezara, rzymskiego wodza i polityka. Szyfrował on prywatną korespondencję do swoich przyjaciół, zapisaną po łacinie, używając szyfru przesuwającego z kluczem 3. Z tego powodu niekiedy szyfrem Cezara określa się wyłącznie szyfr przesuwający z przesunięciem 3, zaś termin szyfr przesuwający jest zarezerwowany dla przypadku ogólnego[4].
Informacje na temat szyfru stosowanego przez Cezara pochodzą m.in. od Swetoniusza:
Exstant et ad Ciceronem, item ad familiares domesticis de rebus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quartam elementorum litteram, id est D, pro A et perinde reliquas commutet[5].
Zachowały się także jego listy do Cycerona, do bliskich znajomych w sprawach domowych, w których rzeczy wymagające tajemnicy podawał szyfrem, tj. tak ułożywszy szereg liter, aby nie dało się z nich utworzyć żadnego wyrazu. Jeśliby ktoś chciał zbadać i prześledzić ten szyfr, musiałby pod każdą literę podstawić czwartą z kolei literę abecadła, tj. D, podstawić A, i tak samo zmieniać resztę[6].
Adoptowany syn Cezara, Oktawian August, używał szyfru przesuwającego z przesunięciem 1 w prawo, przy czym zamiast podówczas ostatniej w alfabecie litery X[3], pisał podwójne A, o czym pisze Swetoniusz:
Quotiens autem per notas scribit, B pro A, C pro B ac deinceps eadem ratione sequentis litteras ponit; pro X autem duplex A[7].
Ilekroć posługuje się szyfrem, B stawia zamiast A, C zamiast B, i w tenże sam sposób umieszcza następne litery, zamiast X – podwójne A[8].
Istnieją źródła mówiące o tym, że Cezar używał również bardziej skomplikowanych systemów szyfrowania[9]. Także pisarz rzymski Gelliusz nawiązuje do traktatu (obecnie zagubionego) na temat szyfrów rzymskiego wodza[10].
Zastosowania
edytujSzyfr Cezara z przesunięciem 1 w lewo zastosowany został na odwrocie mezuz do zakodowania hebrajskich imion Boga (zapisanych po odwróceniu pergaminu o 180°, by zachowana została kolejność liter po drugiej stronie). Na pergaminie widnieje szyfrogram KUZU BMUKSZ KUZU, co po odkodowaniu (w alfabecie hebrajskim) daje YHVH ELHYNU YHVH. Według niektórych autorytetów jest to pozostałość czasów, gdy Żydom nie pozwalano na posiadanie mezuzy. Natomiast same litery kryptogramu zawierają boskie imię, co miało chronić przed złymi mocami[11].
W XIX wieku rubryki ogłoszeń drobnych w gazetach były czasami wykorzystywane do przekazywania zaszyfrowanych prostymi kodami wiadomości. Amerykański historyk wojskowy, David Kahn opisał w 1967 roku przypadki kochanków potajemnie komunikujących się zakodowanymi szyfrem Cezara wiadomościami na łamach The Times[12]. Z kodu Cezara korzystano nawet w 1915 roku. Armia Imperium Rosyjskiego posługiwała się nim jako zamiennikiem dla jej bardziej skomplikowanych szyfrów, które były zbyt trudne do opanowania dla rosyjskiego wojska, dzięki czemu niemieccy i austriaccy kryptoanalitycy nie mieli większych problemów z odczytaniem tych wiadomości[13].
Szyfr Cezara obecny jest także w dzisiejszych czasach. Ma zastosowanie w zabawkach typu secret decoder ring (dwa przylegające i obrotowe względem siebie pierścienie z nadrukowanymi kolejnymi literami alfabetu), a szyfr z przesunięciem 13, tzw. ROT13, jest stosowany jako prosta metoda ukrycia treści (np. puenty dowcipów i zakończeń fabuły – tzw. spoilery), szeroko rozpowszechniona w systemach Unix[14].
Szyfr Vigenère’a jest natomiast szyfrem Cezara ze zmiennym przesunięciem na każdej pozycji w tekście. Wartość przesunięcia jest definiowana przez dowolne słowo kluczowe. Jeśli słowo kluczowe jest losowe i o długości nie krótszej niż sama wiadomość, wtedy jest to szyfr z kluczem jednorazowym, niemożliwy do złamania, pod warunkiem utrzymania klucza w tajemnicy. Klucz krótszy od wiadomości (jak np. słowa Complete Victory używane przez Konfederację podczas wojny secesyjnej) niesie ze sobą powtarzający się wzór, który może być rozpoznany przez zaawansowane techniki analizy częstościowej[15].
Kryptoanaliza
edytujNie istnieją żadne źródła mówiące o technice złamania prostych szyfrów podstawieniowych w starożytności. Pierwsze udokumentowane metody łamania takich szyfrów autorstwa arabskiego filozofa Al-Kindi pochodzą z IX wieku, gdy zaczęto stosować analizę częstościową[16].
| Przesunięcie deszyfrujące |
Otrzymana treść |
|---|---|
| 0 | DŹDŃŚADRMI
|
| 1 | ĆZĆNSŻĆPŁH
|
| 2 | CYCMRŹCÓLG
|
| 3 | BWBŁPZBOKF
|
| 4 | ĄUĄLÓYĄŃJĘ
|
| 5 | ATAKOWANIE
|
| 6 | ŻŚŻJŃUŻMHD
|
| … | |
| 29 | FĄFPWCFTOL
|
| 30 | ĘAĘÓUBĘŚŃK
|
| 31 | EŻEOTĄESNJ
|
Obecnie wypracowane są techniki łamania szyfru Cezara. Można go bardzo łatwo złamać nawet wtedy, gdy dostępny jest wyłącznie szyfrogram, o ile zachodzi jedna z poniższych możliwości:
- wiadomo (lub przypuszcza się), że zastosowano jakiś prosty szyfr podstawieniowy, ale nie wiadomo, czy jest to szyfr Cezara;
- wiadomo, że zastosowano szyfr Cezara, ale nieznane jest przesunięcie, jakiego użyto do zakodowania wiadomości.
W pierwszym przypadku szyfr może zostać łatwo złamany przez zastosowanie tych samych technik, których używa się do łamania innych szyfrów podstawieniowych, jak np. atak statystyczny[17]. Jest bardzo prawdopodobne, że osoba chcąca rozszyfrować tekst szybko spostrzeże pewną prawidłowość w szyfrogramie i wywnioskuje, że do zakodowania użyto szyfru Cezara.
W drugim przypadku szyfr Cezara jest jeszcze prostszy do złamania. Ponieważ istnieje skończona liczba możliwych przesunięć (32 w języku polskim), każda z kombinacji może być przetestowana atakiem brute force[18]. Jednym ze sposobów uczynienia tego jest wypisanie fragmentu zaszyfrowanego tekstu w tabeli razem z jego wszystkimi możliwymi przesunięciami[19] – technika zwana czasem „układaniem elementu jawnego” (ang. completing the plain component)[20]. Niech przykładowym szyfrogramem będzie DŹDŃŚADRMI. Bez wnikliwej analizy można od razu zauważyć, że rozkodowanie tekstu następuje przy przesunięciu 5. Istnieje jeszcze jeden sposób wykorzystania takiej tabeli. Pod każdą literą szyfrogramu wypisywane są w odwrotnej kolejności poprzedzające ją litery w alfabecie. Można wykorzystać ten fakt w celu szybszego rozkodowania tekstu, używając zestawu pasków z pionowo wypisanymi literami alfabetu także w odwrotnej kolejności. Po dopasowaniu poszczególnych liter z pasków do szyfrogramu, rozkodowany tekst będzie widoczny w którymś z ułożonych rzędów.
Innym rodzajem ataku brute force jest dopasowanie rozkładu częstości liter. Tworząc wykres częstości liter w szyfrogramie oraz znając rozkład tych liter w języku, w którym został zapisany tekst jawny, można z łatwością rozpoznać wartość przesunięcia szyfrującego poprzez zaobserwowanie przemieszczenia układu najwyższych słupków wykresu odpowiadającym najpopularniejszym literom. Na przykład w języku polskim najczęściej używanymi w tekstach są litery A, I, O, E, a charakterystyczny utworzony przez nie układ jest widoczny w rozkładzie większości dostatecznie długich szyfrogramów[21]. W bardziej zaawansowanej wersji można użyć metod statystycznych dla wyliczenia w jakim stopniu cały rozkład częstości w próbie odpowiada rozkładowi oczekiwanemu, na przykład za pomocą testu zgodności chi-kwadrat[22]. Takimi badaniami posługuje się kryptoanaliza statystyczna.
Dla tekstu w języku naturalnym najczęściej tylko jeden klucz daje zrozumiały wynik, aczkolwiek pewnych bardzo krótkich wiadomości nie można jednoznacznie złamać bez znajomości klucza. Na przykład zakodowany tekst „WĄĘ” może być rozkodowany na słowo „KOT” lub „RYB” (przyjąwszy, że językiem tekstu jawnego jest polski), podobnie szyfrogram „ŻYAH” na „TRUĆ” lub „ROSĄ”, a tekst „DIFBA” na „MROKI” lub „RYTON”.
Wielokrotne kodowanie tej samej treści szyfrem Cezara nie zwiększa bezpieczeństwa, ponieważ dwie operacje szyfrowania, na przykład z przesunięciem 3 i z przesunięciem 5 są równoważne kodowaniu z przesunięciem Używając terminologii matematycznej, można to wyrazić następująco: zbiór wszystkich szyfrów Cezara z różnymi kluczami tworzy grupę cykliczną ze względu na złożenie operacji szyfrowania[23].
Zobacz też
edytuj- szyfr Vernama – ulepszona wersja szyfru Cezara. Każda litera przesunięta jest o losową liczbę miejsc i w losową stronę
Przypisy
edytuj- ↑ Dennis Luciano, Gordon Prichett. Cryptology: From Caesar Ciphers to Public-Key Cryptosystems. „The College Mathematics Journal”. 18 (1), s. 3, styczeń 1987. DOI: 10.2307/2686311. (ang.).
- ↑ Reinhard Wobst: Cryptology Unlocked. Wiley, 2001, s. 19. ISBN 978-0470060643.
- ↑ a b Alfabet łaciński w czasach Cezara liczył 21 liter – kończył się na X, brakowało w nim J, U, W, Y, Z. patrz: Henry Rogers: Writing systems: a linguistic approach. Oxford: Blackwell, 2004, s. 174.
- ↑ Szyfrowanie Informacje. Szyfrowanie.info. [dostęp 2009-08-05].
- ↑ Gajus Swetoniusz Trankwillus: De Vita Caesarum. Divus Julius. 56. The Latin Library. [dostęp 2009-08-24].
- ↑ Gajus Swetoniusz Trankwillus, Żywoty cezarów, przekład, wstęp i komentarz J. Niemirska-Pliszczyńska, przedmowa J. Wolski, wyd. 2 zmienione, Wrocław 1960, s. 37 (Boski Juliusz, 56).
- ↑ Gajus Swetoniusz Trankwillus: De Vita Caesarum. Divus Augustus. 88. [dostęp 2009-08-26].
- ↑ Gajus Swetoniusz Trankwillus, Żywoty cezarów, przekład, wstęp i komentarz J. Niemirska-Pliszczyńska, przedmowa J. Wolski, wyd. 2 zmienione, Wrocław 1960, s. 115 (Boski August, 88).
- ↑ Edgar C. Reinke. Classical Cryptography. „The Classical Journal”. 58 (3), s. 114, grudzień 1992. (ang.).
- ↑ Aulus Gellius: Noctes Atticae. XVII, 9,5. [dostęp 2009-08-24].
- ↑ Alexander Poltorak: Mezuzah and Astrology. chabad.org. [dostęp 2009-08-06]. (ang.).
- ↑ David Kahn: The Codebreakers – The Story of Secret Writing. Scribner, 1996, s. 775–776. ISBN 0-684-83130-9.
- ↑ David Kahn: The Codebreakers – The Story of Secret Writing. Scribner, 1996, s. 631–632. ISBN 0-684-83130-9.
- ↑ Reinhard Wobst: Cryptology Unlocked. Wiley, 2001, s. 20. ISBN 978-0470060643.
- ↑ David Kahn: The Codebreakers – The Story of Secret Writing. Scribner, 1996. ISBN 0-684-83130-9.
- ↑ Simon Singh: The Code Book. Anchor, 2000, s. 14–20. ISBN 0-385-49532-3.
- ↑ Albrecht Beutelspacher: Cryptology. Mathematical Association of America, 1994, s. 9–11. ISBN 0-88385-504-6.
- ↑ Albrecht Beutelspacher: Cryptology. Mathematical Association of America, 1994, s. 8–9. ISBN 0-88385-504-6.
- ↑ Albert C. Leighton. Secret Communication among the Greeks and Romans. „Technology and Culture”. 10 (2), s. 153, kwiecień 1969. DOI: 10.2307/3101474. (ang.).
- ↑ Abraham Sinkov, Paul L. Irwin: Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America, 1966, s. 13–15. ISBN 0-88385-622-0.
- ↑ Adam Przepiórkowski: Poradnia językowa. pwn.pl, 20 marca 2006. [dostęp 2009-08-07].
- ↑ Chris Savarese, Brian Hart: The Caesar Cipher. 15 lipca 2002. [dostęp 2009-08-07]. (ang.).
- ↑ Reinhard Wobst: Cryptology Unlocked. Wiley, 2001, s. 31. ISBN 978-0470060643.
Bibliografia
edytuj- David Kahn: The Codebreakers – The Story of Secret Writing. Scribner, 1996. ISBN 0-684-83130-9. (ang.).
- F.L. Bauer: Decrypted Secrets. Springer, 2000. ISBN 3-540-66871-3. (ang.).
- Chris Savarese, Brian Hart: The Caesar Cipher. 15 lipca 2002. [dostęp 2016-10-09]. (ang.).