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

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

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

Обоснование [ править ]

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

США Национальный институт стандартов и технологий (NIST) одобрил эллиптическую кривую криптографию в Люкс В набор рекомендуемых алгоритмов, в частности , эллиптической кривой Диффи-Хеллмана (ECDH) для обмена ключами и эллиптических кривых Digital Signature Algorithm (ECDSA) для цифровой подписи . Агентство национальной безопасности США (АНБ) разрешает их использование для защиты информации, засекреченной до совершенно секретной, с помощью 384-битных ключей. ^[2] Однако в августе 2015 года АНБ объявило, что планирует заменить Suite B новым набором шифров из-за опасений по поводу атак квантовых вычислений на ECC. ^[3]

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

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

История [ править ]

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

Теория [ править ]

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

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

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

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

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

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

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

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

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

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

Реализация [ править ]

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

Параметры домена [ править ]

Чтобы использовать ECC, все стороны должны согласовать все элементы, определяющие эллиптическую кривую, то есть параметры области схемы. Поле определяется буквой p в простом случае и парой m и f в двоичном случае. Эллиптическая кривая определяется константами a и b, используемыми в ее определяющем уравнении. Наконец, циклическая подгруппа определяется ее генератором (он же базисной точки ) G . Для криптографической заявки порядка из G , то есть наименьшее положительное число п такое , что (в точку на бесконечности${\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 и построение кривых

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

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

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

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

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

Размеры ключей [ править ]

Поскольку все самые быстрые известные алгоритмы , которые позволяют решить ECDLP ( алгоритм шенкса , ро Полларда и т.д.), необходимость шагов, отсюда следует , что размер базового поля должна быть примерно в два раза параметр безопасности. Например, для 128-битной защиты нужна кривая , где . Это можно противопоставить криптографии с конечным полем (например, DSA ), которая требует ^[19] 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 месяца с использованием этого кластера при непрерывной работе. ^[20] Случай двоичного поля был раскрыт в апреле 2004 года с использованием 2600 компьютеров в течение 17 месяцев. ^[21]

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

Проективные координаты [ править ]

Внимательное изучение правил сложения показывает, что для сложения двух точек требуется не только несколько сложений и умножений, но и операция инверсии. Инверсия (для данной находки такая, что ) выполняется на один-два порядка медленнее ^[23], чем умножение. Однако точки на кривой могут быть представлены в разных системах координат, которые не требуют операции инверсии для добавления двух точек. Было предложено несколько таких систем: в проективной системе каждая точка представлена ​​тремя координатами с помощью следующего соотношения: , ; в системе Якоби точка также представлена ​​тремя координатами${\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)}$, но используется другое отношение: , ; в системе López-Dahab выполняется соотношение , ; в модифицированной системе Якоби используются те же соотношения, но четыре координаты сохраняются и используются для вычислений ; а в системе Якобиана Чудновского используются пять координат . Обратите внимание, что могут быть разные соглашения об именах, например, стандарт IEEE P1363 -2000 использует «проективные координаты» для обозначения того, что обычно называется якобианскими координатами. Дополнительное ускорение возможно при использовании смешанных координат. ^[24]${\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 является псевдо- простым числом Мерсенна , то есть ; например, или по сравнению с сокращением Барретта , ускорение может быть на порядок. ^[25] Ускорение здесь является скорее практическим, чем теоретическим, и происходит из того факта, что модули чисел в сравнении с числами, близкими к степени двойки, могут эффективно выполняться компьютерами, работающими с двоичными числами с помощью побитовых операций .${\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.}$

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

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

Приложения [ править ]

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

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

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

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

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

Криптография с эллиптической кривой используется криптовалютой Биткойн . ^[33] Ethereum версии 2.0 широко использует пары эллиптических кривых с использованием подписей BLS - как указано в проекте спецификации BLS IETF - для криптографической гарантии того, что конкретный валидатор Eth2 действительно проверил конкретную транзакцию. ^{[34] [35]}

Безопасность [ править ]

Атаки по побочным каналам [ править ]

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

Бэкдоры [ править ]

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

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

Квантовые вычислительные атаки [ править ]

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

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

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

Недействительная кривая атака [ править ]

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

Патенты [ править ]

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

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

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

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

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

• Эллиптические кривые в Стэнфордском университете

Викискладе есть медиафайлы по теме эллиптической кривой .