Протокол обмена ключами с использованием суперсингулярных изогений () — взломанный постквантовый криптографический алгоритм, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищённый от прослушивания канал связи. Он основан на протоколе Диффи-Хеллмана с использованием суперсингулярной изогении ( Supersingular isogeny Diffie-Hellman key exchange, SIDH) — аналоге протокола Диффи-Хеллмана, основанном на блуждании в суперсингулярном изогенном графе. Он был предназначен противостоять криптоаналитической атаке противника, владеющего квантовым компьютером. Из всех постквантовых протоколов обмена ключами SIDH имеет наименьшую длину ключа; с учетом сжатия, SIDH использует 2688-битный публичный ключ на 128-битном квантовом криптографическом уровне. Также SIDH отличается от других похожих систем, таких как NTRU и Ring-LWE тем, что поддерживает совершенную прямую секретность, которая гарантирует, что сессионные ключи, полученные при помощи набора ключей долговременного пользования, не будут скомпрометированы при компрометации одного из долговременных ключей. Эти свойства SIDH сделали его одним из кандидатов на замену Диффи-Хеллмана (DHE) и Диффи-Хеллмана на эллиптических кривых (ECDHE), которые используются при защите данных, передаваемых через сеть. Однако после взлома обнаруженных в SIDH уязвимостей эта криптосистема не рекомендуется к применению.
Введение Для некоторых классов задач алгоритмы, выполняющиеся на квантовом компьютере, способны достичь меньшей временной сложности, чем при выполнении на классическом компьютере. Использование квантовых алгоритмов существенно влияет на открытую криптографию. Например, алгоритм Шора может разложить целое число N за полиномиальное время, в то время как наиболее эффективный факторизующий классический алгоритм, общий метод решета числового поля, работает за субэкспоненциальное время. При этом под угрозу попадает защищенность RSA, основывающаяся на сложности задачи факторизации целых чисел. Алгоритм Шора может так же эффективно решить задачу дискретного логарифмирования, от сложности которой зависит защищенность Диффи-Хеллмана, Диффи-Хеллмана на эллиптических кривых, ECDSA, Curve25519, ed25519 и Эль-Гамаля. Таким образом, как задача факторизации целых чисел, так и задача дискретного логарифмирования будут легко разрешимы на достаточно больших квантовых компьютерах. В настоящее время ведется разработка постквантовой криптографии, которая использует алгоритмы, независимые от квантовых вычислений, то есть устойчивые к квантовым атакам.
SIDH был создан De Feo, Jao и Plut в 2011 году. Он использует стандартные операции на эллиптических кривых и не запатентован. SIDH предоставляет совершенную прямую секретность и не полагается на защищенность закрытых ключей долговременного пользования. Прямая секретность улучшает долговременную защищенность шифрованных соединений, помогает защититься от mass surveillance и уменьшает влияние таких уязвимостей, как Heartbleed.
Описание алгоритма j-инвариант эллиптической кривой, заданной уравнением , имеет вид:
Изоморфные кривые имеют одинаковый j-инвариант; над алгебраически замкнутым полем две кривые с одинаковым j-инвариантом изоморфны.
SIDH использует множество суперсингулярных эллиптических кривых и их изогений. Для изоморфных кривых стоит рассматривать изогении между различными классами изоморфных кривых. Изогения между эллиптическими кривыми, и — это рациональное отображение, являющееся гомоморфизмом. Если сепарабельно, то оно определено своим ядром с точностью до изоморфизма кривой .
Для работы SIDH необходима характеристика поля — простое число типа , c небольшими простыми числами и , большими степенями и и небольшим сомножителем ; а также суперсингулярная кривая , заданная над . Такая кривая имеет две большие подгруппы кручения, и , которые предназначены Алисе и Бобу, соответственно. Каждая сторона начинает протокол тем, что выбирает (секретную) случайную циклическую подгруппу из соответствующей подгруппы кручения и вычисляет соответственную (секретную) изогению. Затем они обмениваются уравнениями преобразованных кривых, которые являются результатами действия их изогений на кривую , а также значениями их изогений, посчитанных по группе кручения другой стороны. Это позволяет обеим сторонам секретно вычислить новые изогении из , чьи ядра совместно сгенерированы с использованием двух секретных циклических подгрупп. Так как ядра этих изогений согласованы, их новые преобразованные кривые изоморфны. В этом случае совместный j-инвариант преобразованных кривых может быть использован как необходимый общий секрет.
Более подробную информацию по этой теме можно найти в статье De Feo «Mathematics of Isogeny Based Cryptography.»
Криптографическая стойкость Множество изогений суперсингулярных эллиптических кривых вместе с композицией образуют неабелеву группу и защищенность SIDH основывается на этой неабелевой структуре. Защищенность SIDH тесно связана с задачей нахождения изогенных отображений между двумя суперсингулярными эллиптическими кривыми, имеющих одинаковое число точек. De Feo, Jao и Plut предположили, что защищенность SIDH будет для классического компьютера и для квантового. Получается, что SIDH с 768-битным простым числом будет иметь криптостойкость на уровне 128 бит. В 2014 году при изучении проблемы изогенных отображений Delfs и Galbraith подтвердили защищенность для классического компьютера. Уровень стойкости был также подтвержден в работе Biasse, Jao и Sankar, и в работе Galbraith, Petit, Shani и Bo Ti.
Эффективность В процессе обмена ключами, каждой из сторон А и В будут переданы коэффициентов, задающих эллиптическую кривую, и 2 точки эллиптической кривой. Для каждого коэффициента эллиптической кривой требуется бит. Каждая точка эллиптической кривой может быть передана за бит. Всего передается бит. Получается 6144 бит для 768-битной длины характеристики поля (128-битная криптографическая стойкость). Однако это число может быть уменьшено до 2640 бит (330 байт) с использованием техники сжатия ключей, последнюю версию которой можно найти в работе авторов Costello, Jao, Longa, Naehrig, Renes и Urbanik. С учетом сжимающей техники SIDH имеет требования к ширине канала, близкие традиционной 3072-битной RSA сертификации или обмену ключей Диффи-Хеллмана. Благодаря малым требованиям к длине ключа, SIDH может быть использован в контексте ограниченного доступного места, например в Bitcoin и Tor. Размер ячейки данных в Tor должен быть меньше, чем 517 байт и SIDH с длиной ключей в 330 байт туда помещается, в то время как NTRUEncrypt должен обменяться примерно 600 байтами, чтобы достичь 128-битного уровня защищенности и не может быть использован в Tor без увеличения размера ячейки данных.
В 2014 году исследователи из университета Уотерлу разработали программную реализацию SIDH. Она была запущена на процессоре x86-64 с частотой 2.4 GHz. Для длины характеристики в 768 бит они смогли выполнить обмен ключами за 200 миллисекунд, показывая практичность вычисления SIDH.
В 2016 году исследователи из Microsoft опубликовали программное обеспечение для SIDH, которое работает за константное время (тем самым устойчиво к атакам по времени) и является наиболее эффективной реализацией на сегодняшний день. Их реализацию можно найти по ссылке.
В 2016 году исследователи из Флоридского Атлантического университета разработали эффективную реализацию SIDH под ARM архитектуру и сделали сравнение для аффинных и проективных координат. В 2017 году в этом же университете была разработана первая ПЛИС реализация SIDH.
Протокол Диффи-Хеллмана с использованием суперсингулярной изогении В то время как некоторые шаги SIDH используют сложные вычисления изогений, общее понимание SIDH для сторон А и В довольно просто для тех, кто знаком с протоколом Диффи-Хеллмана или его вариантом на эллиптических кривых.
Доменные параметры Используются следующие доменные параметры, которые могут быть доступны каждому в сообществе или же стороны могут их предоставить в начале сессии.
Характеристика поля — простое число вида Суперсингулярная эллиптическая кривая над . Фиксированные точки на эллиптической кривой . Точки и имеют порядок , а и порядок .
Обмен ключами При обмене ключами каждая из сторон А и В должна сгенерировать изогению из общей эллиптической кривой . Это делается с помощью генерации случайной точки, в которой будет ядро их изогении. Базисными векторами для этого ядра будут пары точек , и , соответственно. Использование разных пар точек гарантирует, что стороны сгенерировали разные, некоммутирующие изогении. Случайная точка (, или ) в ядре изогений генерируется как случайная линейная комбинация точек , и точек , .
Используя , или , стороны A и B применяют формулу Велю для получения изогений и соответственно. После этого они вычисляют образы пар точек , или , при действии изогений и соответственно.
В результате, у A и B есть две пары точек , и , соответственно. Теперь A и B обмениваются посчитанными парами точек через канал связи.
А и В используют пары точек, полученные от другой стороны в качестве базиса для ядра их новой изогении. Взяв те же линейные коэффициенты, которые использовались ранее для генерации случайной точки (, или ), каждый из них генерируют точку в ядре изогении, которую они хотят построить. Каждая из сторон вычисляет точки и и использует формулу Велю для построения новых изогений.
Чтобы завершить обмен ключей, A и B вычисляют коэффициенты двух новых эллиптических кривых с учетом двух новых изогений и вычисляют их j-инвариант. Если при передаче не возникло ошибок, j-инвариант кривой, построенной А должен равняться j-инварианту кривой, построенной В.
Обмен ключей между сторонами А и В, используя SIDH, можно записать в следующем виде:
1A. A генерирует два случайных целых числа
2A. A генерирует
3A. A использует точку для построения изогении и кривой , изогенной
4A. A применяет к и для получения двух точек на и
5A. A передает B и
1B — 4B: Аналогично A1 — A4, заменив А на В (и наоборот).
5B. B передает A и
6A. У A есть и . А находит
7A. A использует для построения изогении .
8A. A использует для построения эллиптической кривой , которая изогенна .
9A. A вычисляет кривой .
6B. Аналогично, у B есть и . В находит .
7B. B использует для построения изогении .
8B. B использует для построения эллиптической кривой , которая изогенна .
9B. B вычисляет кривой .
Кривые и обязаны иметь одинаковый j-инвариант. Функция от используется как общий ключ.
Пример параметров Следующие параметры были использованы De Feo et al.:
p = характеристика поля(простое число) для обмена ключами с wA = 2, wB = 3, eA = 63, eB = 41, и f = 11. Получается p = (263·341·11) — 1.
E0 = основная (начальная) кривая для обмена ключами = y2 = x3 + x
Luca De Feo, один из авторов статьи описывающей обмен ключей, опубликовал программную реализацию обмена ключей для этих и других параметров.
История и аналоги Фактически SIDH является развитием метода, предложенного 2006 году Ростовцевым и Столбуновым. Этот метод использовал обычные эллиптические кривые, что делало его нестойким к квантовым атакам (на квантовом компьютере он взламывался за субэкспоненциальное время). Авторы SIDH - De Feo, Jao, и Plut развили метод Ростовцева-Столбунова, предложив использовать суперсингулярные эллиптические кривые
В марте 2014 года, исследователи из Chinese State Key Lab for Integrated Service Networks и Xidian University расширили защищенность SIDH до формы цифровой подписи со строго заданными верификаторами. В октябре 2014 года, исследователи Jao и Soukharev из университета Уотерлу представили альтернативным способ получения явных подписей с заданными верификаторами, используя эллиптические кривые.
В 2021 году С.В. Гребнев, П.Г. Ключарёв и др. предложили протокол Форзиция, основанный на SIDH.
Криптографические атаки
Активная атака