Problem 1

Napisz program szyfrujący i deszyfrujący tekst przy użyciu szyfru Cezara. Przetestuj jego działanie dla wiadomości „JESIENNIE” i dla klucza równego 3.

Specyfikacja:

Dane:

  • klucz – liczba całkowita; wartość klucza szyfrowania

  • wiadomosc – ciąg znaków; wiadomość do zaszyfrowania zapisana dużymi literami

Wynik:

Program na wyjściu standardowym zwróci w jednej linii wiadomość zaszyfrowaną, a w drugiej – deszyfrowaną.

RpZhschTPTXhl
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Polecenie 1

Porównaj swoje rozwiązanie z przedstawionym w filmie.

R18Dq6UwlViqt1
Nagranie filmowe dotyczące szyfru Cezara - implementacji algorytmu szyfrowania i deszyfrowania wiadomości zapisanej alfabetem łacińskim.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

R13qEE6wiKU1G
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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

R1GnTbmlKmJEY
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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:

Linia 1. wyraz znak równości cudzysłów informatyka cudzysłów. Linia 2. zaszyfrowanyWyraz znak równości cudzysłów cudzysłów. Linia 3. klucz znak równości 4.

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

Linia 1. wyraz znak równości cudzysłów informatyka cudzysłów. Linia 2. zaszyfrowanyWyraz znak równości cudzysłów cudzysłów. Linia 3. klucz znak równości 4. Linia 5. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły wyraz zamknij nawias okrągły 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:

Linia 1. wyraz znak równości cudzysłów informatyka cudzysłów. Linia 2. zaszyfrowanyWyraz znak równości cudzysłów cudzysłów. Linia 3. klucz znak równości 4. Linia 5. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły wyraz zamknij nawias okrągły wykonuj. Linia 6. przesunietaLitera znak równości wartośćASCII otwórz nawias okrągły wyraz otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły plus klucz. Linia 7. poprawkaNaKoniecAlfabetu znak równości otwórz nawias okrągły przesunietaLitera minus wartośćASCII otwórz nawias okrągły apostrof a apostrof zamknij nawias okrągły zamknij nawias okrągły procent 26. Linia 8. zaszyfrowanaLitera znak równości znakZASCII otwórz nawias okrągły poprawkaNaKoniecAlfabetu plus wartośćASCII otwórz nawias okrągły apostrof a apostrof zamknij nawias okrągły zamknij nawias okrągły.

W omówionym pseudokodzie pojawiają się dwie funkcje: wartośćASCII()znakZASCII(). Pierwsza z nich zwraca wartość kodu ASCII podanego znaku. Druga zwraca znak o podanym kodzie ASCII.

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

Linia 1. wyraz znak równości cudzysłów informatyka cudzysłów. Linia 2. zaszyfrowanyWyraz znak równości cudzysłów cudzysłów. Linia 3. klucz znak równości 4. Linia 5. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły wyraz zamknij nawias okrągły wykonuj. Linia 6. przesunietaLitera znak równości wartośćASCII otwórz nawias okrągły wyraz otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły plus klucz. Linia 7. poprawkaNaKoniecAlfabetu znak równości otwórz nawias okrągły przesunietaLitera minus wartośćASCII otwórz nawias okrągły apostrof a apostrof zamknij nawias okrągły zamknij nawias okrągły procent 26. Linia 8. zaszyfrowanaLitera znak równości znakZASCII otwórz nawias okrągły poprawkaNaKoniecAlfabetu plus wartośćASCII otwórz nawias okrągły apostrof a apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 9. zaszyfrowanyWyraz znak równości zaszyfrowanyWyraz plus zaszyfrowanaLitera.

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

Słownik

kod ASCII
kod ASCII

 7‑bitowy system kodowania znaków, w którym każdy z obsługiwanych symboli jest reprezentowany przez liczbę; 7 bitów umożliwia przechowanie informacji o znakach o kodach z zakresu 0‑127; używany m.in. we współczesnych komputerach oraz sieciach komputerowych

konkatenacja
konkatenacja

łączenie ze sobą łańcuchów znaków

kryptoanaliza
kryptoanaliza

analiza systemu kryptograficznego w celu wyciągnięcia informacji przez niego utajnionych

kryptografia
kryptografia

nauka zajmująca się szyfrowaniem, czyli zamianą treści jawnej i dostępnej publicznie, na treść tajną, która może zostać odczytana tylko przez upoważnione jednostki

szyfr Cezara
szyfr Cezara

metoda utajniania tekstu, polegająca na zmianie liter z tekstu na litery położone w alfabecie określoną liczbę miejsc dalej