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.

Szyfr Cezara – przykład zastosowania

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

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 kod ASCII. 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ękonkatenacjakonkatenację 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