Spotlight #34 – Teoria Liczb i Kryptografia: Liczby Pierwsze, RSA, Krzywe Eliptyczne i Bezpieczeństwo Postkwantowe

Teoria liczb bywa nazywana królową matematyki: gałąź zajmująca się liczbami całkowitymi i ich własnościami, która pochłaniała błyskotliwe umysły od tysiącleci, konsekwentnie opierając się pełnemu zrozumieniu. Pozorna bezużyteczność tej czystej matematyki okazała się iluzją. Gdy w latach 70. wynaleziono kryptografię klucza publicznego, opierała się ona bezpośrednio na trudności faktoryzacji dużych liczb całkowitych, a później na dyskretnych logarytmach w grupach skończonych — obiektach badanych przez teoretyków liczb ze względów czysto estetycznych stulecie wcześniej. Dzisiejsze propozycje postkwantowe opierają się na problemach na kratach, których trudność sama w sobie jest twierdzeniem teorioliczbowym.

1. Twierdzenie o liczbach pierwszych

Liczby pierwsze są multiplikatywnymi atomami liczb całkowitych: każda liczba całkowita dodatnia większa od jedynki rozkłada się jednoznacznie na czynniki pierwsze (podstawowe twierdzenie arytmetyki). Mimo tej roli liczby pierwsze wyglądają nieregularnie, gdy je wypiszemy: 2, 3, 5, 7, 11, 13, … Pierwsze pytanie ilościowe brzmi po prostu: ile liczb pierwszych leży poniżej danej granicy.

π(x) = liczba liczb pierwszych ≤ x

Twierdzenie o liczbach pierwszych (Gauss, Hadamard, de la Vallée Poussin):
  π(x) ~ x / ln(x)    gdy x → ∞

Rownowaznie, n-ta liczba pierwsza spelnia:
  p_n ~ n ln(n)

Lepsze przyblizenie (calka logarytmiczna):
  Li(x) = ∫²^x dt/ln(t)   (blad << √x · ln(x) przy zalozeniu RH)

Trzecie twierdzenie Mertensa:
  ∏_{p ≤ x} (1 − 1/p)¹ ~ e^γ ln(x)    (γ = 0,5772...)
          

Dowód twierdzenia o liczbach pierwszych w 1896 roku wymagał zrozumienia funkcji zeta Riemanna ζ(s) = ∑_n=1^∞ n^−s, analitycznie przedłużonej na całą płaszczyznę zespoloną. Praca Riemanna z 1859 roku połączyła rozkład liczb pierwszych z zerami ζ(s) poprzez wzór jawny:

ψ(x) = x − ∑_ρ x^ρ / ρ − ln(2π) − ½ ln(1 − x^−²)

gdzie ψ(x) = ∑_{p^k ≤ x} ln(p)  (funkcja psi Czebyszewa)
      ρ przebiega nietrywialne zera ζ(s)

Zera trywialne: s = −2, −4, −6, ...
Zera nietrywialne: Re(ρ) = ½ (hipoteza Riemanna, nieudowodniona)

Zweryfikowane dla pierwszych 10^13 zer (Platt i Trudgian 2021)
π(10^23) = 1 925 320 391 606 803 968 923 (dokladnie, 2022)
          

Hipoteza Riemanna stwierdza, że wszystkie nietrywialne zera leżą na linii krytycznej Re(s) = ½. Jest to jeden z siedmiu Problemów Milenijnych (Clay Mathematics Institute, nagroda 1 mln dolarów). Jej prawdziwość implikowałaby najostrzejsze znane granice błędu w π(x) — z bezpośrednimi konsekwencjami dla analizy bezpieczeństwa losowych algorytmów testowania pierwszości używanych przy generowaniu kluczy RSA.

2. Arytmetyka modularna

Arytmetyka modularna zwija liczby całkowite wokół okręgu o obwodzie n: dwie liczby całkowite są przystające modulo n, jeśli ich różnica jest podzielna przez n. Notacja a ≡ b (mod n) oddaje tę ideę. Arytmetyka modularna zamienia zbiory skończone w struktury algebraiczne (pierścienie, a gdy n jest liczbą pierwszą — ciała), które wspierają szybkie obliczenia.

Male twierdzenie Fermata (p pierwsza, gcd(a,p)=1):
  a^(p−1) ≡ 1  (mod p)
  ⇒ a^p ≡ a  (mod p)

Twierdzenie Eulera (gcd(a,n)=1):
  a^φ(n) ≡ 1  (mod n)
  φ(n) = n ∏_{p|n} (1 − 1/p)  (funkcja Eulera)

Chinskie twierdzenie o resztach:
  Jesli n = p·q z gcd(p,q)=1,
  to Z_n ≅ Z_p × Z_q  (izomorfizm pierscieni)
  x mod n ↔ (x mod p, x mod q)

Reszty kwadratowe (p nieparzysta liczba pierwsza):
  a jest RK mod p wtedy i tylko wtedy gdy a^((p−1)/2) ≡ 1 (mod p)
  Symbol Legendre'a: (a/p) = a^((p−1)/2) mod p ∈ {±1}
          

Potęgowanie modularne — obliczanie a^e mod n efektywnie metodą powtarzanego podnoszenia do kwadratu — jest podstawową operacją RSA i Diffiego-Hellmana. Działa w czasie O(log e) mnożeń. Bez tego algorytmu praktyczna kryptografia klucza publicznego byłaby niewykonalna.

3. Kryptografia RSA

RSA (Rivest, Shamir, Adleman 1977) był pierwszym praktycznym systemem kryptografii klucza publicznego. Jego bezpieczeństwo opiera się na trudności problemu faktoryzacji liczb całkowitych: mając n = p · q, gdzie p i q są dużymi liczbami pierwszymi, znaleźć p i q. Przy n rzędu 2048 bitów (≈ 617 cyfr dziesiętnych) żaden znany algorytm klasyczny nie potrafi rozłożyć n na czynniki w rozsądnym czasie.

Generowanie kluczy:
  1. Wybierz duze liczby pierwsze p, q  (kazda ~1024 bity dla RSA-2048)
  2. Oblicz n = p · q,  φ(n) = (p−1)(q−1)
  3. Wybierz e z gcd(e, φ(n)) = 1  (zwykle e = 65537)
  4. Oblicz d = e^−¹  (mod φ(n))  poprzez rozszerzony algorytm Euklidesa
  5. Klucz publiczny:  (n, e);   Klucz prywatny: (n, d)  [p, q tajne]

Szyfrowanie:   c = m^e  mod n        (m < n, z paddingiem OAEP)
Deszyfrowanie: m = c^d  mod n

Poprawnosc:  c^d = m^(ed) = m^(1 + kφ(n)) = m  (Euler)

Podpis cyfrowy (podpis kluczem prywatnym d, weryfikacja kluczem publicznym e):
  s = hash(wiad)^d  mod n
  weryfikacja: s^e mod n == hash(wiad)
          

Najlepszym znanym klasycznym algorytmem faktoryzacji jest ogólne sito ciała liczbowego (GNFS), o subwykładniczej złożoności L[1/3, 1,923]. Wyzwanie RSA-768 (moduł 768-bitowy) zostało rozłożone na czynniki w 2009 roku przy użyciu około 2000 lat-CPU. RSA-2048 wymagałoby ogromnie więcej. Obecne praktyczne zalecenia: RSA 2048-bitowe dla poufności danych, 3072-bitowe dla danych wymagających długoterminowego bezpieczeństwa po 2030 roku (NIST SP 800-57).

4. Kryptografia krzywych eliptycznych

Krzywa eliptyczna nad ciałem F to zbiór punktów spełniających y² = x³ + ax + b wraz z punktem w nieskończoności O, z zastrzeżeniem warunku niezdegenerowania 4a³ + 27b² ≠ 0. Punkty te tworzą grupę abelową z geometrycznym prawem dodawania: dla dwóch punktów P, Q, ich suma P + Q jest zdefiniowana przez odbicie względem osi x trzeciego punktu przecięcia linii PQ z krzywą.

Krzywa: E nad F_p (cialo pierwsze),  p > 3

Dodawanie punktow P + Q = R (P ≠ Q):
  λ = (y_Q − y_P) / (x_Q − x_P)  mod p
  x_R = λ² − x_P − x_Q  mod p
  y_R = λ(x_P − x_R) − y_P  mod p

Podwajanie punktu 2P (przypadek stycznej):
  λ = (3x_P² + a) / (2y_P)  mod p

Problem dyskretnego logarytmu krzywej eliptycznej (ECDLP):
  Majac G (generator) i Q = kG, znalezc k
  Najlepszy znany algorytm: rho Pollarda, O(√n)

Porownanie bezpieczenstwa:
  256-bitowe ECC  ≈  3072-bitowe RSA  ≈  128-bitowe symetryczne AES
  384-bitowe ECC  ≈  7680-bitowe RSA  ≈  192-bitowe symetryczne AES
          

ECDSA i ECDH

Wymiana kluczy Diffiego-Hellmana na krzywych eliptycznych (ECDH) pozwala dwóm stronom wyprowadzić wspólny sekret przez niepewny kanał: Alicja publikuje aG; Bob publikuje bG; oboje obliczają abG. ECDSA (algorytm podpisu cyfrowego krzywych eliptycznych) to schemat podpisu używany w Bitcoinie, Ethereum i TLS 1.3. Krzywe NIST P-256 i P-384 oraz szybsza Curve25519 (Bernstein 2006) obejmują przytłaczającą większość obecnego zastosowania.

5. Kryptografia postkwantowa

Algorytm kwantowy Petera Shora z 1994 roku faktoryzuje liczby całkowite i rozwiązuje dyskretne logarytmy w czasie wielomianowym na komputerze kwantowym. Wystarczająco duży komputer kwantowy złamałby RSA i wszystkie schematy ECC. Choć obecny sprzęt kwantowy nie potrafi faktoryzować dużych liczb całkowitych (komunikat NSA/CISA z 2022 roku), zagrożenie „zbierz teraz, odszyfruj później" jest realne: przeciwnicy mogą przechowywać zaszyfrowany ruch dzisiaj i odszyfrować go, gdy komputery kwantowe dojrzeją. Migracja kryptograficzna musi się zacząć, zanim zagrożenie nadejdzie.

Learning With Errors (LWE):
  Majac A (macierz), b = As + e  (mod q)
  Znalezc tajny wektor s
  Blad e pobierany z dyskretnego rozkladu Gaussa χ
  Trudnosc w najgorszym przypadku redukuje sie do SVP na kracie

Module-LWE (MLWE):
  s, e sa wektorami wielomianow w R_q = Z_q[x]/(x^n + 1)
  Podstawa dla CRYSTALS-Kyber (KEM) i CRYSTALS-Dilithium (podpisy)

Standardy NIST PQC (FIPS 2024):
  FIPS 203: ML-KEM (CRYSTALS-Kyber) — kapsulowanie kluczy
  FIPS 204: ML-DSA (CRYSTALS-Dilithium) — podpisy cyfrowe
  FIPS 205: SLH-DSA (SPHINCS+) — podpisy oparte na hashach, bezstanowe
  FIPS 206: FN-DSA (FALCON) — podpisy na kratach NTRU

Kategoria bezpieczenstwa III (rownowaznik AES-192): Kyber-768
  Klucz publiczny: 1184 bajty   Szyfrogram: 1088 bajtow
  W porownaniu z 256-bajtowym szyfrogramem RSA-2048 — wiekszy, ale bezpieczny kwantowo
          

Podpisy oparte na hashach (Lamport 1979, XMSS, SPHINCS+) opierają się wyłącznie na odporności funkcji hash na kolizje i dlatego są konserwatywnymi opcjami bez struktury algebraicznej podatnej na atak kwantowy. SPHINCS+-128s produkuje podpisy o rozmiarze 7856 bajtów — większe niż schematy oparte na kratach, ale przy minimalnych założeniach bezpieczeństwa. Rząd federalny USA wymaga migracji wszystkich systemów klasyfikowanych do algorytmów PQC do 2035 roku (NSA CNSA 2.0, 2022).

6. Dowody z wiedzą zerową

Dowód z wiedzą zerową (ZKP) to protokół, dzięki któremu dowodzący przekonuje weryfikatora, że stwierdzenie jest prawdziwe, nie ujawniając niczego poza prawdziwością tego stwierdzenia. Zaproponowany przez Goldwassera, Micali i Rackoffa w 1985 roku, ZKP spełnia trzy własności: kompletność (uczciwy dowodzący zawsze przekonuje uczciwego weryfikatora), poprawność (oszukujący dowodzący nie może przekonać weryfikatora o fałszywym stwierdzeniu, poza znikomym prawdopodobieństwem) i wiedza zerowa (weryfikator nie dowiaduje się niczego poza tym, że stwierdzenie jest prawdziwe).

Konfiguracja: grupa G rzedu pierwszego q, generator g, klucz tajny x, klucz publiczny y = g^x

Dowodzacy:
  1. Wybierz losowe r ∈ Z_q;  wyslij zobowiazanie R = g^r
  2. Odbierz wyzwanie c od weryfikatora
  3. Oblicz odpowiedz s = r + cx  (mod q);  wyslij s

Weryfikator:
  4. Sprawdz: g^s == R · y^c
     (poniewaz g^s = g^(r+cx) = g^r · (g^x)^c = R · y^c  ✓)

Poprawnosc: lemat forkingowy pokazuje, ze ekstraktor moze odzyskac x
           jesli dowodzacy odpowie na dwa rozne wyzwania dla tego samego R
Wiedza zerowa: (R, c, s) mozna zasymulowac bez x
           wybierz s, c losowo; ustaw R = g^s / y^c
          

zk-SNARK-i i zastosowania

Zwięzłe nieinteraktywne argumenty wiedzy (SNARK) pozwalają dowodzącemu wyprodukować krótki (o stałym rozmiarze) dowód, że ogólne obliczenie zostało wykonane poprawnie. Schemat Groth16 (2016) produkuje dowody o rozmiarze zaledwie 196 bajtów, weryfikowalne w <1 ms, dla dowolnych obwodów boolowskich. zk-SNARK-i stanowią podstawę Zcash (transakcje osłonięte), zkSync i StarkNet (rollupy warstwy 2 Ethereum) i są badane pod kątem uczenia maszynowego zachowującego prywatność, weryfikacji tożsamości i dowodów zgodności w systemach finansowych.

Wypróbuj te symulacje