Szyfr afiniczny
Szyfruj i odszyfrowuj według wzoru E(x) = (ax + b) mod 26. Wpisz a i b, a narzędzie sprawdzi, czy a da się cofnąć, znajdzie jego odwrotność modularną i rozpisze obliczenia dla każdej litery; jeśli nie znasz klucza, tryb odszyfrowania wypróbuje wszystkie 312 i uszereguje je według tego, jak angielsko wyglądają wyniki.
Nie może mieć wspólnego dzielnika z 26 — wybierz jedną z 12 wartości poniżej.
Dowolna liczba całkowita; jest brana modulo 26.
Obliczenia dla tego klucza
Szyfrowanie: E(x) = (5x + 8) mod 26
Odszyfrowanie: D(y) = 21(y − 8) mod 26
21 jest odwrotnością 5, ponieważ 5 × 21 = 105, czyli o 1 więcej niż wielokrotność 26.
Każde dozwolone a i jego odwrotność
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Litera po literze — pierwsze litery (liczba: 12)
| Litera | x | a·x + b | mod 26 | Wynik |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
| C | 2 | 18 | 18 | S |
| I | 8 | 48 | 22 | W |
| P | 15 | 83 | 5 | F |
| H | 7 | 43 | 17 | R |
| E | 4 | 28 | 2 | C |
| R | 17 | 93 | 15 | P |
Jak korzystać z szyfru afinicznego
- 1. Wybierz tryb i wpisz tekst. Szyfrowanie zamienia tekst jawny w tekst zaszyfrowany; odszyfrowanie robi odwrotnie.
- 2. Ustaw klucz. Wpisz a — mnożnik, i b — przesunięcie. a musi być jedną z 12 wartości wymienionych pod polami — kliknij którąś, aby jej użyć. b może być dowolną liczbą całkowitą; jest redukowane modulo 26.
- 3. Przeczytaj obliczenia. Panel pod wynikiem pokazuje oba wzory dla Twojego klucza, odwrotność a oraz obliczenia dla każdej litery.
- 4. Nie masz klucza? Wypróbuj wszystkie. W trybie odszyfrowania zaznacz Wypróbuj wszystkie 312 kluczy. Wyniki są uszeregowane według tego, jak bardzo liczności liter przypominają angielski, a Użyj tego klucza wczytuje dowolny z nich.
Wzór szyfru afinicznego
Ponumeruj litery od zera: A = 0, B = 1 … Z = 25. Aby zaszyfrować literę x, pomnóż ją przez a, dodaj b i weź resztę z dzielenia przez 26: E(x) = (a·x + b) mod 26. Aby odszyfrować literę y, cofnij te kroki w odwrotnej kolejności — odejmij b, a następnie pomnóż przez a⁻¹, czyli odwrotność modularną liczby a: D(y) = a⁻¹·(y − b) mod 26. Odwrotność to liczba, która pomnożona przez a daje resztę 1. Dla a = 5 jest to 21, ponieważ 5 × 21 = 105 = 4 × 26 + 1.
Dlaczego działa tylko 12 wartości a
Mnożenie przez a nie może nigdy wysłać dwóch liter w to samo miejsce, bo odszyfrowanie miałoby dwie odpowiedzi. Dzieje się tak zawsze, gdy a ma wspólny dzielnik z 26 = 2 × 13. Przy a = 2, na przykład, A (0) i N (13) obie lądują na b, ponieważ 2 × 13 = 26, czyli 0 mod 26. Dlatego a musi być nieparzyste i różne od 13, co zostawia dwanaście liczb z tabeli poniżej — dokładnie te, które mają odwrotność modulo 26. Przy 26 wyborach b daje to 12 × 26 = 312 kluczy, z których jeden (a = 1, b = 0) niczego nie zmienia.
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Przykład krok po kroku: a = 5, b = 8
Dla a = 5 i b = 8 tekst AFFINE CIPHER zostaje zaszyfrowany jako IHHWVC SWFRCP — to próbka narzędzia. Litery słowa AFFINE, krok po kroku:
| Litera | x | 5x + 8 | mod 26 | Wynik |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
Aby odszyfrować, narzędzie mnoży przez a⁻¹ = 21. Litera I (8) zamienia się w 21 × (8 − 8) = 0, czyli A; litera H (7) w 21 × (7 − 8) = −21, czyli 5 mod 26, czyli F. Wartości ujemne na tym etapie są normalne — mod 26 oznacza tylko dodawanie lub odejmowanie 26, aż liczba trafi między 0 a 25.
Dwa znane szyfry to w istocie szyfry afiniczne. Przy a = 1 wzór to x + b, czyli przesunięcie Cezara o b; przy a = 25 i b = 25 to szyfr Atbash, czyli alfabet czytany od tyłu.
Jak złamać szyfr afiniczny
Ponieważ tylko 311 kluczy cokolwiek zmienia, najprostszym atakiem jest wypróbowanie ich wszystkich, co opcja siłowa robi w ułamku sekundy. Trudne jest rozpoznanie właściwej odpowiedzi, dlatego narzędzie szereguje każdy wynik na podstawie porównania chi-kwadrat liczności jego liter z typowym angielskim. Przy zdaniu lub dłuższym tekście właściwy klucz ląduje na szczycie; przy krótkiej frazie może tak nie być — dla samego IHHWVC SWFRCP prawdziwy klucz (5, 8) zajmuje czwarte miejsce — więc przeglądaj listę zamiast ufać pierwszej linii.
Kryptoanalitycy potrafią więcej dzięki algebrze. Szyfr afiniczny jest szyfrem podstawieniowym monoalfabetycznym — każda litera zawsze zamienia się w tę samą literę — więc analiza częstości podpowiada, które litery szyfrogramu oznaczają E i T, a dwa takie przypuszczenia dają dwa równania. Przy powyższym kluczu E (4) zamienia się w C (2), a T (19) w Z (25), więc 4a + b ≡ 2 i 19a + b ≡ 25 (mod 26). Odjęcie pierwszego od drugiego daje 15a ≡ 23; pomnożenie przez 7, odwrotność 15, daje a ≡ 161 ≡ 5, a potem b ≡ 2 − 20 ≡ 8. Dwie litery znanego tekstu jawnego odzyskują cały klucz.
Najczęstsze pytania
- Czym jest szyfr afiniczny?
- Szyfr podstawieniowy, który zamienia numer x każdej litery na (a·x + b) mod 26, czyli każdą literę mnoży przez a, a potem przesuwa o b. Kluczem jest para (a, b). Ponieważ dana litera zawsze zamienia się w tę samą literę szyfrogramu, jest monoalfabetyczny — to z wyglądu mocniejszy krewny szyfru Cezara i wcale nie trudniejszy do złamania.
- Dlaczego a musi być względnie pierwsze z 26?
- Odszyfrowanie mnoży przez odwrotność a modulo 26, a ta odwrotność istnieje tylko wtedy, gdy a i 26 nie mają wspólnego dzielnika. Jeśli mają, dwie różne litery szyfrują się w tę samą literę i wiadomości nie da się odczytać z pewnością. To wyklucza każdą liczbę parzystą i 13, zostawiając 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 i 25.
- Jak znaleźć odwrotność modularną a?
- Znajdź liczbę od 1 do 25, która pomnożona przez a daje resztę 1 z dzielenia przez 26. Dla a = 7 jest to 15, ponieważ 7 × 15 = 105 = 4 × 26 + 1. Przy zaledwie dwunastu przypadkach najszybciej odczytać je z tabeli powyżej; dla dużych modułów odwrotność znajduje wprost rozszerzony algorytm Euklidesa.
- Ile kluczy ma szyfr afiniczny?
- 312 — dwanaście wyborów a razy 26 wyborów b. Jeden z nich, a = 1 przy b = 0, nie zmienia tekstu, więc faktycznie szyfruje 311. To na tyle mało, że można wypróbować każdy klucz ręcznie w jedno popołudnie, a komputerem — w mgnieniu oka.
- Czy szyfr Cezara jest rodzajem szyfru afinicznego?
- Tak. Ustawienie a = 1 zmienia wzór w x + b, czyli przesunięcie Cezara o b; ROT13 to a = 1, b = 13. Atbash też jest afiniczny, z a = 25 i b = 25. Oba mieszczą się wśród 312 kluczy, które sprawdza metoda siłowa.
- Czy szyfr afiniczny jest bezpieczny?
- Nie. Ulega metodzie siłowej, analizie częstości i zaledwie dwóm literom znanego tekstu jawnego, jak pokazuje powyższa algebra. To doskonałe ćwiczenie z arytmetyki modularnej, ale do wszystkiego, co ma znaczenie, potrzebne jest nowoczesne szyfrowanie.