Szyfry podstawieniowe

Szyfr Cezara należy do tzw. szyfrów podstawieniowychszyfr podstawieniowyszyfrów podstawieniowych. Tego rodzaju algorytmy szyfrujące są proste w swoich założeniach – polegają na zamianie każdego znaku tekstu jawnegotekst jawnytekstu jawnego na inny znak (lub znaki).

Spróbujmy zaszyfrować tekst, korzystając z tej metody. Za tekst jawny niech posłuży nam słowo ROWER. Znaki będziemy podmieniać zgodnie z losowo stworzonym kluczem przedstawionym w tabeli Szyfrowanie.

Przykład 1

RHlrA1sxVBJex

Ilustracja przedstawia szyfr podstawowy słowa rower.
W pięć bloków wpisano litery ze słowa rower.
Od tych bloków wychodzi strzałka do bloku: szyfrowanie.
W pierwszym rzędzie znajdują się znaki: E, O, R, W.
W drugim rzędzie: S, 7, N, P.
Efekt końcowy wpisany jest w bloki na dole: N, 7, P, S, N.

W efekcie procesu szyfrowania nasz tekst jawny, czyli ROWER, został zamieniony na szyfrogramszyfrogramszyfrogram o treści N7PSN.

Działanie zaprezentowanego algorytmu polegało na zamianie liter tworzących dany wyraz na inne pojedyncze znaki. Warto pamiętać, że szyfry podstawieniowe nie zawsze bazują na zastępowaniu pojedynczego znaku innym pojedynczym znakiem. Może być tak, że pojedynczy znak zastępowany jest parą lub grupą znaków. Istnieje nawet możliwość przypisania do jednego znaku zbioru znaków bądź ich grup – wówczas ten sam tekst możemy zaszyfrować na wiele sposobów. Spróbujmy zrobić coś takiego ze słowem KOT.

Przykład 2

Rhxn0EdkccJZH

Ilustracja przedstawia szyfr podstawowy słowa rower.
W trzy bloki wpisano litery ze słowa kot.
Od tych bloków wychodzi strzałka do bloku: szyfrowanie.
W pierwszym rzędzie znajdują się znaki: K, O, T.
W drugim rzędzie: R, 12, 8, B, L, P.
Efekt końcowy wpisany jest w bloki na dole: 12, 8, P. R, 8, L. R, B, P.

Każdej literze znajdującej się w wyrazie KOT przypisaliśmy dwa możliwe znaki lub grupy znaków – dzięki temu efekt szyfrowania nie będzie za każdym razem jednakowy. Oznacza to, że każdy z uzyskanych ciągów znaków, może posłużyć nam jako ostateczny szyfrogram. Wypisaliśmy przykładowe trzy teksty zaszyfrowane przy użyciu dowolnego z dwóch przypisanych znaków lub grup znaków. Całkowita liczba możliwych szyfrogramów wynosi 8. Taki typ szyfrowania podstawieniowego jest znacznie trudniejszy do złamania niż jednoznaczny szyfr użyty w przypadku słowa ROWER.

Uogólniony szyfr Cezara

Szyfr Cezara to nieskomplikowany algorytm stworzony w celu zabezpieczenia treści prywatnej korespondencji. W miejsce każdej kolejnej litery wstawiana była inna, przesunięta o określoną liczbę miejsc w alfabecie (wartość tego przesunięcia nazywana jest kluczem). Ewentualne znaki interpunkcyjne nie były szyfrowane, podobnie jak nie uwzględniano wielkości liter. Istotne było natomiast zachowanie stałego kierunku kolejnych przesunięć, zależnego od wartości klucza:

• $n=0$ – przesunięcie nie następuje,

• $n>0$ – przesunięcie w prawo,

• $n<0$ – przesunięcie w lewo,

• $n$ – wartość przesunięcia.

Według części źródeł historycznych, oryginalny szyfr stosowany w korespondencji Juliusza Cezara zakładał stałą wartość przesunięcia równą 3, jednak uogólniona wersja tego algorytmu umożliwia dobranie dowolnej wartości klucza.

Skoro znamy już dokładne działanie algorytmu, spróbujmy zaszyfrować słowo RZYM przy użyciu pierwotnej wersji szyfru Cezara oraz alfabetu łacińskiego.

Przykład 3

R1XMYnH7krbU2

Ilustracja przedstawia szyfr Cezara słowa RZYM
W cztery bloki wpisano litery ze słowa Rzym.
Od tych bloków wychodzi strzałka do bloku: szyfrowanie.
Od bloku z literą M wychodzi strzałka wskazująca na literę P, od bloku z literą R wychodzi strzałka wskazująca na blok z literą U, od bloków Y, Z wychodzą strzałki do bloków z literami: B, C.
Poniżej znajduje się alfabet w blokach.
Od Bloku szyfrowania wychodzi strzałka z efektem końcowym: UCBP.

Każdą literę zawartą w wyrazie RZYM zastąpiliśmy literą oddaloną od niej w alfabecie o trzy pozycje w prawo. W wyniku tej operacji otrzymaliśmy zaszyfrowane słowo UCBP. Aby je odszyfrować, stosujemy analogiczną zamianę liter, tylko tym razem będzie to przesunięcie w lewo (klucz przyjmie wartość -3).

R1ja0CgU1kSJH

Ilustracja przedstawia odszyfrowanie słowa RZYM z szyfru Cezara
W cztery bloki wpisano litery: UCBP.
Od tych bloków wychodzi strzałka do bloku: Deszyfrowanie.
Od bloku z literą P wychodzi strzałka wskazująca na literę M, od bloku z literą U wychodzi strzałka wskazująca na blok z literą R, od bloków B, C wychodzą strzałki do bloków z literami: Y, Z.
Poniżej znajduje się alfabet w blokach.
Od Bloku szyfrowania wychodzi strzałka z efektem końcowym: Rzym.

Po przeanalizowaniu tych przykładów widzimy, że do odkodowania otrzymanej wiadomości potrzebujemy znać jedynie wartości przesunięcia, czyli klucz.

Co jednak w sytuacji, gdy wartość przesunięcia wykracza poza liczbę znaków w alfabecie? Otóż charakterystyczną cechą szyfru Cezara jest zapętlenie alfabetu, w wyniku czego po ostatniej literze znów występuje litera pierwsza oraz kolejne, zajmujące pozycje na prawo od niej. Jest to niezbędne, by umożliwić zaszyfrowanie, np. litery Z przy dodatniej wartości klucza. Ma to zasadnicze znaczenie również w przypadku przesunięcia, którego wartość bezwzględna jest większa niż liczba znaków w alfabecie.

Przykład 4

Załóżmy, że wartość klucza wynosi 31, a literą wybraną do zaszyfrowania jest D. Jak wiemy, alfabet łaciński zawiera 26 liter (bez użycia polskich znaków, np. „ą”), zatem od litery D do końca alfabetu dzielą nas tylko 23 pozycje. Co dalej? Spójrzmy na poniższy przykład.

R9a98fxw1NjwY

Ilustracja przedstawia szyfr cezara z alfabetem przesuniętym o 23 pozycje.
W blok wpisano literę D.
Wychodzi od niej strzałka podpisana: Przesunięcie o 23 pozycje w prawo.
Strzałka ta wskazuje na blok z literą Z.
Poniżej znajduje się blok z wpisaną literą D.
Wychodzi od niej strzałka podpisana: Przesunięcie o 26 pozycji w prawo.
Wskazuje on na literę: D.
Poniżej znajduje się blok z literą D.
Wychodzi od niej strzałka z podpisem: Przesunięcie o 31 pozycji w prawo.
Strzałka ta wskazuje na blok z literą I.

Jak widzimy, w momencie przesunięcia o 26 pozycji (czyli pełną liczbę znaków w alfabecie łacińskim) wracamy do punktu wyjścia – otrzymujemy taki sam rezultat jak w przypadku braku zmiany pozycji (gdyby wartość klucza była równa 0). Natomiast przesunięcie zgodnie z kluczem o 31 pozycji daje identyczny wynik jak przesunięcie o 5 miejsc. Oznacza to, że nie musimy za każdym razem analizować tak długiego przesunięcia, a jedynie przeprowadzić następujące działanie:

gdzie:

• $a$ – liczba liter w alfabecie,

• $b$ – podana wartość klucza,

• $n$ – wartość klucza $<a$.

Wynik będzie taki sam, jak przy użyciu klucza $b$.

Nowa wartość klucza jest więc po prostu resztą z dzielenia podanej wartości klucza przez liczbę liter w alfabecie. W ten sposób niejako omijamy niepotrzebne przesunięcia wykonane wokół „alfabetowej pętli”. Analizując przedstawione przykłady, możemy wyznaczyć wzór na pozycję zaszyfrowanej litery w alfabecie.

gdzie:

• $P_l$ – pozycja litery w alfabecie przed zaszyfrowaniem,

• $P_{sz}$ – pozycja litery w alfabecie po zaszyfrowaniu.

Analogicznie wyznaczymy wzór na pozycję litery w alfabecie przed zaszyfrowaniem.

Algorytm ten jest prosty w implementacji i zastosowaniu, jednak tym samym łatwo go złamać, przez co nie gwarantuje on wysokiego poziomu bezpieczeństwa.

Pseudokod

Zapiszmy program szyfrowania oraz deszyfrowania, w którym wykorzystamy uogólniony szyfr Cezara. Zapiszemy go za pomocą pseudokodu.

Szyfrowanie

Specyfikacja problemu:

Dane:

• tekst – ciąg znaków do zaszyfrowania

• klucz – liczba całkowita określająca przesunięcie

Wynik:

• ciąg znaków reprezentujący zaszyfrowany tekst zapisany za pomocą wielkich liter

Zaczniemy od zapisania funkcji szyfruj.

Funkcja przyjmie dwa argumenty – tekst oraz klucz. ZnormalizujemynormalizacjaZnormalizujemy wartość klucza.

W następnym kroku utworzymy zmienną zaszyfrowanyTekst i przypiszemy jej pusty łańcuch znaków. Ta zmienna będzie przechowywać zaszyfrowany przez nas tekst.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
	zaszyfrowanyTekst ← ""

Tworzymy pętlę dla, za pomocą będziemy przeglądać wszystkie elementy łańcucha znaków tekst. W pętli tworzymy zmienną znak, której przypiszemy wartość sprawdzanego znaku łańcucha znaków tekst.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
    zaszyfrowanyTekst ← ""

    dla indeks od 0 do długość(tekst) - 1 wykonaj:
        znak ← tekst[indeks]

Zapisujemy instrukcję warunkową. Będziemy sprawdzać, czy analizowany znak jest wielką literą. Robimy to, ponieważ zaszyfrowany łańcuch znaków powinien być zapisany za pomocą wielkich liter.

Zatem jeśli analizowany znak jest małą literą (czyli jego kod ASCII należy do zakresu wyznaczonego przez kody liter a oraz z), zamienimy go na wielką literę za pomocą odpowiedniej instrukcji.

Od wartości kodu ASCII analizowanego znaku odejmujemy 32. Następnie otrzymany wynik przekształcamy ponownie do znaku za pomocą funkcji znakZKodu i przypisujemy zmiennej znak.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
    zaszyfrowanyTekst ← ""

    dla indeks od 0 do długość(tekst) - 1 wykonaj:
        znak ← tekst[indeks]
        
        jeżeli kodZnaku('a') <= kodZnaku(znak) <= kodZnaku('z') wykonaj:
            znak ← znakZKodu(kodZnaku(znak) - 32)

W kolejnym kroku sprawdzamy, czy analizowany znak jest wielką literą alfabetu łacińskiego, czyli czy wartość jego kodu ASCII należy do przedziału wyznaczonego przez wartości kodów ASCII liter A oraz Z.

Jeśli tak, szyfrujemy go, wykorzystując podaną wartość przesunięcia przechowywaną w zmiennej klucz.

Robimy to, od kodu ASCII znaku przechowywanego w zmiennej znak odejmując wartość kodu ASCII litery A (czyli 65), a następnie dodając wartość klucza. W kolejnym kroku obliczamy resztę z dzielenia otrzymanego wyniku przez liczbę 26. Do otrzymanego wyniku dodajemy kod znaku A (65). Całość ponownie przekształcamy, wykorzystując funkcję znakZKodu i otrzymaną literę przypisujemy zmiennej zaszyfrowanyZnak. Wartość zmiennej zaszyfrowanyZnak dodajemy na końcu łańcucha znaków zaszyfrowanyTekst.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
    zaszyfrowanyTekst ← ""

    dla indeks od 0 do długość(tekst) - 1 wykonaj:
        znak ← tekst[indeks]
        
        jeżeli kodZnaku('a') <= kodZnaku(znak) <= kodZnaku('z') wykonaj:
            znak ← (kodZnaku(znak) - kodZnaku('a') + kodZnaku('A'))
        jeżeli kodZnaku('A') <= kodZnaku(znak) <= kodZnaku('Z') wykonaj:
            zaszyfrowanyZnak ← ((kodZnaku(znak) - kodZnaku('A') + klucz) mod 26 + kodZnaku('A')) przekształcony na znak
            zaszyfrowanyTekst ← zaszyfrowanyTekst + zaszyfrowanyZnak

Jeśli analizowany znak nie jest wielką literą, nie szyfrujemy go i przypisujemy do zmiennej zaszyfrowanyZnak. Następnie wartość zmiennejzaszyfrowanyZnak dodajemy na koniec łańcucha znaków zaszyfrowanyTekst.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
    zaszyfrowanyTekst ← ""

    dla indeks od 0 do długość(tekst) - 1 wykonaj:
        znak ← tekst[indeks]
        
        jeżeli kodZnaku('a') <= kodZnaku(znak) <= kodZnaku('z') wykonaj:
            znak ← (kodZnaku(znak) - kodZnaku('a') + kodZnaku('A'))
        jeżeli kodZnaku('A') <= kodZnaku(znak) <= kodZnaku('Z') wykonaj:
            zaszyfrowanyZnak ← ((kodZnaku(znak) - kodZnaku('A') + klucz) mod 26 + kodZnaku('A')) przekształcony na znak
            zaszyfrowanyTekst ← zaszyfrowanyTekst + zaszyfrowanyZnak
        w przeciwnym razie:
            zaszyfrowanyTekst ← zaszyfrowanyTekst + znak

Zwracamy zaszyfrowany łańcuch znaków.

funkcja szyfruj(tekst, klucz):
    klucz ← (klucz mod 26 + 26) mod 26
    zaszyfrowanyTekst ← ""

    dla indeks od 0 do długość(tekst) - 1 wykonaj:
        znak ← tekst[indeks]
        jeżeli kodZnaku('a') <= kodZnaku(znak) <= kodZnaku('z') wykonaj:
            znak ← (kodZnaku(znak) - kodZnaku('a') + kodZnaku('A')) przekształcony na znak
        jeżeli kodZnaku('A') <= kodZnaku(znak) <= kodZnaku('Z') wykonaj:
            zaszyfrowanyZnak ← ((kodZnaku(znak) - kodZnaku('A') + klucz) mod 26 + kodZnaku('A')) przekształcony na znak
            zaszyfrowanyTekst ← zaszyfrowanyTekst + zaszyfrowanyZnak
        w przeciwnym razie:
            zaszyfrowanyTekst ← zaszyfrowanyTekst + znak

    zwróć zaszyfrowanyTekst

Deszyfrowanie

Specyfikacja problemu:

Dane:

• zaszyfrowany_tekst – ciąg znaków do odszyfrowania

• klucz – liczba całkowita określająca przesunięcie

Wynik:

• odszyfrowany łańcuch znaków

Zapiszmy funkcję deszyfrującą. Szyfr Cezara jest szyfrem symetrycznym – do szyfrowania i deszyfrowania używamy tego samego klucza, oraz podstawieniowym – polega na zastępowaniu znaku przesuniętym w zapętlonym alfabecie o długość klucza innym znakiem. Z tego wynika, że deszyfrowanie to operacja odwrotna do szyfrowania i polega na przesuwaniu znaku w zapętlonym alfabecie w odwrotnym kierunku niż podczas szyfrowania.

Funkcja deszyfrująca wygląda następująco:

funkcja deszyfruj(zaszyfrowanyTekst, klucz):
    klucz ← (-klucz mod 26 + 26) mod 26
    odszyfrowanyTekst ← ""

    dla indeks od 0 do długość(zaszyfrowanyTekst) - 1 wykonaj:
        znak ← zaszyfrowanyTekst[indeks]
        jeżeli kodZnaku('a') <= kodZnaku(znak) <= kodZnaku('z') wykonaj:
            znak ← znakZKodu(kodZnaku(znak) - 32)
        jeżeli kodZnaku('A') <= kodZnaku(znak) <= kodZnaku('Z') wykonaj:
            odszyfrowanyZnak ← znakZKodu((kodZnaku(znak) - kodZnaku('A') + klucz) mod 26 + kodZnaku('A'))
            odszyfrowanyTekst ← odszyfrowanyTekst + odszyfrowanyZnak
        w przeciwnym razie:
            odszyfrowanyTekst ← odszyfrowanyTekst + znak

    zwróć odszyfrowanyTekst

Alfabet jawny i alfabet szyfrowy

Istotnymi pojęciami związanymi z szyfrem Cezara są alfabet jawny oraz alfabet szyfrowy. Alfabet jawny jest po prostu standardowym alfabetem wykorzystywanym w pisaniu tekstu jawnego, natomiast alfabet szyfrowy zawiera te same litery co alfabet jawny, jednakże są one przesunięte o ustaloną wartość klucza. W ten sposób na pierwszej pozycji w alfabecie szyfrowym znajduje się litera będąca w alfabecie jawnym na pozycji 1 + wartość przesunięcia. Przy zestawieniu wszystkich pozycji tego alfabetu z pozycjami o tych samych numerach alfabetu jawnego otrzymamy prostą tabelę. Dzięki niej bardzo szybko możemy odczytać, jakie znaki tekstu jawnego i szyfrogramu wzajemnie sobie odpowiadają, a tym samym skrócić czas szyfrowania i deszyfrowania.

Słownik