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

Подход к криптографии с открытым ключом

Криптография на основе эллиптических кривых ( ECC ) — это подход к криптографии с открытым ключом , основанный на алгебраической структуре эллиптических кривых над конечными полями . ECC позволяет использовать меньшие ключи для обеспечения эквивалентной безопасности по сравнению с криптосистемами, основанными на модульном возведении в степень в полях Галуа , такими как криптосистема RSA и криптосистема Эль-Гамаля . ^[1]

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

История

Использование эллиптических кривых в криптографии было предложено независимо друг от друга Нилом Коблицем ^[2] и Виктором С. Миллером ^[3] в 1985 году. Алгоритмы криптографии на основе эллиптических кривых стали широко использоваться в 2004–2005 годах.

В 1999 году NIST рекомендовал пятнадцать эллиптических кривых. В частности, FIPS 186-4 ^[4] рекомендует десять конечных полей:

• Пять простых полей для определенных простых чисел p размером 192, 224, 256, 384 и 521 бит. Для каждого из простых полей рекомендуется одна эллиптическая кривая. ${\displaystyle \mathbb {F} _{p}}$
• Пять двоичных полей для m равны 163, 233, 283, 409 и 571. Для каждого из двоичных полей была выбрана одна эллиптическая кривая и одна кривая Коблица . ${\displaystyle \mathbb {F} _{2^{m}}}$

Рекомендация NIST, таким образом, содержит в общей сложности пять простых кривых и десять бинарных кривых. Кривые были выбраны для оптимальной безопасности и эффективности внедрения. ^[5]

На конференции RSA 2005 года Агентство национальной безопасности (NSA) анонсировало Suite B , который использует исключительно ECC для генерации цифровой подписи и обмена ключами. Этот пакет предназначен для защиты как секретных, так и несекретных систем и информации национальной безопасности. ^[1] Национальный институт стандартов и технологий (NIST) одобрил криптографию на основе эллиптических кривых в своем наборе рекомендуемых алгоритмов Suite B , в частности алгоритм Диффи-Хеллмана на эллиптических кривых (ECDH) для обмена ключами и алгоритм цифровой подписи на эллиптических кривых (ECDSA) для цифровой подписи. АНБ разрешает их использование для защиты информации, классифицированной вплоть до совершенно секретной, с 384-битными ключами. ^[6]

Недавно ^{[ когда? ]} было введено большое количество криптографических примитивов, основанных на билинейных отображениях на различных группах эллиптических кривых, таких как пары Вейля и Тейта . Схемы, основанные на этих примитивах, обеспечивают эффективное шифрование на основе идентификации , а также подписи на основе пар, шифрование подписей , согласование ключей и повторное шифрование прокси . ^{[ нужна цитата ]}

Криптография на основе эллиптических кривых успешно используется во многих популярных протоколах, таких как Transport Layer Security и Bitcoin .

Проблемы безопасности

В 2013 году The New York Times заявила, что Dual Elliptic Curve Deterministic Random Bit Generation (или Dual_EC_DRBG) был включен в качестве национального стандарта NIST из-за влияния Агентства национальной безопасности , которое включило преднамеренную слабость в алгоритм и рекомендуемую эллиптическую кривую. ^{[7] В сентябре 2013 года} RSA Security выпустила рекомендацию, в которой рекомендовала своим клиентам прекратить использование любого программного обеспечения на основе Dual_EC_DRBG. ^{[8] [9]} После разоблачения Dual_EC_DRBG как «тайной операции Агентства национальной безопасности» эксперты по криптографии также выразили обеспокоенность по поводу безопасности рекомендуемых NIST эллиптических кривых, ^[10] предложив вернуться к шифрованию на основе групп, не являющихся эллиптическими кривыми.

Кроме того, в августе 2015 года АНБ объявило, что планирует заменить Suite B новым набором шифров из-за опасений по поводу атак на ECC с помощью квантовых вычислений . ^{[11] [12]}

Патенты

Хотя патент RSA истек в 2000 году, могут существовать действующие патенты, охватывающие определенные аспекты технологии ECC, включая по крайней мере одну схему ECC ( ECMQV ). Однако RSA Laboratories ^[13] и Daniel J. Bernstein ^[14] утверждают, что стандарт цифровой подписи правительства США на основе эллиптических кривых (ECDSA; NIST FIPS 186-3) и некоторые практические схемы обмена ключами на основе ECC (включая ECDH) могут быть реализованы без нарушения этих патентов.

Теория эллиптических кривых

В данной статье эллиптическая кривая — это плоская кривая над конечным полем (а не действительными числами), состоящая из точек, удовлетворяющих уравнению:

${\displaystyle y^{2}=x^{3}+ax+b,\,}$

вместе с выделенной точкой на бесконечности , обозначенной ∞. Координаты здесь должны быть выбраны из фиксированного конечного поля характеристики , не равной 2 или 3, иначе уравнение кривой было бы несколько сложнее.

Этот набор точек, вместе с групповой операцией эллиптических кривых , является абелевой группой , с точкой на бесконечности в качестве единичного элемента. Структура группы наследуется от группы делителей базового алгебраического многообразия :

${\displaystyle \mathrm {Div} ^{0}(E)\to \mathrm {Pic} ^{0}(E)\simeq E,\,}$

Применение в криптографии

Криптография с открытым ключом основана на неразрешимости некоторых математических задач . Ранние системы с открытым ключом, такие как патент RSA 1983 года, основывали свою безопасность на предположении, что трудно разложить большое целое число, состоящее из двух или более больших простых множителей, которые находятся далеко друг от друга. Для более поздних протоколов на основе эллиптических кривых базовым предположением является то, что нахождение дискретного логарифма случайного элемента эллиптической кривой относительно публично известной базовой точки невыполнимо ( вычислительное предположение Диффи–Хеллмана ): это «задача дискретного логарифма эллиптической кривой» (ECDLP). Безопасность криптографии на эллиптических кривых зависит от способности вычислять точечное умножение и невозможности вычислять множимое, учитывая исходную точку и точку произведения. Размер эллиптической кривой, измеряемый общим числом пар дискретных целых чисел, удовлетворяющих уравнению кривой, определяет сложность задачи.

Основным преимуществом эллиптической кривой по сравнению с альтернативами, такими как RSA, является меньший размер ключа , что снижает требования к хранению и передаче. ^[1] Например, 256-битный открытый ключ эллиптической кривой должен обеспечивать сопоставимую безопасность с 3072-битным открытым ключом RSA.

Криптографические схемы

Несколько протоколов на основе дискретного логарифма были адаптированы к эллиптическим кривым, заменив группу эллиптической кривой: ${\displaystyle (\mathbb {Z} _{p})^{\times }}$

• Схема согласования ключей Диффи–Хеллмана на эллиптических кривых ( ECDH) основана на схеме Диффи–Хеллмана ,
• Интегрированная схема шифрования на основе эллиптических кривых (ECIES), также известная как схема расширенного шифрования на основе эллиптических кривых или просто схема шифрования на основе эллиптических кривых,
• Алгоритм цифровой подписи на основе эллиптической кривой (ECDSA) основан на алгоритме цифровой подписи ,
• Схема деформации с использованием p-адической манхэттенской метрики Харрисона,
• Алгоритм цифровой подписи на основе кривой Эдвардса (EdDSA) основан на подписи Шнорра и использует скрученные кривые Эдвардса ,
• Схема согласования ключей ECMQV основана на схеме согласования ключей MQV ,
• Схема неявного сертификата ECQV .

Выполнение

Некоторые общие соображения по реализации включают в себя:

Параметры домена

Чтобы использовать ECC, все стороны должны договориться обо всех элементах, определяющих эллиптическую кривую, то есть о параметрах домена схемы. Размер используемого поля обычно либо простой (и обозначается как p), либо является степенью двойки ( ); последний случай называется двоичным случаем , и этот случай требует выбора вспомогательной кривой, обозначаемой как f . Таким образом, поле определяется как p в простом случае и как пара m и f в двоичном случае. Эллиптическая кривая определяется константами a и b, используемыми в ее определяющем уравнении. Наконец, циклическая подгруппа определяется ее генератором (он же базовая точка ) G . Для криптографического применения порядок G , то есть наименьшее положительное число n такое, что ( точка на бесконечности кривой и элемент идентичности ), обычно является простым. Поскольку n является размером подгруппы , из теоремы Лагранжа следует , что число является целым числом. В криптографических приложениях это число h , называемое кофактором , должно быть малым ( ) и, желательно, . Подводя итог: в простом случае параметры домена равны ; в двоичном случае они равны . ${\displaystyle 2^{m}}$ ${\displaystyle nG={\mathcal {O}}}$ ${\displaystyle E(\mathbb {F} _{p})}$ ${\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{p})|}$ ${\displaystyle h\leq 4}$ ${\displaystyle h=1}$ ${\displaystyle (p,a,b,G,n,h)}$ ${\displaystyle (m,f,a,b,G,n,h)}$

Если нет уверенности в том, что параметры домена были сгенерированы стороной, доверенной в отношении их использования, параметры домена должны быть проверены перед использованием.

Генерация параметров домена обычно не выполняется каждым участником, поскольку это включает в себя вычисление количества точек на кривой , что требует много времени и является сложным для реализации. В результате несколько органов стандартизации опубликовали параметры домена эллиптических кривых для нескольких распространенных размеров полей. Такие параметры домена обычно известны как «стандартные кривые» или «именованные кривые»; на именованную кривую можно ссылаться либо по имени, либо по уникальному идентификатору объекта , определенному в стандартных документах:

• NIST , Рекомендованные эллиптические кривые для государственного использования
• SECG , SEC 2: Рекомендуемые параметры домена эллиптической кривой
• ECC Brainpool ( RFC  5639), Стандартные кривые ECC Brainpool и генерация кривых ^{[15] [16]}

Также доступны тестовые векторы SECG. ^[17] NIST одобрил множество кривых SECG, поэтому существует значительное совпадение между спецификациями, опубликованными NIST и SECG. Параметры домена EC могут быть указаны либо по значению, либо по имени.

Если, несмотря на предыдущее предостережение, кто-то решает построить собственные параметры домена, он должен выбрать базовое поле, а затем использовать одну из следующих стратегий, чтобы найти кривую с подходящим (т.е. близким к простому) числом точек, используя один из следующих методов:

• Выберите случайную кривую и используйте общий алгоритм подсчета точек, например, алгоритм Шуфа или алгоритм Шуфа–Элкиса–Аткина ,
• Выберите случайную кривую из семейства, позволяющего легко рассчитать количество точек (например, кривые Коблица), или
• Выберите количество точек и сгенерируйте кривую с этим количеством точек, используя технику комплексного умножения . ^[18]

Некоторые классы кривых являются слабыми и их следует избегать:

• Кривые с непростым m уязвимы для атак спуска Вейля . ^{[19] [20]} ${\displaystyle \mathbb {F} _{2^{m}}}$
• Кривые, такие, что n делится (где p — характеристика поля: q для простого поля или для двоичного поля) для достаточно малого B , уязвимы для атаки Менезеса–Окамото–Ванстоуна (MOV) ^{[21] [22]} , которая применяет обычную задачу дискретного логарифмирования (DLP) в поле расширения малой степени для решения ECDLP. Граница B должна быть выбрана так, чтобы дискретные логарифмы в поле были по крайней мере столь же трудны для вычисления, как и дискретные логарифмы на эллиптической кривой . ^[23] ${\displaystyle p^{B}-1}$ ${\displaystyle 2}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle \mathbb {F} _{p^{B}}}$ ${\displaystyle E(\mathbb {F} _{q})}$
• Кривые, которые уязвимы для атаки, которая отображает точки на кривой в аддитивную группу . ^{[24] [25] [26]} ${\displaystyle |E(\mathbb {F} _{q})|=q}$ ${\displaystyle \mathbb {F} _{q}}$

Размеры клавиш

Поскольку все самые быстрые известные алгоритмы, позволяющие решить ECDLP ( baby-step giant-step , Pollard's rho и т. д.), требуют шагов, из этого следует, что размер базового поля должен быть примерно вдвое больше параметра безопасности. Например, для 128-битной безопасности нужна кривая над , где . Это можно противопоставить криптографии с конечным полем (например, DSA ), которая требует ^[27] 3072-битных открытых ключей и 256-битных закрытых ключей, и криптографии с целочисленной факторизацией (например, RSA ), которая требует 3072-битного значения n , где закрытый ключ должен быть таким же большим. Однако открытый ключ может быть меньше для обеспечения эффективного шифрования, особенно когда вычислительная мощность ограничена (например, в Африке). ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q\approx 2^{256}}$

Самая сложная схема ECC (публично) взломанная на сегодняшний день ^{[ когда? ]} имела 112-битный ключ для случая простого поля и 109-битный ключ для случая двоичного поля. Для случая простого поля это было взломано в июле 2009 года с использованием кластера из более чем 200 игровых консолей PlayStation 3 и могло быть завершено за 3,5 месяца с использованием этого кластера при непрерывной работе. ^[28] Случай двоичного поля был взломан в апреле 2004 года с использованием 2600 компьютеров в течение 17 месяцев. ^[29]

Текущий проект направлен на преодоление проблемы ECC2K-130 от Certicom, используя широкий спектр различного оборудования: центральные процессоры, графические процессоры, ПЛИС. ^[30]

Проективные координаты

Тщательное изучение правил сложения показывает, что для сложения двух точек необходимо не только несколько сложений и умножений, но и операция инверсии . Инверсия (для заданного find такого, что ) на один-два порядка медленнее ^[31] , чем умножение. Однако точки на кривой можно представить в разных системах координат, которые не требуют операции инверсии для сложения двух точек. Было предложено несколько таких систем: в проективной системе каждая точка представлена ​​тремя координатами с использованием следующего соотношения: , ; в якобианской системе точка также представлена ​​тремя координатами , но используется другое соотношение: , ; в системе Лопеса–Дахаба соотношение равно , ; в модифицированной якобианской системе используются те же соотношения, но для вычислений хранятся и используются четыре координаты ; а в якобианской системе Чудновского используются пять координат . Обратите внимание, что могут быть разные соглашения об именах, например, стандарт IEEE P1363 -2000 использует «проективные координаты» для обозначения того, что обычно называют якобианскими координатами. Дополнительное ускорение возможно, если используются смешанные координаты. ^[32] ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle x\in \mathbb {F} _{q}}$ ${\displaystyle y\in \mathbb {F} _{q}}$ ${\displaystyle xy=1}$ ${\displaystyle (X,Y,Z)}$ ${\displaystyle x={\frac {X}{Z}}}$ ${\displaystyle y={\frac {Y}{Z}}}$ ${\displaystyle (X,Y,Z)}$ ${\displaystyle x={\frac {X}{Z^{2}}}}$ ${\displaystyle y={\frac {Y}{Z^{3}}}}$ ${\displaystyle x={\frac {X}{Z}}}$ ${\displaystyle y={\frac {Y}{Z^{2}}}}$ ${\displaystyle (X,Y,Z,aZ^{4})}$ ${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$

Быстрое восстановление (кривые NIST)

Редукция по модулю p (которая необходима для сложения и умножения) может быть выполнена намного быстрее, если простое число p является псевдопростым числом Мерсенна , то есть ; например, или По сравнению с редукцией Барретта , может быть ускорение на порядок. ^[33] Ускорение здесь является скорее практическим, чем теоретическим, и вытекает из того факта, что модули чисел по числам, близким к степеням двойки, могут быть эффективно выполнены компьютерами, работающими с двоичными числами с побитовыми операциями . ${\displaystyle p\approx 2^{d}}$ ${\displaystyle p=2^{521}-1}$ ${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1.}$

Кривые с псевдомерсенновским p рекомендуются NIST. Еще одним преимуществом кривых NIST является то, что они используют a  = −3, что улучшает сложение в якобианских координатах. ${\displaystyle \mathbb {F} _{p}}$

По словам Бернстайна и Ланге, многие решения, связанные с эффективностью в NIST FIPS 186-2, являются неоптимальными. Другие кривые более безопасны и работают так же быстро. ^[34]

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

Атаки по побочным каналам

В отличие от большинства других систем DLP (где можно использовать одну и ту же процедуру для возведения в квадрат и умножения), сложение EC существенно отличается для удвоения ( P = Q ) и общего сложения ( P ≠ Q ) в зависимости от используемой системы координат. Следовательно, важно противодействовать атакам по побочным каналам (например, атакам по времени или простому/дифференциальному анализу мощности ), используя, например, методы фиксированного окна шаблона (также известного как гребенка) ^{[ необходимо разъяснение ] [35]} (обратите внимание, что это не увеличивает время вычислений). В качестве альтернативы можно использовать кривую Эдвардса ; это особое семейство эллиптических кривых, для которых удвоение и сложение могут быть выполнены с помощью одной и той же операции. ^[36] Еще одной проблемой для систем ECC является опасность атак с ошибками , особенно при работе на смарт-картах . ^[37]

Бэкдоры

Эксперты по криптографии выразили обеспокоенность тем, что Агентство национальной безопасности вставило клептографический бэкдор по крайней мере в один псевдослучайный генератор на основе эллиптических кривых. ^[38] Внутренние меморандумы, обнародованные бывшим подрядчиком АНБ Эдвардом Сноуденом, предполагают, что АНБ вставило бэкдор в стандарт Dual EC DRBG . ^[39] Один из анализов возможного бэкдора пришел к выводу, что злоумышленник, обладающий секретным ключом алгоритма, может получить ключи шифрования, имея только 32 байта выходных данных PRNG. ^[40]

Проект SafeCurves был запущен с целью каталогизации кривых, которые легко реализовать безопасно и которые разработаны полностью публично проверяемым способом, чтобы свести к минимуму вероятность бэкдора. ^[41]

Атака квантовых вычислений

Алгоритм Шора может быть использован для взлома криптографии эллиптических кривых путем вычисления дискретных логарифмов на гипотетическом квантовом компьютере . Последние оценки квантовых ресурсов для взлома кривой с 256-битным модулем (уровень безопасности 128 бит) составляют 2330 кубитов и 126 миллиардов вентилей Тоффоли . ^[42] Для случая двоичной эллиптической кривой необходимо 906 кубитов (для взлома 128 бит безопасности). ^[43] Для сравнения, использование алгоритма Шора для взлома алгоритма RSA требует 4098 кубитов и 5,2 триллиона вентилей Тоффоли для 2048-битного ключа RSA, что говорит о том, что ECC является более легкой целью для квантовых компьютеров, чем RSA. Все эти цифры значительно превышают любой квантовый компьютер, который когда-либо был построен, и оценки относят создание таких компьютеров к десятилетию или более. ^{[ необходима цитата ] [44]}

Суперсингулярная изогения Диффи-Хеллмана Key Exchange, как утверждается, обеспечивает постквантовую безопасную форму эллиптической кривой криптографии, используя изогении для реализации обмена ключами Диффи-Хеллмана . Этот обмен ключами использует большую часть той же арифметики полей, что и существующая эллиптическая кривая криптография, и требует вычислительных и передающих накладных расходов, аналогичных многим используемым в настоящее время системам с открытым ключом. ^[45] Однако новые классические атаки подорвали безопасность этого протокола. ^[46]

В августе 2015 года АНБ объявило, что планирует перейти «в недалеком будущем» на новый набор шифров, устойчивый к квантовым атакам. «К сожалению, рост использования эллиптических кривых столкнулся с фактом продолжающегося прогресса в исследованиях квантовых вычислений, что требует переоценки нашей криптографической стратегии». ^[11]

Неверная кривая атака

Когда ECC используется в виртуальных машинах , злоумышленник может использовать недействительную кривую, чтобы получить полный закрытый ключ PDH. ^[47]

Альтернативные представления

Альтернативные представления эллиптических кривых включают в себя:

• кривые Гессе
• кривые Эдвардса
• Извилистые кривые
• Скрученные кривые Гессе
• Скрученная кривая Эдвардса
• Кривая Доша–Икарта–Кохеля, ориентированная на удвоение
• Кривая Доше–Икарта–Коэля, ориентированная на утроение
• кривая Якоби
• кривые Монтгомери

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

• Криптовалюта
• Кривая25519
• FourQ
• DNSCurve
• RSA (криптосистема)
• Патенты ЕСС
• Эллиптическая кривая Диффи-Хеллмана (ECDH)
• Алгоритм цифровой подписи на основе эллиптических кривых (ECDSA)
• EdDSA
• ECMQV
• Умножение точек эллиптической кривой
• Гомоморфные сигнатуры для сетевого кодирования
• Криптография на основе гиперэллиптических кривых
• Криптография на основе парного шифрования
• Криптография с открытым ключом
• Квантовая криптография
• Суперсингулярный изогенический обмен ключами
• Цифровая подпись BLS

Примечания

1. "The Case for Elliptic Curve Cryptography". NSA . Архивировано из оригинала 2009-01-17.
2. Коблиц, Н. (1987). «Криптосистемы на эллиптических кривых». Математика вычислений . 48 (177): 203–209. doi : 10.2307/2007884 . JSTOR  2007884.
3. Миллер, В. (1986). «Использование эллиптических кривых в криптографии». Достижения в криптологии — Труды CRYPTO '85 . Конспект лекций по информатике. Том 85. С. 417–426. doi :10.1007/3-540-39799-X_31. ISBN 978-3-540-16463-0. S2CID  206617984.
4. "Стандарт цифровой подписи (DSS)". Национальный институт стандартов и технологий. 2013-07-19. doi : 10.6028/NIST.FIPS.186-4 .
5. FIPS PUB 186-3, Стандарт цифровой подписи (DSS).
6. "Fact Sheet NSA Suite B Cryptography". Агентство национальной безопасности США . Архивировано из оригинала 2009-02-07.
7. Перлрот, Николь; Ларсон, Джефф; Шейн, Скотт (2013-09-05). «АНБ способно нарушить основные гарантии конфиденциальности в Интернете». New York Times . Архивировано из оригинала 2022-01-01 . Получено 28 октября 2018 г.
8. Ким Зеттер, RSA сообщает своим клиентам-разработчикам: прекратите использовать алгоритм, связанный с АНБ Wired , 19 сентября 2013 г. «Рекомендуется не использовать SP 800-90A Dual Elliptic Curve Deterministic Random Bit Generation: NIST настоятельно рекомендует, до разрешения проблем безопасности и повторного выпуска SP 800-90A, Dual_EC_DRBG, как указано в версии SP 800-90A от января 2012 г., больше не использовать».
9. "Поиск – CSRC". csrc.nist.gov .
10. Брюс Шнайер (5 сентября) «Я больше не доверяю константам. Я считаю, что АНБ манипулировало ими через свои связи с промышленностью». См. Are the NIST Standard Elliptic Curves Back-doored?, Slashdot , 11 сентября 2013 г.
11. "Commercial National Security Algorithm Suite". www.nsa.gov . 19 августа 2015 г. Архивировано из оригинала 2019-06-04 . Получено 2020-01-08 .
12. FAQ по набору коммерческих алгоритмов национальной безопасности и квантовым вычислениям. Агентство национальной безопасности США, январь 2016 г.
13. RSA Laboratories. "6.3.4 Патентуются ли криптосистемы на эллиптических кривых?". Архивировано из оригинала 2016-11-01.
14. Бернстайн, DJ «Нерелевантные патенты на криптографию на основе эллиптических кривых».
15. Архивировано 17.04.2018 в Wayback Machine
16. "Эллиптическая кривая криптографии "Сделано в Германии"" (пресс-релиз). 2014-06-25.
17. "GEC 2: Тестовые векторы для SEC 1" (PDF) . www.secg.org . Архивировано из оригинала (загрузка PDF) 2013-06-06.
18. Лэй, Георг-Иоганн; Циммер, Хорст Г. (1994). «Построение эллиптических кривых с заданным групповым порядком над большими конечными полями». Алгоритмическая теория чисел . Конспект лекций по информатике. Том 877. С. 250–263. doi :10.1007/3-540-58691-1_64. ISBN 978-3-540-58691-3.
19. Гэлбрейт, SD; Смарт, NP (1999). "Криптографическое применение спуска Вейля". Криптографическое применение спуска Вейля . Lecture Notes in Computer Science. Vol. 1746. p. 799. doi :10.1007/3-540-46665-7_23. ISBN 978-3-540-66887-9. S2CID  15134380.
20. Годри, П.; Гесс, Ф.; Смарт, Н. П. (2000). "Конструктивные и деструктивные грани спуска Вейля на эллиптических кривых" (PDF) . Технический отчет Hewlett Packard Laboratories . Архивировано из оригинала (PDF) 2006-12-06 . Получено 2006-01-02 .
21. Менезес, А.; Окамото, Т.; Ванстоун, С.А. (1993). «Сведение логарифмов эллиптических кривых к логарифмам в конечном поле». Труды IEEE по теории информации . 39 (5): 1639–1646. doi :10.1109/18.259647.
22. Хитт, Л. (2006). «Об улучшенном определении степени внедрения». Отчет IACR ePrint . 415 .
23. IEEE P1363 Архивировано 13 февраля 2007 г. на Wayback Machine , раздел A.12.1
24. Семаев, И. (1998). "Оценка дискретного логарифма в группе точек p-кручения эллиптической кривой в характеристике p". Математика вычислений . 67 (221): 353–356. Bibcode :1998MaCom..67..353S. doi : 10.1090/S0025-5718-98-00887-4 .
25. Смарт, Н. (1999). «Проблема дискретного логарифмирования на эллиптических кривых следа один». Журнал криптологии . 12 (3): 193–196. CiteSeerX 10.1.1.17.1880 . doi :10.1007/s001459900052. S2CID  24368962. 
26. Сато, Т.; Араки, К. (1998). «Факторы Ферма и алгоритм дискретного логарифмирования с полиномиальным временем для аномальных эллиптических кривых». Комментарии Mathematici Universitatis Sancti Pauli . 47 .
27. NIST, Рекомендации по управлению ключами — Часть 1: общие положения, Специальная публикация 800-57, август 2005 г.
28. "112-битный простой ECDLP решен – LACAL". lacal.epfl.ch . Архивировано из оригинала 2009-07-15 . Получено 2009-07-11 .
29. "Certicom объявляет победителя конкурса Elliptic Curve Cryptography Challenge". Certicom . 27 апреля 2004 г. Архивировано из оригинала 2011-07-19.
30. "Взлом ECC2K-130". www.ecc-challenge.info .
31. Хичкок, Y.; Доусон, E.; Кларк, A.; Монтегю, P. (2002). «Реализация эффективной эллиптической криптосистемы над GF(p) на смарт-карте» (PDF) . Журнал ANZIAM . 44 . Архивировано из оригинала (PDF) 2006-03-27.
32. Коэн, Х.; Мияджи , А .; Оно, Т. (1998). «Эффективное возведение в степень эллиптической кривой с использованием смешанных координат». Достижения в криптологии — ASIACRYPT'98 . Конспект лекций по информатике. Том 1514. С. 51–65. doi :10.1007/3-540-49649-1_6. ISBN 978-3-540-65109-3.
33. Браун, М.; Ханкерсон, Д.; Лопес, Дж.; Менезес, А. (2001). «Программная реализация эллиптических кривых NIST над простыми полями». Темы по криптологии — CT-RSA 2001. Конспект лекций по информатике. Том 2020. С. 250–265. CiteSeerX 10.1.1.25.8619 . doi :10.1007/3-540-45353-9_19. ISBN  978-3-540-41898-6.
34. Дэниел Дж. Бернстайн и Таня Ланге . "SafeCurves: выбор безопасных кривых для криптографии на основе эллиптических кривых" . Получено 1 декабря 2013 г.
35. Хедабу, М.; Пинель, П.; Бенето, Л. (2004). «Метод гребня для обеспечения устойчивости ECC к атакам по сторонним каналам» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
36. "Cr.yp.to: 2014.03.23: Как разработать систему подписи на эллиптических кривых".
37. См., например, Biehl, Ingrid; Meyer, Bernd; Müller, Volker (2000). "Differential Fault Attacks on Elliptic Curve Cryptosystems". Advances in Cryptology — CRYPTO 2000 (PDF) . Lecture Notes in Computer Science . Vol. 1880. pp. 131–146. doi :10.1007/3-540-44598-6_8. ISBN 978-3-540-67907-3.
38. «АНБ встроило секретный бэкдор в новый стандарт шифрования?». www.schneier.com .
39. «Правительство объявляет о шагах по восстановлению доверия к стандартам шифрования». NY Times – Bits Blog . 2013-09-10 . Получено 2015-11-06 .
40. Шумов, Дэн; Фергюсон, Нильс. «О возможности бэкдора в NIST SP800-90 Dual Ec Prng» (PDF) . Microsoft .
41. Бернстайн, Дэниел Дж.; Ланге, Таня. «SafeCurves: выбор безопасных кривых для криптографии на основе эллиптических кривых» . Получено 1 октября 2016 г.
42. Роттлер, Мартин; Наериг, Майкл; Своре, Криста М.; Лаутер, Кристин (2017). «Оценки квантовых ресурсов для вычисления дискретных логарифмов эллиптических кривых». arXiv : 1706.06752 [quant-ph].
43. Банегас, Г.; Бернштейн, Д.Дж.; Хоф, И. ван; Ланге, Т. (2020). «Конкретный квантовый криптоанализ бинарных эллиптических кривых» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
44. Холмс, Дэвид (7 сентября 2021 г.). «RSA в мире «до-постквантовых» вычислений». f5 . Архивировано из оригинала 2020-08-08 . Получено 16 марта 2021 г. .
45. De Feo, Luca; Jao, Plut (2011). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". Архив Cryptology ePrint, Отчет 2011/506 . IACR. Архивировано из оригинала 2014-05-03 . Получено 3 мая 2014 .
46. Роберт, Дэмиен (2022). «Взлом SIDH за полиномиальное время». Архив Cryptology ePrint .
47. Cohen, Cfir (25 июня 2019 г.). "AMD-SEV: восстановление ключа DH платформы через атаку с недопустимой кривой (CVE-2019-9836)". Seclist Org . Архивировано из оригинала 2 июля 2019 г. Получено 4 июля 2019 г. Реализация эллиптической кривой (ECC) SEV оказалась уязвимой для атаки с недопустимой кривой. При команде launch-start злоумышленник может отправить точки ECC малого порядка, не находящиеся на официальных кривых NIST, и заставить прошивку SEV умножить точку малого порядка на частный скаляр DH прошивки.

Ссылки

• Группа стандартов эффективной криптографии (SECG) , SEC 1: Криптография на эллиптических кривых, версия 1.0, 20 сентября 2000 г. (архивировано 11 ноября 2014 г.)
• Д. Ханкерсон, А. Менезес и С.А. Ванстоун, Руководство по криптографии на основе эллиптических кривых , Springer-Verlag, 2004.
• И. Блейк, Г. Серусси и Н. Смарт, Эллиптические кривые в криптографии , Лондонское математическое общество 265, Издательство Кембриджского университета, 1999.
• И. Блейк, Г. Серусси и Н. Смарт, редакторы, «Достижения в криптографии эллиптических кривых» , Лондонское математическое общество 317, Издательство Кембриджского университета, 2005.
• Л. Вашингтон, Эллиптические кривые: теория чисел и криптография , Chapman & Hall / CRC, 2003.
• Аргументы в пользу эллиптической кривой криптографии, Агентство национальной безопасности (архивировано 17 января 2009 г.)
• Онлайн-руководство по криптографии на основе эллиптических кривых, Certicom Corp. (архивировано здесь по состоянию на 3 марта 2016 г.)
• K. Malhotra, S. Gardner и R. Patz, Реализация эллиптической криптографии на мобильных медицинских устройствах, Сети, датчики и управление, 2007 IEEE Международная конференция, Лондон, 15–17 апреля 2007 г. Страницы: 239–244
• Сайкат Басу, Новая параллельная оконная реализация умножения точек эллиптической кривой в многоядерных архитектурах, Международный журнал сетевой безопасности, том 13, № 3, 2011 г., страницы: 234–241 (архивировано здесь по состоянию на 4 марта 2016 г.)
• Кристоф Паар, Ян Пельцль, «Криптосистемы на эллиптических кривых», Глава 9 книги «Понимание криптографии. Учебник для студентов и практиков». (сопутствующий веб-сайт содержит онлайн-курс по криптографии, охватывающий криптографию на эллиптических кривых), Springer, 2009. (архивировано здесь по состоянию на 20 апреля 2016 г.)
• Лука Де Фео, Дэвид Джао, Джером Плут, «К квантово-устойчивым криптосистемам на основе суперсингулярных изогений эллиптических кривых», Springer 2011. (архивировано здесь по состоянию на 7 мая 2012 г.)
• Густаво Банегас, Дэниел Дж. Бернстайн, Игги Ван Хоф, Таня Ланге, Конкретный квантовый криптоанализ бинарных эллиптических кривых, Springer 2020. (архивировано здесь по состоянию на 1 июня 2020 г.)

• Жак Велю, Courbes elliptiques (...), Société Mathématique de France, 57, 1-152, Париж, 1978.

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

• Эллиптические кривые в Стэнфордском университете
• Интерактивное введение в эллиптические кривые и криптографию на основе эллиптических кривых с Sage от Майке Массирер и команды CrypTool
• Медиа, связанные с Эллиптическая кривая на Wikimedia Commons