Случайные числа в электронной подписи
Случайности не случайны. Истина где-то рядом.
Пока вы двигали шайбу в нашей мини-игре, каждое движение пальца или мыши немного отличалось от предыдущего. Скорость, траектория, паузы — всё это трудно точно предсказать заранее.
Для электронной подписи такая непредсказуемость тоже очень важна.
Случайные числа используются как минимум в двух местах:
при создании закрытого ключа;
при формировании каждой новой электронной подписи.
Это два разных числа и две разные задачи.
Первое становится постоянным секретом владельца ключа. Второе используется один раз и помогает безопасно создать конкретную подпись.
Если случайность окажется слабой, предсказуемой или повторится там, где не должна, даже хороший криптографический алгоритм может лишиться защиты.
Так что в криптографии случайность — не хаос и не «авось». Наоборот, это очень дисциплинированная случайность.
Закрытый ключ: придумать нельзя сгенерировать
У электронной подписи есть два математически связанных ключа:
закрытый ключ хранится в секрете и используется при подписании;
открытый ключ можно передавать другим людям — он используется для проверки.
Закрытый ключ нельзя выбирать как пароль:
Ivan1985
или:
12345678
И даже такой вариант:
SuperMegaSecretKey2026!!!
не становится хорошим криптографическим ключом только потому, что в нём есть восклицательные знаки.
Закрытый ключ должен быть создан криптографическим генератором из достаточно непредсказуемых данных.
В упрощённом виде его можно представить как очень большое случайное число:
Непредсказуемые данные ↓ Криптографический генератор ↓ Закрытый ключ
Для ГОСТ Р 34.10-2012 закрытый ключ — число из определённого диапазона, заданного параметрами используемой эллиптической кривой.
В зависимости от варианта алгоритма используются параметры порядка 256 или 512 бит.
Например:
2²⁵⁶ ≈ 1,16 × 10⁷⁷
Это число примерно из 78 десятичных цифр.
Вариантов столько, что перебрать их все практически невозможно.
Но есть нюанс.
Большое — ещё не значит случайное
Представим, что программа создаёт огромный ключ так:
Текущая дата + Время запуска ↓ «Случайный» ключ
На вид получится длинное число.
Но если злоумышленник знает примерное время создания ключа, он сможет проверить ограниченное количество вариантов.
То есть ключ большой, а реальная непредсказуемость маленькая.
Можно сравнить с дверью, на которой установлен замок с миллиардами комбинаций, но хозяин всегда выбирает код из года рождения.
Формально возможностей много.
Практически — заметно меньше.
Поэтому в криптографии важна не только длина ключа, но и то, как именно он был создан.
Энтропия: немного порядка в царстве хаоса
Для описания непредсказуемости используют слово энтропия.
Чем меньше посторонний знает о будущем результате, тем выше неопределённость и тем труднее угадать созданный ключ.
Источниками энтропии могут быть:
аппаратные генераторы физических случайных процессов;
шум электронных компонентов;
системные события;
временные интервалы между действиями;
движения мыши;
нажатия клавиш;
сочетание нескольких независимых источников.
Но здесь важно не представлять процесс слишком буквально.
Одно движение мыши не превращается напрямую в кусочек закрытого ключа.
Обычно события:
собираются;
смешиваются;
проходят криптографическую обработку;
влияют на внутреннее состояние генератора.
Упрощённо:
Движения мыши + Нажатия клавиш + Системные события + Другие источники ↓ Сбор и обработка энтропии ↓ Криптографический генератор ↓ Непредсказуемые числа
Именно здесь появляется связь с нашей мини-игрой: действия человека могут давать системе дополнительную непредсказуемость.
Но это не означает, что любой ключ создаётся исключительно мышью.
Современные операционные системы, аппаратные устройства и средства криптографической защиты используют собственные источники и механизмы накопления энтропии.
Так что если программа просит подвигать мышью, она не проверяет, проснулись ли вы.
Скорее всего, она собирает дополнительную случайность.
Может ли компьютер придумать случайность
Компьютер выполняет инструкции по определённым правилам.
Если запустить обычный детерминированный алгоритм дважды с совершенно одинаковым начальным состоянием, он выдаст одинаковый результат.
Поэтому в криптографии разделяют два понятия.
Источник физической случайности
Он получает данные из процессов, которые трудно точно предсказать:
электронного шума;
джиттера генератора;
физических процессов;
аппаратных источников.
Такие устройства называют аппаратными генераторами или датчиками случайных чисел.
Криптографически стойкий генератор псевдослучайных чисел
Такой генератор работает алгоритмически.
Он получает непредсказуемое начальное состояние — зерно, или seed, — а затем создаёт длинную последовательность значений.
Энтропия ↓ Начальное состояние генератора ↓ Криптографически стойкий генератор ↓ Псевдослучайная последовательность
Слово «псевдослучайная» звучит подозрительно.
Будто случайность ненастоящая и куплена на маркетплейсе.
Но в криптографии это нормальный и широко используемый подход.
При правильной конструкции результат должен быть практически непредсказуем для того, кто не знает внутреннее состояние генератора.
Физическую энтропию можно собирать постепенно, а криптографический генератор быстро выдаёт нужное количество случайных данных.
random() хорош для игры. Для ключа — нет
Во многих языках программирования есть функции вроде:
random()
Они полезны для:
игр;
анимации;
моделирования;
случайного выбора;
перемешивания списка.
Например, с их помощью можно определить, какой сундук появится на карте или куда полетит виртуальный мяч.
Но генератор для игры не обязан подходить для криптографии.
Обычные псевдослучайные генераторы могут быть быстрыми и выглядеть случайными, но при этом оставаться предсказуемыми.
Если злоумышленник узнает часть результатов или восстановит внутреннее состояние, он иногда сможет вычислить следующие значения.
Для электронной подписи этого недостаточно.
Нужен криптографически стойкий генератор случайных чисел, у которого предсказание будущих значений по известным результатам должно быть вычислительно неосуществимым.
Поэтому нельзя создавать ключ так:
ключ = random()
или:
ключ = текущее_время
или:
ключ = дата_рождения + номер_телефона
Даже если результат выглядит длинным и сложным, настоящей непредсказуемости в нём может быть совсем немного.
Первый акт: рождается закрытый ключ
Ключевая пара обычно создаётся один раз на определённый период использования.
Процесс можно представить так:
Надёжная случайность ↓ Закрытый ключ d ↓ Математическое преобразование ↓ Открытый ключ Q
Закрытый ключ остаётся у владельца.
Открытый вычисляется из закрытого и может быть включён в сертификат.
Для криптографии на эллиптических кривых связь часто записывают так:
Q = d × G
где:
d— закрытый ключ;G— заранее заданная базовая точка;Q— открытый ключ.
Вычислить Q, зная d, легко.
Получить d, зная только G и Q, при правильно выбранных параметрах считается вычислительно неосуществимым.
Но вся защита начинается с одного условия:
d должно быть действительно непредсказуемым.
Если закрытый ключ можно угадать, сложную задачу на эллиптической кривой решать уже не потребуется.
Зачем идти через математические дебри, если секрет лежит под ковриком.
Почему человек — плохой генератор случайных чисел
Если попросить людей назвать «случайное число», многие будут:
избегать повторяющихся цифр;
чаще выбирать одни значения и реже другие;
использовать даты;
строить красивые последовательности;
выбирать то, что легко запомнить.
Например:
7391852046
выглядит вполне случайно.
Но неизвестно, как оно появилось.
Возможно, это:
две даты подряд;
часть номера телефона;
комбинация из любимых чисел;
результат простого генератора.
Человек хорошо замечает закономерности.
Но плохо создаёт их отсутствие.
Поэтому случайность нельзя оценивать «на глаз».
Ключи должны создавать проверенные криптографические средства, а не пользователь вручную.
Случайный ключ создали. Теперь его нужно не потерять
После создания закрытый ключ должен оставаться секретным.
Он может храниться:
на USB-токене;
на смарт-карте;
в защищённом контейнере;
в аппаратном криптографическом модуле;
в инфраструктуре облачной электронной подписи.
Здесь важно разделять две задачи:
случайность защищает ключ от угадывания;
защищённое хранение защищает созданный ключ от кражи.
Очень хороший случайный ключ не поможет, если его скопировали.
И наоборот: надёжный токен не исправит ключ, созданный предсказуемым генератором.
Можно изготовить идеальный ключ от сейфа.
Но если оставить его в дверце — математике будет обидно.
Второй акт: новая случайность при каждой подписи
На создании ключевой пары роль случайности не заканчивается.
При формировании подписи по ГОСТ Р 34.10-2012 используется новое случайное или псевдослучайное число.
Обычно его обозначают буквой:
k
Это одноразовый параметр подписи.
Упрощённо:
Документ ↓ Хеш документа + Закрытый ключ d + Новое одноразовое число k ↓ Электронная подпись
Закрытый ключ d используется многократно в течение срока эксплуатации.
А k создаётся заново для каждой подписи.
Подпись документа № 1 Закрытый ключ d + одноразовое число k₁ Подпись документа № 2 Тот же закрытый ключ d + новое число k₂ Подпись документа № 3 Тот же закрытый ключ d + новое число k₃
Главное условие:
k₁ ≠ k₂ ≠ k₃
Это упрощённая запись.
Смысл в том, что значения должны безопасно формироваться и не использоваться повторно.
Зачем подписи ещё одно секретное число
Можно спросить:
Если закрытый ключ уже секретный, зачем добавлять ещё один?
Одноразовый параметр участвует в математике подписи и не даёт многократным вычислениям раскрыть постоянный секрет.
В ГОСТ Р 34.10-2012 подпись состоит из двух чисел:
r и s
Без погружения во все детали одну из частей вычисления можно представить так:
s = (r × d + k × e) mod q
где:
d— закрытый ключ;k— одноразовое число;e— значение, полученное из хеша документа;r— первая часть подписи;q— параметр используемой группы.
Формула приведена не для ручного расчёта.
Не нужно доставать инженерный калькулятор и пытаться подписать договор в блокноте.
Она показывает важную связь:
В одной подписи одновременно участвуют документ, постоянный закрытый ключ и новое одноразовое число.
Правильно созданное k не раскрывается вместе с подписью.
Но если оно предсказуемо или используется повторно, математика может начать выдавать информацию о закрытом ключе.
Дважды в одну случайность лучше не входить
Представим, что два разных документа подписали одним закрытым ключом и по ошибке использовали одинаковое k.
Получатся две подписи:
Документ A Хеш e₁ Одноразовое число k Закрытый ключ d ↓ Подпись A Документ B Хеш e₂ То же число k Тот же закрытый ключ d ↓ Подпись B
У наблюдателя есть:
оба документа;
обе подписи;
открытые параметры алгоритма.
Повторившийся одноразовый параметр создаёт математическую связь между подписями.
В некоторых схемах из этих данных можно восстановить сначала одноразовое число, а затем и закрытый ключ.
То есть одна ошибка генератора способна раскрыть секрет, который должен был использоваться годами.
После компрометации закрытого ключа злоумышленник сможет создавать новые подписи, соответствующие той же ключевой паре.
Вот почему одноразовое число действительно должно быть одноразовым.
Название здесь не декоративное.
А если число не повторилось, но его можно предсказать?
Полное совпадение — не единственная опасность.
Проблемы могут возникнуть, если k:
предсказуемо;
имеет слишком мало возможных значений;
зависит от времени;
содержит систематическое смещение;
частично раскрывается через ошибки реализации;
генерируется слабым или скомпрометированным источником.
Даже небольшая утечка информации о множестве одноразовых значений в некоторых схемах может ослабить защиту закрытого ключа.
Поэтому генератор случайных чисел — не второстепенная утилита где-то в подвале программы.
Это часть криптографической безопасности.
Пользователь нажал «Подписать». Где вся эта случайность?
Обычно пользователь ничего не замечает.
Он выбирает документ и запускает подписание:
Выбор документа ↓ Вычисление хеша ↓ Формирование одноразового числа ↓ Вычисление подписи ↓ Готовая электронная подпись
Пользователю не нужно:
придумывать
k;вводить его вручную;
записывать на бумажку;
сохранять рядом с документом;
передавать проверяющей стороне.
Криптографическое средство делает всё автоматически.
Во время создания ключевой пары некоторые программы могут предложить подвигать мышью или нажимать клавиши.
Это способ получить дополнительную энтропию, а не ритуал посвящения в криптографы.
Но при каждом обычном подписании заново водить мышью по экрану не требуется.
Генератор работает внутри системы и получает нужное состояние предусмотренным способом.
Случайность не обязана выглядеть случайной
Нам кажется, что:
1111111111111111
выглядит неслучайно.
А:
5830271946104827
выглядит случайно.
Но по одному результату нельзя надёжно определить качество генератора.
Даже хороший источник теоретически может выдать длинную последовательность одинаковых битов.
Редкое событие не становится невозможным.
Качество оценивают по:
устройству генератора;
источникам энтропии;
модели угроз;
контролю внутреннего состояния;
требованиям к реализации.
А не по тому, насколько хаотично выглядит одна строка.
Иначе самым надёжным генератором считался бы кот, пробежавший по клавиатуре.
Случайность и уникальность — не близнецы
Эти понятия часто путают.
Уникальное значение должно отличаться от других.
Случайное значение должно быть непредсказуемым.
Например:
1001 1002 1003 1004
Все значения уникальны.
Но следующий номер угадать нетрудно.
Точная отметка времени тоже может быть почти уникальной, но часто предсказуема.
Поэтому:
номер документа;
идентификатор;
счётчик;
время создания
не становятся автоматически хорошими криптографическими секретами.
Иногда алгоритму нужна уникальность.
Иногда — непредсказуемость.
Иногда — оба свойства.
Требования зависят от конкретной схемы.
Хорошая случайность не спасёт от плохой практики
Даже идеальный генератор не решает все проблемы.
Электронная подпись остаётся безопасной только при сочетании нескольких условий:
Качественная случайность + Стойкий алгоритм + Правильные параметры + Корректная реализация + Защищённое хранение ключа + Безопасное использование
Слабость любого элемента может повлиять на результат.
Например:
надёжный ключ можно украсть;
хороший алгоритм можно реализовать с ошибкой;
защищённый токен можно использовать на заражённом компьютере;
владелец может передать другому человеку токен и PIN-код;
пользователь может подписать не тот документ.
Криптография защищает математическую часть процесса.
Но она не умеет выхватывать токен из рук злоумышленника и не читает документ вместо пользователя.
Пока.
Что важно пользователю
Обычно управлять генератором случайных чисел вручную не требуется.
Практические правила просты:
создавайте ключи средствами, предназначенными для электронной подписи;
не придумывайте закрытый ключ самостоятельно;
не заменяйте криптографический генератор обычной функцией
random();не прерывайте без необходимости процесс сбора дополнительной энтропии;
храните закрытый ключ в предусмотренной защищённой среде;
не передавайте другим людям токен, ключевой контейнер и PIN-код.
Большая часть работы происходит внутри криптографического средства.
И это хорошо.
Пользователю достаточно подписывать документы.
Пусть случайными числами занимается тот, кто умеет.
Главное
Случайность защищает электронную подпись дважды.
При создании ключевой пары:
Случайность ↓ Закрытый ключ ↓ Открытый ключ
При подписании документа:
Хеш документа + Закрытый ключ + Новое одноразовое число ↓ Электронная подпись
Закрытый ключ должен быть непредсказуемым, чтобы его нельзя было угадать.
Одноразовое число должно безопасно формироваться для каждой подписи, чтобы вычисления не раскрывали закрытый ключ.
Именно поэтому случайность — не дополнительная функция и не формальность.
Это одна из опор всей электронной подписи.
Но случайное число само по себе ещё не создаёт открытый ключ.
Нужна математическая конструкция, которая позволяет легко перейти от секрета к открытому значению и делает обратный путь вычислительно неосуществимым.
В следующей статье: «Зачем электронной подписи нужна эллиптическая кривая».