Szyfr Cezara [historia i autorzy]

Szyfr Cezara (zwany też szyfrem przesuwającym, kodem Cezara lub przesunięciem Cezariańskim) – w kryptografii jedna z najprostszych technik szyfrowania. Jest to rodzaj szyfru podstawieniowego, w którym każda litera tekstu jawnego (niezaszyfrowanego) zastępowana jest oddaloną od niej o stałą liczbę pozycji w alfabecie inną 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.

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.

Spis treści

Przykład

Sposó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 2) 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

Operację szyfrowania i deszyfrowania można wyrazić w języku arytmetyki modularnej. 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:

,

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.

Informacje historyczne

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.

Informacje na temat szyfru stosowanego przez Cezara pochodzą m.in. od Swetoniusza:

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, pisał podwójne A, o czym pisze Swetoniusz:

Istnieją źródła mówiące o tym, że Cezar używał również bardziej skomplikowanych systemów szyfrowania. Także pisarz rzymski Gelliusz nawiązuje do traktatu (obecnie zagubionego) na temat szyfrów rzymskiego wodza.

Zastosowanie

Szyfr 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.

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. 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.

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.

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.

Kryptoanaliza

Nie 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ą.

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:

  1. wiadomo (lub przypuszcza się), że zastosowano jakiś prosty szyfr podstawieniowy, ale nie wiadomo, czy jest to szyfr Cezara;
  2. 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. 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. Jednym ze sposobów uczynienia tego jest wypisanie fragmentu zaszyfrowanego tekstu w tabeli razem z jego wszystkimi możliwymi przesunięciami – technika zwana czasem "układaniem elementu jawnego" (ang. completing the plain component). 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. 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. 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.

Pokaż ten artykuł na Wikipedia.pl

Tekst udostępniany na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Zobacz szczegółowe informacje o warunkach korzystania.
Zasady zachowania poufności. O Wikipedii. Korzystasz z Wikipedii tylko na własną odpowiedzialność. Materiał pochodzący z Wikipedii został zmodyfikowany poprzez ograniczenie liczby przypisów. Wikipedia® is a registered tradmark of the Wikimedia Foundation.

Kategorie dla tego artykułu