09:01
Береговая охрана США подтвердила обнаружение обломков батискафа «Титан»

10:16
Исследование: автомобили Toyota, Honda, Ford и другие передают гигабайты данных компаниям

10:16
15 лет «Фланта»: переход от сервисной компании к продуктовой, покупка внешнего продукта, вера в Open Source

10:46
Как сэкономить свои нервы и деньги компании на перестроении структуры больших таблиц без простоя в PostgreSQL

11:01
День СТО в Москве: инженеры Southbridge рассказали про SRE и DDoS-атаки

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

07:01
Умный дом с голосовым ассистентом на минималках

04:01
Самая мощная молния за всё время наблюдений возникла при извержении вулкана Тонга

01:46
Как мы сделали справочник о диджитале для старших

01:16
Полиция Великобритании столкнулась с наплывом тихих звонков со смартфонов Android на номер службы экстренной помощи 999

19:16
Google урегулирует коллективный иск жителей США 2010 года — пользователи поиска получат чуть менее $8 каждый

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

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

Введение

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

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

Напомним, что некоторые сведения об арифметике точек эллиптической кривой, а также пояснение относительно 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}$ в силу коммутативности. Следовательно, g_1=g_3. Что касается МЭЦП, то

формирует подпись для заданного сообщения при помощи с учётом значения хеш-функции $\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. Поскольку 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.$ Например, это могут быть сообщения другой сессии. Однако с подавляющей вероятностью отвергнет предоставленное доказательство, так как $\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$ в среднем на 85,37 % эффективнее скалярного произведения $\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$ — секретный ключ предназначенный для формирования ЭЦП сертификата.

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

В итоге располагает двумя сертификатами $\{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', поскольку отсутствует критерий принятия решения. Очевидно, что подобная неопределённость недопустима.

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

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

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

Особенность протокола Шнорра в том, что любой, кто имеет доступ в переменным $\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.