Imprerium Rzymskie, I w. p.n.e. Państwem włada Juliusz Cezar.Juliusz CezarJuliusz Cezar. Przypuszcza się, że do komunikowania się ze swoimi przyjaciółmi używał szyfru, który później zyskał miano szyfru Cezara. W jaki sposób szyfrowano informacje w starożytności?

Szyfr przesuwający

Pod pojęciem „szyfr Cezara” kryje się szyfr przesuwający. To niezwykle prosta technika, będąca szczególnym przypadkiem szyfru podstawieniowegoszyfr podstawieniowyszyfru podstawieniowego, w której każdy znak szyfrowanej wiadomości jest zastępowany innym, oddalonym od niego w alfabecie o określoną odległość. W przypadku tego algorytmu ignoruje się wielkość liter.

Na czym polega szyfr Cezara?

Szyfr Cezara jest szyfrem podstawieniowym, służącym do utajniania tekstów. Oznacza to, że każda litera w szyfrowanym ciągu znaków zastępowana jest inną, oddaloną w alfabecie o pewną stałą liczbę miejsc. Odległość, o którą oddalone są litery zastępowana i zastępująca, nazywa się kluczem szyfru.

Posłużmy się przykładem. Przyjmijmy, że używając klucza równego 4 chcemy zaszyfrować literę „a”. Musimy ją więc zastąpić literą położoną o 4 miejsca dalej w alfabecie:

R5QIyoN50rFJm

Ilustracja przedstawia ciąg liter: a b c d e f g ... Od a do e nad szeregiem biegnie strzałka, nad strzałką jest napis: 4 miejsca w prawo.

Po zaszyfrowaniu litera „a” stanie się literą „e”. Tekst zapisany w taki sposób jest w stanie odkodować tylko osoba znająca metodę szyfrowania i rozmiar klucza.

Ponieważ alfabet łaciński składa się z 26 liter, a zastosowanie klucza równego zero nie powoduje zastąpienia jednych znaków innymi, możemy zakodować tekst tylko na 25 sposobów. W rezultacie szyfr Cezara jest dość łatwy do złamania, nawet gdy nie znamy użytego klucza.

Spróbujmy teraz zaszyfrować literę „z”, używając klucza 5. Ponieważ „z” jest ostatnią literą alfabetu, nie możemy jej zastąpić inną, położoną o choćby jedno miejsce dalej. W takiej sytuacji zaczynamy odliczanie od początku alfabetu:

R1aiKwmIuzMnR

Ilustracja przedstawia ciąg liter: z a b c d e f ... Od z do e  nad szeregiem biegnie strzałka, nad strzałką jest napis: 5 miejsc w prawo.

Litera „z” po zaszyfrowaniu zamieni się zatem w literę „e”.

Jak już wspominaliśmy, klucz może przybrać tylko 25 wartości, aby jedne litery w tekście zostały zastąpione innymi. Wynika to z liczby znaków alfabetu łacińskiego. Dlaczego jednak nie zastosować klucza o wartości większej niż 25?

Otóż jeżeli użyjemy klucza o wartości 27, tekst wciąż będzie szyfrowany, ale osiągniemy taki sam wynik jak w przypadku zastosowania klucza o wartości 1. Klucz równy 28 odpowiada kluczowi wynoszącemu 2 itd. W rezultacie mamy do dyspozycji tylko 25 kluczy.

Przykład I

Spróbujmy zaszyfrować słowo „ser”, używając klucza równego 3. Zaczniemy od pierwszej litery, czyli „s”:

R1QGEY6E9r4P5

Ilustracja przedstawia ciąg liter: ... s t u v w x ... Od s do v nad szeregiem biegnie strzałka, nad strzałką jest napis: 3 miejsca w prawo.

Litera „s” zostanie zastąpiona przez „v”. Następna jest litera „e”:

R13qEE6wiKU1G

Ilustracja przedstawia ciąg liter: ... e f g h i j ... Od e do h nad szeregiem biegnie strzałka, nad strzałką jest napis: 3 miejsca w prawo.

W tym przypadku nowym znakiem jest „h”. Pozostało nam jeszcze zaszyfrować literę „r”:

R1GnTbmlKmJEY

Ilustracja przedstawia ciąg liter: ... r s t u v w ... Od r do u nad szeregiem biegnie strzałka, nad strzałką jest napis: 3 miejsca w prawo.

Ostatecznie słowo „ser”, zakodowane za pomocą szyfru Cezara o kluczu równym 3, zmienia się w wyraz „vhu”. Jeżeli każdy jego znak zastąpimy literą o trzy pozycje wcześniejszą (czyli przesuniemy je „w lewo” o wartość klucza), odszyfrujemy ciąg, otrzymując ponownie słowo „ser”.

Przykład II

Posłużymy się jeszcze jednym przykładem, aby sprawdzić, jak działa taka technika. Załóżmy, że chcemy zorganizować niespodziewane przyjęcie urodzinowe dla naszego kolegi. Musimy wysłać wiadomość do jego znajomych, kiedy wyjdzie z domu, ale nie chcemy, by przypadkiem ją odczytał. Umówiliśmy się, że zakodujemy wiadomość jak Juliusz Cezar, który stosował przesunięcie o trzy pozycje do przodu. W przypadku tego algorytmu jest to klucz szyfru.

Przygotujemy sobie wiadomość do zaszyfrowania, czyli tekst jawny:

Tekst jawny: MIESZKANIE OTWARTE WRACAMY ZA GODZINĘ

Polski alfabet liczy 32 litery, zatem przesuwając cały alfabet o trzy pozycje, otrzymamy następujący szyfr:

Alfabet:	AĄBC ĆDEĘ FGHI JKLŁ MNŃO ÓPRS ŚTUW YZŹŻ
Szyfr:		CĆDE ĘFGH IJKL ŁMNŃ OÓPR SŚTU WYZŹ ŻAĄB

Podmieniając każdą literę tekstu jawnego jej zaszyfrowanym odpowiednikiem, otrzymamy następujący wynik, czyli tekst zaszyfrowany:

Tekst jawny:
	MIESZKANIE OTWARTE WRACAMY ZA GODZINĘ
    
Tekst zaszyfrowany:
	OLGUAMCÓLG RYŹCTYG ŹTCECOŻ AC JRFALÓH

Tak zaszyfrowany tekst wygląda jak przypadkowa wiadomość, ale może zawierać istotne informacje – w tym wypadku czas, jaki pozostał do powrotu kolegi do domu. Niestety, ze względu na swoją prostotę szyfr Cezara znajduje zastosowanie jedynie tam, gdzie nie zależy nam na gwarancji bezpieczeństwa komunikacji. Czasem bywa również fragmentem bardziej złożonych algorytmów szyfrujących.

Odszyfrowanie wiadomości to operacja odwrotna do wykonanej na początku. Zatem jeśli wiadomość zaszyfrowano, przesuwając alfabet o trzy pozycje do przodu, to rozszyfrowanie sprowadza się do przesunięcia go o trzy pozycje do tyłu.

KryptoanalizakryptoanalizaKryptoanaliza

Istnieją dwie techniki łamania szyfru Cezara, zależne od tego, czy jesteśmy pewni, że to właśnie on został użyty. Przyjrzyjmy się najpierw przypadkowi, w którym wiemy, że użyto szyfru Cezara.

Liczbę możliwych przesunięć możemy wyrazić wzorem:

$L=n-1$

gdzie n jest liczbą znaków w alfabecie; w przypadku języka polskiego mamy do dyspozycji 32 litery.

W przypadku alfabetu łacińskiego mowa już tylko o 26 znakach. Jedno przesunięcie możemy pominąć, ponieważ wiadomość znajduje się już w stanie początkowym. Oczywiście moglibyśmy użyć znacznie bardziej skomplikowanego alfabetu i utrudniłoby to ręczne odszyfrowanie wiadomości. Programistycznie jednak przypadek ten sprowadza się do metody siłowej, gdzie w prosty sposób jesteśmy w stanie uzyskać wszystkie możliwe przesunięcia, a wśród nich będzie również to prawidłowe. Podchodząc do problemu matematycznie, moglibyśmy przyjąć, że każda litera alfabetu oznaczona jest liczbą, na przykład A→0, Ą→1, B→2. Szyfrowanie moglibyśmy zatem zapisać w postaci następującego równania:

$S_i=(x_i+t)modn$

gdzie:
SIndeks dolny i_i – numer litery po zaszyfrowaniu,
xIndeks dolny i_i – przyporządkowany numer litery,
t – przesunięcie,
mod – operator reszty z dzielenia (modulo),
n – liczba znaków w alfabecie.

Używając tego równania, moglibyśmy skonstruować następujący pseudokod:

dla t = 0, 1, 2 ... n - 1 wykonuj:
	przesuń każdy znak o t pozycji

A co zrobić, jeśli słowo było wielokrotnie szyfrowane? Przesunięcia się sumują, zatem przesunięcie o 10 do przodu, 3 do tyłu i 5 do przodu w rzeczywistości sprowadza się do jednego przesunięcia o 12 do przodu. Jedynym przypadkiem, w którym rozszyfrowanie może nie być skuteczne, są bardzo krótkie wiadomości. Dla nich może istnieć więcej niż jedno rozwiązanie.

Drugą techniką łamania szyfru jest sytuacja, w której nie mamy pewności, czy użyto szyfru Cezara. Stosuje się wtedy te same metody, co w przypadku innych szyfrów podstawieniowych, np. wykorzystuje się statystykę. Litery w różnych językach pojawiają się z pewnym prawdopodobieństwem. W języku polskim najczęściej występują litery A, I, O oraz E. Zatem w zaszyfrowanej wiadomości można czasem odnaleźć pewną zależność i wywnioskować, że użyto właśnie szyfru Cezara.

Szyfr Cezara – pseudokod

Skoro wiemy już jak działa szyfr Cezara, spróbujmy zapisać jego algorytm w pseudokodzie, który później przełożymy na język Python. Zaczniemy od zdefiniowania kilku zmiennych:

wyraz = "informatyka"
zaszyfrowanyWyraz = ""
klucz = 4

Następną czynnością jest odczytanie poszczególnych liter szyfrowanego wyrazu (musimy bowiem zakodować każdy znak osobno):

wyraz = "informatyka"
zaszyfrowanyWyraz = ""
klucz = 4

dla i = 0, 1, ..., długość(wyraz) wykonuj

W jaki sposób zastąpimy („przesuniemy w prawo”) litery składające się na wyraz? Przypomnijmy sobie, czym jest kodkod ASCIIkodASCIIkod ASCIIASCII. Każdy zapisany w tym systemie znak ma przyporządkowany odpowiednik liczbowy. Litery są uporządkowane alfabetycznie („a” ma przypisaną wartość 97, zaś „z” – 122). Wystarczy zatem dodać wartość klucza do liczby odpowiadającej literze w kodzie ASCII. Otrzymamy nowy kod, który odpowiada zaszyfrowanej literze.

Niestety, napotkamy wówczas pewien problem. Co się stanie, gdy – przykładowo –  będziemy chcieli przesunąć literę „z” o 3 miejsca dalej?

Liczbowy zapis „z” w kodzie ASCII to 122. Po dodaniu do niego liczby 3, nie otrzymamy litery „c” – jej wartość w kodzie ASCII wynosi 99. Zamiast tego uzyskamy symbol } (prawy nawias klamrowy) – właśnie jemu w kodzie ASCII odpowiada liczba 125.

Aby rozwiązać taki problem, musimy najpierw odjąć od sumy (wynoszącej w opisywanym przypadku 125) wartość litery „a” w kodzie ASCII. Następnie obliczamy resztę z dzielenia otrzymanej różnicy przez 26. Na koniec do wyniku dodajemy ponownie wartość litery „a” w kodzie ASCII.

W rezultacie po otrzymaniu kodu ASCII spoza zakresu odpowiadającego literom łacińskim, znak zostanie przeniesiony na początek alfabetu:

wyraz = "informatyka"
zaszyfrowanyWyraz = ""
klucz = 4

dla i = 0, 1, ..., długość(wyraz) wykonuj
przesunietaLitera = wartośćASCII(wyraz[i]) + klucz
poprawkaNaKoniecAlfabetu = (przesunietaLitera - wartośćASCII('a')) % 26
zaszyfrowanaLitera = znakZASCII(poprawkaNaKoniecAlfabetu + wartośćASCII('a'))

Pozostaje jeszcze zastosować konkatenację w celu dopisania zaszyfrowanej litery do wyrazu:

wyraz = "informatyka"
zaszyfrowanyWyraz = ""
klucz = 4

dla i = 0, 1, ..., długość(wyraz) wykonuj
przesunietaLitera = wartośćASCII(wyraz[i]) + klucz
poprawkaNaKoniecAlfabetu = (przesunietaLitera - wartośćASCII('a')) % 26
zaszyfrowanaLitera = znakZASCII(poprawkaNaKoniecAlfabetu + wartośćASCII('a'))
zaszyfrowanyWyraz = zaszyfrowanyWyraz + zaszyfrowanaLitera

W kolejnej sekcji przełożymy pseudokod na instrukcje w języku Python.

Słownik