Конспект: RSA и обмен ключами

Понятия

Симметричный шифр - один ключ и для шифрования, и для расшифровки. Быстрый; ключ надо как-то доставить.

Дискретный логарифм - по g, p и A найти x с gˣ ≡ A (mod p).

Открытый и секретный ключ - пара, в которой одним действие выполняется, а другим отменяется.

Криптографический хеш - число фиксированной длины по всему тексту; подобрать текст под хеш или два текста с одним хешем практически невозможно.

Подпись - число, которое изготовить может владелец секретного ключа, а проверить - любой. Сертификат - подпись центра под записью «имя и открытый ключ».

Что унести

ОБМЕН КЛЮЧАМИ ДИФФИ-ХЕЛЛМАНА            открыто: p = 101, g = 2
Алиса: секрет a = 37                    Боб: секрет b = 58
A = gᵃ mod p = 55          →
                           ←            B = gᵇ mod p = 47
Bᵃ mod p = 82                           Aᵇ mod p = 82
общий секрет g^(ab)

Стойкость - разница в цене. Степень - число битов показателя. Показатель обратно - около √p.

КЛЮЧ RSA                           пример
p, q - простые                     11, 17
n = p · q                          187
φ(n) = (p − 1)(q − 1)              160
e взаимно просто с φ(n)            7
d = e⁻¹ mod φ(n)                   23          7 · 23 = 161 = 160 + 1

шифрование:   c = mᵉ mod n         42⁷ mod 187 = 15
расшифровка:  m = cᵈ mod n         15²³ mod 187 = 42
подпись:      s = hᵈ mod n         50²³ mod 187 = 84
проверка:     sᵉ mod n = h ?       84⁷ mod 187 = 50

Почему работает. e · d = 1 + k · φ(n), и m^φ(n) ≡ 1 по теореме Эйлера: m^(e·d) = m · (m^φ(n))ᵏ ≡ m.

Что секретно. Не формула и не e, а разложение n: без p и q не узнать φ(n), без φ(n) не найти d.

КТО ЧТО ДЕЛАЕТ В СОЕДИНЕНИИ
обмен Диффи-Хеллмана        →  ключ сеанса, свой на каждое соединение
подпись сервера + сертификат →  «это число прислал тот, кто нужен»
симметричный шифр           →  сами данные

ОШИБКА ПРИМЕНЕНИЯ            ЧЕМ ВСКРЫВАЕТСЯ       ЗАЩИТА
шифрование без дополнения    перебор догадок       OAEP из библиотеки
e = 3, сообщение короткое    кубический корень     e = 65 537, дополнение
e = 3, одно сообщение троим  китайская теорема     e = 65 537, дополнение
общее простое у двух ключей  НОД: 46 шагов         генератор для ключей
соседние p и q               Ферма: один круг      независимые простые

Ошибка применения не даёт сбоев. Расшифровка работает, тесты проходят. Чужие ключи проверяет badkeys.

Длина. RSA: минимум 2048 бит; рекорд разложения на сентябрь 2026 года - 896 бит. Эллиптические кривые: 256 бит. Срок RSA по стандартам США - до 2035 года; замена - ML-KEM и ML-DSA.

В Python: pow(m, e, n), pow(e, -1, phi), случайность для ключей - модуль secrets.

Ловушки джокера

d по модулю n. Обратный ищется по модулю φ(n). С n расшифровка возвращает мусор.

e, не взаимно простое с φ(n). Ключа не существует: p = 5, q = 11, e = 5.

Сообщение не меньше модуля. Шифруется m mod n, назад вернётся остаток.

RSA для данных. Гигабайт блоками по 245 байт - больше часа. RSA шифрует ключ сеанса.

Формула вместо библиотеки. mᵉ mod n для одного сообщения всегда даёт один шифртекст. Сообщение дополняют случайными данными по стандартной схеме - это делает библиотека.

Общее простое у двух ключей. НОД(187, 253) = 11 - разложены оба модуля. Причина - ключ, созданный сразу после первого включения, когда случайности ещё нет.

Соседние простые. 8633 = 93² − 4² = 89 · 97: метод Ферма начинает с корня из n и находит ответ с первого круга при любой длине модуля.

Показатель 3. Ключ (187, 3), шифртекст 125: остаток не брался, сообщение - кубический корень, 5.

Подпись без хеша. Произведение двух подписей - подпись произведения.

Один ключ на подпись и расшифровку. Обе операции - xᵈ mod n.

Обмен без проверки собеседника. Посторонний посередине проводит обмен с каждой стороной отдельно.

Постоянный секретный показатель. Утечка сегодня раскрывает всю записанную переписку.

random для ключей. Обычный генератор восстанавливается по нескольким выходам. Для ключей - secrets.

Устаревший хеш. Для MD5 и SHA-1 строятся разные документы с одним хешем.

Куда это ведёт

Четыре главы раздел работал с целыми числами, где каждое действие точно, а трудность - в длине и в отсутствии быстрых алгоритмов. Последняя глава - про другую половину вычислений: дробные числа, где алгоритм известен и быстр, а трудность в том, что ни одно действие не выполняется точно. Метод Гаусса решает систему уравнений за n³, и вопрос там не «сколько шагов», а «сколько верных цифр осталось в ответе».