Szyfr Cezara w Pythonie i C++

Szyfr Cezara to jeden z najstarszych znanych szyfrów: według przekazów Juliusz Cezar używał go w korespondencji wojskowej. Każdą literę zastępujemy literą przesuniętą o stałą liczbę miejsc w alfabecie. Tę liczbę nazywamy kluczem. Z kluczem 3 słowo SZYFR zamienia się w VCBIU. Dziś taki szyfr nie chroni niczego, ale to idealny pierwszy algorytm na tekstach: łączy pętlę po napisie, kody znaków i resztę z dzielenia.

Na tej stronie znajdziesz szyfrowanie, odszyfrowanie, obsługę spacji i innych znaków oraz łamanie szyfru, w Pythonie i C++. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź szyfr Cezara krok po kroku

Idea: litery to liczby

Alfabet łaciński ma 26 liter. Jeśli ponumerujemy je od 0 (A = 0, B = 1, …, Z = 25), szyfrowanie staje się zwykłym dodawaniem: nowy numer = numer + klucz. Problem pojawia się na końcu alfabetu: Y (24) + 3 = 27, a litery numer 27 nie ma. Tu pomaga reszta z dzielenia przez 26: 27 % 26 = 1, czyli B. Alfabet zachowuje się jak tarcza zegara, na której po Z znowu jest A.

Komputer też widzi litery jako liczby. W Pythonie ord("A") daje 65 (kod znaku), a chr(65) zamienia kod z powrotem na “A”. Wielkie litery A-Z mają kolejne kody od 65 do 90, więc numer litery w alfabecie to ord(znak) - ord("A").

Szyfrowanie szyfrem Cezara w Pythonie

tekst = "ALGORYTM"
klucz = 3
szyfr = ""
for znak in tekst:
    numer = ord(znak) - ord("A")
    nowy = (numer + klucz) % 26
    szyfr += chr(nowy + ord("A"))
print(szyfr)

DOJRUBWP

Prześledźmy zmienne w każdym obrocie pętli:

Tylko przy Y reszta z dzielenia coś zmienia: tu alfabet “zawija się” na początek.

Odszyfrowanie i znaki spoza alfabetu

Odszyfrowanie to przesunięcie o minus klucz, więc wystarczy ta sama funkcja. Prawdziwa wiadomość ma też spacje i znaki interpunkcyjne. Te przepisujemy bez zmian, a szyfrujemy tylko wielkie litery:

def cezar(tekst, klucz):
    wynik = ""
    for znak in tekst:
        if "A" <= znak <= "Z":
            wynik += chr((ord(znak) - ord("A") + klucz) % 26 + ord("A"))
        else:
            wynik += znak
    return wynik


s = cezar("ATAK O SWICIE", 3)
print(s)
print(cezar(s, -3))

DWDN R VZLFLH
ATAK O SWICIE

W Pythonie reszta z dzielenia liczby ujemnej przez dodatnią jest zawsze nieujemna: (-2) % 26 to 24. Dlatego A (0) przesunięte o -3 daje poprawnie X (23).

Krokuj odszyfrowanie i znaki spoza alfabetu

Szyfr Cezara w C++

W C++ napis trzymamy w tablicy znaków char, a znak jest liczbą (kodem), więc nie potrzeba ord ani chr: t[i] - 'A' to numer litery, a 'A' + nowy z powrotem litera. Program zmienia tablicę w miejscu i kończy pętlę na znaku '\0':

#include <iostream>
using namespace std;

int main() {
  char t[] = "ALGORYTM";
  int klucz = 3;
  for (int i = 0; t[i] != '\0'; i++) {
    if (t[i] >= 'A' && t[i] <= 'Z') {
      int nowy = (t[i] - 'A' + klucz) % 26;
      t[i] = 'A' + nowy;
    }
  }
  cout << t << endl;
  return 0;
}

DOJRUBWP

Przy odszyfrowaniu C++ zachowuje się inaczej niż Python. Reszta z dzielenia liczby ujemnej jest w C++ ujemna, więc (0 - 3) % 26 to -3, a nie 23. Rozwiązanie: przed resztą dodać 26. Wtedy liczba jest zawsze dodatnia, a wynik się nie zmienia:

#include <iostream>
using namespace std;

void cezar(char t[], int klucz) {
  for (int i = 0; t[i] != '\0'; i++) {
    if (t[i] >= 'A' && t[i] <= 'Z') {
      int nowy = (t[i] - 'A' + klucz % 26 + 26) % 26;
      t[i] = 'A' + nowy;
    }
  }
}

int main() {
  cout << -3 % 26 << endl;
  char t[] = "SZYFR CEZARA";
  cezar(t, 3);
  cout << t << endl;
  cezar(t, -3);
  cout << t << endl;
  return 0;
}

-3
VCBIU FHCDUD
SZYFR CEZARA

Wyrażenie klucz % 26 chroni też przed kluczem większym niż 26 albo mniejszym niż -26: po nim do numeru dodajemy liczbę od -25 do 25, a +26 wystarczy, żeby suma nie była ujemna.

Łamanie szyfru Cezara

Kluczy, które coś zmieniają, jest tylko 25. Szyfr łamie się więc przez przeszukiwanie wyczerpujące (brute force): odszyfrowujemy wiadomość każdym kluczem i patrzymy, który wynik ma sens.

def cezar(tekst, klucz):
    wynik = ""
    for znak in tekst:
        if "A" <= znak <= "Z":
            wynik += chr((ord(znak) - ord("A") + klucz) % 26 + ord("A"))
        else:
            wynik += znak
    return wynik


szyfr = "GHTLR"
for k in range(1, 26):
    print(k, cezar(szyfr, -k))

1 FGSKQ
2 EFRJP
3 DEQIO
4 CDPHN
5 BCOGM
6 ABNFL
7 ZAMEK
8 YZLDJ
9 XYKCI
10 WXJBH
11 VWIAG
12 UVHZF
13 TUGYE
14 STFXD
15 RSEWC
16 QRDVB
17 PQCUA
18 OPBTZ
19 NOASY
20 MNZRX
21 LMYQW
22 KLXPV
23 JKWOU
24 IJVNT
25 HIUMS

Tylko klucz 7 daje polskie słowo: ZAMEK. Dla dłuższych wiadomości zamiast czytać 25 wersji można policzyć, która litera szyfrogramu występuje najczęściej, i założyć, że odpowiada najczęstszej literze języka (w polskich tekstach zwykle A, I albo E). To analiza częstości, pierwszy krok do łamania trudniejszych szyfrów podstawieniowych.

Krokuj łamanie szyfru wszystkimi kluczami

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Szyfr Cezara

Specyfikacja. Dane: tekst s (wielkie litery A-Z, inne znaki zostają bez zmian) i klucz k. Wynik: tekst zaszyfrowany (dla klucza -k: odszyfrowany).

Lista kroków:

1. Wczytaj tekst s i klucz k. Ustaw w na pusty napis.
2. Weź kolejny znak c tekstu s. Jeśli to wielka litera od A do Z, przesuń ją o k miejsc w alfabecie, za Z wracając do A: numer litery plus k, reszta z dzielenia przez 26.
3. Dopisz c na końcu napisu w.
4. Jeśli w tekście zostały znaki, wróć do kroku 2.
5. Wypisz w i zakończ.

Pseudokod:

wczytaj s, k
w ← ""
dla i = 1, 2, ..., długość(s) wykonuj
  c ← s[i]
  jeżeli c ≥ "A" i c ≤ "Z" to
    c ← znak((kod(c) - kod("A") + k) mod 26 + kod("A"))
  w ← w + c
wypisz w

Schemat blokowy:

Najczęstsze błędy

• Brak reszty z dzielenia. Bez % 26 litery z końca alfabetu wychodzą poza Z: Y + 3 daje znak \ (kod 92), a nie B.
• Ujemna reszta w C++. (numer - klucz) % 26 może być ujemne i daje znak sprzed A. Dodaj 26 przed resztą. W Pythonie tego problemu nie ma.
• Szyfrowanie spacji. Bez warunku "A" <= znak <= "Z" spacja (kod 32) też zostanie przesunięta i zamieni się w przypadkową literę albo znak.
• Zapomniane - ord("A"). (ord(znak) + klucz) % 26 liczy resztę z kodu znaku, a nie z numeru litery, więc wynik jest przesunięty o 65 % 26 = 13 miejsc.
• Małe litery. Małe a-z mają kody od 97 do 122 i potrzebują osobnej gałęzi z ord("a"). Polskie znaki (ą, ę, ś) leżą poza tymi zakresami, więc zwykle przepisuje się je bez zmian.

Ćwicz w przeglądarce

W temacie “Szyfr Cezara” kursu Algorytmy z podstawy programowej czekają trzy przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• zaszyfruj słowo kluczem 5,
• odszyfruj wiadomość,
• szyfr Cezara dla małych i wielkich liter.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości znak, numer i rosnącego szyfr. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Zamiana znaku na liczbę i z powrotem wraca przy systemach liczbowych, a przeszukiwanie po kolei wszystkich możliwości przy wyszukiwaniu liniowym i binarnym. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Szyfr Cezara dobrze sprawdza się jako zadanie dwuetapowe: najpierw szyfrowanie, potem łamanie cudzej wiadomości, co pokazuje uczniom, dlaczego mała liczba kluczy oznacza słaby szyfr. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.