Протокол идентификации Шнорра совместим с режимом моментальной цифровой подписи / forpes.ru

Главная
Протокол идентификации Шнорра совместим с режимом моментальной цифровой подписи

Протокол идентификации Шнорра совместим с режимом моментальной цифровой подписи +7

22.06.2023 14:55

ENCRY 11 1200 Источник

В настоящей публикации приводиться описание модификации протокола идентификации Шнорра, совместимого с режимом моментальной цифровой подписи.

Введение

В публикации приводится описание интерактивного протокола идентификации Шнорра (далее протокол Шнорра) и сформулирована проблема совместимости этого протокола с режимом моментальной электронной цифровой подписи (МЭЦП). В настоящей заметке показано как модифицировать протокол Шнорра так, чтобы обеспечить такую совместимость.

МЭЦП-совместимый протокол Шнорра

Напомним, что некоторые сведения об арифметике точек эллиптической кривой, а также пояснение относительно ECDLP и DLP, можно почерпнуть из этой публикации.

В целях упрощения оставим без изменения всё, что касается протокола Шнорра, в том числе пару ключей $\{\mathbf{x},\mathsf{R}=[-\mathbf{x}]\mathsf{G}_1\}$ и сертификат $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}.$

Если интерпретировать необходимое условие, то МЭЦП-совместимость возможна тогда, когда и способны вычислить некоторую общую секретную компоненту. Такой компонентой может быть общий сессионный секретный ключ. Покажем как это сделать на примере протокола Шнорра. Обозначим криптографическую хеш-функцию как $\hslash(\cdot).$

Внесём в протокол некоторые изменения. Воспользуемся следующим приёмом: “спрячем” эфемериду $\phi$ в точке кривой. Это приводит к тому, что $\textit {response}$ также превращается в точку. В результате получим следующий протокол.

Сообщения протокола.

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{G}_1$
$P \longrightarrow V : \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}$

Действия сторон.

выбирает $\upsilon\in_R\!(0,m-1]$ $(\textit {commitment}),$ вычисляет $\mathsf{S}=[\upsilon]\mathsf{G}_1$ $(\textit {witness}),$ проверяет условие $\mathsf{S}\stackrel{?}\neq\infty.$ Если $\mathsf{S}=\infty,$ то выбирает новое $\upsilon$ и заново выполняет необходимые вычисления и проверки;
считывает действующий сертификат $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ и проверяет ЭЦП $\mathfrak{B}\Leftarrow{\rm{Verify}}(\hslash(\mathsf{R}||D_{\mathsf{R}}), \Im_{\mathsf{R}}, \rm{P}_T),$ где $\rm{P}_T$ — общедоступный ключ доверенной стороны Если $\mathfrak{B}=False,$ то сессия завершается. Если $\mathfrak{B}=True,$ то выбирает $\phi\in_R\!(0, m-1]$ и вычисляет $\mathsf{T}=[\phi]\mathsf{G}_1$ $(\textit {challenge}).$ Если $\mathsf{T}=\infty,$ то выбирает новое $\phi$ и заново выполняет необходимые вычисления и проверки;
проверяет условие $\mathsf{T}\stackrel{?}\neq\infty,$ если выполняется, то вычисляет $\mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}=[\mathbf{x}\phi+\upsilon \pmod m]\mathsf{G}_1$ $(\textit {response}),$ в противном случае сессия завершается;
вычисляет $\mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R}.$ Затем проверяет $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}.$ Если равно, то доказательство принимается, и отвергается в противном случае.

Итак, предположим, что этап идентификации завершился успешно и принял предоставленное доказательство.

К этому моменту располагает следующим набором данных: $\upsilon$ $(\textit {commitment}$ по построению), $\mathsf{T}$ (получил от в качестве $\textit {challenge}).$ знает $\mathsf{S}$ (получил от в качестве $\textit {witness}),$ $\phi$ (по построению), $\mathsf{N}$ (получил от в качестве $\textit {response}).$

Стороны независимо формируют общий сессионный секретный ключ в соответствии со следующими правилами:

вычисляет $\mathsf{A}=[\upsilon]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1,$ $g_1=\hslash(x_{\mathsf{A}}\|y_{\mathsf{A}}).$
вычисляет $\mathsf{B}=[\phi]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1,$ $g_3=\hslash(x_{\mathsf{B}}\|y_{\mathsf{B}}).$

Очевидно, что $\mathsf{A}=\mathsf{B}$ в силу коммутативности. Следовательно, Что касается МЭЦП, то

формирует подпись для заданного сообщения при помощи с учётом значения хеш-функции $\hslash(g_1\|M\|\ldots).$
проверяет подпись для некоторого сообщения при помощи с учётом значения хеш-функции $\hslash(g_3\|M'\|\ldots).$

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

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

Предварительный анализ

Заметим, что $\upsilon,$ $\phi$ известны только и соответственно. Тогда злоумышленник может получить $\upsilon$ или $\phi,$ отыскав решение ECDLP при условии $\mathsf{S}$ или $\mathsf{T}$ соответственно. Также можно найти решение DLP при условии $e_m(\mathsf{S}, \mathsf{G}_1)$ или $e_m(\mathsf{T}, \mathsf{G}_1).$ Назначение функции $e_m(\cdot, \cdot),$ а также связь между ECDLP и DLP объясняется в Приложении A. Поскольку то сформировать МЭЦП может только тот, кто знает $\upsilon$ или $\phi,$ а также секретный ключ выбранной для этой цели произвольной схемы ЭЦП.

Активный злоумышленник, используя технику перехвата и блокировки, способен навязать $\mathsf{S}'=[\upsilon']\mathsf{G}_1$ вместо $\mathsf{S},$ $\mathsf{T}'=[\phi']\mathsf{G}_1$ вместо $\mathsf{T}$ и $\mathsf{N}'=[\mathbf{x}]\mathsf{T}'+\mathsf{S}'$ вместо $\mathsf{N}$ при $\upsilon'\neq\upsilon,$ $\phi'\neq\phi.$ Например, это могут быть сообщения другой сессии. Однако с подавляющей вероятностью отвергнет предоставленное доказательство, так как $\mathsf{Q}'=\mathsf{N}'+[\phi]\mathsf{R}=[\mathbf{x}(\phi'-\phi)+\upsilon'\pmod m]\mathsf{G}_1$ и $x_{\mathsf{Q}'}=x_{\mathsf{S}'}$ с пренебрежимо малой вероятностью. Кроме этого, $\mathsf{A}'=[\upsilon]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G}_1,$ $\mathsf{B}'=[\phi]\mathsf{S}'=[\phi\upsilon'\pmod m]\mathsf{G}_1$ и $\mathsf{A}'=\mathsf{B}'$ с пренебрежимо малой вероятностью.

Количество передаваемой информации

Воспользуемся компактным представлением точки кривой [Cohen_etc._2006] (раздел 13.2.5).

Точка $\mathsf{Q}$ задана парой координат $x_\mathsf{Q}, y_\mathsf{Q}\in\mathbb{F}_p.$ Если $\mathsf{Q}$ лежит на кривой, то справедливо уравнение $y_\mathsf{Q}^2=x_\mathsf{Q}^3+ax_\mathsf{Q}+b$ для некоторых $a, b\in\mathbb{F}_p.$ Это уравнение можно интерпретировать как $y_\mathsf{Q}^2 \equiv r \bmod p,$ где — квадратичный вычет и тогда существует ровно два решения $\pm y_\mathsf{Q}.$ При $y_\mathsf{Q}<p$ решение $-y_\mathsf{Q}\bmod p=p-y_\mathsf{Q}.$ Если $y_\mathsf{Q}$ — чётное, то $(p-y_\mathsf{Q})$ — нечётное, и наоборот. В общем случае из двух решений всегда одно — чётное, а другое — нечётное.

Пусть точка $\mathsf{Q}$ представлена координатой $x_\mathsf{Q}.$ Будем передавать по каналу связи $(x_\mathsf{Q}, \mathfrak{s}),$ где $\mathfrak{s}$ — бинарный признак, который позволяет определить нужное решение из пары возможных. Примем за правило, что $\mathfrak{s}=0$ означает чётность, а $\mathfrak{s}=1$ — нечётность. Например, для $(x_\mathsf{Q}, 1)$ следует получить пару $\{y_\mathsf{Q}, p-y_\mathsf{Q}\}$ и затем из этой пары выбрать нечётное решение.

Для хранения произвольной точки кривой потребуется $\lceil\log_{2}p\rceil+1$ бит памяти. В $\mathbb{F}_p$ квадратный корень вычисляется по алгоритму Tonelli-Shanks асимптотической трудоёмкости $O(\log_{2}^2{p})$ [Cohen_etc._2006] (раздел 11.1.5).

Тогда для восстановления точки $\mathsf{Q}$ выполняют следующие действия.

Для заданной координаты $x_\mathsf{Q}$ при помощи алгоритма Tonelli-Shanks вычисляют некоторую координату
Если $(\mathfrak{s}=1)\land(y_*\bmod 2\neq 0),$ то $y_\mathsf{Q}=y_*.$
Если $(\mathfrak{s}=1)\land(y_*\bmod 2=0),$ то $y_\mathsf{Q}=p-y_*.$
Если $(\mathfrak{s}=0)\land(y_*\bmod 2=0),$ то $y_\mathsf{Q}=y_*.$
Если $(\mathfrak{s}=0)\land(y_*\bmod 2\neq 0),$ то $y_\mathsf{Q}=p-y_*.$

Если применяется компактное представление, то для доставки $\mathsf{S},$ $\mathsf{T}$ и $\mathsf{N}$ в совокупности потребуется передать $3(\lceil\log_{2}{p}\rceil+1)$ бит. Для сравнения, в исходном протоколе Шнорра при тех же условиях для доставки $\mathsf{S},$ $\phi$ и $\psi$ в совокупности необходимо передать $2(\lceil\log_{2}m\rceil)+\lceil\log_{2}p\rceil+1$ бит.

Оптимизация вычислений

Трудоёмкость зависит от методов вычисления скалярного произведения, а также выбора вычислительной платформы. Так, например, испытания, которые проводились при помощи тестового стенда, реализованного на языке программирования Scala v2.13.6 на аппаратной платформе MacBook Pro (15-inch, 2016) c 4-ядерным процессором Intel Core i7 под управлением macOS Monterey версия 12.6.2 с привлечением примитивов из библиотеки PBC показывают, что за счёт предобработки, возможной для константы $\mathsf{G}_1,$ скалярное произведение $\mathsf{Q}_1=[\alpha]\mathsf{G}_1$ в среднем на % эффективнее скалярного произведения $\mathsf{Q}_2=[\alpha]\mathsf{P},$ где $\mathsf{P}\neq\mathsf{G}_1\neq const.$ Результаты замеров сведены в Таблицу 1.

Режим МЭЦП и сертификаты общедоступных ключей

Сторона владеет парой ключей $\{\mathbf{x}, \mathsf{R}\}.$ Для общедоступного ключа $\mathsf{R}$ выпускается соответствующий сертификат. Необходимо ответить на следующий вопрос: какую пользу можно извлечь из режима МЭЦП при наличии сертификата общедоступного ключа?

Пусть для общедоступного ключа $\mathsf{R}$ выпущен сертификат $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\},$ где $\Im_{\mathsf{R}}\Leftarrow{\rm{Sign}}(\hslash(\mathsf{R}||D_{\mathsf{R}}), \rm{S}_T)$ — ЭЦП доверенной стороны $D_{\mathsf{R}}$ — персональные данные и $\rm{S}_T$ — секретный ключ предназначенный для формирования ЭЦП сертификата.

Поставим мысленный эксперимент и в отсутствии режима МЭЦП предположим, что передаёт некоторые заверенные ЭЦП персональные данные При этом утверждает, что — его собственные персональные данные. Следует сразу оговориться, эти данные могли быть получены различными способами, например, в результате сговора, применения методов социальной инженерии или просто скопированы из общедоступной долговременной памяти. Для проверки ЭЦП сторона должна воспользоваться общедоступным ключом $\mathsf{P}'$ из сертификата $\{D',\mathsf{P}', \Im_{\mathsf{P}'}\}.$ Предположим также, что все необходимые проверки подтвердили подлинность и целостность $\mathsf{P}',$

В итоге располагает двумя сертификатами $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ и $\{D',\mathsf{P}', \Im_{\mathsf{P}'}\},$ каждый из которых выпущен доверенным удостоверяющим центром. Рассмотрим случай, когда $D_{\mathsf{R}}\neq D'$ ( $D_{\mathsf{R}}=D'$ трактуется однозначно). В результате не в состоянии сделать правильный выбор относительно $D_{\mathsf{R}}$ или поскольку отсутствует критерий принятия решения. Очевидно, что подобная неопределённость недопустима.

Если задействовать режим МЭЦП, то принимая решение относительно $D_{\mathsf{R}}$ или сторона опирается на доказательство, которое было предоставлено на этапе идентификации. Рассуждения стороны подчиняются следующей логике.

Сформировать ЭЦП для персональных данных может только тот, кто одновременно имеет доступ к переменным отдельной сессии протокола идентификации, как общедоступным, так и секретным, включая секретный ключ для формирования ЭЦП.
Предположим, что ЭЦП получена в результате сговора. Для этого злоумышленник должен вынудить владельца персональных данных заверить их своей ЭЦП, но с включением некоторых вспомогательных данных, про которые заверителю ничего не известно. Если исходить из модели сопутствующих рисков, то такое событие представляется неправдоподобным. С подавляющей вероятностью заверитель откажется от включения таких данных, опасаясь нежелательных последствий, например, неявного навязывания долговых обязательств, занесения в чёрные списки, блокировки учётных записей и так далее.

Открытая верификации в протоколе Шнорра

Особенность протокола Шнорра в том, что любой, кто имеет доступ в переменным $\mathsf{S},$ $\phi$ и $\psi,$ может проверить корректность вердикта, вынесенного относительно доказательства, предоставленного

Действительно, упомянутые выше переменные передаются по незащищённому каналу связи и, следовательно, общедоступны. Поскольку каждый может воспользоваться общедоступным ключом $\mathsf{R},$ то совсем не обязательно обладать полномочиями для того, чтобы вычислить $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}=[\psi-\phi\mathbf{x}\pmod m]\mathsf{G}_1$ и затем проверить $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}.$

Практический смысл здесь в возможности контроля действий как со стороны так и Это важно при возникновении разногласий. Например, когда утверждает, что предоставил корректное доказательство, а это отрицает.

Выводы

Оценки количества передаваемой информации для исходного протокола Шнорра и описанной выше модификации различаются несущественно.

В исходном протоколе Шнорра задействовано три скалярных произведения, тогда как в модификации протокола таких произведений четыре. Поскольку скалярные произведения $\mathsf{S}=[\upsilon]\mathsf{G}_1$ и $\mathsf{T}=[\phi]\mathsf{G}_1$ вычисляются относительно образующего элемента $\mathsf{G}_1,$ то возможна оптимизация, которая позволяет сократить вычислительные трудозатраты в обмен на выделение дополнительной памяти, предназначенной для хранения промежуточных результатов (см. Таблицу 1). Заметим, что в исходном протоколе при вычислении точки $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}$ допустима только частичная оптимизация. Однако в модифицированном протоколе при вычислении точек $\mathsf{N}$ и $\mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R},$ а также скалярных произведений $\mathsf{A}=[\upsilon]\mathsf{T}$ и $\mathsf{B}=[\phi]\mathsf{S}$ такая оптимизация невозможна.

В предложенной модификации протокола открытая верификация нереализуема.

Заключение

Следует засвидетельствовать, что нам удалось решить поставленную задачу для конкретного протокола сравнительно простым способом. Однако для произвольного протокола идентификации проблема совместимости с режимом МЭЦП продолжает оставаться открытой. В дальнейшем мы предпримем попытку отыскать решение задачи для некоторого известного протокола идентификации, отличного от протокола Шнорра.

Текст статьи в формате pdf можно скачать тут.

Список литературы

[Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2006.

Комментарии (11)

nikhotmsk
22.06.2023 19:29
#25680314
Здорово. Мгновенная цифровая подпись - хорошая вещь, только не совсем понятно, для чего она может быть нужна. Есть же обычная. Это должна быть какая-то высоконагруженная система, где надо много подписывать.

Если возможна мгновенная цифровая подпись, значит может быть и мгновенное шифрование с открытым ключем?

Честно признаюсь, когда я читаю статьи, я стараюсь проговаривать их в голове на промежуточном человеческом языке. Если не получается, значит со статьей проблемы. В случае с матаном я бессилен, слишком много непонятного.
1. AndrChm
  22.06.2023 19:29
  #25680402
  +1
  Вы не смотрите публикации по ссылкам. Задача поставлена. И вполне конкретная. Режим МЭЦП важен, когда персональные данные подписываются. И почему важен подробно объясняется в других публикациях. Матан тут ни причём. Это алгебра.
  1. suurtoll
    22.06.2023 19:29
    #25681198
    +1
    А вы не уважаете ваших читателей, вам, наверное, важнее просмотры набить под публикациями?
    
    Публикация должна быть целостной, все необходимые определения, за исключением общепринятых, а также постановка задачи должны содержаться в ней самой. Вот попробуйте вашу работу отправить в нормальный ВАКовский журнал, любой рецензент ее завернёт по формальным признакам.
    
    AndrChm
    22.06.2023 19:29
    #25682322
    +1
    А вы не уважаете ваших читателей, вам, наверное, важнее просмотры набить под публикациями?
    
    Ну вот зачем так? Вы ведь понимаете, по крайней мере надеюсь на это, что для того, чтобы «набить» просмотры достаточно публиковать новости из открытых источников или писать тексты, в которых есть что угодно, но только не оригинальный результат. Если бы я ставил перед собой такую цель, то писал бы совсем о другом.
    
    Что касается набора тематически связанных статей с перекрестными ссылками — так это вполне себе распространённая норма. Если бы я каждый раз переписывал уже опубликованное в новой заметке, то нашлись бы другие критики, которые с радостью начали бы пенять именно на это. И критика эта по большей части от того, что по-существу сказать нечего. Что ж, с этим приходится жить.
    
    Ещё раз выражаю благодарность за то, что указали на явный ляп в предыдущей публикации. Считаю, что на этом можно и закончить.
  1. domix32
    22.06.2023 19:29
    #25681924
    Потыкал прошлые статьи, увидел только "МЭЦП - это особый режим" и кучу формул вокруг свидетеля и игры с испытаниями. В чем отличие от остальных режимов подписи, почему остальные режимы не подходят и как они между собой связаны и в чём собственно проблематика так толком и не пояснено.
    
    AndrChm
    22.06.2023 19:29
    #25681958
    +2
    Вы даже главного не заметили, что предлагаемая модификация протокола Шнорра уже включает в себя протокол Диффи-Хеллмана. Это позволяет много чего делать: уже готов виртуальный туннель для передачи конфиденциальной информации, но мы это ещё используем в режиме МЭЦП. Кроме этого, экономится один раунд проколола Диффи-Хеллмана. В общем с такими публикациями разбираться надо, а не смотреть в полглаза.

suurtoll
22.06.2023 19:29
#25680336
Эммм...

нам удалось решить поставленную задачу для конкретного протокола сравнительно простым способом.

А в чем состоит постановка задачи-то? Вы не могли бы, следуя общепринятым нормам оформления научных статей, во введении четко сформулировать как собственно задачу с точки зрения математики, так и прикладную проблему, которую вы решаете?

suurtoll
22.06.2023 19:29
#25680352
И ещё вопрос. Вот я заглянул в одну из старых ваших публикаций и вижу такое.

Известными протоколами идентификации также являются протокол аутентификации Шнорра...

А как протокол идентификации может быть протоколом аутентификации? Это же разные задачи. Если бы мне студент на экзамене такое ляпнул - вылетел бы с неудом без дальнейших разговоров.
1. AndrChm
  22.06.2023 19:29
  #25680518
  +1
  Спасибо за замечание. Пожалуйста, дайте ссылку на эту публикацию. Хотя такое вполне может быть. Наблюдалась некоторая путаница в начале славных дел. Потом всё нормализовалось. Ну, что делать, поставьте мне неуд, если это вас успокоит — всегда готов помочь. А вот по-существу есть ли что?
  1. suurtoll
    22.06.2023 19:29
    #25681224
    +1
    Спасибо, конечно, но я не беспокоюсь и помощи не прошу :)
    
    По существу: я выше (возможно, слегка токсично - ну это профдеформация, извиняюсь :) намекаю на необходимость сделать статью более self-consistent.
1. AndrChm
  22.06.2023 19:29
  #25680690
  Известными протоколами идентификации также являются протокол аутентификации Шнорра
  
  Сам нашел. Ну да, ляп. Казнить нельзя, помиловать.