← к оглавлению

Теория чисел — устные вопросы 12–13

Функция и теорема Эйлера, RSA, показатели по модулю, первообразные корни, Диффи-Хеллман. Формулировки — по лекциям курса.

Содержание: 12. Эйлер и RSA 13. Показатели и Диффи-Хеллман

12. Функция и теорема Эйлера. Алгоритм RSA

Сравнения по модулю

a ≡ b (mod N) — a и b дают одинаковый остаток при делении на N. Эквивалентно: N | (a−b). Сравнения совместимы со сложением, вычитанием и умножением: можно работать с остатками вместо самих чисел.

Малая теорема Ферма

p простое, p не делит a → a^(p−1) ≡ 1 (mod p).

Функция Эйлера

φ(n) = количество чисел от 1 до n, взаимно простых с n.

Теорема Эйлера

Если gcd(a,n)=1, то a^φ(n) ≡ 1 (mod n). (МТФ — частный случай: для простого p имеем φ(p)=p−1.)

Идея доказательства: рассмотрим вычеты r₁..r_φ(n), взаимно простые с n. Умножение на a — биекция на этом множестве (все ar_i по-прежнему взаимно просты с n и различны). Перемножив r_i и ar_i, получим a^φ(n)·∏r_i ≡ ∏r_i, откуда a^φ(n) ≡ 1.

Алгоритм RSA

  1. Берём два больших простых p, q; вычисляем n=pq (p,q секретны, n публично).
  2. φ(n) = (p−1)(q−1).
  3. Публичный ключ e: gcd(e, φ(n))=1.
  4. Приватный ключ d = e⁻¹ (mod φ(n)).

Шифрование: c ≡ m^e (mod n). Дешифрование: c^d ≡ m^(ed) ≡ m (mod n) (работает по теореме Эйлера, так как ed ≡ 1 mod φ(n)).

Стойкость: чтобы найти d, злоумышленнику нужен φ(n), а для этого — разложить n на p и q. Факторизация больших чисел — вычислительно трудная задача, на этом держится RSA.
Спросят: почему c^d ≡ m (через теорему Эйлера), на чём держится стойкость, доказательство теоремы Эйлера (биекция x↦ax или граф функции).

13. Показатели по модулю. Алгоритм Диффи — Хеллмана

Показатель (порядок)

ord_n(a) = наименьшее положительное l, для которого a^l ≡ 1 (mod n) (требуется gcd(a,n)=1).

Лемма: a^k ≡ 1 (mod n) ⇔ ord_n(a) | k. Следствие: ord_n(a) | φ(n) (порядок всегда делит φ(n)).

Первообразный корень

Первообразный корень по модулю n — вычет g с ord_n(g) = φ(n). Его степени дают все взаимно простые с n остатки по одному разу.

Существует не для всех n (например, для n=15 нет), но для простых модулей всегда есть.

Алгоритм Диффи — Хеллмана

  1. Общие открытые параметры: большое простое p и первообразный корень g по модулю p.
  2. Алиса: секрет a, публикует A = g^a (mod p).
  3. Боб: секрет b, публикует B = g^b (mod p).
  4. Обмен A и B по открытому каналу.
  5. Общий ключ: K = g^(ab) = B^a = A^b (mod p).
Пример (p=29, g=8): Алиса a=5 → A=8⁵ mod 29 = 27. Боб b=8 → B=8⁸ mod 29 = 20. Общий ключ: K = 20⁵ mod 29 = 24 = 27⁸ mod 29. Оба получили 24, не передавая его.
Стойкость: чтобы по g, A=g^a найти a, нужно решить задачу дискретного логарифмирования — для больших p неизвестно быстрого классического алгоритма. Есть Baby-step Giant-step за O(√n), но это всё ещё экспоненциально от длины числа.
Спросят: почему K совпадает у обоих (g^ab = (g^a)^b = (g^b)^a), что такое дискретный логарифм, идея BSGS (m=⌈√n⌉, две таблицы, поиск совпадения), угроза квантовых компьютеров.
RSA vs Диффи-Хеллман: оба — криптография с открытым ключом. RSA шифрует сообщения (разные ключи для шифровки/расшифровки), стойкость на факторизации. Диффи-Хеллман вырабатывает общий секретный ключ для двоих, стойкость на дискретном логарифме.