RSA: замок, который может закрыть каждый

Если ты построишь ключ RSA из двух простых, зашифруешь и расшифруешь число и объяснишь, почему расшифровка возвращает исходное сообщение и что мешает вычислить d по открытому ключу, - листай до «Теперь сам».

Как думаешь, можно ли шифровать без общего секрета

Обмен ключами из прошлого урока требует, чтобы обе стороны были на связи одновременно. А если нужно написать человеку, которого сейчас нет в сети, - отправить письмо, оставить файл?

Прежде чем читать дальше, ответь себе: может ли существовать шифр, в котором ключ для шифрования опубликован на всеобщее обозрение, а расшифровать сообщение способен только один человек? И если тот, кто шифрует, знает ключ шифрования, почему он не может им же и расшифровать?

На что это похоже

Представь навесной замок, который защёлкивается без ключа. Хозяин раздаёт открытые замки всем желающим, а ключ оставляет себе. Любой может положить письмо в ящик и защёлкнуть замок - и после этого сам не откроет то, что закрыл. Открыть может только хозяин.

Закрыть и открыть - разные действия, и умение делать первое не даёт умения делать второе. В RSA «защёлкнуть» - возвести в открытую степень, «открыть» - возвести в секретную.

Механизм: две степени, которые отменяют друг друга

Ключ строится в пять шагов. Справа - маленький пример, который можно проверить руками.

1. Выбрать два простых           p = 11,  q = 17
2. Перемножить: модуль           n = 187
3. Длина круга степеней          φ(n) = (p − 1)(q − 1) = 10 · 16 = 160
4. Открытый показатель,          e = 7        НОД(7, 160) = 1
   взаимно простой с φ(n)
5. Секретный показатель:         d = 23       7 · 23 = 161 = 160 + 1
   обратный к e по модулю φ(n)

открытый ключ: (n, e) = (187, 7)          секретный ключ: d = 23

Сообщение - число m от 0 до n − 1: байты текста читаются как одно число по основанию 256. Шифрование: c = mᵉ mod n. Расшифровка: cᵈ mod n.

m = 42:    c = 42⁷ mod 187 = 15          15²³ mod 187 = 42

Почему вернулось 42. Расшифровка вычисляет (mᵉ)ᵈ = m^(e · d). По построению e · d = 1 + k · φ(n) - здесь 161 = 1 + 1 · 160. По теореме Эйлера m^φ(n) ≡ 1 (mod n), значит

m^(e·d) = m^(1 + k·φ(n)) = m · (m^φ(n))ᵏ ≡ m · 1ᵏ = m      (mod n)

Показатели живут по модулю φ(n) - это следствие теоремы Эйлера из прошлой главы, - и d выбран так, чтобы произведение показателей по этому модулю было единицей. Возвести в степень e, а потом в d - всё равно что возвести в первую.

Теорема Эйлера требует, чтобы m было взаимно просто с n. Для RSA равенство верно и без этого условия: по китайской теореме его достаточно проверить отдельно по модулю p и по модулю q, а там случай m, кратного модулю, даёт ноль с обеих сторон, а для остальных m работает теорема Ферма: φ(n) делится на p − 1.

Теперь что знает посторонний: n и e. Ему нужно d, обратное к e по модулю φ(n). Алгоритм Евклида нашёл бы его мгновенно - если бы был известен модуль φ(n) = (p − 1)(q − 1). А чтобы узнать его, нужны p и q. Хозяин ключа знает множители, потому что сам их выбрал. Остальным пришлось бы раскладывать n.

Правило

Ключ RSA: простые p и q, модуль n = p · q, открытый показатель e, взаимно простой с φ(n) = (p − 1)(q − 1), секретный показатель d = e⁻¹ mod φ(n). Открытый ключ - пара (n, e), секретный - d (вместе с p и q). Шифрование числа m < n: c = mᵉ mod n. Расшифровка: m = cᵈ mod n. Корректность следует из теоремы Эйлера: m^(e·d) ≡ m (mod n). Стойкость опирается на то, что φ(n) нельзя вычислить, не зная множителей n.

Разбор: ключ побольше и цена каждого шага

p = 60000011
q = 130000001
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)

m = 20261004
c = pow(m, e, n)
print(c, pow(c, d, n))

n = 7 800 001 490 000 011        открыт
e = 65 537                       открыт
d = 726 597 310 473 473          секрет
c = 1 903 173 972 263 712        шифртекст числа 20 261 004

Вторая степень возвращает 20 261 004. Цена на тренажёре:

действие                                                       шагов
поиск p и q вверх от 60 и 130 миллионов и расчёт d            1 674
шифрование: степень e = 65 537, 17 бит                            19
расшифровка: степень d, 50 бит                                    52
вычисление d при известных p и q                                  14

Первая строка - отдельная программа: от каждого из двух стартовых чисел она идёт по нечётным вверх до первого простого, проверяя кандидатов тестом Миллера-Рабина с двенадцатью основаниями.

Шифрование дешевле расшифровки, и это устроено намеренно. Число 65 537 = 2¹⁶ + 1 в двоичной записи - две единицы и пятнадцать нулей между ними: из семнадцати кругов степени домножение есть только в двух. Его берут почти всегда. Секретный показатель получается длиной с модуль, и короче его делать нельзя.

Ответы на вопросы из начала. Такой шифр существует. А отправитель не может расшифровать собственное письмо, потому что знает только e: обратное действие требует d, а d - это знание множителей n.

Разбор: что на самом деле трудно

Ключ в примере - шестнадцать цифр, и ро-метод из прошлой главы разложит такое n за секунду. Настоящий модуль - 2048 бит, 617 цифр, и вопрос в том, как растёт работа каждой стороны.

действие                   кто делает     цена в числе битов b модуля
найти простое из b/2 бит   хозяин ключа   около b/6 кандидатов
                                          (простое - одно из ln N чисел)
вычислить d                хозяин ключа   один расширенный Евклид
зашифровать                кто угодно     17 умножений по модулю
расшифровать               хозяин ключа   около b умножений по модулю
разложить n                взломщик       растёт быстрее любого
                                          многочлена от b

Каждое умножение по модулю - b² действий над битами столбиком. Удвоение длины ключа делает расшифровку дороже в восемь раз, а разложение - по оценке цены решета числового поля для перехода от 2048 к 4096 битам - в сотни миллионов раз. Законный пользователь и взломщик находятся по разные стороны границы между многочленом и экспонентой, и длиной ключа эту границу можно отодвигать сколько угодно.

При этом никто не доказал, что разложение трудно. Нет даже доказательства, что взлом RSA требует разложения, - известно только, что разложение даёт взлом. RSA держится на том, что почти за пятьдесят лет быстрого способа не нашли.

Что ломается без этого

Первое: e, не взаимно простое с φ(n). Обратного не существует, ключ не строится. Обычно проверяют наоборот: берут e = 65 537 и отбрасывают простые p, у которых p − 1 делится на него.

Второе: сообщение не меньше модуля. Шифруется m mod n, и расшифровка вернёт остаток, а не сообщение. Длинные данные RSA не шифрует вовсе - об этом следующий урок.

Третье: φ(n) или простые в открытом виде. Любое из чисел p, q, φ(n), d раскрывает ключ целиком. Отладочная печать «для проверки» - самый частый путь утечки.

Четвёртое: шифрование числа как есть. Формула mᵉ mod n для одного и того же сообщения всегда даёт один и тот же шифртекст. Поэтому библиотеки перед шифрованием дополняют сообщение случайными данными по стандартной схеме - OAEP, - и пользоваться надо ими, а не формулой. Как именно читают сообщение без дополнения - в уроке об ошибках примененияРазбирается в разделе 18, глава «RSA и обмен ключами»: Где RSA ломают на самом деле: четыре ошибки применения.

Зачем это в работе

Сертификаты сайтов. Когда браузер проверяет, что сервер - тот, за кого себя выдаёт, он проверяет подпись, и очень часто это подпись RSA. Ключи SSH вида ssh-rsa, подписи пакетов в дистрибутивах, подписи писем - то же самое.

Расшифровка в библиотеках идёт через китайскую теорему: две степени по модулям p и q вместо одной по n, вчетверо быстрее: числа и показатели вдвое короче, каждая степень в восемь раз дешевле. Поэтому секретный ключ в файле - не одно число d, а набор из p, q и заранее посчитанных остатков.

Генерация ключа командой openssl genrsa 2048 - это ровно пять шагов из механизма. Долгая часть - поиск простых: случайные кандидаты и тест Миллера-Рабина.

Срок жизни схемы известен. Алгоритм Шора на квантовом компьютере раскладывает числа за полиномиальное время, и стандарты США предписывают отказаться от RSA к 2035 году. До тех пор это самая распространённая подпись в мире.

Теперь сам

1. p = 5, q = 11, e = 3. Найди n, φ(n) и d.
2. Этим ключом зашифруй m = 9. Расшифруй результат и проверь.
3. Почему для этого ключа нельзя взять e = 5?
4. Модуль удлинили с 2048 до 4096 бит. Во сколько раз подорожала расшифровка, если умножение - столбиком?