ЧетыреQ

ЧетыреQ
Разработчик(и)	Microsoft Исследования
Первоначальный выпуск	2015 ; 9 лет назад
Стабильная версия	v3.1
Репозиторий	github .с /Microsoft /FourQlib
Написано в	С
Операционная система	Виндовс 10 , Линукс
Платформа	ИА-32 , x86-64 , ARM32 , ARM64
Тип	эллиптических кривых Криптографическая библиотека
Лицензия	МОЯ лицензия
Веб-сайт	www .microsoft .с /en-нас /исследовать /проект /fourqlib /

В криптографии , FourQ — это эллиптическая кривая разработанная Microsoft Research . Он предназначен для схем соглашений о ключах ( эллиптическая кривая Диффи-Хеллмана ) и цифровых подписей ( Шнорр ) и предлагает около 128 бит безопасности . ^[1] Он оснащен эталонной реализацией, созданной авторами оригинальной статьи. Реализация с открытым исходным кодом называется FourQlib , работает в Windows и Linux и доступна для x86, x64 и ARM. ^[2] Он распространяется по лицензии MIT License , а исходный код доступен на GitHub . ^[3]

Его название происходит от четырехмерного скалярного умножения Галланта – Ламберта – Ванстона, которое позволяет выполнять высокопроизводительные вычисления. ^[4] Кривая определена над двумерным расширением поля простого , определенного простым числом Мерсенна. $2^{127}-1$ .

История

Кривая была опубликована в 2015 году Крейгом Костелло и Патриком Лонгой из Microsoft Research на сайте ePrint . ^[1]

Документ был представлен в Asiacrypt в 2015 году в Окленде , Новая Зеландия, и впоследствии эталонная реализация была опубликована на веб-сайте Microsoft . ^[2]

Были предприняты некоторые попытки стандартизировать использование кривой в рамках IETF ; эти усилия были прекращены в конце 2017 года. ^[5]

Математические свойства

Кривая определяется перекрученным уравнением Эдвардса

-x^{2}+y^{2}=1+dx^{2}y^{2}

$d$ является неквадратом в $\mathbb {F} _{p^{2}}$ , где $p$ это простое число Мерсенна $2^{127}-1$ .

Чтобы избежать атак небольших подгрупп , ^[6] проверяется, что все точки лежат в N - крученной подгруппе эллиптической кривой , где N задано как 246-битное простое число, делящее порядок группы.

Кривая снабжена двумя нетривиальными эндоморфизмами : $\psi$ связанные с $p$ -степенная карта Фробениуса и $\phi$ , эффективно вычислимый эндоморфизм низкой степени (см. комплексное умножение ).

Криптографические свойства

Безопасность

В настоящее время наиболее известной атакой дискретного логарифма является общий алгоритм Ро Полларда , требующий около $2^{122.5}$ групповые операции в среднем. Поэтому обычно он относится к 128-битному уровню безопасности.

Чтобы предотвратить атаки по времени , все групповые операции выполняются за постоянное время, т.е. без раскрытия информации о ключевом материале. ^[1]

Эффективность

Большинство криптографических примитивов, и особенно ECDH , требуют быстрого вычисления скалярного умножения, т.е. $[k]P$ за точку $P$ на кривой и целом числе $k$ , который обычно считается распределенным равномерно и случайным образом по $\{0,\ldots ,N-1\}$ .

Поскольку мы рассматриваем подгруппу простого порядка циклическую , можно написать скаляры $\lambda _{\psi },\lambda _{\phi }$ такой, что $\psi (P)=[\lambda _{\psi }]P$ и $\phi (P)=[\lambda _{\phi }]P$ за каждую точку $P$ в N -торсионной подгруппе.

Следовательно, для данного $k$ мы можем написать

k=a_{1}+a_{2}\lambda _{\phi }+a_{3}\lambda _{\psi }+a_{4}\lambda _{\phi }\lambda _{\psi }{\pmod {N}}

Если мы найдем маленький $a_{i}$ , мы можем вычислить $[k]P$ быстро, используя подразумеваемое уравнение

[k]P=[a_{1}]P+[a_{2}]\phi (P)+[a_{3}]\psi (P)+[a_{4}]\phi (\psi (P))

закругления бабая Техника ^[7] используется для поиска небольших $a_{i}$ . Для FourQ оказывается, что можно гарантировать эффективно вычислимое решение с $a_{i}<2^{64}$ .

Более того, поскольку характеристикой поля является простое число Мерсенна , модуляции могут передаваться эффективно.

Оба свойства (четырехмерное разложение и простая характеристика Мерсенна), наряду с использованием формул быстрого умножения ( расширенные скрученные координаты Эдвардса), делают FourQ самой быстрой на данный момент эллиптической кривой для 128-битного уровня безопасности.

Использование

FourQ реализован в криптографической библиотеке CIRCL , опубликованной Cloudflare . ^[8]

См. также

Ссылки

↑ Перейти обратно: Перейти обратно: ^а ^б ^с Костелло, Крейг; Лонга, Патрик (2015). «FourQ: четырехмерные разложения на Q-кривой над простым числом Мерсенна» . Проверено 23 мая 2019 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
↑ Перейти обратно: Перейти обратно: ^а ^б «ЧетыреКлиб» . Исследования Майкрософт . Проверено 23 мая 2019 г.
^ «Ссылки» . Гитхаб . 4 октября 2021 г.
^ Лонга, Патрик; Сика, Франческо (2011). «Четырехмерное скалярное умножение Галланта – Ламберта – Ванстона» . arXiv : 1106.5149 . Проверено 23 мая 2019 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Лэдд, Уотсон; Лонга, Патрик; Барнс, Ричард (27 марта 2017 г.). "draft-ladd-cfrg-4q-01" . Ietf Datatracker . Проверено 23 мая 2019 г.
^ ван Оршот, Пол К.; Винер, Майкл Дж. (1996). «О ключевом соглашении Диффи-Хеллмана с короткими показателями». Достижения в криптологии — EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. Шпрингер Берлин Гейдельберг. стр. 332–343. дои : 10.1007/3-540-68339-9_29 . ISBN 978-3-540-61186-8 .
^ Бабай, Л. (1 марта 1986 г.). «О редукции решетки Ловаса и проблеме ближайшей точки решетки». Комбинаторика . 6 (1): 1–13. дои : 10.1007/BF02579403 . ISSN 1439-6912 . S2CID 7914792 .
^ «Знакомство с CIRCL» . blog.cloudflare.com . 20 июня 2019 г. Проверено 28 июля 2019 г.

Внешние ссылки

Эталонная реализация от Microsoft

[4q-1] Перейти обратно: Перейти обратно: ^а ^б ^с Костелло, Крейг; Лонга, Патрик (2015). «FourQ: четырехмерные разложения на Q-кривой над простым числом Мерсенна» . Проверено 23 мая 2019 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[msf-2] Перейти обратно: Перейти обратно: ^а ^б «ЧетыреКлиб» . Исследования Майкрософт . Проверено 23 мая 2019 г.

[3] «Ссылки» . Гитхаб . 4 октября 2021 г.

[4] Лонга, Патрик; Сика, Франческо (2011). «Четырехмерное скалярное умножение Галланта – Ламберта – Ванстона» . arXiv : 1106.5149 . Проверено 23 мая 2019 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[5] Лэдд, Уотсон; Лонга, Патрик; Барнс, Ричард (27 марта 2017 г.). "draft-ladd-cfrg-4q-01" . Ietf Datatracker . Проверено 23 мая 2019 г.

[6] ван Оршот, Пол К.; Винер, Майкл Дж. (1996). «О ключевом соглашении Диффи-Хеллмана с короткими показателями». Достижения в криптологии — EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. Шпрингер Берлин Гейдельберг. стр. 332–343. дои : 10.1007/3-540-68339-9_29 . ISBN 978-3-540-61186-8 .

[7] Бабай, Л. (1 марта 1986 г.). «О редукции решетки Ловаса и проблеме ближайшей точки решетки». Комбинаторика . 6 (1): 1–13. дои : 10.1007/BF02579403 . ISSN 1439-6912 . S2CID 7914792 .

[8] «Знакомство с CIRCL» . blog.cloudflare.com . 20 июня 2019 г. Проверено 28 июля 2019 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]