Łamanie szyfrów — analiza częstości i Vigenère

🎯 Po co Ci to?

IX wiek, Bagdad. Filozof Al-Kindi opisuje metodę, która na tysiąc lat przesądzi los szyfrów podstawieniowych: nie próbuj kluczy — policz litery. Każdy język ma swój odcisk palca: w polszczyźnie „a" i „i" pojawiają się dziesięć razy częściej niż „ń". Podstawienie zmienia litery, ale częstości przenosi żywcem — wystarczy je zdjąć jak odcisk daktyloskopijny. Dziś zostaniesz łamaczem: najpierw położysz na łopatki Cezara jednym histogramem, potem zmierzysz się z szyfrem, który przez 300 lat nosił dumny tytuł „le chiffre indéchiffrable" — nie do złamania. Spoiler: dziś złamiesz i jego.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• policzyć histogram częstości liter i użyć go do automatycznego złamania Cezara;
• zaszyfrować i odszyfrować tekst szyfrem Vigenère'a (klucz-słowo);
• wyjaśnić, dlaczego Vigenère opiera się prostej analizie częstości — i jak mimo to pada.

🔁 Przypomnij sobie

Z 5.1: zliczanie liter przebiegiem po alfabecie; z 5.3: Cezar to $(p+k) \bmod 26$, kluczy 25; z 5.4: co szyfrogram „przecieka".

📘 Wyjaśnienie

Odcisk palca języka. Policz wystąpienia każdej litery w dowolnym dłuższym polskim tekście i podziel przez długość — dostaniesz zawsze niemal ten sam profil: a (~9%), i (~8%), o (~8%), e (~7,5%), z (~6%)… a na ogonie ń, ź, f poniżej pół procenta. Profil jest stabilny jak grupa krwi: nie zależy od autora ani tematu (chyba że tekst jest wyjątkowo krótki albo wyjątkowo dziwny — patrz ⚠️).

Łamanie Cezara statystyką. Skoro Cezar przesuwa wszystkie litery o ten sam klucz $k$, to przesuwa też cały histogram: szczyt, który w polszczyźnie stoi nad „a", w szyfrogramie stanie nad literą $(0 + k) \bmod 26$. Łamacz liczy histogram szyfrogramu, patrzy, gdzie wylądował szczyt — i odczytuje klucz bez próbowania:

def zlam_cezara(szyfrogram):
    najlepsza = None
    for znak in "abcdefghijklmnopqrstuvwxyz":
        ile = szyfrogram.count(znak)
        if najlepsza is None or ile > szyfrogram.count(najlepsza):
            najlepsza = znak
    k = (ord(najlepsza) - ord("a")) % 26          # zakładamy: najczęstsza = "a"
    return k

(Wersja przemysłowa porównuje cały profil, nie tylko szczyt — pojedyncza najczęstsza litera bywa zdradliwa w krótkich tekstach; ale idea jest dokładnie ta.) Zauważ, co się stało: atak siłowy z 5.3 czytał 25 kandydatur ludzkim okiem — statystyka wybiera klucz sama. Automatyzacja łamania to moment, w którym kryptoanaliza staje się informatyką.

Vigenère: Cezar w wielu osobach. Skoro jeden klucz przecieka przez histogram — weź wiele kluczy naraz. Klucz Vigenère'a to słowo; jego litery to kolejne przesunięcia Cezara, stosowane cyklicznie:

tekst:   t a j n a w i a d o m o s c
klucz:   b o r b o r b o r b o r b o     (klucz "BOR" powtarzany)
szyfr:   u o a o o n j o u p a f t q

(t + B(1) = u; a + O(14) = o; j + R(17) = a — z zawinięciem; itd.) Pierwsza litera „a" tekstu przeszła w „o", ale trzecia „a" — w „r"? nie, w… policz: a + R = r. Ta sama litera tekstu szyfruje się różnie, zależnie od pozycji! Histogram całości to zmiksowane trzy histogramy Cezara — spłaszczony, bez wyraźnego szczytu. Prosta analiza częstości ślepnie. Przez trzy stulecia (XVI–XIX w.) uchodziło to za nie-do-złamania.

Jak padł niezłamywalny. Pomysł (Kasiski, 1863; wcześniej — nieopublikowany — Babbage): klucz się powtarza co $d$ znaków (u nas $d = 3$). Więc litery na pozycjach $0, 3, 6, 9, \dots$ są szyfrowane tym samym Cezarem! Podziel szyfrogram na $d$ „grzebieni" (co $d$-ta litera), a każdy grzebień złam histogramem jak zwykłego Cezara. Cała trudność spada na odgadnięcie $d$ — a i tu statystyka pomaga: powtarzające się w tekście słowa (np. „się"), trafiając na tę samą fazę klucza, dają powtarzające się fragmenty szyfrogramu; odległości między powtórkami są wielokrotnościami $d$, więc ich NWD (Euklides! — dział 4 w akcji na polu bitwy) zdradza długość klucza. Niezłamywalny szyfr złożono z kawałków, które umiesz łamać od pół godziny.

💭 Pomyśl: Co się stanie z bezpieczeństwem Vigenère'a, gdy klucz będzie (a) bardzo krótki, np. 2 litery, (b) tak długi jak cały tekst i nigdy nieużyty ponownie?

Sprawdź odpowiedź

(a) Dwa grzebienie, każdy z połową tekstu — histogramy grube i wyraźne, łamanie natychmiastowe; krótki klucz to prawie-Cezar. (b) Żadnych powtórek klucza = żadnych grzebieni = każda litera ma własny, jednorazowy szyfr. Taki system — klucz losowy, długości tekstu, jednorazowy — to szyfr z kluczem jednorazowym i jest dowodnie niezłamywalny (nie „trudny": niemożliwy, bo szyfrogram pasuje do każdego tekstu tej długości przy jakimś kluczu). Cena: klucz trzeba bezpiecznie dostarczyć, jest długi jak wiadomość i wolno go użyć raz — dlatego używały go głównie wywiady i dyplomacja. Cała praktyczna kryptografia mieszka w rozpiętości między (a) i (b).

⚠️ Uwaga, pułapka

Statystyka wymaga próby: histogram dziesięciu liter to wróżenie z fusów, a tekst-pułapka potrafi ograć profil języka. Ostrzeżeniem niech będzie „Gadsby" — powieść, w której Ernest Vincent Wright nie użył ani razu litery „e", najczęstszej w angielszczyźnie (po polsku ten wyczyn to lipogram). Łamacz, który dostał krótki albo dziwny tekst, musi to rozpoznać i nie ufać ślepo szczytowi histogramu — porównanie pełnych profili i zdrowy sceptycyzm to część metody, nie dodatek.

🕰️ Skąd to wiemy

Traktat Al-Kindiego „O odczytywaniu zaszyfrowanej korespondencji" odnaleziono dopiero w 1987 roku w stambulskim archiwum — nauka arabska wyprzedziła Europę o sześćset lat. A polski akcent tej historii jest pierwszoligowy: w 1932 roku Marian Rejewski, Jerzy Różycki i Henryk Zygalski złamali Enigmę — szyfr, który był (upraszczając) Vigenère'em o kluczu zmienianym co literę przez wirujące bębny — używając nie zliczania liter, lecz teorii permutacji. Metoda się zmieniła; zasada „szukaj struktury, którą szyfr mimowolnie zachowuje" — ani na jotę.

🛠️ Teraz Ty

Z komputerem: (1) policz histogram dowolnego długiego polskiego tekstu (wklej akapit z Wikipedii) i porównaj z profilem z ryciny; (2) zaszyfruj tekst Cezarem z tajnym kluczem, po czym złam go własną funkcją histogramową — trafiła? (3) zaimplementuj vigenere_szyfruj(tekst, klucz) (przesunięcie litery klucza cyklicznie: klucz[i % len(klucz)]). Bez komputera: zaszyfruj Vigenère'em słowo INFORMATYKA kluczem BIT.

📐 Definicje tej lekcji

• Analiza częstości — łamanie podstawień przez porównanie histogramu szyfrogramu z profilem języka.
• Szyfr Vigenère'a — Cezar o kluczu-słowie stosowanym cyklicznie; spłaszcza histogram całości.
• Metoda Kasiskiego — odgadnięcie długości klucza $d$ z odległości powtórek (NWD), potem łamanie $d$ grzebieni osobno.

📌 Najważniejsze w pigułce

• Podstawienie przenosi częstości — histogram to wytrych do każdego szyfru „jedna litera → zawsze ta sama litera".
• Vigenère miesza $d$ Cezarów; pada, gdy odzyskasz $d$ — bo grzebienie co $d$-ta litera to zwykłe Cezary.
• Granice metody: krótkie/dziwne teksty mylą statystykę; klucz jednorazowy długości tekstu jest niezłamywalny z dowodem.

🎒 Zadania

1. W szyfrogramie po Cezarze najczęstszą literą jest „t". Podaj najbardziej prawdopodobny klucz (dla polskiego profilu) i dwie hipotezy zapasowe. Jak je zweryfikujesz tanio?

Wskazówka i odpowiedź

Jeśli „t" to obraz „a" (poz. 0): $k = 19$. Zapasowe: „t" jako obraz „i" (poz. 8): $k = 11$; jako obraz „o" (14): $k = 5$. Weryfikacja: odszyfruj pierwsze 30 znaków każdą hipotezą i spójrz, która daje polszczyznę — pełne deszyfrowanie wszystkich wariantów jest zbędne. Łamanie to hipotezy + tani test, w pętli.

2. Zaszyfruj Vigenère'em słowo ALGORYTM kluczem ABC. Co zauważasz w wyniku i czemu klucz zaczynający się od „A" to kiepski pomysł?

Wskazówka i odpowiedź

A=0, B=1, C=2: A+0=A, L+1=M, G+2=I, O+0=O, R+1=S, Y+2=A, T+0=T, M+1=N → AMIOSATN. Co trzecia litera (pozycje 0, 3, 6: A, O, T) jest niezaszyfrowana — przesunięcie o 0! Klucz z literą „A" zostawia co $d$-ty znak jawnym tekstem; dłuższe fragmenty potrafią wtedy „prześwitywać" całymi sylabami. Dobry klucz unika „A" tak samo, jak dobry PIN unika „0000".

3. Szyfrogram Vigenère'a zawiera powtórzony czteroliterowy fragment na pozycjach 10 i 58, a inny — na pozycjach 23 i 95. Oszacuj długość klucza metodą Kasiskiego.

Wskazówka i odpowiedź

Odległości: $58 - 10 = 48$ i $95 - 23 = 72$. $\text{NWD}(48, 72) = 24$ — ale klucz 24-literowy to rzadkość; dzielniki 24 to kandydaci: 12, 8, 6, 4, 3, 2. Zwykle bierze się największy „rozsądny" wspólny dzielnik i testuje grzebienie (czy każdy ma sensowny histogram?). Przy dwóch powtórkach pewności nie ma — z pięcioma odległościami NWD wskazuje $d$ niemal jednoznacznie. Statystyka lubi liczne dowody.

🔍 Sprawdź, czy umiesz

• Złamać Cezara histogramem bez próbowania kluczy — i powiedzieć, kiedy ta metoda zawodzi.
• Zaszyfrować/odszyfrować Vigenère'em na kartce.
• Objaśnić metodę grzebieni: czemu co $d$-ta litera to zwykły Cezar.

---