Спотлайт #34 – Теорія чисел та криптографія: прості числа, RSA, еліптичні криві та постквантова безпека

Теорію чисел часто називають царицею математики: галузь, що вивчає цілі числа та їхні властивості, яка тисячоліттями поглинала блискучі уми, наполегливо опираючись повному розумінню. Здавана марність цієї чистої математики виявилася оманливою. Коли в 1970-х роках було винайдено криптографію з відкритим ключем, вона безпосередньо спиралася на складність факторизації великих цілих чисел, а пізніше — на дискретні логарифми у скінченних групах — об'єкти, які теоретики чисел вивчали з суто естетичних міркувань століттям раніше. Сьогоднішні постквантові пропозиції спираються на ґраткові задачі, складність яких сама є теоретико-числовим твердженням.

1. Теорема про розподіл простих чисел

Прості числа — це мультиплікативні атоми цілих чисел: кожне додатне ціле число, більше за одиницю, розкладається на прості множники єдиним способом (Основна теорема арифметики). Попри цю роль, прості числа виглядають нерегулярними в переліку: 2, 3, 5, 7, 11, 13, … Перше кількісне питання — просто скільки простих чисел лежить нижче заданої межі.

π(x) = кількість простих чисел ≤ x

Теорема про розподіл простих чисел (Гаусс, Адамар, де ла Валле-Пуссен):
  π(x) ~ x / ln(x)    при x → ∞

Еквівалентно, n-те просте число задовольняє:
  p_n ~ n ln(n)

Краще наближення (логарифмічний інтеграл):
  Li(x) = ∫²^x dt/ln(t)   (похибка << √x · ln(x) за умови ГР)

Третя теорема Мертенса:
  ∏_{p ≤ x} (1 − 1/p)¹ ~ e^γ ln(x)    (γ = 0,5772...)
          

Доведення теореми про розподіл простих чисел у 1896 році вимагало розуміння дзета-функції Рімана ζ(s) = ∑_n=1^∞ n^−s, аналітично продовженої на всю комплексну площину. Стаття Рімана 1859 року пов'язала розподіл простих чисел з нулями ζ(s) через явну формулу:

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

де ψ(x) = ∑_{p^k ≤ x} ln(p)  (функція псі Чебишова)
   ρ пробігає нетривіальні нулі ζ(s)

Тривіальні нулі: s = −2, −4, −6, ...
Нетривіальні нулі: Re(ρ) = ½ (гіпотеза Рімана, не доведена)

Перевірено для перших 10^13 нулів (Платт і Труджіан, 2021)
π(10^23) = 1 925 320 391 606 803 968 923 (точно, 2022)
          

Гіпотеза Рімана стверджує, що всі нетривіальні нулі лежать на критичній лінії Re(s) = ½. Це одна з семи проблем тисячоліття (Математичний інститут Клея, приз $1 мільйон). Її доведення дало б найточніші відомі оцінки похибки в π(x) — з прямими наслідками для аналізу безпеки рандомізованих алгоритмів перевірки на простоту, що використовуються в генерації ключів RSA.

2. Модульна арифметика

Модульна арифметика згортає цілі числа навколо кола з довжиною окружності n: два цілих числа конгруентні за модулем n, якщо їхня різниця ділиться на n. Позначення a ≡ b (mod n) фіксує це. Модульна арифметика перетворює скінченні множини на алгебраїчні структури (кільця, а коли n просте — поля), що підтримують швидкі обчислення.

Мала теорема Ферма (p просте, gcd(a,p)=1):
  a^(p−1) ≡ 1  (mod p)
  ⇒ a^p ≡ a  (mod p)

Теорема Ейлера (gcd(a,n)=1):
  a^φ(n) ≡ 1  (mod n)
  φ(n) = n ∏_{p|n} (1 − 1/p)  (функція Ейлера)

Китайська теорема про остачі:
  Якщо n = p·q з gcd(p,q)=1,
  то Z_n ≅ Z_p × Z_q  (ізоморфізм кілець)
  x mod n ↔ (x mod p, x mod q)

Квадратичні лишки (p непарне просте):
  a є КЛ за модулем p тоді й лише тоді, коли a^((p−1)/2) ≡ 1 (mod p)
  Символ Лежандра: (a/p) = a^((p−1)/2) mod p ∈ {±1}
          

Модульне піднесення до степеня — обчислення a^e mod n ефективно за допомогою повторного піднесення до квадрата — це основна операція RSA та Діффі-Гелмана. Вона виконується за O(log e) множень. Без цього алгоритму практична криптографія з відкритим ключем була б нездійсненною.

3. Криптографія RSA

RSA (Рівест, Шамір, Адлеман, 1977) була першою практичною криптосистемою з відкритим ключем. Її безпека спирається на складність задачі факторизації цілих чисел: маючи n = p · q, де p і q — великі прості числа, знайти p і q. При n порядку 2048 біт (≈ 617 десяткових цифр) жоден відомий класичний алгоритм не може розкласти n на множники за прийнятний час.

Генерація ключів:
  1. Обрати великі прості числа p, q  (кожне ~1024 біти для RSA-2048)
  2. Обчислити n = p · q,  φ(n) = (p−1)(q−1)
  3. Обрати e з gcd(e, φ(n)) = 1  (зазвичай e = 65537)
  4. Обчислити d = e^−¹  (mod φ(n))  за розширеним алгоритмом Евкліда
  5. Відкритий ключ:  (n, e);   Закритий ключ: (n, d)  [p, q секретні]

Шифрування:   c = m^e  mod n        (m < n, доповнено OAEP)
Розшифрування:   m = c^d  mod n

Коректність:  c^d = m^(ed) = m^(1 + kφ(n)) = m  (Ейлер)

Цифровий підпис (підписати закритим ключем d, перевірити відкритим e):
  s = hash(msg)^d  mod n
  перевірка: s^e mod n == hash(msg)
          

Найкращий відомий класичний алгоритм факторизації — це General Number Field Sieve (GNFS), із субекспоненційною складністю L[1/3, 1.923]. Виклик RSA-768 (модуль 768 біт) було розкладено на множники у 2009 році з використанням приблизно 2000 процесоро-років. RSA-2048 вимагатиме на порядки більше. Поточні практичні рекомендації: 2048-бітний RSA для конфіденційності даних, 3072-бітний для даних, що потребують довгострокової безпеки після 2030 року (NIST SP 800-57).

4. Криптографія на еліптичних кривих

Еліптична крива над полем F — це множина точок, що задовольняють y² = x³ + ax + b, разом із точкою на нескінченності O, за умови несингулярності 4a³ + 27b² ≠ 0. Ці точки утворюють абелеву групу за геометричним законом додавання: маючи дві точки P, Q, їхня сума P + Q визначається відображенням через вісь x третьої точки перетину прямої PQ з кривою.

Крива: E над F_p (просте поле),  p > 3

Додавання точок 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

Подвоєння точки 2P (випадок дотичної):
  λ = (3x_P² + a) / (2y_P)  mod p

Задача дискретного логарифма на еліптичній кривій (ECDLP):
  Маючи G (генератор) і Q = kG, знайти k
  Найкращий відомий алгоритм: ро-алгоритм Полларда, O(√n)

Порівняння безпеки:
  256-бітний ECC  ≈  3072-бітний RSA  ≈  128-бітний симетричний AES
  384-бітний ECC  ≈  7680-бітний RSA  ≈  192-бітний симетричний AES
          

ECDSA та ECDH

Обмін ключами Діффі-Гелмана на еліптичних кривих (ECDH) дозволяє двом сторонам вивести спільний секрет по незахищеному каналу: Аліса публікує aG; Боб публікує bG; обоє обчислюють abG. ECDSA (алгоритм цифрового підпису на еліптичних кривих) — це схема підпису, що використовується в Bitcoin, Ethereum та TLS 1.3. Криві NIST P-256 і P-384, а також швидша Curve25519 (Бернштейн, 2006), покривають переважну більшість поточного використання.

5. Постквантова криптографія

Квантовий алгоритм Пітера Шора 1994 року факторизує цілі числа й розв'язує дискретні логарифми за поліноміальний час на квантовому комп'ютері. Достатньо великий квантовий комп'ютер зламав би RSA і всі схеми ECC. Хоча поточне квантове обладнання не може факторизувати великі цілі числа (рекомендація NSA/CISA 2022 року), загроза «зберегти зараз, розшифрувати пізніше» є реальною: противники можуть зберігати зашифрований трафік сьогодні й розшифрувати його, коли квантові комп'ютери дозріють. Криптографічна міграція повинна розпочатися до появи цієї загрози.

Навчання з помилками (LWE):
  Маючи A (матриця), b = As + e  (mod q)
  Знайти секретний вектор s
  Помилка e взята з дискретного гауссіана χ
  Складність у найгіршому випадку зводиться до SVP на ґратці

Модульне LWE (MLWE):
  s, e — вектори поліномів у R_q = Z_q[x]/(x^n + 1)
  Основа для CRYSTALS-Kyber (KEM) і CRYSTALS-Dilithium (підписи)

Стандарти NIST PQC (FIPS 2024):
  FIPS 203: ML-KEM (CRYSTALS-Kyber) — інкапсуляція ключів
  FIPS 204: ML-DSA (CRYSTALS-Dilithium) — цифрові підписи
  FIPS 205: SLH-DSA (SPHINCS+) — підписи на основі хешів, безстанові
  FIPS 206: FN-DSA (FALCON) — підписи на ґратках NTRU

Категорія безпеки III (еквівалент AES-192): Kyber-768
  Відкритий ключ: 1184 байти   Шифротекст: 1088 байт
  Порівняно з 256-байтовим шифротекстом RSA-2048 — більший, але
  квантово-безпечний
          

Підписи на основі хешів (Лампорт, 1979, XMSS, SPHINCS+) спираються виключно на стійкість хеш-функцій до колізій і тому є консервативними варіантами без алгебраїчної структури, придатної для квантової атаки. SPHINCS+-128s створює підписи розміром 7856 байт — більші за ґраткові схеми, але з мінімальними припущеннями про безпеку. Федеральний уряд США вимагає міграції всіх засекречених систем на алгоритми PQC до 2035 року (NSA CNSA 2.0, 2022).

6. Докази з нульовим розголошенням

Доказ з нульовим розголошенням (ZKP) — це протокол, за яким доводжуюча сторона переконує перевіряючу сторону в істинності твердження, не розкриваючи нічого, крім факту його істинності. Запропонований Голдвассер, Мікалі та Ракоффом у 1985 році, ZKP задовольняє три властивості: повноту (чесний доводжуючий завжди переконує чесного перевіряючого), непорушність (шахрайський доводжуючий не може переконати перевіряючого в хибному твердженні, крім як з нехтовно малою ймовірністю) та нульове розголошення (перевіряючий не дізнається нічого, окрім того, що твердження істинне).

Налаштування: група G простого порядку q, генератор g, закритий ключ x, відкритий ключ y = g^x

Доводжуюча сторона:
  1. Обрати випадкове r ∈ Z_q;  надіслати зобов'язання R = g^r
  2. Отримати виклик c від перевіряючої сторони
  3. Обчислити відповідь s = r + cx  (mod q);  надіслати s

Перевіряюча сторона:
  4. Перевірити: g^s == R · y^c
     (оскільки g^s = g^(r+cx) = g^r · (g^x)^c = R · y^c  ✓)

Непорушність: лема розгалуження показує, що екстрактор може відновити x,
           якщо доводжуючий відповідає на два різні виклики для того самого R
Нульове розголошення: (R, c, s) можна симулювати без x
           обрати s, c випадково; задати R = g^s / y^c
          

zk-SNARK та застосування

Стислі неінтерактивні аргументи знання (SNARK) дозволяють доводжуючій стороні створити короткий (сталого розміру) доказ того, що загальне обчислення було виконано коректно. Схема Groth16 (2016) створює докази всього у 196 байт, які перевіряються менш ніж за 1 мс, для довільних булевих схем. zk-SNARK лежить в основі Zcash (екрановані транзакції), zkSync та StarkNet (роллапи Layer-2 Ethereum), і досліджується для машинного навчання зі збереженням приватності, перевірки особистості та доказів відповідності у фінансових системах.

Спробуйте ці симуляції