Подпись, хеш и гибридная схема: как RSA используют на самом деле

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

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

Модуль RSA в 2048 бит - это 256 байт. За один раз шифруется число меньше модуля, то есть блок чуть меньше 256 байт. Расшифровка одного блока на обычном процессоре занимает около миллисекунды: это тысячи умножений чисел по шестьсот цифр.

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

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

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

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

Механизм: гибридная схема и подпись

Гибридная схема. Отправитель выбирает случайный ключ для быстрого шифра - 256 бит - и шифрует им данные. Сам ключ шифрует открытым ключом получателя. По каналу идут два куска:

┌─────────────────────────────┬──────────────────────────────────────┐
│ ключ сеанса, зашифрованный  │ данные, зашифрованные ключом сеанса  │
│ открытым ключом получателя  │ быстрым шифром (AES, ChaCha20)       │
│ 256 байт - длина модуля     │ любой длины, гигабайты в секунду     │
└─────────────────────────────┴──────────────────────────────────────┘

Получатель секретным ключом достаёт ключ сеанса и расшифровывает им всё остальное. Медленная операция выполняется один раз, какой бы длины ни были данные. В соединениях по сети ключ сеанса чаще получают обменом Диффи-Хеллмана, а не пересылкой, но разделение труда то же.

Подпись. У RSA две степени отменяют друг друга в любом порядке: (mᵈ)ᵉ = m^(d·e) ≡ m. Если сначала применить секретную степень, получится число, которое мог вычислить только владелец d, а проверить может каждый:

подписать:    s = hᵈ mod n         делает владелец секретного ключа
проверить:    sᵉ mod n = h ?       делает любой, у кого есть (n, e)

Здесь h - не само сообщение, а его криптографический хеш: число фиксированной длины, вычисленное по всему тексту. От хеша для хеш-таблиц он отличается требованием: должно быть практически невозможно подобрать два разных текста с одним хешем или текст под заданный хеш. Сегодня это функции семейства SHA-2 и SHA-3 с результатом в 256 бит и больше.

Хеш нужен по двум причинам. Сообщение длинное, а подписать можно одно число меньше n. И без хеша подпись подделывается - это второй разбор.

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

Правило

Открытым ключом не шифруют данные: им шифруют или согласуют короткий ключ сеанса, а данные шифруют шифром с общим ключом - его называют симметричным. Подпись RSA сообщения M - число s = H(M)ᵈ mod n; проверка - сравнение sᵉ mod n с H(M). Подпись подтверждает, что текст не менялся и что подписавший владеет секретным ключом. Она не скрывает текст. Подписывается хеш, дополненный по стандарту служебными байтами до длины модуля, а не само сообщение; один ключ не используют и для подписи, и для расшифровки.

Разбор: подпись на числах

Ключ из прошлого урока: n = 7 800 001 490 000 011, e = 65 537, d = 726 597 310 473 473. Пусть хеш сообщения - h = 271 828 182 845. Настоящий хеш - 256 бит, и модуль под него - 2048 бит; здесь модуль из 53 бит, поэтому и «хеш» взят коротким. В Python хеш текста даёт модуль hashlib.

s = pow(h, d, n)
print(s, pow(s, e, n))

подпись s = hᵈ mod n          1 664 178 189 538 386
проверка sᵉ mod n                   271 828 182 845   совпало с хешем:
                                                      подпись верна
проверка (s + 1)ᵉ mod n       3 305 756 183 651 364   не совпало:
                                                      подпись отвергнута

Изменение подписи на единицу даёт при проверке число, не имеющее ничего общего с хешем. То же произойдёт, если изменить хоть один бит сообщения: хеш станет другим, и старая подпись к нему не подойдёт. Подписание стоит 52 шага тренажёра, проверка - 19: проверять дёшево, и это удобно, потому что подписывают один раз, а проверяют многие.

Ответ на вопрос из начала. Гигабайт - это больше четырёх миллионов блоков по 245 байт (256 байт модуля минус 11 байт обязательного дополнения); по миллисекунде на блок выходит больше часа. Быстрый шифр справляется за секунду. Разница - больше четырёх тысяч раз, и поэтому RSA шифрует только ключ.

Разбор: почему подписывают хеш, а не сообщение

Возьмём маленький ключ, чтобы произведения помещались: n = 2 021 027, e = 17, d = 712 241. Пусть владелец подписывает числа напрямую, без хеша.

подпись числа 2:       2ᵈ mod n = 375 488
подпись числа 500:   500ᵈ mod n = 1 611 535
подпись числа 1000: 1000ᵈ mod n = 402 064

375 488 · 1 611 535 mod n = 402 064

Произведение двух подписей - подпись произведения: 2ᵈ · 500ᵈ = (2 · 500)ᵈ. Тот, у кого есть подписи под числами 2 и 500, изготовит подпись под числом 1000, не зная d. Владелец её никогда не ставил.

Вторая подделка ещё проще. Возьмём любое число как «подпись», например s = 123 456, и вычислим открытой степенью, какое «сообщение» ей соответствует: sᵉ mod n = 682 704. Пара «сообщение 682 704, подпись 123 456» проходит проверку. Сообщение при этом получилось случайным - но для протокола, где подписывают числа, этого бывает достаточно.

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

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

Первое: один ключ на подпись и расшифровку. Подписать число и расшифровать число - одна и та же операция xᵈ mod n. Сервис, который подписывает что попросят, расшифрует чужой шифртекст, если ему подать его как «документ на подпись».

Второе: устаревший хеш. Для MD5 и SHA-1 научились строить разные документы с одним хешем. Подпись под одним из них подходит к другому. В 2012 году так подделали сертификат для подписи кода, и вредоносная программа выдавала себя за обновление системы.

Третье: слабая случайность ключа сеанса. В 2008 году обнаружилось, что в одном дистрибутиве Linux из-за ошибки в исправлении библиотеки генератор выдавал всего 32 767 разных ключей. Все ключи, созданные за два года, перебирались за минуты. Для ключей - только системный криптографический генератор.

Четвёртое: проверка подписи «на глаз». Проверяющий обязан сверить весь результат sᵉ mod n с ожидаемым числом, включая служебные байты вокруг хеша. Библиотеки, которые сравнивали только часть, принимали подделки для ключей с открытым показателем 3.

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

Соединение HTTPS сегодня - все три механизма сразу. Обмен ключами Диффи-Хеллмана даёт ключ сеанса. Сервер подписывает свои числа обмена ключом из сертификата - так закрыта подмена, о которой шла речь в первом уроке главы. Сертификат подписан центром, которому доверяет браузер. Данные идут под быстрым шифром.

Подпись без шифрования встречается чаще, чем шифрование. Пакеты в репозитории дистрибутива, коммиты и теги в git, обновления приложений, токены доступа формата JWT, электронная подпись документов - везде текст открыт, а проверяется авторство и целостность.

И про случайность. Обычный генератор вида «умножь на константу по модулю» выдаёт числа, которые выглядят случайными, но по нескольким подряд восстанавливается всё его состояние. Для моделирования и тестов он годится, для ключей - нет. В Python граница проходит между модулями random и secrets.

Теперь сам

1. Ключ из прошлого урока: n = 187, e = 7, d = 23. Подпись числа 50 равна 50²³ mod 187 = 84. Как её проверить и что должно получиться?
2. Проверяющему пришло «сообщение 50, подпись 85». 85⁷ mod 187 = 68. Что он решит?
3. Файл в 10 гигабайт отправляют по гибридной схеме с RSA-2048. Сколько операций RSA выполнит получатель?
4. Подпись скрывает содержание документа?