SEC·X Секреты и атаки Глава 60 из 65
Секрет на виду у всех
Одно открытие, сделанное дважды: открыто — в Стэнфорде и Массачусетском технологическом, тайно — в британской спецслужбе, где о нём молчали до 1997 года. Две истории идут рядом, а между ними — краски Диффи и Хеллмана, RSA своими руками и его взлом, подписи, хеши, пароли и замок в адресной строке.
Секреты и атаки
- 59 Шифры
- 60 Открытый ключ вы здесь
- 61 Безопасность
Опирается на: 59 · Шифровальный отдел 05 · Свои слова 26 · Подбросим монетку
Что вы унесёте из главы
- объяснять, как двое договариваются о секретном ключе по открытому каналу и почему подслушивающий его не узнаёт
- написать игрушечный RSA, подписать им сообщение и взломать слишком короткий ключ
- хранить пароли правильно — с солью и медленным хешем — и понимать, что делает браузер, когда показывает замок
10Как договориться о секрете, если каждое слово подслушивают?
Шифровальный отдел из прошлой главы закрылся на неприятном вопросе. Все его шифры, от Цезаря до AES, требуют общего ключа, и этот ключ кто-то должен заранее и тайно привезти. Интернет так не работает. Вы открываете сайт, на котором никогда не были, ваши пакеты идут через десятки чужих маршрутизаторов, и любой из них может записать каждый байт. Как договориться о секрете, если каждое слово подслушивают?
Назовём собеседников, как принято у криптографов, Алисой и Бобом, а подслушивающую — Евой, от английского eavesdropper, «подслушивающий». Задача кажется безнадёжной. Если Ева слышит всё, что говорят Алиса и Боб, она знает всё, что знают они, — откуда у них возьмётся то, чего не знает она? И всё же решение есть, и найдено оно дважды. Один раз — открыто, американскими учёными, которые опубликовали его и прославились. Другой раз — раньше и в тайне, математиками британской спецслужбы, которым двадцать с лишним лет нельзя было никому об этом рассказать. Эта глава идёт по двум историям сразу, открытой и секретной, и их эпизоды стоят рядом. Они сойдутся в 1997 году. А между ними мы соберём своими руками всё, на чём держится замок в адресной строке браузера.
Задача о ключах
Обе стороны упёрлись в одно и то же. Нужен замок, который может защёлкнуть каждый, а открыть — только хозяин. Обычный навесной замок именно такой: защёлкнуть его можно без ключа, достаточно нажать. Если бы у Алисы был такой замок, она могла бы отправить его Бобу открытым, Боб запер бы им ящик с письмом, и вскрыть ящик по дороге не смог бы никто — даже тот, кто видел замок. В математике такой замок — функция, которую легко вычислить и очень трудно обратить.
Улица с односторонним движением
В 1874 году английский экономист и логик Уильям Стэнли Джевонс написал в книге «Принципы науки»: «Может ли читатель сказать, какие два числа при перемножении дают число 8 616 460 799? Думаю, маловероятно, что кто-нибудь, кроме меня, это узнает». О шифрах он не думал: он рассуждал о том, что многие действия легко выполнить и трудно обратить. Проверим, как обстоит дело с компьютером.
Число Джевонса компьютер раскладывает за миллисекунды; его разложили и без компьютера — в 1889 году, а позже Соломон Голомб показал, что хватает карманного калькулятора и смекалки. Но сама мысль верна, только числа нужны больше. Умножение двух чисел из $k$ цифр занимает порядка $k^2$ действий, а перебор делителей числа из $2k$ цифр — порядка $10^k$. Каждые две лишние цифры замедляют перебор в десять раз, и уже число из шестисот цифр перебором не разложить, пока светит Солнце.
Функцию, которую легко вычислить, но практически невозможно обратить, называют односторонней. Оговоримся сразу: никто не доказал, что односторонние функции вообще существуют. Если они есть, то $\mathrm P \ne \mathrm{NP}$ — проверить ответ легко, найти трудно, — а это открытая проблема из главы 57. Вся современная криптография стоит на том, что лучшие математики мира десятилетиями ищут быстрый способ обратить несколько конкретных функций и не находят.
Вторая такая функция — возведение в степень по модулю. Вычислить $g^x \bmod p$ легко даже для чисел из сотен цифр. Не умножать же $g$ на себя $x$ раз: показатель из 600 цифр — это больше умножений, чем атомов во Вселенной. Вместо этого возводят в квадрат: $g, g^2, g^4, g^8, \ldots$ — и перемножают те квадраты, которые отвечают единицам в двоичной записи $x$. Это тот же приём «половина и квадрат», что в задаче «Степень за двадцать шагов» из главы 9, только после каждого умножения берётся остаток, чтобы числа не росли. Для 2048-битного показателя это около трёх тысяч умножений. Подробно и с доказательством — в «Царице наук»; в Python всё это делает встроенная pow(g, x, p) с тремя аргументами.
А обратная задача — по $A = g^x \bmod p$ найти $x$ — называется дискретным логарифмом. У обычного логарифма есть подсказка: чем больше $x$, тем больше $g^x$. У остатков её нет — степени прыгают по кругу без видимого порядка. Остаётся перебирать.
Модуль cs.pk — помощник этой главы: random_prime(bits) выдаёт случайное простое число нужной длины, проверяя кандидатов тестом Миллера — Рабина из главы 26. Каждые два лишних бита модуля — вчетверо дольше перебор. Для модуля в 2048 бит, какой берут на деле, перебору понадобилось бы порядка $2^{2048}$ шагов, число из шестисот с лишним цифр. Лучшие известные алгоритмы куда хитрее перебора, но и им нужно около $2^{112}$ операций — это за пределами всех компьютеров Земли вместе взятых.
Краски
Прежде чем считать, удобно представить обмен красками. Алиса и Боб открыто договариваются об общей краске — скажем, жёлтой. Каждый берёт свою тайную краску, подмешивает её к жёлтой и отправляет смесь другому. Ева видит жёлтую и обе смеси. Получив смесь Боба, Алиса добавляет в неё свою тайную краску. Боб делает то же со смесью Алисы. Теперь у обоих в банке жёлтая и обе тайные краски, а значит, один и тот же цвет. Ева же смешать его не может: разделить смесь обратно на краски она не умеет, а слив две смеси вместе, получит вдвое больше жёлтой, и цвет выйдет другой.
В числах всё то же самое. Общая краска — открыто известные простое число $p$ и основание $g$. Тайная краска Алисы — случайный показатель $a$, её смесь — $A = g^a \bmod p$. У Боба — $b$ и $B = g^b \bmod p$. Подмешать свою краску к чужой смеси — возвести её в свою степень: Алиса считает $B^a$, Боб — $A^b$, и это одно и то же число:
$$B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b \pmod p.$$Ева знает $p$, $g$, $A$ и $B$, но, чтобы получить $g^{ab}$, ей нужно $a$ или $b$, а это дискретный логарифм. Так устроен обмен ключами Диффи — Хеллмана. Вот он на рабочей группе — простом числе в 2048 бит из стандарта RFC 3526, где описаны группы для интернет-протоколов.
Десятки миллисекунд на всё, и у Алисы с Бобом общий секрет из шестисот с лишним цифр, который ни разу не был произнесён. Из него обе стороны делают ключ для AES — например, берут хеш, о котором речь пойдёт ниже, — и дальше говорят быстрым симметричным шифром из прошлой главы.
Ева меняет тактику
Обмен Диффи — Хеллмана защищает от того, кто слушает. А если Ева не только слушает, но и сидит посередине линии и может подменять сообщения? Включите в виджете «Ева подменяет». Ева перехватывает смесь Алисы и отправляет Бобу свою, а смесь Боба заменяет своей для Алисы. Алиса договаривается с Евой, думая, что с Бобом; Боб — тоже с Евой. Теперь Ева расшифровывает каждое письмо Алисы своим первым ключом, читает, зашифровывает вторым и отправляет Бобу. Оба уверены, что говорят друг с другом наедине. Это атака посредника, или «человек посередине».
Шифрование тут не помогает: беда не в том, что Ева читает, а в том, что Алиса не знает, с кем говорит. Нужен способ доказать, что смесь отправил именно Боб, — подпись, которую может проверить каждый, а поставить только Боб. Её дал второй шифр с открытым ключом.
Замок, который защёлкнет каждый
Рецепт такой. Владелец ключа выбирает два больших простых числа $p$ и $q$ и держит их в тайне. Публикует он их произведение $n = pq$ и число $e$, обычно $65\,537$. Себе он вычисляет $d$ — число, обратное к $e$ по модулю $\varphi = (p - 1)(q - 1)$, то есть такое, что $e \cdot d$ даёт остаток 1 при делении на $\varphi$. Пара $(n, e)$ — открытый ключ, её можно напечатать в газете. Число $d$ — закрытый ключ. Зашифровать число $m$ может кто угодно: $c = m^e \bmod n$. Расшифровать — только владелец $d$: $m = c^d \bmod n$.
Почему $c^d$ возвращает $m$, доказывается малой теоремой Ферма; полное доказательство — в «Царице наук», а здесь соберём шифр в коде. Обратный по модулю элемент вычисляет та же pow с показателем −1: внутри неё работает расширенный алгоритм Евклида — родственник наибольшего общего делителя из главы 5.
Вот и замок, который защёлкнет каждый. Шифр с двумя разными ключами — открытым для шифрования и закрытым для расшифровки — называют шифрованием с открытым ключом или асимметричным, в отличие от симметричных шифров прошлой главы. А $d$ — это лазейка: знание, которое превращает трудную обратную задачу в лёгкую. Без $p$ и $q$ вычислить $\varphi$, а значит и $d$, никто не умеет быстрее, чем разложив $n$ на множители.
В лаборатории ниже то же самое можно проделать с ключами любой длины, а заодно подписать письмо и взломать ключ.
Сколько стоит разложить
Стойкость RSA держится на трудности разложения $n$. Вот как она выглядит в цифрах, если перебирать делители до корня:
Четыре лишних бита — вчетверо дольше: перебор идёт до $\sqrt n$, а корень растёт вдвое на каждые два бита. Есть способы гораздо хитрее. Ро-метод Полларда, который работает в лаборатории, опирается на парадокс дней рождения из главы 16 и находит делитель $p$ примерно за $\sqrt p$ шагов, то есть за корень четвёртой степени из $n$, — вы напишете его в задаче. Лучший известный метод, решето числового поля, ещё быстрее. Рекорд — число RSA-250 из 250 десятичных цифр, или 829 бит: в феврале 2020 года его разложили за время, равное примерно 2700 годам работы одного процессорного ядра. До 2048 бит, которые используют сегодня, — пропасть, и о ней подробнее в «Царице наук».
Общий делитель на тысячу ключей
Но разлагать в лоб и не нужно, если ключи сделаны плохо. В 2012 году Надя Хенингер, Закир Дурумерик, Эрик Вустров и Алекс Холдерман собрали открытые ключи RSA со всех серверов интернета, до которых смогли дотянуться, и для каждой пары ключей посчитали наибольший общий делитель модулей. У правильно сделанных ключей он равен единице. Но у некоторых нашёлся общий простой множитель — и тогда оба ключа раскладываются мгновенно: $\gcd(n_1, n_2) = p$, а $q_1 = n_1 / p$, $q_2 = n_2 / p$. Так исследователи вычислили закрытые ключи 0,5 % серверов TLS и 0,03 % серверов SSH. Виноватыми оказались в основном маршрутизаторы, межсетевые экраны и другие сетевые устройства: ключ они создают при первом включении, когда случайности, о которой говорила глава 26, у них ещё почти нет, — и разные устройства выбирают одно и то же простое число.
Ключи в ячейке короче реальных, чтобы их быстро создать, но алгоритму Евклида всё равно, какой длины числа, и тысячи пар он проверяет мгновенно. Для миллионов ключей в исследовании понадобился приём похитрее: общие делители считали сразу для всех ключей деревом произведений. Идея та же. Математика RSA тут ни при чём. Подвела случайность при рождении ключа.
Подпись
У RSA есть свойство, которое Диффи и Хеллман искали с самого начала. Ключи можно поменять ролями. Если владелец возведёт число в свою закрытую степень $d$, то вернуть исходное сможет кто угодно — открытой степенью $e$. Зашифровать так ничего нельзя, раз расшифровывает каждый. Зато получается доказательство: такое число мог сделать только тот, у кого есть $d$. Это цифровая подпись.
Подписывают не само письмо — оно может быть длиннее модуля, — а его отпечаток: короткое число, которое вычисляется из письма целиком и меняется при любой правке. Такие отпечатки даёт хеш-функция; о ней следующий раздел, а пока воспользуемся готовой.
Подпись останавливает Еву-посредника. Если Боб подписывает свою смесь, Алиса проверяет подпись его открытым ключом, и подменённая смесь проверку не пройдёт: подделать подпись Ева не может. Включите в виджете с красками «Смеси подписаны» — атака посредника разваливается. Остаётся последний вопрос: откуда Алиса знает открытый ключ Боба? Если Ева подсунет ей свой ключ под именем Боба, всё начнётся сначала.
Ответ — цепочка подписей. Открытый ключ сайта вместе с его именем подписывает удостоверяющий центр; такой подписанный документ называют сертификатом. Ключ удостоверяющего центра подписан центром повыше, и так до корневого, чей открытый ключ уже лежит в вашем браузере или операционной системе — его привезли вместе с ними. Браузер проверяет цепочку подписей сверху вниз и только тогда верит, что ключ принадлежит именно этому сайту. Подписи же проверяют обновления программ: телефон не установит обновление, подпись которого не сходится с ключом производителя.
Отпечаток в 256 бит
Хеш-функции мы строили в главе 16 для хеш-таблиц, и там же увидели, как противник подбирает ключи с одинаковым хешем. Хеш для подписей должен выдерживать противника, который располагает огромными вычислительными мощностями и знает функцию до последнего бита. Такую функцию называют криптографической, и от неё требуют трёх вещей. По хешу нельзя найти вход. По данному входу нельзя найти другой с тем же хешем — иначе подписанный договор подменят. И вообще нельзя найти никакие два входа с одинаковым хешем. Самая распространённая сегодня — SHA-256 из семейства SHA-2: её разработало американское Агентство национальной безопасности, а стандартом опубликовал американский институт стандартов NIST: проект — в 2001 году, окончательный текст — в 2002-м. Она превращает вход любой длины в 256 бит.
Пять мегабайт романа уместились в 64 шестнадцатеричные цифры. Если в любом месте романа изменить одну букву, отпечаток будет совсем другим. Как сильно другим, показывает вторая половина ячейки: одна точка в конце строки изменила около половины из 256 бит. Это лавинный эффект: любое изменение входа переворачивает в среднем половину битов результата, и предсказать, какую, нельзя. Будь иначе, по похожим хешам можно было бы угадывать похожие входы.
Возьмём от SHA-256 только первые 32 бита — четыре миллиарда возможных значений. Сколько разных писем нужно перебрать, чтобы среди них нашлись два с одинаковым укороченным отпечатком?
Хватает нескольких десятков тысяч: порядка $\sqrt{2^{32}} = 65\,536$. Ищем не письмо с заданным отпечатком, а любую пару совпавших, а пар среди $k$ писем — $k^2/2$. Ячейка ниже проверяет это опытом.
Длину в 256 бит выбрали из-за дней рождения. Как мы выяснили в главе 16, совпадение среди случайных значений из $N$ возможных появляется уже после $\sqrt N$ попыток. Для хеша длиной $k$ бит это $2^{k/2}$. Проверим на укороченной SHA-256 — возьмём от неё только первые биты.
Сорокабитный отпечаток сдаётся за доли секунды. У полной SHA-256 столкновения пришлось бы ждать $2^{128}$ попыток; таков её запас прочности, тот же, что у AES-128. А её предшественницу SHA-1 со 160 битами сломали хитрее, чем днями рождения: в феврале 2017 года исследователи из амстердамского института CWI и Google показали два разных PDF-файла с одинаковым SHA-1. Это стоило около $2^{63}$ вычислений хеша — примерно 6500 лет работы одного процессора и 110 лет работы одной видеокарты, — но после этого SHA-1 для подписей не годится. Git из главы 40 по-прежнему адресует файлы по SHA-1: ему важнее заметить порчу, чем устоять перед противником. Но режим с SHA-256 в нём уже есть.
Пароли: хранить, не зная
Хеш решает и бытовую задачу, с которой сталкивается любой сайт с регистрацией. Хранить пароли в открытом виде нельзя: базы утекают, и тогда утекают пароли, которыми люди пользуются и на других сайтах. Поэтому хранят хеш пароля. При входе сайт хеширует то, что ввели, и сравнивает. Сам пароль сайту не нужен, а по хешу его, как мы выяснили, не восстановить. Вот такая база попадает к взломщику.
По хешу пароль не восстановить, но угадать — можно. Люди выбирают одни и те же пароли, и взломщику достаточно один раз посчитать хеши миллиона самых расхожих и хранить таблицу «хеш → пароль». Хуже того, у Анны и Глеба одинаковые хеши: видно, что пароль у них один, даже не зная какой. Так было с LinkedIn: в июне 2012 года в сеть попали около 6,5 миллиона хешей паролей, посчитанных SHA-1 без всякой соли, и многие из них быстро подобрали.
Лекарство придумали ещё в 1970-х годах для Unix, а описали его Роберт Моррис и Кен Томпсон в статье «Безопасность паролей: история одного случая», напечатанной в 1979 году. Моррис, по одной из версий, первым напечатал слово «хеш», а его сын написал червя из главы 61; Томпсона мы встречали в главе 52. К паролю каждого пользователя перед хешированием приписывают случайную строку — соль, как в хеш-таблицах главы 16, только здесь она своя у каждого пароля и хранится рядом с хешем открыто. Одинаковые пароли получают разные хеши, а заранее посчитанная таблица бесполезна: её пришлось бы считать для каждой соли заново. В Unix соль была двенадцатибитной; сегодня берут 16 байтов и больше.
Соль не мешает подбирать пароль одного конкретного пользователя: взломщик берёт его соль и перебирает словарь. Против этого второе лекарство — медленный хеш. SHA-256 задумана быстрой, и для паролей это беда. Хеш паролей делают нарочно дорогим: повторяют вычисление сотни тысяч раз или заставляют занимать много памяти. Пользователь при входе заплатит около десятой доли секунды и не заметит, а взломщику каждая попытка встанет в столько же.
Функция hashlib.pbkdf2_hmac — стандарт PBKDF2: она прогоняет пароль с солью через хеш заданное число раз. Шестьсот тысяч повторов — столько для PBKDF2 с SHA-256 сейчас советует OWASP, сообщество специалистов по безопасности веб-приложений. Разница с одиночным SHA-256 — в сотни тысяч раз: словарь из миллиона паролей против одной учётной записи взломщик проверял бы порядка суток на одном ядре процессора вместо долей секунды, и так для каждого пользователя отдельно. Такие функции называют медленными хешами паролей. Кроме PBKDF2 это bcrypt, scrypt и Argon2 — последний выиграл открытый конкурс хешей паролей в 2015 году, и его OWASP рекомендует в первую очередь: Argon2 требует много памяти, а значит, плохо ускоряется на видеокартах.
Пароли хранят так: у каждого своя соль, хеш медленный, библиотека готовая. Ни открытым текстом, ни быстрым хешем вроде MD5 или SHA-256, даже с солью, ни «зашифрованными» — шифровку расшифруют, если украдут ещё и ключ. А пользователю нужны длинные пароли, разные на разных сайтах: соль и медленный хеш защищают от перебора, но не от пароля «qwerty».
Двадцать лет молчания
Замок в адресной строке
Теперь у нас есть всё, чтобы прочитать замок. Вот что ответил сервер этого сайта, когда 2 октября 2026 года к нему подключилась утилита openssl — та же процедура, которую ваш браузер проделал, открывая эту страницу. Из её вывода мы оставили только строки, о которых пойдёт речь.
Прочитаем снизу вверх. TLSv1.3 — версия протокола TLS, утверждённая в 2018 году; во что обходится её рукопожатие, мы считали в главе 43. Peer Temp Key: X25519 — это обмен Диффи — Хеллмана, только вместо возведения в степень по модулю простого числа он идёт на эллиптической кривой Curve25519: та же идея «смешать краски», но точки кривой вместо остатков, и ключ в 256 бит держит столько же, сколько 3000-битный модуль. Об эллиптических кривых — глава «Царицы наук». Слово «Temp» значит, что ключи для обмена каждый раз новые и после разговора стираются. Даже если через год украдут все ключи сервера, записанный сегодня разговор не прочесть.
Peer signature type: ecdsa_secp256r1_sha256 — сервер подписал свою часть обмена, чтобы никакая Ева не встала посередине. Подпись — ECDSA на кривой P-256: устроена она иначе, чем подпись RSA, но правило то же — подписывают закрытым ключом, проверяют открытым, а отпечаток для неё считает SHA-256. Проверяет её браузер открытым ключом из сертификата CN=legost.in. Сертификат подписан центром Let's Encrypt, а тот — корнем ISRG, ключ которого уже лежит в вашей системе. Сертификаты Let's Encrypt пока действуют 90 дней, и их принято обновлять автоматически. Наконец, TLS_AES_256_GCM_SHA384: сами данные идут симметричным AES с 256-битным ключом, выведенным из общего секрета обмена.
Подслушивающий не может узнать секрет, если для него вычислить секрет из услышанного — задача, которую никто в мире не умеет решать быстро. Алиса и Боб открыто обмениваются «смесями» $A = g^a$ и $B = g^b$, и каждый получает общий ключ $g^{ab}$, подмешав к чужой смеси свой секретный показатель. Ева слышит $A$ и $B$, но, чтобы получить $g^{ab}$, ей нужен $a$ или $b$ — дискретный логарифм, которому не известно быстрого решения. Против Евы, которая не только слушает, но и подменяет, нужна подпись: открытым ключом сервера любой проверит, что смесь прислал он, а подделать подпись без закрытого ключа нельзя. Сам открытый ключ браузер получает в сертификате, подписанном цепочкой удостоверяющих центров, корень которой встроен в систему. Так за долю секунды, по чужим проводам, браузер и сервер, никогда не встречавшиеся, получают ключ для быстрого шифра AES. Всё держится на односторонних функциях, стойкость которых не доказана, но проверена десятилетиями неудачных атак. И на аккуратности тех, кто пишет программы: об их ошибках — глава 61.
Квантовая тень
У этой конструкции есть известная угроза. В 1994 году Питер Шор придумал алгоритм для квантового компьютера, который раскладывает числа на множители и находит дискретные логарифмы быстро — за время, растущее как степень числа цифр. Квантовая часть алгоритма находит период последовательности $a, a^2, a^3, \ldots \bmod n$, а дальше работает обычная арифметика остатков; как именно — в «Царице наук», а что такое кубиты — в главе 64. Квантового компьютера, способного на такое, пока нет. Оценки, сколько кубитов ему нужно, падают: в мае 2025 года Крейг Гидни из Google оценил, что для 2048-битного RSA хватило бы меньше миллиона шумных кубитов и меньше недели работы.
Ждать опасно: шифровки можно записать сегодня и прочесть, когда такой компьютер появится. Поэтому 13 августа 2024 года тот же NIST утвердил первые постквантовые стандарты: FIPS 203 — согласование ключей ML-KEM, FIPS 204 и FIPS 205 — подписи ML-DSA и SLH-DSA. Первые два построены на задачах о решётках — о коротких векторах в многомерных сетках точек, — третий на хеш-функциях; быстрых квантовых алгоритмов для них не знают. Постквантовая криптография уже работает: в тот же день, 2 октября 2026 года, сервер google.com договорился с openssl о ключе по гибридной схеме X25519MLKEM768 — классическая кривая и ML-KEM одновременно. Если сломают одну из двух, вторая продолжит держать.
Перестраховкой гибрид не назовёшь. Один из кандидатов того же конкурса NIST, схема SIKE, дошёл до четвёртого, последнего раунда, а летом 2022 года его взломали на обычном компьютере примерно за час, математикой, придуманной для совсем других целей. Это урок шифровального отдела: стойкость не объявляют, её проверяют, и новым односторонним функциям доверяют только после многих лет атак.
Задачи
Четыре задачи: обмен ключами, полный RSA, взлом короткого ключа и хранение паролей. В модуле cs.pk есть is_prime, random_prime, группа MODP_P, MODP_G и rsa_keys; в задачах ими можно пользоваться, кроме тех мест, где условие просит сделать самим.
Напишите power_mod(base, exp, mod) — остаток от деления $\text{base}^{\text{exp}}$ на $\text{mod}$ для целых $\text{exp} \ge 0$ и $\text{mod} \ge 1$, — не пользуясь ** и pow. И две функции обмена Диффи — Хеллмана: public_key(p, g, secret) — открытая «смесь» $g^{\text{secret}} \bmod p$, и shared_secret(p, other_public, secret) — общий секрет из чужой смеси и своего показателя. Тесты проводят обмен в 2048-битной группе из главы, где показатели — числа из шестисот цифр, и дают на три обмена секунду. Заготовка умножает в цикле — посчитайте, сколько бы это заняло.
Посмотрите на двоичную запись показателя. $g^{13} = g^{8} \cdot g^{4} \cdot g^{1}$, потому что $13 = 1101_2$. А $g, g^2, g^4, g^8, \ldots$ получаются друг из друга возведением в квадрат. Значит, нужен цикл по битам показателя: на каждом шаге основание возводится в квадрат, а если очередной бит — единица, текущее основание домножается в результат.
Младший бит числа — exp % 2, а сдвиг к следующему — exp // 2. После каждого умножения берите остаток по модулю: иначе числа вырастут до миллионов цифр.
Один тест с подвохом: power_mod(7, 0, 1). Любое число по модулю 1 — ноль, даже $7^0 = 1$.
Цикл делает столько шагов, сколько битов в показателе: для 2048-битного — 2048 возведений в квадрат и в среднем 1024 умножения. Заготовка для того же показателя сделала бы $2^{2047}$ умножений — больше, чем можно сосчитать до конца света. Это тот же приём, что в задаче «Степень за двадцать шагов», только без рекурсии и с остатком на каждом шаге. Встроенная pow(base, exp, mod) устроена по той же идее и написана на C, но на числах в 2048 бит выигрывает у нашей функции лишь в полтора раза: почти всё время уходит на умножение огромных чисел, а его и так делает C.
Соберите RSA из пяти функций. make_keys(p, q, e=65537) возвращает пару ключей ((n, e), (n, d)); если p == q или $e$ не взаимно просто с $\varphi = (p - 1)(q - 1)$, она выбрасывает ValueError. encrypt(m, public) и decrypt(c, private) шифруют и расшифровывают число $0 \le m < n$. sign(m, private) подписывает число $m$, а verify(m, signature, public) возвращает True или False. Простые числа тесты передают сами — от учебных $61$ и $53$ до 512-битных. Заготовка вычисляет $d$ с ошибкой, которую делают очень часто.
pow(e, -1, x) находит число, обратное к $e$ по модулю $x$. Но по какому модулю нужно обратное в RSA? Перечитайте рецепт: $e \cdot d \equiv 1 \pmod{\varphi}$, а не по модулю $n$.
Проверку взаимной простоты делает math.gcd. Если gcd(e, phi) != 1, обратного нет, и pow(e, -1, phi) сама выбросит ValueError, — но лучше проверить явно и выбросить исключение с понятным сообщением. Случай p == q проверка взаимной простоты не поймает.
Подпись — это «расшифровка» сообщения закрытым ключом, а проверка — «шифрование» подписи открытым и сравнение результата с сообщением.
Обратный элемент по модулю $n$ вместо $\varphi$ — ошибка, после которой всё выглядит работающим: ключи есть, шифровка есть, только расшифровка выдаёт мусор. Теорема о том, что $m^{ed} \equiv m \pmod n$, требует именно $ed \equiv 1 \pmod{\varphi}$. При $p = q$ формула $\varphi = (p - 1)^2$ неверна — для квадрата простого $\varphi(p^2) = p(p - 1)$, — и к тому же $n = p^2$ раскладывается одним извлечением корня. А verify сравнивает с m % n, чтобы подпись числа, большего модуля, не ломала проверку; на деле подписывают отпечаток, который всегда меньше $n$.
Ева перехватила шифровку $c$ и знает открытый ключ $(n, e)$, но модуль короткий — до 64 бит. Напишите crack(n, e, c), которая возвращает открытый текст $m$. Заготовка раскладывает $n$ перебором делителей, и с учебными ключами она справляется. Но для 64-битного модуля из двух 32-битных простых ей пришлось бы перебрать до четырёх миллиардов делителей, а тесты дают на пять таких ключей четыре секунды.
Вспомните дни рождения из главы 16. Если брать случайные числа по модулю неизвестного делителя $p$, повтор появится примерно через $\sqrt p$ попыток. Для 32-битного $p$ это десятки тысяч шагов вместо миллиардов. Как заметить повтор по модулю $p$, не зная $p$? Если $x \equiv y \pmod p$, то $p$ делит $x - y$, и $\gcd(x - y, n)$ — больше единицы.
Случайные числа заменяют последовательностью $x \to x^2 + 1 \bmod n$: она выглядит случайной, а по модулю $p$ рано или поздно зацикливается — её путь похож на греческую букву ρ, отсюда название ро-метода Полларда. Цикл ловят двумя бегунами: «черепаха» делает один шаг, «заяц» — два, и после каждого шага считают $\gcd(|x - y|, n)$. Как только он больше единицы, делитель найден.
Изредка $\gcd$ оказывается равен самому $n$: оба множителя зациклились одновременно. Тогда начните заново с другой последовательностью, например $x^2 + 2$.
Перебор делителей тратит до $\sqrt n$ шагов, ро-метод — около $\sqrt p \le \sqrt[4]{n}$: для 64-битного модуля это разница между миллиардами и десятками тысяч. Закрытый ключ после разложения находится той же формулой, что у владельца, — у Евы теперь есть всё, что было у него. Но и ро-метод растёт экспоненциально: каждые восемь бит модуля — вчетверо дольше. В лаборатории RSA он за секунды справляется с ключами в 80–90 бит, а к 2048 битам не подходит и близко.
Напишите две функции для хранения паролей. hash_password(password) возвращает строку для базы данных вида pbkdf2_sha256$итерации$соль$хеш: число итераций — не меньше 100 000, соль — не меньше 16 случайных байтов, своя при каждом вызове, соль и хеш — в шестнадцатеричной записи, а хеш — hashlib.pbkdf2_hmac("sha256", …) от пароля в UTF-8 с этой солью. check_password(password, stored) возвращает True, если пароль подходит к сохранённой строке. Учтите, что строки в базе могли быть созданы в другие годы, с другим числом итераций. Заготовка хранит обычный SHA-256 без соли — почти как LinkedIn в 2012 году, только там был SHA-1.
Соль — secrets.token_bytes(16), в строку её превращает метод .hex(), а обратно — bytes.fromhex(…). Функция hashlib.pbkdf2_hmac("sha256", пароль_в_байтах, соль, итерации) возвращает байты хеша.
check_password не может просто вызвать hash_password и сравнить: соль каждый раз новая. Разберите сохранённую строку по знаку $, возьмите из неё соль и число итераций, посчитайте хеш введённого пароля с ними и сравните.
Число итераций хранится в самой строке, поэтому его можно поднимать с годами: старые пароли проверяются со старым числом, а при следующем входе пользователя сайт пересчитывает хеш с новым. Похоже хранит пароли фреймворк Django: алгоритм, число итераций, соль и хеш в одной строке. Сравнение через hmac.compare_digest тратит одинаковое время, где бы ни нашлось первое расхождение: обычное == останавливается на первом несовпавшем байте, и по времени ответа противник теоретически может подбирать хеш байт за байтом. Это тот же побочный канал, что в главе 35, только в миниатюре.
Куда дальше
Вопрос, который в начале главы звучал как парадокс, решён: двое договариваются о секрете при свидетелях, подпись нельзя подделать, пароль хранят, не зная его. Всё это держится на нескольких односторонних функциях — разложении на множители, дискретном логарифме, задачах о решётках. Их не умеют обращать ни в открытых университетах, ни, судя по всему, в закрытых ведомствах, и для 2048-битного ключа никакого компьютера на Земле не хватит.
И всё же по дороге мы уже видели, где такие системы ломаются. Тысячи ключей RSA разложил один алгоритм Евклида, потому что при рождении ключей не хватило случайности. Хеши LinkedIn хранились без соли, и после утечки многие пароли быстро подобрали. Телеграммы, которые прочла «Венона», выдал один блокнот на два письма. Математика стойкая, а взламывают системы через ошибки людей, которые их строят: забытую проверку длины, склеенный из строк запрос, лишние права. Как это происходит и как писать код, который так не ломается, — следующая глава, учебный полигон.