FourQ - 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 d}$ не квадрат в ${ displaystyle mathbb {F} _ {p ^ {2}}}$, куда ${ displaystyle p}$ это Мерсенн прайм ${ displaystyle 2 ^ {127} -1}$.

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

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

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

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

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

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

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

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

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

Следовательно, для данного ${ 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 (П))}$

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

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

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

Использует

Эта секция отсутствует информация об использовании. Пожалуйста, разверните раздел, чтобы включить эту информацию. Дополнительные сведения могут быть указаны на страница обсуждения. (Июль 2019)

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

Смотрите также

• Криптография с эллиптическими кривыми
• Подкрутка25519
• Подкрутка448

Рекомендации

внешняя ссылка

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