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

Введение

В последующих разделах приводится описание двух схем электронной цифровой подписи (ЭЦП) на основе функции спаривания (Приложение 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) или подобных.

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

Выберем Протокол 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).$ вычисляет ${\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 при условии $\mathsf{P}_V$ или $e_m(\mathsf{P}_V, \mathsf{G}_1).$ Тогда ${\mathsf{S}'=[\mathbf{y}^{-1} \mathbf{\acute{y}}\pmod m]\mathsf{S}= [\upsilon]\mathsf{P}_{V'}}.$ Связь между 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}.$

Заключение

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

Скачать статью в pdf-формате

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

[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.

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