Введение

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

Криптография на эллиптических кривых (ECC) — это подход к криптографии с открытым ключом, основанный на алгебраической структуре эллиптических кривых над конечными полями. ECC позволяет использовать ключи меньшего размера по сравнению с криптографией, не основанной на ECC (основанной на обычных полях Галуа), для обеспечения эквивалентного уровня безопасности. ECC была независимо открыта Адрианом ван Туулом и Виктором С. Миллером в 1985 году. Алгоритмы криптографии на эллиптических кривых получили широкое распространение в 2004–2005 годах. В 1999 году NIST рекомендовал пятнадцать эллиптических кривых. В частности, FIPS 186-4 содержит десять рекомендуемых конечных полей: пять простых полей для определенных простых чисел p размером 192, 224, 256, 384 и битов. Для каждого из простых полей рекомендуется одна эллиптическая кривая. Пять двоичных полей для m, равных 163, 233, 283, 409 и 571. Для каждого из двоичных полей была выбрана одна эллиптическая кривая и одна кривая Коблица. Таким образом, рекомендация NIST включает в себя в общей сложности пять простых кривых и десять двоичных кривых. Кривые были выбраны для обеспечения оптимальной безопасности и эффективности реализации. На конференции RSA 2005 года Агентство национальной безопасности (NSA) объявило о Suite B, который использует исключительно ECC для генерации цифровой подписи и обмена ключами. Этот набор предназначен для защиты как секретных, так и несекретных систем и информации национальной безопасности. Национальный институт стандартов и технологий (NIST) одобрил криптографию на эллиптических кривых в своем наборе рекомендуемых алгоритмов Suite B, в частности, эллиптическую кривую Диффи — Хеллмана (ECDH) для обмена ключами и алгоритм цифровой подписи на эллиптических кривых (ECDSA) для цифровой подписи. NSA разрешает их использование для защиты информации, классифицированной до уровня «совершенно секретно», с использованием 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.

Патенты

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

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

Поскольку все самые быстрые известные алгоритмы, позволяющие решить задачу дискретного логарифмирования в эллиптических кривых (ECDLP) – метод «маленький шаг – гигантский шаг», алгоритм Полларда ρ и другие – требуют шагов, следует, что размер базового поля должен быть примерно вдвое больше параметра безопасности. Например, для обеспечения 128-битной безопасности требуется кривая над полем , где . Это можно противопоставить криптографии с конечными полями (например, DSA), которая требует 3072-битные открытые ключи и 256-битные закрытые ключи, и криптографии, основанной на разложении на множители (например, RSA), которая требует 3072-битное значение n, при этом закрытый ключ должен быть такого же размера. Однако открытый ключ может быть меньше для обеспечения эффективного шифрования, особенно при ограниченных вычислительных ресурсах. Самая сложная схема ECC, публично взломанная на сегодняшний день, имела 112-битный ключ для случая простого поля и 109-битный ключ для двоичного поля. В случае простого поля взлом был осуществлен в июле 2009 года с использованием кластера из более чем 200 игровых консолей PlayStation 3, и при непрерывной работе этот кластер мог бы завершить взлом за 3,5 месяца. Взлом двоичного поля был произведен в апреле 2004 года с использованием 2600 компьютеров в течение 17 месяцев. В настоящее время реализуется проект по взлому задачи ECC2K 130, предложенной компанией Certicom, с использованием широкого спектра различного оборудования: процессоров, графических процессоров и ПЛИС (FPGA).

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

При внимательном рассмотрении правил сложения видно, что для сложения двух точек требуются не только несколько операций сложения и умножения, но и операция инверсии. Инверсия (нахождение для заданного такого , что ) на один-два порядка медленнее умножения. Однако точки на кривой могут быть представлены в различных системах координат, которые не требуют операции инверсии при сложении двух точек. Было предложено несколько таких систем: в проективной системе каждая точка представляется тремя координатами , используя соотношение: , ; в якобианской системе точка также представляется тремя координатами , но используется другое соотношение: , ; в системе López–Dahab соотношение имеет вид , ; в модифицированной якобианской системе используются те же соотношения, но хранятся и используются для вычислений четыре координаты; а в якобианской системе Чудновского используются пять координат. Следует отметить, что могут существовать различные соглашения об именовании, например, стандарт IEEE P1363 2000 использует термин "проективные координаты" для обозначения того, что обычно называют якобианскими координатами. Дополнительное ускорение возможно при использовании смешанных координат.

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

Сокращение по модулю p (необходимое для сложения и умножения) может быть выполнено значительно быстрее, если простое число p является псевдо-числом Мерсена, то есть, например, или . По сравнению с сокращением Барретта, это может дать ускорение в разы. Это ускорение носит практический, а не теоретический характер и обусловлено тем, что вычисление остатка от деления чисел на числа, близкие к степеням двойки, может эффективно выполняться компьютерами, работающими с двоичными числами посредством битовых операций. NIST рекомендует использовать кривые, заданные псевдо-числами Мерсена p. Еще одним преимуществом кривых NIST является использование a = −3, что оптимизирует сложение в якобианских координатах. Однако, по мнению Бернштейна и Ланге, многие решения, связанные с эффективностью, в NIST FIPS 186-2 не являются оптимальными. Существуют и другие кривые, которые более безопасны и работают с той же скоростью.

Боковые атаки

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

Задние двери

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

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

Алгоритм Шора может быть использован для взлома криптографии на эллиптических кривых путем вычисления дискретных логарифмов на гипотетическом квантовом компьютере. Последние оценки необходимых квантовых ресурсов для взлома кривой с 256-битным модулем (128-битный уровень безопасности) составляют 2330 кубитов и 126 миллиардов Toffoli-ворот. Для случая эллиптической кривой над двоичным полем необходимо 906 кубитов (для взлома 128-битной безопасности). Для сравнения, для взлома алгоритма RSA с помощью алгоритма Шора требуется 4098 кубитов и 5,2 триллиона Toffoli-шлюзов для 2048-битного ключа RSA, что указывает на то, что ECC является более простой целью для квантовых компьютеров, чем RSA. Все эти цифры значительно превышают возможности любых когда-либо созданных квантовых компьютеров, и по оценкам, создание таких компьютеров займет десять и более лет. Supersingular Isogeny Diffie–Hellman Key Exchange заявлял об обеспечении постквантово безопасной формы криптографии на эллиптических кривых, используя изогении для реализации обмена ключами Диффи–Хеллмана. Этот обмен ключами использует ту же арифметику полей, что и существующая криптография на эллиптических кривых, и требует вычислительных и передаточных накладных расходов, сопоставимых с многими современными системами с открытым ключом. Однако новые классические атаки подорвали безопасность этого протокола. В августе 2015 года АНБ объявило о планах перейти "в обозримом будущем" на новый набор шифров, устойчивый к квантовым атакам. "К сожалению, расширение использования эллиптических кривых столкнулось с продолжающимся прогрессом в исследованиях квантовых вычислений, что требует пересмотра нашей криптографической стратегии."

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

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