FourQ

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

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

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

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

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

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

${\displaystyle -x^{2}+y^{2}=1+dx^{2}y^{2}}$

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

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

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

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

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

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

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

Следовательно, для некоторого данности мы можем записать${\displaystyle k}$

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

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

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

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

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

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

This section is missing information about uses. Please expand the section to include this information. Further details may exist on the talk page. (July 2019)

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

• Криптография на основе эллиптических кривых
• Кривая25519
• Кривая448

• Референтная реализация от Microsoft