Teoria liczb i kryptografia

Arytmetyka reszt wygląda na zabawę zegarem, dopóki nie okaże się, że na niej stoi podpis cyfrowy i bezpieczne połączenie. Ten moduł prowadzi od dodawania modulo n, przez algorytm Euklidesa i małe twierdzenie Fermata, aż po kompletny szyfr RSA — z generowaniem kluczy, szyfrowaniem i sprawdzeniem, że deszyfrowanie odtwarza każdą wiadomość, a nie tylko wybraną.

a mod n

Arytmetyka modularna

Zegar modulo n, generatory grupy addytywnej i dzielniki zera w mnożeniu

ℤₙ = {0, 1, …, n−1}

NWD(a,b)

Algorytm Euklidesa

Wersja rozszerzona: współczynniki Bézouta i odwrotność modularna, z podziałem prostokąta na kwadraty

ax + by = NWD(a,b)

a^(p−1) ≡ 1

Twierdzenia Fermata i Eulera

Rzędy elementów, twierdzenie Lagrange'a w praktyce i liczby Carmichaela, które oszukują test

a^φ(n) ≡ 1 (mod n)

RSA

Szyfr RSA

Klucze, szyfrowanie, deszyfrowanie i kontrola bijektywności dla wszystkich wiadomości

c = mᵉ mod n, m = c^d mod n

ZADANIA

Przykłady krok po kroku

Odwrotność modularna, potęgowanie szybkie, pełny przebieg RSA

3 rozwiązane zadania

Arytmetyka modularna — zegar

W ℤₙ liczby „zawijają się” po n krokach. Dodawanie a, 2a, 3a, … obchodzi cały zegar wtedy i tylko wtedy, gdy NWD(a, n) = 1; w przeciwnym razie zamyka się w mniejszym cyklu długości n/NWD(a,n).

moduł n 12

krok a 5

liczba kroków 12

Działanie

NWD(a, n)–

długość cyklu–

czy a generuje całe ℤₙ–

φ(n) — ile elementów odwracalnych–

odwrotność a⁻¹ mod n–

zegar modulo n z kolejnymi krokami

tabliczka mnożenia mod n — czarne pola to iloczyn 0

Algorytm Euklidesa (rozszerzony)

Kolejne dzielenia z resztą kończą się w skończenie wielu krokach, bo reszty maleją. Wersja rozszerzona wypisuje przy okazji liczby x, y z tożsamości Bézouta:

a·x + b·y = NWD(a, b)

Jeśli NWD(a, n) = 1, to x jest właśnie odwrotnością a modulo n.

a 240

b 46

NWD(a, b)–

liczba kroków–

współczynniki Bézouta x, y–

kontrola a·x + b·y–

a⁻¹ mod b–

prostokąt a × b dzielony na kwadraty — każdy krok algorytmu

Małe twierdzenie Fermata i uogólnienie Eulera

p pierwsze, NWD(a,p)=1 ⇒ a^(p−1) ≡ 1 (mod p)

ogólnie: a^φ(n) ≡ 1 (mod n)

Rząd elementu a (najmniejsze k z aᵏ ≡ 1) zawsze dzieli φ(n) — to twierdzenie Lagrange'a zastosowane do grupy ℤₙ*.

moduł n 13

podstawa a 2

czy n jest pierwsze–

φ(n)–

rząd a modulo n–

czy rząd dzieli φ(n)–

a^(n−1) mod n–

świadkowie złożoności / kłamcy–

potęgi aᵏ mod n — cykl zamyka się na rzędzie

test Fermata dla wszystkich podstaw a

Szyfr RSA od początku do końca

Klucz publiczny (n, e) wolno ogłosić; klucz prywatny d wynika z p i q. Bezpieczeństwo opiera się na tym, że z samego n nie umiemy szybko odtworzyć p i q — choć na liczbach z tej zakładki zajmuje to ułamek sekundy.

p (pierwsza)

q (pierwsza)

wykładnik publiczny e 17

wiadomość m 42

wszystkie m odtworzone poprawnie?–

czas faktoryzacji n metodą brute force–

odwzorowanie m → c = mᵉ mod n jest bijekcją

szybkie potęgowanie mᵉ mod n krok po kroku

Przykład 1 — odwrotność modularna przez algorytm Euklidesa

Znajdź 17⁻¹ modulo 3120 (to dokładnie ten rachunek, który pojawia się przy generowaniu klucza RSA dla p = 61, q = 53).

1. Algorytm Euklidesa dla (3120, 17):
   3120 = 183·17 + 9
   17 = 1·9 + 8
   9 = 1·8 + 1
   8 = 8·1 + 0 → NWD = 1, więc odwrotność istnieje.
2. Podstawianie wstecz, zaczynając od przedostatniej linii:
   1 = 9 − 1·8
3. Z linii wyżej: 8 = 17 − 1·9. Wstawiamy:
   1 = 9 − 1·(17 − 1·9) = 2·9 − 1·17
4. Z pierwszej linii: 9 = 3120 − 183·17. Wstawiamy:
   1 = 2·(3120 − 183·17) − 1·17 = 2·3120 − 367·17
5. Czyli 3120·2 + 17·(−367) = 1 — to jest tożsamość Bézouta. Redukując modulo 3120:
   17·(−367) ≡ 1 (mod 3120), a −367 mod 3120 = 3120 − 367 = 2753.
6. Sprawdzenie: 17 · 2753 = 46801, a 46801 = 15·3120 + 1 = 46800 + 1 ✓.
7. Dlaczego to działa zawsze przy NWD = 1: algorytm Euklidesa wyraża NWD jako kombinację ax + by, a przy NWD = 1 dostajemy ax ≡ 1 (mod b). Gdy NWD > 1, odwrotność nie istnieje — bo ax mod b jest zawsze wielokrotnością NWD, więc nigdy nie da 1.

Przykład 2 — szybkie potęgowanie i małe twierdzenie Fermata

Oblicz 7²⁰⁰ mod 13 bez liczenia gigantycznej potęgi.

1. 13 jest pierwsze, a NWD(7,13) = 1, więc z małego twierdzenia Fermata: 7¹² ≡ 1 (mod 13).
2. Dzielimy wykładnik: 200 = 16·12 + 8.
3. Zatem 7²⁰⁰ = (7¹²)¹⁶ · 7⁸ ≡ 1¹⁶ · 7⁸ = 7⁸ (mod 13).
4. Liczymy 7⁸ przez szybkie potęgowanie (kolejne kwadraty):
   7² = 49 = 3·13 + 10 ≡ 10
   7⁴ ≡ 10² = 100 = 7·13 + 9 ≡ 9
   7⁸ ≡ 9² = 81 = 6·13 + 3 ≡ 3
5. Odpowiedź: 7²⁰⁰ ≡ 3 (mod 13).
6. Ile to kosztowało? Trzy mnożenia zamiast 199. Ogólnie szybkie potęgowanie wykonuje O(log k) mnożeń — i dokładnie dlatego RSA na liczbach 2048-bitowych jest w ogóle wykonalny: wykładnik ma 2048 bitów, ale mnożeń jest tylko kilka tysięcy, a nie 2²⁰⁴⁸.
7. Uwaga na warunek: gdyby 13 nie było pierwsze albo gdyby 13 dzieliło 7, krok 1 byłby nieprawdziwy. Dla n złożonego trzeba użyć φ(n), czyli twierdzenia Eulera — i to jest dokładnie ten mechanizm, na którym stoi RSA.

Przykład 3 — pełny przebieg RSA dla p = 61, q = 53

1. Generowanie kluczy. n = p·q = 61 · 53 = 3233.
2. φ(n) = (p−1)(q−1) = 60 · 52 = 3120.
3. Wybieramy e względnie pierwsze z φ(n): niech e = 17 (NWD(17, 3120) = 1 ✓).
4. Liczymy d = e⁻¹ mod φ(n) = 17⁻¹ mod 3120 = 2753 (Przykład 1).
   Klucz publiczny: (n, e) = (3233, 17). Klucz prywatny: d = 2753.
5. Szyfrowanie wiadomości m = 42: c = m^e mod n = 42¹⁷ mod 3233.
   Szybkie potęgowanie przez kolejne kwadraty:
   42² = 1764
   42⁴ = 1764² mod 3233 = 3 111 696 mod 3233 = 1550
   42⁸ = 1550² mod 3233 = 2 402 500 mod 3233 = 381
   42¹⁶ = 381² mod 3233 = 145 161 mod 3233 = 2909
   17 = 16 + 1 (binarnie 10001₂), więc c ≡ 2909 · 42 mod 3233 = 122 178 mod 3233 = 2557.
   Cztery podniesienia do kwadratu i jedno mnożenie — zamiast szesnastu mnożeń. Dokładnie tę tabelkę wypisuje prawy panel zakładki „Szyfr RSA”.
6. Deszyfrowanie: m = c^d mod n = 2557²⁷⁵³ mod 3233 = 42 ✓ (zakładka „Szyfr RSA” liczy to szybkim potęgowaniem i pokazuje każdy krok).
7. Dlaczego to działa. Z konstrukcji e·d ≡ 1 (mod φ(n)), czyli e·d = 1 + kφ(n). Wtedy c^d = m^(ed) = m^(1+kφ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m (mod n) — na mocy twierdzenia Eulera. (Dla m podzielnego przez p lub q trzeba osobnego rachunku przez chińskie twierdzenie o resztach, ale wynik jest ten sam — aplikacja sprawdza wszystkie m od 0 do n−1, więc te przypadki też są objęte.)
8. Gdzie jest bezpieczeństwo. Nie w e ani w n, tylko w tym, że policzenie d wymaga znajomości φ(n) = (p−1)(q−1), a to wymaga rozłożenia n na czynniki. Dla n = 3233 zajmuje to mikrosekundę (aplikacja to mierzy i pokazuje). Dla n o 2048 bitach nie znamy metody wykonalnej w rozsądnym czasie — i cała ochrona polega wyłącznie na tym.