Pull to refresh

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

Level of difficulty Hard
Reading time 7 min
Views 1.9K

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

Введение

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

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

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

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

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

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

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

  1. P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1

  2. P \longleftarrow V :  \mathsf{T}=[\phi]\mathsf{G}_1

  3. P \longrightarrow  V  : \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}

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

P доказывает V,что владеет (знает) \mathbf{x}. Для этого выполняются следующие действия:

  1. P выбирает \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 и заново выполняет необходимые вычисления и проверки;

  2. V считывает действующий сертификат \{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 — общедоступный ключ доверенной стороны 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 и заново выполняет необходимые вычисления и проверки;

  3. P проверяет условие \mathsf{T}\stackrel{?}\neq\infty, если выполняется, то вычисляет \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}=[\mathbf{x}\phi+\upsilon \pmod m]\mathsf{G}_1 (\textit {response}), в противном случае сессия завершается;

  4. V вычисляет \mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R}. Затем проверяет x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}. Если равно, то доказательство принимается, и отвергается в противном случае.

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

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

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

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

  2. V вычисляет \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} в силу коммутативности. Следовательно, g_1=g_3. Что касается МЭЦП, то

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

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

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

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

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

Заметим, что \upsilon, \phi известны только P и V соответственно. Тогда  злоумышленник может получить \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.  Поскольку g_1=g_3, то сформировать МЭЦП может только тот, кто знает \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. Например, это могут быть сообщения другой сессии. Однако V с подавляющей вероятностью отвергнет предоставленное доказательство, так как \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, где r — квадратичный вычет и тогда существует ровно два решения \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} выполняют следующие действия. 

  1. Для заданной координаты x_\mathsf{Q} при помощи алгоритма Tonelli-Shanks вычисляют некоторую координату y_*. 

  2. Если  (\mathfrak{s}=1)\land(y_*\bmod 2\neq 0), то y_\mathsf{Q}=y_*. 

  3. Если  (\mathfrak{s}=1)\land(y_*\bmod 2=0), то y_\mathsf{Q}=p-y_*. 

  4. Если  (\mathfrak{s}=0)\land(y_*\bmod 2=0), то y_\mathsf{Q}=y_*. 

  5. Если  (\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 в среднем на 85,37% эффективнее скалярного произведения \mathsf{Q}_2=[\alpha]\mathsf{P}, где \mathsf{P}\neq\mathsf{G}_1\neq const. Результаты замеров сведены в Таблицу 1.

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

Сторона P владеет парой ключей \{\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) — ЭЦП доверенной стороны T, D_{\mathsf{R}} — персональные данные P и \rm{S}_T — секретный ключ T, предназначенный для формирования ЭЦП сертификата.

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

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

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

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

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

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

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

Действительно, упомянутые выше переменные передаются по незащищённому каналу связи и, следовательно, общедоступны. Поскольку каждый может воспользоваться общедоступным ключом \mathsf{R}, то совсем не обязательно обладать полномочиями V для того, чтобы вычислить \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}}.

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

Выводы

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

В исходном протоколе Шнорра задействовано три скалярных произведения, тогда как в модификации протокола таких произведений четыре. Поскольку скалярные произведения \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.

Tags:
Hubs:
+7
Comments 11
Comments Comments 11

Articles