dxdt.ru: занимательный интернет-журнал

Немного занимательных математических основ криптографии.

Российская криптосистема электронной подписи (ГОСТ 34.10-2012) работает в группе точек эллиптической кривой над конечным полем, как и криптосистема ECDSA, широко используемая в TLS и в других протоколах защиты информации. Можно ли устроить так, чтобы открытый и секретный ключи для ГОСТ-подписи и ECDSA – совпадали? Дело в том, что если ключи одинаковые, то это добавляет удобства: например, можно использовать некие унифицированные сертификаты. Естественно, это чисто теоретической вопрос, но он довольно занятный. Если вынести за скобки криптографические параметры и способ интерпретации битовых строк, то главное отличие между ГОСТ-подписью и ECDSA состоит в уравнениях, используемых этими криптосистемами. Упростим ситуацию и рассмотрим лишь уравнения вычисления значения подписи:

ECDSA: s = k^(-1)(h + rd)

ГОСТ: s = (rd + kh)

Здесь использованы общие буквенные обозначения: h – это подписываемое значение (можно считать, что это значение хеш-функции от сообщения – натуральное число); k – случайный параметр (натуральное число); r – значение х-координаты вычисляемой на основе k “случайной” точки кривой (это элемент конечного поля, но и его в нашем случае можно понимать как натуральное число), d – секретный ключ (натуральное число). Здесь везде опущены упоминания того, что значения вычисляются по модулю порядка группы точек, связанной с точкой-генератором G, но, опять же, это нисколько не помешает изложению.

Итак, сразу видно, что секретные ключи d для обоих вариантов математически эквивалентны, так как секретный ключ – это натуральное число. Это так и есть на практике, с оговоркой, что значение секретного ключа должно лежать в некотором интервале, но это технические детали. На практике, вряд ли имеет смысл использовать небольшое значение d, которое может оказаться угадываемым. То есть и для ГОСТ-подписи, и для ECDSA в качестве секретного ключа можно использовать одно и то же значение. Если оно находится в подходящем интервале, то в работе алгоритмов, реализующих криптосистемы, равным счётом ничего не поменяется.

Как быть с соответствующими открытыми ключами? С открытыми – уже не так просто. Открытый ключ в обоих криптосистемах – это точка кривой, полученная в результате “умножения” точки-генератора G на число d (значение секретного ключа): открытый ключ Q == dG. “Умножение” здесь взято в кавычки по той причине, что для точек кривой никакого умножения не определяется, но есть “повторное сложение” точек: так, 3*A == A + A + A, где A – точка кривой. Повторное сложение и позволяет ввести умножение на скаляры (на целые числа). Итак, открытый ключ – точка кривой Q – это пара координат (x, y). Значения координат, x и y, – элементы поля, над которым рассматривается кривая. Именно здесь и кроется отличие: штатно, обсуждаемые криптосистемы используют разные кривые и разные поля, поэтому полученные значения открытого ключа будут различными, если, конечно, мы хотим сохранить корректность прочих операций (а корректность сохранить необходимо).

Таким образом, из-за использования разных криптографических параметров (уравнения кривой, базового поля, точки-генератора), для одного и того же значения секретного ключа значения открытых ключей, вообще говоря, в ECDSA и ГОСТ-подписи не совпадут. Однако, если использовать одно и то же поле, одну и ту же кривую и генератор, то и значения открытых ключей будут равны, поскольку и в одной, и в другой криптосистеме – открытый ключ Q == dG. Обе криптосистемы могут работать на общей кривой – математические операции не отличаются. Понятно, что так как уравнения подписи разные, то подписи для одного и того же значения не будут совпадать, даже если ключи удалось привести к “единому формату”. (Естественно, подписи для сообщений могут отличаться и из-за использования разных хеш-функций.) Однако все операции (вычисление подписи, проверка) останутся корректными и для ECDSA, и для ГОСТ-подписи. Поэтому использовать, буквально, одну и ту же пару ключей (секретный – для вычисления подписи, а открытый – для проверки) уже окажется возможным.

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

Адрес записки: https://dxdt.ru/2020/11/25/8983/