Создание и проверка электронной подписи
Как создаётся и проверяется электронная подпись: весь процесс по шагам
Как создаётся и проверяется электронная подпись: весь процесс по шагам
Нажал «Подписать» — и началось. Нет, не магия
В предыдущих статьях мы разобрали детали будущего механизма по отдельности:
случайность помогает сформировать закрытый ключ и защищает каждую новую подпись;
открытый ключ позволяет проверять подпись, не раскрывая закрытый.
Теперь пора собрать всё вместе. Вы нажимаете на кнопку «Подписать», и, через мгновение, получает файл электронной подписи или документ со встроенной подписью.
За этой короткой операцией скрывается целая цепочка вычислений:
Документ ↓ Хеш ↓ Одноразовое число ↓ Операции на эллиптической кривой ↓ Два числа подписи: r и s ↓ Готовая электронная подпись
При проверке процесс идёт другим путём:
Документ + Подпись + Открытый ключ ↓ Повторное вычисление хеша ↓ Операции на эллиптической кривой ↓ Подпись верна или Проверка не пройдена
Разберём оба процесса без прыжка сразу в высшую математику. Хотя немного букв всё-таки будет., и они уже пришли и расселись по формулам :)
Кто участвует в процессе
Для создания и проверки подписи нужны несколько элементов.
Документ
В стандарте его обычно называют «сообщением» и обозначают буквой «M» — message. Это может быть:
PDF-Документ;
XML-файл;
текстовый файл;
ZIP, RAR-архив и т.п.;
изображение;
видео, аудио, программа или любой набор данных;
любой другой конечный набор байтов.
Криптографический алгоритм не знает, договор перед ним или фотография кота. Для него это последовательность нулей и единиц.
Хеш-функция
С помощью неё сначала вычисляют цифровой отпечаток документа:
H = h(M)
где:
M— документ;h— хеш-функция;H— полученный хеш.
Для ГОСТ-подписи используется хеш-функция, описанная в ГОСТ Р 34.11-2012.
Закрытый ключ
Обозначим его как «d». Это секретное число владельца. Оно используется при создании подписи и не должно передаваться проверяющей стороне.
Открытый ключ
Обозначим его как «Q» Он математически связан с закрытым:
Q = d × G
В тексте ГОСТа базовую точку обычно обозначают P. В предыдущей статье мы использовали распространённое обозначение G.
Смысл один:
Открытый ключ = закрытый ключ × базовая точка
Открытый ключ используется при проверке.
Одноразовое число
Обозначим его «k». Оно заново формируется для каждой подписи. Это число не является частью готовой подписи и не должно раскрываться.
Параметры криптографической схемы
В вычислениях участвуют:
параметры конечного поля;
коэффициенты эллиптической кривой;
базовая точка;
порядок используемой подгруппы;
другие заранее определённые значения.
Пользователь обычно их не вводит. И это хорошо, потому, что, например если при подписании вам бы система выдала такое окно с запросом:
Введите порядок циклической подгруппы точек эллиптической кривой
то, это вряд ли улучшило бы удобство сервиса.
До нажатия кнопки: ключи уже должны существовать
Электронная подпись начинается не в момент подписания документа.
Раньше была создана ключевая пара:
Случайное число d ↓ Закрытый ключ ↓ Умножение базовой точки ↓ Открытый ключ Q
Закрытый ключ хранится у владельца:
на токене;
в защищённом ключевом контейнере;
в аппаратном модуле;
в инфраструктуре облачной подписи.
Открытый ключ может находиться в сертификате. Также, важно, что при каждом подписании новая ключевая пара обычно не создаётся. Один закрытый ключ может использоваться для множества подписей в течение предусмотренного срока.
А вот новое одноразовое число k требуется для каждой подписи. Не перепутать:
d — постоянный секрет владельца k — новый одноразовый параметр подписи
Шаг 1. Программа получает именно те данные, которые будут подписаны
Допустим, пользователь выбрал файл «dogovor.pdf». Сначала программа читает его содержимое. Подписывается не название файла и не картинка, которую человек видит на экране. Подписывается конкретная последовательность байтов.
Имя файла: dogovor.pdf Содержимое: 25 50 44 46 2D 31 2E 37 ...
Для человека важны страницы, таблицы и текст.
Для криптографического алгоритма — байты.
Поэтому:
переименование неизменённого файла обычно не меняет подпись;
повторное сохранение PDF может изменить его внутренние байты;
два визуально одинаковых документа могут иметь разные хеши;
подпись одного файла нельзя проверить на другом, если их содержимое различается.
Первое правило криптографической кухни:
Что подали на вход, то и подписали.
Не то, что хотели подписать. Не то, что было открыто пять минут назад. А именно тот набор данных, который получил механизм подписи.
Шаг 2. Вычисляется хеш документа
Документ может занимать:
2 КБ 20 МБ 2 ГБ
Алгоритму подписи не нужно выполнять операции на эллиптической кривой отдельно для каждого байта.
Сначала вычисляется компактный цифровой отпечаток:
H = h(M)
Схематично:
Документ M ↓ Хеш-функция ↓ Хеш H
Для выбранного варианта алгоритма длина хеша фиксирована. Документ может быть огромным, но результат будет определённого размера. Это позволяет связать подпись со всем содержимым файла. Именно эта операция создания цифрового отпечатка (хеша) занимает разное время в зависимости от мощности компьютера на котором это происходит и от размера файла.
Изменился хотя бы один байт:
M → M'
изменится и хеш:
H → H'
А значит, исходная подпись уже не должна пройти проверку для изменённого документа. Хеш здесь работает как чрезвычайно чувствительный цифровой отпечаток.
Переставили запятую — новый отпечаток. Поменяли сумму — новый отпечаток. Программа пересохранила внутренние объекты PDF — тоже может получиться новый отпечаток. Хеш-функция не читает смысл. Она педантична до последнего байта.
Шаг 3. Хеш превращается в число для дальнейших вычислений
Хеш — последовательность битов. Математике подписи нужно представить её как число.
Упрощённо:
Хеш H ↓ Число α ↓ e = α mod q
Здесь:
α— числовое представление хеша;q— порядок используемой подгруппы точек;e— значение, которое будет участвовать в подписи.
Для общего понимания достаточно помнить:
Хеш документа переводится в числовую форму, подходящую для математики конкретной криптографической схемы.
Сам документ при этом не исчезает.
Он понадобится проверяющей стороне, чтобы вычислить тот же хеш заново.
Шаг 4. Создаётся новое одноразовое число
Теперь криптографическое средство формирует «k»
Для него должно выполняться условие:
0 < k < q
Это новое случайное или псевдослучайное число.
Оно используется только в текущей подписи.
Документ № 1 → k₁ Документ № 2 → k₂ Документ № 3 → k₃
Постоянным остаётся закрытый ключ «d», а одноразовый параметр меняется «k». Почему это важно, мы подробно разобрали в предыдущей статье.
Если k повторяется или становится предсказуемым, может возникнуть угроза раскрытия закрытого ключа. Так что перед нами не одноразовый пароль из SMS. Но принцип «использовал и забыл» здесь очень кстати.
Шаг 5. Одноразовое число отправляется гулять по кривой
Теперь вычисляется точка эллиптической кривой C = k × G (или в обозначениях стандарта C = k × P)
Здесь:
k— одноразовое число;GилиP— базовая точка;C— полученная точка.
У точки есть две координаты:
C = (xC, yC)
Для формирования подписи используется её координата x.
Из неё получают первую часть подписи:
r = xC mod q
Если вдруг получилось:
r = 0
выбирается новое k, и вычисление повторяется.
Такое событие для корректных больших параметров крайне маловероятно.
Но стандарт не полагается на:
Да ладно, вряд ли выпадет.
Он явно говорит, что делать.
Криптография вообще не любит фразу «авось пронесёт».
Шаг 6. Вычисляется вторая часть подписи
Теперь в одной формуле встречаются:
первая часть подписи
r;закрытый ключ
d;одноразовое число
k;значение
e, полученное из хеша документа.
Вычисляется:
s = (r × d + k × e) mod q
Если:
s = 0
одноразовое число создаётся заново, и процесс повторяется.
В результате получены два числа:
r s
Это и есть математическая сердцевина электронной подписи.
Можно представить процесс так:
Документ M ↓ Хеш H ↓ Число e │ ├──────────────┐ │ │ │ Одноразовое k │ ↓ │ C = k × G │ ↓ │ r │ │ └──────┐ │ ▼ ▼ Закрытый ключ d │ ▼ s = (r × d + k × e) mod q │ ▼ Подпись (r, s)
Формула выглядит грозно. Но пользователю не нужно считать её вручную. Криптографическое средство делает это быстрее, чем мы успеваем произнести:
дискретное логарифмирование в группе точек эллиптической кривой.
Шаг 7. Два числа превращаются в готовую подпись
Числа r и s кодируются в последовательность битов или байтов.
В ГОСТ Р 34.10-2012 предусмотрены варианты подписи:
с параметрами порядка 256 бит;
с параметрами порядка 512 бит.
Сама математическая подпись состоит из двух частей.
Упрощённо:
r || s
Символ:
||
означает конкатенацию — соединение последовательностей.
Но реальный файл электронной подписи может содержать намного больше, чем два числа.
Например, контейнер подписи может включать:
значение криптографической подписи;
сведения об алгоритмах;
сертификат подписанта;
подписанные атрибуты;
метку доверенного времени;
дополнительные данные для проверки.
Нужно различать:
Криптографическая подпись = математическое значение r, s Файл или контейнер подписи = структура, которая может хранить подпись и дополнительные сведения
Это как двигатель и автомобиль. Двигатель — главная рабочая часть, но в готовой машине есть ещё кузов, колёса, приборы и тот самый индикатор, который почему-то загорелся перед дальней поездкой.
Что передаётся получателю
Для проверки нужны:
Документ Электронная подпись Открытый ключ
Открытый ключ обычно получают из сертификата. Закрытый ключ не передаётся. Одноразовое число k тоже не передаётся. Проверяющий получает результат вычислений, но не секретные значения, которые использовались при подписании.
Остаётся у подписанта: Закрытый ключ d Не раскрывается: Одноразовое число k Передаётся или доступно проверяющему: Документ M Подпись r, s Открытый ключ Q
Теперь начинается обратная сторона процесса.
Не создание подписи, а её проверка.
Проверка. Шаг 1. Из подписи извлекаются числа
Проверяющая программа получает подпись и выделяет:
r s
Сначала проверяется, находятся ли они в допустимом диапазоне:
0 < r < q 0 < s < q
Если условие не выполняется, подпись сразу считается некорректной.
Нет смысла продолжать сложные вычисления с данными, которые не соответствуют формату математической схемы.
Это как билет на поезд, в котором вместо номера вагона написано:
банан
До проверки места дело уже не дойдёт.
Проверка. Шаг 2. Хеш документа вычисляется заново
Проверяющая сторона не обязана доверять хешу, который якобы использовал подписант.
Она берёт полученный документ и самостоятельно вычисляет:
H = h(M)
Затем снова получает:
e
тем же способом, который использовался при подписании.
Полученный документ ↓ Та же хеш-функция ↓ Хеш ↓ Число e
Если документ изменился, получится другое значение. И дальше математическая проверка не должна сойтись. Именно поэтому электронной подписи нужен исходный документ.
Для отсоединённой подписи одного файла .sig недостаточно: нужно указать, какой документ проверять. Подпись не телепат. Она не угадает, к какому файлу относилась.
Проверка. Шаг 3. Вычисляется обратное значение
Программа находит число:
v = e⁻¹ mod q
Это называется мультипликативным обратным значением по модулю q.
Оно обладает свойством:
e × v = 1 mod q
Это не обычная дробь:
1 / e
из школьного калькулятора.
В модульной арифметике всё немного иначе. Но роль похожа: значение v помогает математически «развернуть» часть вычислений подписи.
Проверка. Шаг 4. Вычисляются два коэффициента
Далее программа получает:
z₁ = s × v mod q
и:
z₂ = −r × v mod q
Эти значения будут использоваться в операциях с точками эллиптической кривой.
Пока всё выглядит так:
Документ ↓ Хеш ↓ e ↓ v / \ / \ z₁ z₂
В этот момент буквы уже явно захватили статью. Но осталось главное действие.
Проверка. Шаг 5. Закрытого ключа нет — и не нужен
Проверяющая сторона не знает:
d
и не знает:
k
У неё есть открытый ключ:
Q
Вычисляется точка:
C = z₁ × G + z₂ × Q
В обозначениях стандарта:
C = z₁ × P + z₂ × Q
Здесь используются:
базовая точка;
открытый ключ подписанта;
значения, полученные из документа и подписи.
Затем из координаты x точки C вычисляется:
R = xC mod q
Обратите внимание:
r
было получено при создании подписи.
А:
R
вычислено проверяющей стороной самостоятельно.
Теперь их сравнивают.
Финальная проверка: сошлось или не сошлось
Условие очень короткое:
R = r
Если равенство выполняется:
Подпись прошла криптографическую проверку
Если нет:
Подпись недействительна
И важно, что проверяющий не восстановил закрытый ключ. Не узнал одноразовое число. Не повторил процесс подписания.
Он выполнил другое вычисление, которое должно дать согласованный результат только для правильной комбинации:
документ + подпись + открытый ключ
Почему проверка вообще сходится
Внутри формул есть математическая компенсация.
При подписании:
s = r × d + k × e
При проверке используются:
z₁ = s × e⁻¹ z₂ = −r × e⁻¹
и открытый ключ:
Q = d × G
Подставим идею без всех обозначений mod q:
z₁ × G + z₂ × Q
Поскольку:
Q = d × G
получаем:
(s × e⁻¹) × G − (r × e⁻¹) × (d × G)
А в s уже содержится:
r × d + k × e
Части с:
r × d
взаимно уничтожаются.
Остаётся вклад одноразового числа:
k × G
Именно из этой точки при подписании было получено r.
Поэтому проверяющая сторона должна прийти к той же координате и получить:
R = r
Если документ изменился, изменится
e.Если подпись изменена, изменятся
rилиs.Если используется другой открытый ключ, изменится
Q.
В каждом случае компенсация перестанет работать. Математический пазл не сложится.
Что будет, если изменить документ
Подписали:
Стоимость работ: 100 000 рублей.
После подписания изменили:
Стоимость работ: 900 000 рублей.
Получится новый хеш:
H₁ ≠ H₂
Значит:
e₁ ≠ e₂
Проверяющая программа построит другие значения:
v z₁ z₂ R
И в итоге:
R ≠ r
Проверка завершится ошибкой. Подпись не блокирует редактирование файла. Она делает изменение обнаруживаемым. Это разные вещи. Можно открыть подписанный документ в редакторе и поменять текст, но исходная подпись больше не будет подтверждать изменённую версию.
Что будет, если заменить подпись
Если изменить хотя бы часть r или s, математическая связь нарушится.
Документ прежний ↓ Открытый ключ прежний ↓ Подпись изменена ↓ Проверка не пройдена
Случайное изменение обычно просто повреждает подпись.
А создать новую правильную подпись без закрытого ключа должно быть вычислительно неосуществимо.
Что будет, если использовать чужой открытый ключ
Представим:
документ подписан закрытым ключом Алисы;
для проверки подставили открытый ключ Бориса.
Закрытый ключ Алисы ↓ Подпись Открытый ключ Бориса ↓ Проверка
Математическая связь не совпадёт.
Результат:
Подпись не прошла проверку
Для корректной проверки нужен открытый ключ из той же ключевой пары.
Что именно доказала математика
Если проверка прошла, можно утверждать:
подпись соответствует проверяемому документу;
подпись соответствует использованному открытому ключу;
документ не изменился относительно данных, для которых создана эта подпись.
Но математика сама по себе ещё не ответила:
кому принадлежит открытый ключ;
действовал ли сертификат в нужный момент;
был ли сертификат отозван;
доверяет ли система удостоверяющему центру;
является ли подпись квалифицированной;
имел ли владелец право подписывать конкретный документ.
Это разные уровни проверки.
Можно представить их так:
Уровень 1 Криптография: Подпись соответствует документу и открытому ключу? Уровень 2 Сертификат: Кому принадлежит открытый ключ? Уровень 3 Доверие: Кто подтвердил сертификат? Действителен ли он? Не отозван ли? Уровень 4 Правовой и деловой контекст: Какие последствия имеет подпись? Были ли полномочия?
В этой статье мы разобрали первый уровень. Дальше начинается инфраструктура доверия.
«Подпись верна» — ещё не финальные титры
Допустим, сервис сообщает:
Криптографическая проверка пройдена
Это хороший результат.
Он означает, что математическая связь сошлась.
Но представим, что подпись создана неизвестным самодельным сертификатом:
Владелец подписи: Генеральный директор Вселенной
Криптография может быть совершенно корректной: и открытый ключ соответствует закрытому, и документ не изменён. Но доверять заявленным сведениям без дополнительной проверки оснований нет. Поэтому реальная проверка электронной подписи обычно включает:
проверку криптографического значения;
анализ сертификата;
построение цепочки доверия;
проверку сроков;
проверку отзыва;
анализ назначения ключа;
дополнительные проверки формата и атрибутов.
Математика сказала:
Всё сходится.
Теперь документы должны показать:
А кому именно мы доверяем?
Что видит пользователь, а что происходит внутри
Пользователь видит:
Выберите документ Выберите сертификат Введите PIN-код Нажмите «Подписать»
Внутри:
Чтение документа ↓ Вычисление хеша ↓ Получение доступа к закрытому ключу ↓ Формирование одноразового числа ↓ Операции на эллиптической кривой ↓ Вычисление r и s ↓ Формирование контейнера подписи ↓ Сохранение результата
При проверке пользователь видит:
Загрузите документ и подпись
Внутри:
Разбор контейнера ↓ Извлечение подписи и сертификата ↓ Вычисление хеша документа ↓ Проверка r и s открытым ключом ↓ Проверка сертификата ↓ Проверка доверия и статуса ↓ Формирование понятного отчёта
Хороший сервис прячет сложность, но не смысл. Пользователю не нужно считать точки кривой. Но полезно понимать, почему результат проверки может быть разным:
Подпись математически верна но Сертификат просрочен
или:
Документ изменён поэтому Криптографическая проверка не пройдена
Это разные причины и разные результаты.
Резюме
При создании электронной подписи происходят основные шаги:
Берётся документ
Вычисляется его хеш
Хеш преобразуется в число e
Создаётся новое одноразовое число k
Вычисляется точка k × G
Получается первая часть подписи r
С помощью закрытого ключа вычисляется s
Числа r и s кодируются в подпись
При проверке:
Извлекаются r и s
Заново вычисляется хеш документа
Используются открытый ключ и параметры кривой
Вычисляется контрольное значение R
Проверяется равенство: R = r
Если равенство выполняется, криптографическая подпись соответствует документу и открытому ключу. Но остаётся следующий вопрос:
Откуда мы знаем, что этот открытый ключ действительно принадлежит Ивану Иванову, ООО «Ромашка» или нужному государственному органу?
Математика фамилий не знает.
Для связи ключа с владельцем нужен сертификат.
В следующей статье: «Сертификат электронной подписи: как открытый ключ получает владельца».