Szyfr Cezara

🎯 Po co Ci to?

Swetoniusz, rzymski biograf, zanotował o Juliuszu Cezarze: „jeśli miał do przekazania coś poufnego, pisał szyfrem — zmieniał porządek liter tak, by nie dało się odczytać ani słowa". Metoda wodza: każdą literę zastąp literą o trzy miejsca dalej w alfabecie. Prymitywne? Z dzisiejszej perspektywy — tak. Ale na tym „prymitywie" nauczysz się całego słownika kryptografii: czym jest klucz, co robi szyfrowanie a co deszyfrowanie, i dlaczego o sile szyfru decyduje liczba możliwych kluczy. A operacja mod, którą polubisz w tej jednostce, okaże się dokładnie tą samą, którą znasz z parzystości i Euklidesa.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • szyfrować i deszyfrować tekst szyfrem Cezara z dowolnym przesunięciem (kluczem);
  • zapisać przesunięcie litery wzorem z mod — i wyjaśnić, po co „zawijanie" alfabetu;
  • złamać szyfr Cezara siłowo i wyciągnąć z tego lekcję o przestrzeni kluczy.

🔁 Przypomnij sobie

Z 2.5: znak ma numer (ord("a") = 97, chr(97) = „a"); z 3.2: % to reszta z dzielenia.

📘 Wyjaśnienie

Mechanika. Ustaw litery alfabetu na tarczy zegara. Szyfrowanie z kluczem $k$: przejdź od swojej litery $k$ pozycji do przodu. Kłopot pojawia się na końcu alfabetu: „z" przesunięte o 3 to… no właśnie — tarcza jest kołem, więc zawijamy na początek: x→a, y→b, z→c. Matematyka koła to mod:

$$\text{nowa pozycja} = (\text{pozycja} + k) \bmod 26$$

(dla alfabetu łacińskiego bez polskich znaków; pozycje 0–25). W kodzie tłumaczymy litery na pozycje i z powrotem:

def szyfruj(tekst, k):
    wynik = ""
    for znak in tekst.lower():
        if "a" <= znak <= "z":                       # szyfrujemy tylko litery
            poz = ord(znak) - ord("a")               # litera → pozycja 0-25
            nowa = (poz + k) % 26                    # przesunięcie z zawinięciem
            wynik = wynik + chr(nowa + ord("a"))     # pozycja → litera
        else:
            wynik = wynik + znak                     # spacje itd. bez zmian
    return wynik

szyfruj("ave caesar", 3) → dyh fdhvdu. Deszyfrowanie to cofnięcie przesunięcia — i tu drobna perełka: zamiast pisać osobną funkcję z odejmowaniem (i martwić się ujemnymi pozycjami), wystarczy… szyfrować w drugą stronę dookoła koła: szyfruj(zaszyfrowany, 26 - k). Cofnięcie o 3 = przejście o 23 do przodu. Koło nie zna kierunku „wstecz" — zna tylko dłuższą drogę.

📐 DEFINICJA — szyfr, klucz, szyfrogram: szyfr to para algorytmów (szyfrujący i deszyfrujący); klucz to parametr, od którego zależy wynik (u Cezara: wielkość przesunięcia); szyfrogram to tekst po zaszyfrowaniu.

Po ludzku: szyfr to zamek, klucz to klucz — zamek może być powszechnie znany, byle klucz był tajny. Czym NIE jest: tajność algorytmu nie jest fundamentem bezpieczeństwa. Od XIX wieku kryptografia wyznaje zasadę Kerckhoffsa: projektuj tak, jakby przeciwnik znał wszystko poza kluczem. Historia bezlitośnie karała tych, którzy ufali tajności metody.

Łamanie. I tu Cezar dostaje lekcję pokory. Kluczy jest ledwie 25 (przesunięcie o 0 nic nie robi, a o 26 = o 0). Przeciwnik próbuje wszystkich po kolei i patrzy, który wynik jest po łacinie… to znaczy — po polsku:

def zlam(szyfrogram):
    for k in range(1, 26):
        print(k, szyfruj(szyfrogram, 26 - k))        # wypisz wszystkie kandydatury

25 linijek, z których 24 to bełkot, a jedna — wiadomość. Taki atak nazywa się siłowym (brute force): sprawdź wszystko. Obrona przed nim jest tylko jedna — przestrzeń kluczy zbyt wielka do przejrzenia — i to jest najważniejsze zdanie tej jednostki. Pamiętasz rachunek z 2.7 (bity siły hasła)? 25 kluczy to $\log_2 25 \approx 4{,}6$ bita: mniej niż PIN z jedną cyfrą. Współczesne szyfry mają kluczy $2^{128}$ i więcej — nie dlatego, że ktoś lubi wielkie liczby, tylko dlatego, że przeciw atakowi siłowemu innej obrony nie ma.

🧮 Prześledź

Zaszyfruj ręcznie „gaul" kluczem $k = 5$, wypisując dla każdej litery pozycję, rachunek i wynik.

Sprawdź odpowiedź

g: poz 6, $(6+5) \bmod 26 = 11$ → l. a: 0 → 5 → f. u: 20 → 25 → z. l: 11 → 16 → q. Szyfrogram: lfzq. Kontrola deszyfrowaniem (przesunięcie 21): l→g ✓. Zwróć uwagę na „u→z": pozycja 25 to ostatnia litera, o włos od zawinięcia — dobre dane testowe zawsze zahaczają o brzeg tarczy (litery v–z przy dodatnim kluczu).

🐞 Znajdź błąd

Kolega uprościł: skoro litery to liczby, po co tłumaczyć na pozycje?

nowa = chr(ord(znak) + k)

Dla „ave" i $k=3$ dostaje „dyh" — działa! Wskaż dane, na których się wysypie, i wyjaśnij, co zgubił.

Sprawdź odpowiedź

Każda litera z końca alfabetu: „z" ($ord = 122$) plus 3 to $chr(125)$ = } — nawias klamrowy zamiast „c". Zgubił zawinięcie: dodawanie numerów działa tylko z dala od brzegu tarczy. Poprawka wymaga przejścia przez pozycje 0–25 i % 26 — dokładnie tego, co „uprościł". Morał dwuwarstwowy: (1) testuj brzegi (x, y, z!), (2) uproszczenie, które usuwa mod, zwykle usuwa też poprawność — koło bez zawijania to nie koło.

🕰️ Skąd to wiemy

Cezar używał przesunięcia o 3, jego następca August — o 1 (i to, jak zanotowano, bez zawijania: zamiast „z" pisał „aa" — cesarze też miewali problemy z przypadkiem brzegowym!). Szyfr przesuwający był używany na poważnie jeszcze w I wojnie światowej (armia rosyjska), a jego wariant ROT13 (przesunięcie o 13, samodeszyfrujące się, bo $13 + 13 = 26$) służył w internecie lat 80. do ukrywania spoilerów. Od zabawki dzieli go jedno: 4,6 bita klucza.

🛠️ Teraz Ty

Bez komputera: odszyfruj „fdhvdu" (wiesz, jakim kluczem szyfrował autor tej jednostki). Z komputerem: zaimplementuj szyfruj i zlam; zaszyfruj dowolne zdanie kluczem 17, oddaj koledze sam szyfrogram — i niech zlam znajdzie Twoją wiadomość. Zmierzcie, ile linijek wydruku trzeba było przeczytać, zanim oko wychwyciło polszczyznę.

📐 Definicje tej lekcji

  • Szyfr Cezara — podstawienie każdej litery literą o $k$ pozycji dalej, z zawinięciem: $(p + k) \bmod 26$; deszyfrowanie = klucz $26 - k$.
  • Atak siłowy / przestrzeń kluczy — sprawdzenie wszystkich kluczy; jedyna obrona to przestrzeń zbyt wielka do przejrzenia.

📌 Najważniejsze w pigułce

  • Alfabet to koło: mod 26 załatwia zawijanie, a deszyfrowanie to szyfrowanie dopełnieniem klucza.
  • Bezpieczeństwo mierz kluczami, nie sprytem: 25 kluczy = 4,6 bita = zero bezpieczeństwa.
  • Zasada Kerckhoffsa: algorytm jawny, klucz tajny — projektuj, jakby przeciwnik znał wszystko poza kluczem.

🎒 Zadania

  1. Odszyfruj „vog" wiedząc, że klucz to 10. Pokaż rachunek pozycji dla każdej litery.
Wskazówka i odpowiedź

Deszyfrowanie = szyfrowanie kluczem $26 - 10 = 16$. v: 21 → $(21+16) \bmod 26 = 11$ → l. o: 14 → $(14+16) \bmod 26 = 4$ → e. g: 6 → $(6+16) \bmod 26 = 22$ → w. Wiadomość: lew. Zwróć uwagę, że dwie z trzech liter wymagały zawinięcia ($37 \bmod 26$, $30 \bmod 26$) — przy deszyfrowaniu dopełnieniem klucza zawijanie jest chlebem powszednim, bo dopełnienie bywa duże.

  1. ROT13 szyfruje przesunięciem o 13. Udowodnij (rachunkiem na mod), że dwukrotne zaszyfrowanie ROT13 zwraca oryginał — i wyjaśnij, czemu taki „szyfr" bywa mimo wszystko użyteczny.
Wskazówka i odpowiedź

$(p + 13 + 13) \bmod 26 = (p + 26) \bmod 26 = p$ — dwa obroty o pół tarczy to pełny obrót. ROT13 nie chroni przed nikim (klucz znany, jeden), ale ukrywa przed przypadkowym wzrokiem: spoiler, puentę zagadki, wulgaryzm w cytacie. To uczciwe zastosowanie „szyfru zerowego bezpieczeństwa" — o ile nikt nie udaje, że to coś więcej.

  1. Zaprojektuj wariant Cezara dla pełnego polskiego alfabetu (34 litery z ą, ć, ę…). Co trzeba zmienić w kodzie, a co w matematyce? Czy szyfr stał się bezpieczniejszy?
Wskazówka i odpowiedź

Matematyka: mod 34 zamiast 26. Kod: nie można już liczyć na ciągłość numerów ord (polskie znaki nie sąsiadują z łacińskimi w Unicode!) — potrzebny jawny napis-alfabet "aąbcć…" i pozycja przez alfabet.find(znak). Bezpieczeństwo: 33 klucze zamiast 25 — wciąż ~5 bitów, wciąż zero. Powiększanie tarczy nie ratuje szyfru, którego problemem jest jeden wymiar klucza; ratunek (klucz-słowo zamiast klucz-liczba) pokaże jednostka 5.5.

🔍 Sprawdź, czy umiesz

  • Zaszyfrować i odszyfrować zdanie na kartce z dowolnym kluczem, z zawinięciem.
  • Wyjaśnić wzór $(p+k) \bmod 26$ i rolę każdego składnika.
  • Powiedzieć, ile bitów klucza ma Cezar i co z tego wynika.

Ucz się tej jednostki z asystentem