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

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

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

История

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

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

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

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

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

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

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

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

В 2013 году The New York Times заявила, что детерминированная случайная генерация битов с двойной эллиптической кривой (или Dual_EC_DRBG) была включена в качестве национального стандарта NIST из-за влияния АНБ , которое включило преднамеренную слабость в алгоритм и рекомендуемую эллиптическую кривую. В сентябре 2013 года компания RSA Security выпустила рекомендацию, в которой рекомендовала своим клиентам прекратить использование любого программного обеспечения на базе Dual_EC_DRBG. После разоблачения Dual_EC_DRBG как «тайной операции АНБ» эксперты по криптографии также выразили обеспокоенность по поводу безопасности рекомендованных NIST эллиптических кривых. предлагая вернуться к шифрованию на основе групп неэллиптических кривых.

Дополнительная информация: § Атака квантовых вычислений.

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

Патенты

Основная статья: Патенты ECC

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

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

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

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

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

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

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

Приложение к криптографии

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

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

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

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

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

Выполнение

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

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

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

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

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

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

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

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

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

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

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

Размеры ключей

См. Также: Записи дискретного логарифма § Эллиптические кривые.

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

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

Текущий проект направлен на решение проблемы ECC2K-130 от Certicom за счет использования широкого спектра различного оборудования: процессоров, графических процессоров, FPGA.

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

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

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

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

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

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

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

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

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

Бэкдоры

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

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

Атака с помощью квантовых вычислений

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

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

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

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

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

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

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

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

См. также

• Криптовалюта
• Кривая25519
• ЧетыреQ
• DNSкривая
• RSA (криптосистема)
• Патенты ЕСС
• Эллиптическая кривая Диффи – Хеллмана (ECDH)
• Алгоритм цифровой подписи на основе эллиптических кривых (ECDSA)
• ЭдДСА
• ЕСМQV
• Умножение точек эллиптической кривой
• Гомоморфные подписи для сетевого кодирования
• Криптография гиперэллиптических кривых
• Криптография на основе пар
• Криптография с открытым ключом
• Квантовая криптография
• Обмен ключами суперсингулярной изогении
• Цифровая подпись BLS

Ссылки

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

• Жак Велю, Эллиптические кривые (...) , Société Mathématique de France, 57 , 1-152, Париж, 1978.

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

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