Szyfr Cezara i podstawy kryptografii

1. Wprowadzenie do kryptografii

Kryptografia to nauka o zabezpieczaniu informacji poprzez szyfrowanie.

1.1. Podstawowe pojęcia:

Tekst jawny (plaintext):  HELLO
         ↓ Szyfrowanie (encrypt)
Szyfrogram (ciphertext):  KHOOR
         ↓ Deszyfrowanie (decrypt)
Tekst jawny:              HELLO

Kluczowe terminy: - Szyfrowanie – przekształcanie tekstu jawnego w szyfrogram - Deszyfrowanie – odwracanie szyfrogramu do tekstu jawnego - Klucz – sekret potrzebny do szyfrowania/deszyfrowania - Kryptoanaliza – łamanie szyfrów

2. Szyfr Cezara - historia

Szyfr Cezara (Caesar Cipher) to jeden z najstarszych i najprostszych szyfrów, używany przez Juliusza Cezara (~100 BC) do komunikacji wojskowej.

2.1. Idea:

Każda litera jest przesuwana o stałą liczbę pozycji w alfabecie.

Klucz (shift) = 3

A → D
B → E
C → F
...
X → A
Y → B
Z → C

Przykład:
HELLO → KHOOR

3. Implementacja podstawowa

3.1. Szyfrowanie:

3.2. Deszyfrowanie:

Kluczowa obserwacja: Deszyfrowanie to szyfrowanie z ujemnym przesunięciem!

4. Wizualizacja przesunięcia

Wynik:

Caesar Cipher - Shift 3:

Original:  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Encrypted: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

HELLO → KHOOR
WORLD → ZRUOG
PYTHON → SBWKRQ

5. Łamanie szyfru Cezara

5.1. Brute Force (próba wszystkich kluczy):

Szyfr Cezara ma tylko 26 możliwych kluczy (0-25) → łatwy do złamania!

Wynik:

Ciphertext: KHOOR ZRUOG

Możliwe deszyfracje:

Shift  0: KHOOR ZRUOG
Shift  1: JGNNQ YQTNF
Shift  2: IFMMP XPSME
Shift  3: HELLO WORLD ← To ma sens!
Shift  4: GDKKN VNQKC
...

5.2. Automatyczne łamanie (analiza częstotliwości):

6. Analiza częstotliwości liter

6.1. Częstotliwość w języku angielskim:

E - 12.70%  ← Najczęstsza!
T -  9.06%
A -  8.17%
O -  7.51%
I -  6.97%
N -  6.75%
...
Z -  0.07%  ← Najrzadsza

6.2. Analiza częstotliwości w szyfrze:

Wynik:

Częstotliwość liter:
R: 20 ( 20.00%)  ← Prawdopodobnie 'O' (3 pozycje wstecz)
O: 20 ( 20.00%)  ← Prawdopodobnie 'L'
K: 10 ( 10.00%)  ← Prawdopodobnie 'H'
...

7. Warianty szyfru Cezara

7.1. ROT13 (shift = 13):

Zastosowanie: ROT13 używany w Usenet do ukrywania spoilerów.

7.2. Szyfr Cezara z różnymi alfabetami:

8. Szyfr Vigenère (rozszerzenie Cezara)

Szyfr Vigenère używa różnych przesunięć dla każdej litery (klucz = słowo).

8.1. Implementacja:

Wizualizacja:

Plaintext:  H E L L O   W O R L D
Key:        K E Y K E   Y K E Y K
Shift:      10 4 24 10 4  24 10 4 24 10
Ciphertext: R I J V S   U Y V J N

9. Szyfr podstawieniowy (Substitution Cipher)

9.1. Losowa permutacja alfabetu:

Uwaga: 26! ≈ 4 × 10²⁶ możliwych kluczy → trudniejszy do złamania brute force!

10. Bezpieczeństwo szyfrów klasycznych

10.1. Dlaczego szyfr Cezara jest słaby?

❌ Tylko 26 możliwych kluczy → brute force w sekundę
❌ Analiza częstotliwości łamie go natychmiast
❌ Żadna tajemnica po stronie klucza (algorytm = klucz)

10.2. Nowoczesna kryptografia:

✅ Długie klucze (128-bit, 256-bit)
✅ Złożone operacje matematyczne
✅ Odporność na ataki komputerowe
✅ Kryptografia asymetryczna (RSA)

Przykłady:
- AES (Advanced Encryption Standard)
- RSA (public-key cryptography)
- SHA-256 (hashing)

11. Zastosowania edukacyjne

11.1. Gry i łamigłówki:

11.2. Tajne wiadomości:

12. Benchmark

13. Podsumowanie

Szyfr Cezara:

  • Najprostszy szyfr podstawieniowy
  • Każda litera przesuwana o stałą wartość
  • 26 możliwych kluczy (0-25)
  • Łatwy do złamania (brute force lub częstotliwość)

Złożoność:

Operacja Złożoność Uwagi
Szyfrowanie O(n) n = długość tekstu
Deszyfrowanie O(n) Jak szyfrowanie
Brute force O(26 × n) Wypróbuj wszystkie klucze
Analiza freq. O(n) Zlicz litery

Implementacja:

Warianty: - ROT13 – shift = 13 (szyfrowanie = deszyfrowanie) - Vigenère – różne przesunięcia (klucz = słowo) - Substitution – losowa permutacja alfabetu

Historia: - Używany przez Juliusza Cezara (~100 BC) - Jeden z najstarszych szyfrów - Edukacyjne znaczenie (wprowadzenie do kryptografii)

Bezpieczeństwo:

❌ NIEZABEZPIECZONY dla prawdziwych danych!

Powody:
1. Tylko 26 kluczy → brute force trywialne
2. Analiza częstotliwości → natychmiastowe łamanie
3. Brak tajemnicy klucza

Nowoczesne szyfry (AES, RSA):
✅ 2^128 lub więcej kluczy
✅ Odporne na analizę częstotliwości
✅ Bezpieczne dla prawdziwych danych

Zastosowania:

✅ Edukacja – nauka podstaw kryptografii ✅ Łamigłówki – gry, zagadki ✅ ROT13 – ukrywanie spoilerów w Usenet ✅ Historia – zrozumienie ewolucji szyfrów

❌ Prawdziwe szyfrowanie → użyj AES, RSA ❌ Bezpieczeństwo danych → nowoczesne metody ❌ Ochrona hasłami → hashing (bcrypt, SHA)

Kluczowe formuły:

Łamanie szyfru:

  1. Brute force: Wypróbuj wszystkie 26 kluczy
  2. Częstotliwość: Znajdź najczęstszą literę (prawdopodobnie 'E')
  3. Słowa: Szukaj sensownych słów angielskich
  4. Kontekst: Wykorzystaj znany format wiadomości

Przykład łamania:

Ciphertext: KHOOR ZRUOG

Częstotliwość: O pojawia się 4 razy
Jeśli O = E (najczęstsza), to shift = 10

Ale sprawdźmy wszystkie:
Shift 3: HELLO WORLD ← Ma sens! ✅

Co dalej warto poznać:

  • Szyfr Vigenère – polyalfabetyczny
  • Enigma – historyczny szyfr (WWII)
  • AES – nowoczesne szyfrowanie symetryczne
  • RSA – kryptografia asymetryczna (public-key)
  • Hash functions – SHA-256, bcrypt
  • Kryptoanaliza – metody łamania szyfrów
Wróć do spisu lekcji