Pull to refresh

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

Reading time 9 min
Views 684

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

Введение

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

Для обозначения исчезающе малой вероятности будем использовать сокращение и.м.в. Это означает, что для некоторых \alpha\in\mathbb{F}_m и \beta, распределённого равномерно и независимо на интервале (0,m-1], по другому {\beta\in_R\!(0,m-1]}, {\Pr[\alpha=\beta]=m^{-1}} и для больших m эта величина исчезающе мала. Например, \Pr[\alpha=\beta]\sim 10^{-49} для m\sim 2^{160}. Аналогичное рассуждение справедливо для \Pr[g^{\alpha}=g^{\beta}], где g — порождающий элемент \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}}\}. В этом сертификате D — персональные данные владельца  \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} и D, в противоположном случае \mathfrak{B}=False. Доверенная сторона T может использовать произвольную схему ЭЦП, например, какую-то из описанных ниже. 

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

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

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

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

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

  1. Вычисляет \phi=\hslash(M).

  2. Формирует подпись \mathsf{S}=[\frac{1}{\phi+\mathbf{x}\pmod m}]\mathsf{G}_1=[\psi]\mathsf{G}_1.

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

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

  1. Вычисляет \phi'=\hslash(M').

  2. Проверяет подлинность, целостность и актуальность \mathsf{P}, если  актуальность не подтверждена или \mathfrak{B}=False, то завершает проверку ЭЦП.

  3. Вычисляет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}.

  4. Проверяет g'\stackrel{?}{=}e_m(\mathsf{G}_1, \mathsf{G}_1).

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

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

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

  1. Вычисляет \mathsf{Q}=H(M)=[\upsilon]\mathsf{G}_1.

  2. Формирует подпись \mathsf{S}=[\mathbf{x}]\mathsf{Q}=[\mathbf{x}\upsilon\pmod m]\mathsf{G}_1.

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

  1. Вычисляет \mathsf{Q}'=H(M').

  2. Проверяет подлинность, целостность и актуальность \mathsf{P}, если  актуальность не подтверждена или \mathfrak{B}=False, то завершает проверку ЭЦП;

  3. Проверяет 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

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

  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}=[(\upsilon+\mathbf{x}\pmod m)^{-1}]\mathsf{T}

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

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

  3. P проверяет условие \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}) в противном случае сессия завершается.

  4. V вычисляет 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

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

  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}=[\upsilon\mathbf{x}\pmod m]\mathsf{T}

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

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

  1. Как в Протоколе 1.

  2. Как в Протоколе 1.

  3. P проверяет условие {\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}), в противном случае сессия завершается.

  4. V вычисляет 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 в случае успешного завершения этапа идентификации стороны независимо формируют общий сессионный секретный ключ в соответствии со следующими правилами:

  1. P вычисляет \mathsf{A}=[\upsilon]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1.

  2. V вычисляет \mathsf{B}=[\phi]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1.

Очевидно, что \mathsf{A}=\mathsf{B} в силу коммутативности.

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

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

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

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

V' вычисляет \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} и V' вычисляет \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]} стороны P и V владеют парами ключей \{\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

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

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

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

  3. P \longrightarrow  V  : \mathsf{N}=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}

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

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

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

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

  3. P проверяет условие \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}), в противном случае сессия завершается.

  4. V вычисляет 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). Если равно, то доказательство принимается, и отвергается в противном случае.

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

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

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

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

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

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

Ограничимся анализом Протокола 3, в котором для имперсонификации проверяющего (замены V на V') необходимо вместо \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 и.м.в. P вычисляет \textit{response} как \mathsf{N}'=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}'.

V' вычисляет \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}, то имперсонификация V также невозможна, поскольку 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 сторона P должна сообщить стороне V серийный номер сертификата \{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 стороны P и V вычисляют \{\upsilon^{-1}, \mathbf{x}^{-1}\} и \mathbf{y}^{-1} соответственно.

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

P вычисляет \upsilon^{-1} в каждой отдельной сессии. Если на стороне P производительность платформы превышает пропускную способность канала связи между P и V, то при известном \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, но только P способен предоставить неоспоримое доказательство, поскольку владеет долговременным секретным ключом \mathbf{x} и знает эфемериду \upsilon. Проверить доказательство может только V, так как знает эфемериду \phi.

Кроме этого, независимо вычислить \mathsf{A} и \mathsf{B}, такие, что \mathsf{A}=\mathsf{B}, могут только P и V, так как владеют секретными ключами \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.

Tags:
Hubs:
+1
Comments 0
Comments Leave a comment

Articles