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

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

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

Введение

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

Для обозначения исчезающе малой вероятности будем использовать сокращение и.м.в. Это означает, что для некоторых $\alpha\in\mathbb{F}_m$ и $\beta$ , распределённого равномерно и независимо на интервале , по другому ${\beta\in_R\!(0,m-1]}$ , ${\Pr[\alpha=\beta]=m^{-1}}$ и для больших эта величина исчезающе мала. Например, $\Pr[\alpha=\beta]\sim 10^{-49}$ для $m\sim 2^{160}$ . Аналогичное рассуждение справедливо для $\Pr[g^{\alpha}=g^{\beta}]$ , где — порождающий элемент $\mathbb{G}_3$ (Приложение A).

При описании схем ЭЦП и протоколов идентификации будем исходить из предположения, что имеется пара связанных ключей $\{\mathbf{x},\mathsf{P}=[\mathbf{x}]\mathsf{G}_1\}$ , где $\mathbf{x}$ — секретный, ${\mathbf{x}\in_R\!(0,m-1]},$ а $\mathsf{P}$ — общедоступный, для которого выпущен сертификат $\{D,\mathsf{P}, \Im_{\rm{T}}\}$ . В этом сертификате — персональные данные владельца $\mathsf{P}$ , $\Im_{\rm{T}}$ — ЭЦП доверенной стороны $\rm{T}$ (удостоверяющий центр, который отвечает за выпуск и обслуживание сертификатов).

Обозначим через ${\rm{Sign}}(\cdot,\cdot)$ и ${\rm{Verify}}(\cdot,\cdot,\cdot)$ функции формирования и проверки ЭЦП соответственно. Криптографическую хеш-функцию обозначим через $\hslash(\cdot)$ (Приложение Б). Тогда $\Im_{\rm{T}}\Leftarrow{\rm{Sign}}(\hslash(\mathsf{P}||D), \rm{S}_{\rm{T}})$ , где $\rm{S}_{\rm{T}}$ — секретный ключ доверенной стороны $\rm{T}$ , предназначенный для формирования ЭЦП.

Перед использованием $\mathsf{P}$ проверяется на подлинность, целостность и актуальность, последнее осуществляется при помощи сверки со списком отозванных сертификатов. В том числе вычисляется $\mathfrak{B}\Leftarrow{\rm{Verify}}(\hslash(\mathsf{P}||D), \Im_{\rm{T}}, \rm{P}_{\rm{T}})$ , где $\rm{P}_{\rm{T}}$ — общедоступный ключ доверенной стороны $\rm{T}$ . Если $\Im_{\rm{T}}$ валидна, то булевская переменная $\mathfrak{B}=True$ и это означает целостность, подлинность $\mathsf{P}$ и , в противоположном случае $\mathfrak{B}=False$ . Доверенная сторона может использовать произвольную схему ЭЦП, например, какую-то из описанных ниже.

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

Следует отметить, что большинство известных схем ЭЦП используют простые уравнение «школьного» типа, что важно, так как это упрощает их понимание и анализ. Будем руководствоваться тем же самым \textit{modus operandi} при разработке протоколов идентификации.

Схемы ЭЦП на основе спаривания

Далее по тексту того, кто формирует ЭЦП для сообщения ${M\in\{0,1\}^*}$ будем называть $\textit{заверителем}$ . Ниже приводится описания двух схем ЭЦП на основе спаривания (Приложение A).

В схеме ЭЦП [Zhang_Safavi-Naini_Susilo_2004] для заданного сообщения заверитель выполняет следующие действия:

вычисляет $\phi=\hslash(M)$ ;
формирует подпись $\mathsf{S}=[\frac{1}{\phi+\mathbf{x}\pmod m}]\mathsf{G}_1=[\psi]\mathsf{G}_1$ .

Пусть имеются некоторые подпись $\mathsf{S}'=[\psi']\mathsf{G}_1$ и сообщение .

Проверяющий выполняет следующие действия:

вычисляет $\phi'=\hslash(M')$ ;
проверяет подлинность, целостность и актуальность $\mathsf{P}$ , если актуальность не подтверждена или $\mathfrak{B}=False$ , то завершает проверку ЭЦП;
вычисляет $g'=e_m([\phi']\mathsf{G}_1+ \mathsf{P}, \mathsf{S}')=e_m([\phi'+\mathbf{x}\pmod m]\mathsf{G}_1, [\psi']\mathsf{G}_1)=g^{\psi'(\phi'+\mathbf{x})\pmod m}$ ;
проверяет $g'\stackrel{?}{=}e_m(\mathsf{G}_1, \mathsf{G}_1)$ .

Тогда , если $(\psi'=\psi)\land(\phi'=\phi)\Rightarrow (M'=M)\land(\mathsf{S'}=\mathsf{S})$ . Если $(\psi'\neq\psi)\lor(\phi'\neq\phi)$ , то c и.м.в.

Понятно, что $g=e_m(\mathsf{G}_1, \mathsf{G}_1)$ вычисляется всего один раз и сохраняется в локальной долговременной памяти. Необходимо гарантировать подлинность и целостность . Например, хранить в защищённой памяти вместе с секретным ключом $\mathbf{x}$ .

Рассмотрим ещё одну схему ЭЦП из [Boneh_Shacham_Lynn_2004]. Задана хеш-функция $H:\{0,1\}^*\mapsto\mathbb{G}_1$ (Приложение Б). Заверитель выполняет следующие действия:

вычисляет $\mathsf{Q}=H(M)=[\upsilon]\mathsf{G}_1$ ;
формирует подпись $\mathsf{S}=[\mathbf{x}]\mathsf{Q}=[\mathbf{x}\upsilon\pmod m]\mathsf{G}_1$ .

Имеются некоторые сообщение и подпись $\mathsf{S}'$ . Проверяющий выполняются следующие действия:

вычисляет $\mathsf{Q}'=H(M')$ ;
проверяет подлинность, целостность и актуальность $\mathsf{P}$ , если актуальность не подтверждена или $\mathfrak{B}=False$ , то завершает проверку ЭЦП;
проверяет $e_m(\mathsf{P},\mathsf{Q}')\stackrel{?}{=}e_m(\mathsf{G}_1,\mathsf{S}')$ .

Если $\mathsf{Q}'=\mathsf{Q}=[\upsilon]\mathsf{G}_1$ и $\mathsf{S}'=\mathsf{S}=[\mathbf{x}\upsilon\pmod m]\mathsf{G}_1$ , то в силу билинейности $e_m(\mathsf{P},\mathsf{Q}')=e_m([\mathbf{x}]\mathsf{G}_1, [\upsilon]\mathsf{G}_1)=e_m([\mathbf{x}\upsilon\pmod m]\mathsf{G}_1, \mathsf{G}_1)=e_m(\mathsf{G}_1, \mathsf{G}_1)^{\mathbf{x}\upsilon\pmod m}=g^{\mathbf{x}\upsilon\pmod m}.$ Если $\mathsf{Q}'\neq\mathsf{Q}$ и/или $\mathsf{S}'\neq\mathsf{S}$ , то $e_m(\mathsf{P},\mathsf{Q}')= e_m(\mathsf{G}_1,\mathsf{S}')$ c и.м.в.

Обе схемы ЭЦП используют функцию спаривания $e_m(\cdot, \cdot)$ , но отличаются трудоёмкостью проверки. В схеме [Zhang_Safavi-Naini_Susilo_2004] при проверке ЭЦП вычисляется только одно спаривание, тогда как в [Boneh_Shacham_Lynn_2004] для этого необходимо вычислить два спаривания.

МЭЦП-совместимые протоколы идентификации на основе спаривания

Согласно эвристики Фиата-Шамира [Fiat_Shamir_1987], каждой схеме ЭЦП соответствует свой протокол идентификации. Однако нас будут интересовать МЭЦП-совместимые версии таких протоколов.

Ниже приводится описание МЭЦП-совместимого протокола идентификации для схемы ЭЦП из [Zhang_Safavi-Naini_Susilo_2004].

Протокол 1

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

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{G}_1$
$P \longrightarrow V : \mathsf{N}=[(\upsilon+\mathbf{x}\pmod m)^{-1}]\mathsf{T}$

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

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

выбирает ${\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{P}, \Im_{\rm{T}}\}$ и проверяет ЭЦП доверенной стороны $\rm{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}=[(\upsilon+\mathbf{x}\pmod m)^{-1}]\mathsf{T}=[\frac{\phi}{\upsilon+\mathbf{x}\pmod m}\pmod m]\mathsf{G}_1$ ( $\textit{response}$ ) в противном случае сессия завершается;
вычисляет $g_2=e_m([\phi^{-1}]\mathsf{S}+[\phi^{-1}]\mathsf{P}, \mathsf{N})=e_m([\phi^{-1}(\upsilon+\mathbf{x})\pmod m]\mathsf{G}_1, \mathsf{N})$ . Затем проверяет $g_2\stackrel{?}{=}g$ . Если равно, то доказательство принимается, и отвергается в противном случае.

Теперь посмотрим, какой МЭЦП-совместимый протокол можно предложить для схемы ЭЦП из [Boneh_Shacham_Lynn_2004].

Протокол 2

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

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

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

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

как в Протоколе 1;
как в Протоколе 1;
проверяет условие ${\mathsf{T}\stackrel{?}\neq\infty}$ , если выполняется, то вычисляет ${\mathsf{N}=[\upsilon\mathbf{x}\pmod m]\mathsf{T}=[\phi\upsilon\mathbf{x}\pmod m]\mathsf{G}_1}$ (\textit{response}), в противном случае сессия завершается;
вычисляет $g_2=e_m([\phi]\mathsf{S}, \mathsf{P})=g^{\phi\upsilon\mathbf{x}\pmod m}$ . Затем проверяет $g_2\stackrel{?}{=}e_m(\mathsf{N}, \mathsf{G}_1)$ . Если равно, то доказательство принимается, и отвергается в противном случае.

Для Протоколов 1 и 2 в случае успешного завершения этапа идентификации стороны независимо формируют общий сессионный секретный ключ в соответствии со следующими правилами:

вычисляет $\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}$ в силу коммутативности.

Имперсонификация проверяющего

Активная атака включает комплекс мероприятий, предпринимаемых с целью замены информации, которой стороны обмениваются в ходе протокола идентификации. Протоколы 1 и 2 надёжны при условии пренебрежимо малой вероятности активной атаки. Например, когда обмен данными между и осуществляется при помощи технологии NFC (Near-Field Communication) или подобных.

Если стороны взаимодействуют посредством иных незащищённых каналов связи, включая Интернет, то возможна активная атака, цель которой заключается в имперсонификации проверяющего. Обозначим фиктивного проверяющего через $V'$. Атакующий пытается заменить на .

Выберем Протокол 2 в качестве объекта атаки. Используя технику перехвата и блокировки, атакующий способен вместо $\mathsf{T}$ навязать $\mathsf{T}'=[\phi']\mathsf{G}_1$ , такое, что $\phi'=\phi$ c и.м.в. Сторона вычисляет $\textit{response}$ как $\mathsf{N}'=[\upsilon\mathbf{x}\pmod m]\mathsf{T}'=[\phi'\upsilon\mathbf{x}\pmod m]\mathsf{G}_1$ .

вычисляет $\hat{g}_2=e_m([\phi']\mathsf{S}, \mathsf{P})=g^{\phi'\upsilon\mathbf{x}\pmod m}$ и проверяет $\hat{g}_2\stackrel{?}{=}e_m(\mathsf{N}', \mathsf{G}_1)$ . $P$ вычисляет ${\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}'$ .

Представленные рассуждения в равной мере справедливы для Протокола 1. Кроме этого, атака также применима к модифицированному протоколу Шнорра.

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

Протокол, устойчивый к имперсонификации

Предположим, что для ${\mathbf{x}, \mathbf{y}\in_R\!(0,m-1]}$ стороны и владеют парами ключей $\{\mathbf{x},\mathsf{P}_P=[\mathbf{x}]\mathsf{G}_1\}$ и $\{\mathbf{y},\mathsf{P}_V=[\mathbf{y}]\mathsf{G}_1\}$ соответственно. Для $\mathsf{P}_P$ и $\mathsf{P}_V$ выпущены сертификаты $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}$ и $\{D_V,\mathsf{P}_V, \widehat{\Im}_{\rm{T}}\}$ .

Рассмотрим МЭЦП-совместимый и при этом устойчивый к имперсонификации протокол.

Протокол 3

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

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{P}_V$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{P}_P$
$P \longrightarrow V : \mathsf{N}=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}$

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

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

считывает актуальный сертификат $\{D_V,\mathsf{P}_V, \widehat{\Im}_{\rm{T}}\}$ и проверяет ЭЦП доверенной стороны $\rm{T}$ . Если $\mathfrak{B}=False$ , то сессия завершается. Если $\mathfrak{B}=True$ , то выбирает ${\upsilon\in_R\!(0,m-1]}$ ( $\textit{commitment}$ ) вычисляет $\mathsf{S}=[\upsilon]\mathsf{P}_V=[\upsilon\mathbf{y}\pmod m]\mathsf{G}_1$ ( $\textit{witness}$ ), проверяет условие ${\mathsf{S}\stackrel{?}\neq\infty}$ . Если $\mathsf{S}=\infty$ , то выбирает новое $\upsilon$ и заново выполняет необходимые вычисления и проверки;
считывает актуальный сертификат $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}$ и проверяет ЭЦП доверенной стороны $\rm{T}$ . Если $\mathfrak{B}=False$ , то сессия завершается. Если $\mathfrak{B}=True$ , то выбирает ${\phi\in_R\!(0, m-1]}$ и вычисляет $\mathsf{T}=[\phi]\mathsf{P}_P=[\phi\mathbf{x}\pmod m]\mathsf{G}_1$ ( $\textit{challenge}$ ). Если $\mathsf{T}=\infty$ , то выбирает новое $\phi$ и заново выполняет необходимые вычисления и проверки;
проверяет условие $\mathsf{T}\stackrel{?}\neq\infty$ , если выполняется, то вычисляет $\mathsf{N}=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}=[\phi\upsilon^{-1}\pmod m]\mathsf{G}_1$ ( $\textit{response}$ ), в противном случае сессия завершается;
вычисляет $g_2=e_m(\mathsf{S}, \mathsf{N})=e_m([\upsilon\mathbf{y}\pmod m]\mathsf{G}_1, [\phi\upsilon^{-1}\pmod m]\mathsf{G}_1)=g^{\phi\mathbf{y}\pmod m}$ . Затем проверяет $g_2\stackrel{?}{=}e_m([\phi]\mathsf{P}_V, \mathsf{G}_1)$ . Если равно, то доказательство принимается, и отвергается в противном случае.

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

вычисляет $\mathsf{A}=[\upsilon\mathbf{x}^{-1}\pmod m]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1$ .
вычисляет $\mathsf{B}=[\phi\mathbf{y}^{-1}\pmod m]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1$ .

Понятно, что $\mathsf{A}=\mathsf{B}$ по причине коммутативности.

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

Пусть фиктивный проверяющий владеет парой ключей $\{\mathbf{\acute{y}},\mathsf{P}_{V'}=[\mathbf{\acute{y}}]\mathsf{G}_1\}$ , $\mathbf{\acute{y}}=\mathbf{y}$ c и.м.в.

Ограничимся анализом Протокола 3, в котором для имперсонификации проверяющего (замены на ) необходимо вместо $\mathsf{S}$ навязать $\mathsf{S}'=[\upsilon]\mathsf{P}_{V'}$ . Однако, атакующий не знает эфемериды $\upsilon$ . Для раскрытия $\upsilon$ надлежит отыскать решение ECDLP/DLP при условии $\mathsf{S}$ или $e_m(\mathsf{S}, \mathsf{G}_1)$ . Связь между ECDLP и DLP объясняется в Приложении A.

Атакующий имеет доступ к $\mathsf{P}_P$ и способен вместо $\mathsf{T}$ навязать $\mathsf{T}'=[\phi']\mathsf{P}_P$ , а также вместо $\mathsf{S}$ навязать некоторое $\mathsf{S}'=[\upsilon']\mathsf{P}_{V'}$ , при этом $\phi'=\phi$ и $\upsilon'=\upsilon$ c и.м.в. вычисляет $\textit{response}$ как $\mathsf{N}'=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}'$ .

вычисляет $\hat{g}_2=e_m(\mathsf{S}', \mathsf{N}')=e_m([\upsilon'\mathbf{\acute{y}}\pmod m]\mathsf{G}_1, [\phi'\upsilon^{-1}\pmod m]\mathsf{G}_1)=g^{\upsilon'\mathbf{\acute{y}}\phi'\upsilon^{-1}\pmod m}$ . Очевидно, что $\hat{g}_2=e_m([\phi']\mathsf{P}_{V'}, \mathsf{G}_1)$ c и.м.в. Кроме этого, атакующий может выбрать произвольные $\upsilon'$ и $\phi'$ . Пусть $\upsilon'=\phi'=1$ , но $g^{\mathbf{\acute{y}}\upsilon^{-1}\pmod m}=g^{\mathbf{\acute{y}}}$ c и.м.в.

Легко показать, что подмена $\mathsf{T}$ не приводит к искомому результату. Для этого при вычислении $\hat{g}_2$ положим $\mathsf{N}'=\mathsf{N}$ . Однако, $g^{\upsilon'\mathbf{\acute{y}}\phi\upsilon^{-1}\pmod m}=g^{\phi'\mathbf{\acute{y}}\pmod m}$ с и.м.в.

Если допустить, что атакующий вместо $\mathsf{T}$ навязывает $\mathsf{T}'$ , но при этом отсутствует подмена $\mathsf{S}$ , то имперсонификация также невозможна, поскольку $g^{\phi'\mathbf{y}\pmod m}=g^{\phi'\mathbf{\acute{y}}\pmod m}$ с и.м.в.

Заметим, что $\mathsf{A}'=[\upsilon\mathbf{x}^{-1}\pmod m]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G}_1$ , $\mathsf{B}'=[\phi'\mathbf{\acute{y}}^{-1}\pmod m]\mathsf{S}=[\phi'\upsilon\mathbf{\acute{y}}^{-1}\mathbf{y}\pmod m]\mathsf{G}_1$ или $\mathsf{B}'=[\phi'\mathbf{\acute{y}}^{-1}\pmod m]\mathsf{S}'=[\phi'\upsilon'\pmod m]\mathsf{G}_1$ . Следовательно, $\mathsf{A}'=\mathsf{B}'$ с и.м.в.

При вычислении $\mathsf{T}'$ замена $\mathsf{P}_P$ на некоторое $\mathsf{P}_{P'}$ представляется контрпродуктивной. Если допустить такую замену, то при

$\mathsf{P}_{P'}=[\mathbf{\acute{x}}]\mathsf{G}_1$ , $\mathbf{\acute{x}}=\mathbf{x}$ c и.м.в., возникнет невязка по $\mathbf{x}$ . Пусть заданы $\mathsf{S}$ , $\mathsf{N}'=[\upsilon^{-1}\mathbf{x}^{-1}\phi'\mathbf{\acute{x}}\pmod m]\mathsf{G}_1$ . Тогда $g^{\mathbf{y}\mathbf{x}^{-1}\phi'\mathbf{\acute{x}}\pmod m}=g^{\phi'\mathbf{y}\pmod m}$ с и.м.в.

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

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

В Протоколе 3 сторона должна сообщить стороне серийный номер сертификата $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}$ . Предположим, что для сохранения этого номера в долговременной памяти необходимо зарезервировать $\ell$ бит. Тогда для доставки $\mathsf{S}$ , $\mathsf{T}$ и $\mathsf{N}$ в совокупности потребуется передать $3(\lceil\log_{2}{p}\rceil+1)+\ell$ бит.

Допустимы и другие накладные расходы. Для количества передаваемой информации справедлива асимптотическая оценка $O(\log_{2}{p})$ .

Вычислительные трудозатраты

Кроме скалярного произведения, особенности вычисления которого описаны здесь, в Протоколе 3 стороны и вычисляют $\{\upsilon^{-1}$ , $\mathbf{x}^{-1}\}$ и $\mathbf{y}^{-1}$ соответственно.

При этом $\mathbf{x}^{-1}$ и $\mathbf{y}^{-1}$ вычисляются однократно. и сохраняют вычисленные значения в локальной долговременной защищённой памяти. В итоге и хранят $\{\mathbf{x}, \mathbf{x}^{-1}, \mathsf{P}_P\}$ и $\{\mathbf{y}, \mathbf{y}^{-1}, \mathsf{P}_V\}$ соответственно.

вычисляет $\upsilon^{-1}$ в каждой отдельной сессии. Если на стороне производительность платформы превышает пропускную способность канала связи между и , то при известном $\upsilon$ уместно инициировать вычисление $\upsilon^{-1}$ на опережение, до получения $\mathsf{T}$ . Такой способ позволяет минимизировать вычислительную задержку, так как правдоподобно допустить, что $\upsilon^{-1}$ будет известна к моменту, когда возникнет необходимость в вычислении $\mathsf{N}$ .

Поскольку в силу билинейности $e_m([\phi]\mathsf{P}_V, \mathsf{G}_1)=e_m(\mathsf{P}_V, [\phi]\mathsf{G}_1)$ , то при вычислении $[\phi]\mathsf{G}_1$ возможна оптимизация (Таблица 1).

Пусть аффинные точки $\mathsf{S}$ , $\mathsf{T}$ и $\mathsf{N}$ представлены компактно, тогда для последующих вычислений потребуется восстановить координаты $y_{\mathsf{S}}$ , $y_{\mathsf{T}}$ и $y_{\mathsf{N}}$ при помощи алгоритма Tonelli-Shanks асимптотической трудоёмкости $O(\log_{2}^2{p})$ [Cohen_etc._2006] (раздел 11.1.5). Однако в этом нет необходимости, если арифметика точек построена на основе эллиптической кривой Монтгомери [Montgomery_1987]. Возможно использование бирациональных эквивалентов, например, скрученных кривых Эдвардса [Bernstein_2008].

Методы мультипликативного обращения в $\mathbb{F}_m^*$ представлены в [Cohen_etc._2006] (раздел 11.1).

Для программной реализации рассмотренных протоколов целесообразно воспользоваться примитивами библиотеки PBC.

Проблематика аппаратной реализации билинейных отображений всесторонне рассматривается в ряде публикаций [Rodriguez-Henriquez_etc._2006, Beuchat_etc._Nov_2008, Beuchat_etc._2008, Kammler_etc._2009, Ghosh_etc._2010, Estibals_2010, Ghosh_etc._2011, Beuchat_etc._2011, Cheung_etc._2011, Adikari_etc._2012].

Выводы

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

Предварительный анализ показывает, что в Протоколе 3 имперсонификация невозможна. Каждый может воспользоваться ключами $\mathsf{P}_P$ и $\mathsf{P}_V$ , но только способен предоставить неоспоримое доказательство, поскольку владеет долговременным секретным ключом $\mathbf{x}$ и знает эфемериду $\upsilon$ . Проверить доказательство может только , так как знает эфемериду $\phi$ .

Кроме этого, независимо вычислить $\mathsf{A}$ и $\mathsf{B}$ , такие, что $\mathsf{A}=\mathsf{B}$ , могут только и , так как владеют секретными ключами $\mathbf{x}$ и $\mathbf{y}$ .

Заключение

Сконструированы и исследованы МЭЦП-совместимые протоколы идентификации на основе функции спаривания точек эллиптической кривой. Сформулирована проблема имперсонификации. Разработан устойчивый к имперсонификации МЭЦП-совместимый протокол идентификации.

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

[Boneh_Shacham_Lynn_2004] Boneh, D., Shacham, H. and Lynn B. "Short Signatures from the Weil Pairing.” $\textit{J. Cryptol.}$ , Vol. 17, No. 4, (2004) 297–319.

[Zhang_Safavi-Naini_Susilo_2004] Zhang, F., Safavi-Naini, R. and Susilo, W. "An efficient signature scheme from bilinear pairing and its applications.” $\textit{Public Key Cryptography}$ , LNCS 2947, (2004) 277–290.

[Fiat_Shamir_1987] Fiat, A. and Shamir, "How to prove yourself: Practical solutions to identification and signature problems.” $\textit{Advances in Cryptology — CRYPTO’86}$ , LNCS 263, (1987) 186–194.

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

[Montgomery_1987] Montgomery, Peter L. "Speeding the Pollard and Elliptic Curve Methods of Factorization.” $\textit{Mathematics of Computation}$ , (1987) 48 (177): 243–264.

[Bernstein_2008] Bernstein, Daniel J., Birkner, Peter, Joye, Marc, Lange, Tanja, Peters, Christiane. In Vaudenay, Serge (ed.). "Twisted Edwards Curves.” $\textit{Progress in Cryptology — AFRICACRYPT 2008}$ , LNCS 5023, (2008) 389–405.

[Rodriguez-Henriquez_etc._2006] Rodríguez-Henríquez, F., Díaz-Pérez, A., Saqib, N. A. and Koč, Č. K. $\textit{Cryptographic Algorithms on Reconfigurable Hardware}$ , Signals and Communication Technology. Boston, MA: Springer US, 2006.

[Beuchat_etc._Nov_2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M. and Takagi, T. "Algorithms and Arithmetic Operators for Computing the $\eta T$ Pairing in Characteristic Three.” $\textit{IEEE Transactions on Computers}$ , vol. 57, no. 11, (Nov. 2008) 1454–1468.

[Beuchat_etc._2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E. and Rodríguez-Henríquez, F. "A Comparison Between Hardware Accelerators for the Modified Tate Pairing over $F_{2^m}$ and $F_{3^m}$ .” $\textit{Pairing-Based Cryptography — Pairing 2008}$ , (2008) 297–315.

[Kammler_etc._2009] Kammler, D., Zhang, D., Schwabe, P., Scharwaechter, H., Langenberg, M., Auras, D., Ascheid, G. and Mathar, R. "Designing an ASIP for Cryptographic Pairings over Barreto-Naehrig Curves.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2009},$ Springer Berlin/Heidelberg, (2009) 254–271.

[Ghosh_etc._2010] Ghosh, S., Mukhopadhyay, D. and Roychowdhury, D. "High Speed Flexible Pairing Cryptoprocessor on FPGA Platform.” $\textit{Pairing-Based Cryptography — Pairing 2010},$ vol. 6487, (2010) 450–466.

[Estibals_2010] Estibals, N. "Compact Hardware for Computing the Tate Pairing over 128-Bit Security Supersingular Curves.” $\textit{Pairing-Based Cryptography — Pairing 2010}$ , vol. 6487, (2010) 397–416.

[Ghosh_etc._2011] Ghosh, S., Roychowdhury, D. and Das, A. "High Speed Cryptoprocessor for $\eta T$ Pairing on 128-bit Secure Supersingular Elliptic Curves over Characteristic Two Fields.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2011}$ , (2011) 442–458.

[Beuchat_etc._2011] Beuchat, J.-L., Detrey, J., Estibals, N., Okamoto, E. and Rodríguez-Henríquez, F. "Fast Architectures for the $\eta T$ Pairing over Small-Characteristic Supersingular Elliptic Curves.” $\textit{IEEE Transactions on Computers}$ , vol. 60, no. 2, (Feb. 2011) 266–281.

[Cheung_etc._2011] Cheung, R. C. C., Duquesne, S., Fan, J., Guillermin, N., Verbauwhede, I. and Yao, G. X. "FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2011}$ , no. 07, (2011) 421–441.

[Adikari_etc._2012] Adikari, J., Hasan, M. A. and Negre, C. "Towards Faster and Greener Cryptoprocessor for Eta Pairing on Supersingular Elliptic Curve over $F_{2^{1223}}$ .” $19^{\mbox{th}}$ $\textit{International Conference, Selected Areas in Cryptography 2012}$ , (2012) 166–183.

Источник: https://habr.com/ru/articles/752988/

Вернуться к списку

Интересные статьи

Цифровой рубль утвержден Госдумой, а тиктокеры отбирают работу у компьютерных NPC

Почти все самые важные и интересные финансовые новости в России и мире за неделю: Илон Маск делает самый мощный ИИ вместе с xAI, на Binance.US объявили распродажу крипты со скидками, а судья в США изо...

Симулятор беспилотного гоночного болида на основе Gazebo 11 и ROS2 Foxy

Привет, Хабр! Недавно прошел ROS Russian Meetup, посвященный робототехнике. На митапе наша команда Bauman Racing Team из МГТУ им. Н.Э. Баумана представила собственный симулятор для беспилотного гоночн...

Управление на основе данных. Что общего между электронным дневником и базой налоговой?

Сегодня о подходе к управлению, основанному на данных, не говорит только ленивый. Кто уже имеет с этим дело в своей работе, предлагаем сразу переходить к разделу с описанием опыта Татарстана по управл...

Разметка данных: бизнес на миллиарды долларов, лежащий в основе прогресса AI

Когда два года назад Лэй Ван стала аннотатором данных, её работа была относительно простой: определять гендер людей на фотографиях. Но с тех пор Ван заметила, что сложность её задач становится всё в...

Формирование национальной экосистемы на основе цифровых технологий и «умных вещей»

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