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

редактировать

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

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

Содержание

  • 1 Обоснование
  • 2 История
  • 3 Теория
  • 4 Криптографические схемы
  • 5 Реализация
    • 5.1 Параметры домена
    • 5.2 Размеры ключей
    • 5.3 Проекционные координаты
    • 5.4 Быстрая редукция (кривые NIST)
  • 6 Приложения
  • 7 Безопасность
    • 7.1 Атаки по побочному каналу
    • 7.2 Бэкдоры
    • 7.3 Атаки с использованием квантовых вычислений
    • 7.4 Атака с использованием неверной кривой
  • 8 Патенты
  • 9 Альтернативные представления
  • 10 См. Также
  • 11 Примечания
  • 12 Ссылки
  • 13 Внешние ссылки

Обоснование

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

Национальный институт стандартов и технологий США (NIST) одобрил криптографию с эллиптической кривой в своем наборе рекомендуемых алгоритмов Suite B, в частности, elliptic-curve Диффи – Хеллмана (ECDH) для обмена ключами и алгоритм цифровой подписи с эллиптической кривой (ECDSA) для цифровой подписи. Агентство национальной безопасности США (NSA) разрешает их использование для защиты информации, классифицированной до совершенно секретной, с помощью 384-битных ключей. Однако в августе 2015 года АНБ объявило, что планирует заменить Suite B новым набором шифров из-за опасений по поводу атак квантовых вычислений на ECC.

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

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

История

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

Теория

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

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

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

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

D iv 0 (E) → P ic 0 (E) ≃ E, {\ displaystyle \ mathrm { Div} ^ {0} (E) \ to \ mathrm {Pic} ^ {0} (E) \ simeq E, \,}{\ displaystyle \ mathrm {Div} ^ {0} (E) \ to \ mathrm {Pic} ^ {0} (E) \ simeq E, \,}

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

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

На конференции RSA 2005 года Агентство национальной безопасности (АНБ) объявило Suite B, который использует ECC исключительно для генерации цифровой подписи и обмена ключами. Этот пакет предназначен для защиты как секретных, так и несекретных систем национальной безопасности и информации.

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

Реализация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

Криптография эллиптической кривой используется криптовалютой Bitcoin.Ethereum версия 2.0 широко использует пары эллиптических кривых с использованием подписей BLS - как указано в проекте спецификации BLS IETF - для криптографической гарантии того, что конкретный валидатор Eth2 действительно проверил конкретную транзакцию.

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

Побочный канал атаки

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

Backdoors

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

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

Квантовые вычислительные атаки

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

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

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

Атака на неверную кривую

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

Патенты

По крайней мере одна схема ECC (ECMQV ) и некоторые методы реализации защищены патентами.

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

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

См. Также

Примечания

Ссылки

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

На Викискладе есть материалы, относящиеся к Эллиптическая кривая.
Последняя правка сделана 2021-05-19 07:39:27
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте