Обмен ключами суперсингулярной изогении

Суперсингулярный изогенный обмен ключами Диффи-Хеллмана ( SIDH или SIKE ) — это небезопасное предложение постквантового криптографического алгоритма для установления секретного ключа между двумя сторонами по ненадежному каналу связи. Он аналогичен обмену ключами Диффи-Хеллмана , но основан на блужданиях по суперсингулярному графу изогении и был разработан для противодействия криптоаналитической атаке со стороны противника, обладающего квантовым компьютером . До того, как он был взломан, SIDH мог похвастаться одним из самых маленьких размеров ключей среди всех постквантовых обменов ключами; со сжатием SIDH использовал 2688-битный формат. открытые ключи на 128-битном квантовом уровне безопасности . SIDH также отличается от подобных систем, таких как NTRU и Ring-LWE поддерживая идеальную прямую секретность — свойство, которое предотвращает угрозу конфиденциальности старых сеансов связи скомпрометированными долгосрочными ключами. Эти свойства, по-видимому, сделали SIDH естественным кандидатом на замену Диффи-Хеллмана (DHE) и эллиптической кривой Диффи-Хеллмана (ECDHE), которые широко используются в интернет-коммуникациях. Однако SIDH уязвим для разрушительной атаки с восстановлением ключей, опубликованной в июле 2022 года, и поэтому небезопасен. Для атаки не требуется квантовый компьютер.

Введение

Для определенных классов задач алгоритмы, работающие на квантовых компьютерах , естественно, способны достигать более низкой временной сложности, чем на классических компьютерах. То есть квантовые алгоритмы могут решать определенные проблемы быстрее, чем самый эффективный алгоритм, работающий на традиционном компьютере. Например, алгоритм Шора может факторизовать целое число N за полиномиальное время , в то время как самый известный классический алгоритм факторизации, решето общего числового поля , работает за субэкспоненциальное время . Это важно для криптографии с открытым ключом , поскольку безопасность RSA зависит от невозможности факторизации целых чисел, проблемы факторизации целых чисел . Алгоритм Шора также может эффективно решать задачу дискретного логарифмирования , которая является основой безопасности Диффи-Хеллмана , эллиптической кривой Диффи-Хеллмана , эллиптической кривой DSA , Curve25519 , ed25519 и ElGamal . Хотя квантовые компьютеры в настоящее время находятся в зачаточном состоянии, продолжающееся развитие квантовых компьютеров и их теоретическая способность компрометировать современные криптографические протоколы (такие как TLS/SSL ) послужил толчком к развитию постквантовой криптографии.

SIDH был создан в 2011 году Де Фео, Джао и Плутом. Он использует обычные операции с эллиптическими кривыми и не запатентован. SIDH обеспечивает идеальную прямую секретность и, таким образом, не полагается на безопасность долгосрочных закрытых ключей. Прямая секретность повышает долгосрочную безопасность зашифрованных коммуникаций, помогает защититься от массовой слежки и снижает влияние уязвимостей, таких как Heartbleed .

Фон

J -инвариант эллиптической кривой, заданный уравнением Вейерштрасса $y^{2}=x^{3}+ax+b$ определяется формулой:

$j(E)=1728{\frac {4a^{3}}{4a^{3}+27b^{2}}}$.

Изоморфные кривые имеют один и тот же j-инвариант; над алгебраически замкнутым полем две кривые с одним и тем же j-инвариантом изоморфны.

Протокол Диффи-Хеллмана по суперсингулярной изогении (SIDH) работает с графом, вершины которого являются (классами изоморфизма) суперсингулярных эллиптических кривых , а ребра являются изогениями между этими кривыми. Изогения ​ $\phi :E\to E'$ между эллиптическими кривыми $E$ и $E'$ — рациональное отображение , которое также является гомоморфизмом группы. Если раздельный , $\phi$ определяется своим ядром с точностью до изоморфизма целевой кривой $E'$.

Настройка для SIDH представляет собой простое число вида $p=l_{A}^{e_{A}}\cdot l_{B}^{e_{B}}\cdot f\mp 1$, для разных (маленьких) простых чисел $l_{A}$ и $l_{B}$, (большие) показатели $e_{A}$ и $e_{B}$и малый кофактор $f$, вместе с суперсингулярной эллиптической кривой $E$ определено более $\mathbb {F} _{p^{2}}$. Такая кривая имеет две большие крученые подгруппы: $E[l_{A}^{e_{A}}]$ и $E[l_{B}^{e_{B}}]$, которые назначены Алисе и Бобу соответственно, как указано в индексах. Каждая сторона запускает протокол, выбирая (секретную) случайную циклическую подгруппу своей соответствующей торсионной подгруппы и вычисляя соответствующую (секретную) изогению. Затем они публикуют или иным образом предоставляют другой стороне уравнение целевой кривой своей изогении вместе с информацией об образе торсионной подгруппы другой стороны в этой изогении. Это позволяет им обоим в частном порядке рассчитывать новые изогении на основе $E$ ядра которых совместно генерируются двумя секретными циклическими подгруппами. Поскольку ядра этих двух новых изогений совпадают, их целевые кривые изоморфны. Общий j-инвариант этих целевых кривых можно затем принять в качестве требуемого общего секрета.

Поскольку надежность схемы зависит от меньшей подгруппы кручения, рекомендуется выбирать $l_{A}^{e_{A}}\approx l_{B}^{e_{B}}$.

Отличным справочником по этой теме является статья Де Фео «Математика криптографии, основанной на изогении».

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

Самый простой способ атаковать SIDH — решить проблему нахождения изогении между двумя суперсингулярными эллиптическими кривыми с одинаковым количеством точек. На момент первой публикации благодаря Де Фео, Джао и Плуту лучшая известная атака против SIDH была основана на решении связанной с ней проблемы поиска когтей , что привело к сложности O(p ^1/4 ) для классических компьютеров и O(p ^1/6 ) для квантовых компьютеров . Это предполагало, что SIDH с 768-битным простым числом (p) будет иметь 128-битный уровень безопасности. Исследование проблемы изогении, проведенное Делфсом и Гэлбрейтом в 2014 году, подтвердило гипотезу O(p ^1/4 ) анализ безопасности классических компьютеров. Классическая ценная бумага O(p ^1/4 ) остался незатронутым связанными с ним криптоаналитическими работами Биассе, Джао и Санкара, а также Гэлбрейта, Пети, Шани и Яна.

Более сложная стратегия атаки основана на использовании вспомогательных точек эллиптической кривой, присутствующих в открытых ключах SIDH, которые в принципе раскрывают много дополнительной информации о секретных изогениях, но эта информация поначалу не казалась злоумышленникам полезной в вычислительном отношении. Пети в 2017 году впервые продемонстрировал технику, использующую эти точки для атаки на некоторые довольно своеобразные варианты SIDH. Несмотря на последующую работу по распространению атаки на гораздо более реалистичные экземпляры SIDH, стратегия атаки по-прежнему не смогла сломать «стандартный» SIDH, используемый SIKE, представленным NIST PQC .

В июле 2022 года Кастрик и Декрю опубликовали эффективную атаку на SIKE с целью восстановления ключей, использующую вспомогательные точки. При использовании одноядерного компьютера SIKEp434 был взломан примерно за час, SIKEp503 — примерно за 2 часа, SIKEp610 — примерно за 8 часов и SIKEp751 — примерно за 21 час. Атака основана на склеивании нескольких эллиптических кривых, появляющихся в конструкции SIDH, с получением абелевой поверхности (в более общем смысле, абелева многообразия ) и вычислении специально созданной изогении, определяемой заданными вспомогательными точками на этом многомерном объекте.

Следует подчеркнуть, что атака в значительной степени опирается на вспомогательные точки, данные в SIDH, и не существует известного способа применить аналогичные методы к общей проблеме изогении.

Эффективность

Во время обмена ключами каждый из объектов A и B будет передавать информацию о двух коэффициентах по модулю p. ² ), определяющий эллиптическую кривую и 2 точки эллиптической кривой. Для каждого коэффициента эллиптической кривой требуется $\log _{2}p^{2}$ биты. Каждая точка эллиптической кривой может быть передана в $1+\log _{2}p^{2}$ биты; следовательно, передача $4+4\log _{2}p^{2}$ биты. Это 6144 бита для 768-битного модуля p (128-битная безопасность). Однако его можно уменьшить более чем вдвое до 2640 бит (330 байт) с помощью методов сжатия ключей, последняя из которых появилась в недавней работе авторов Костелло, Джао, Лонги, Наэрига, Ренеса и Урбаника. Благодаря этим методам сжатия SIDH предъявляет те же требования к полосе пропускания, что и традиционные 3072-битные подписи RSA или обмен ключами Диффи-Хеллмана. Это небольшое требование к пространству делает SIDH применимым к контекстам со строгими требованиями к пространству, таким как Биткойн или Tor . Ячейки данных Tor должны иметь длину менее 517 байт, чтобы они могли содержать 330-байтовые ключи SIDH. Напротив, NTRUEncrypt должен обмениваться примерно 600 байтами для достижения 128-битной безопасности и не может использоваться в Tor без увеличения размера ячейки.

В 2014 году исследователи из Университета Ватерлоо разработали программную реализацию SIDH. Они запустили свой частично оптимизированный код на процессоре x86-64, работающем на частоте 2,4 ГГц. Для 768-битного модуля они смогли завершить вычисления обмена ключами за 200 миллисекунд, продемонстрировав тем самым, что SIDH практичен в вычислительном отношении.

В 2016 году исследователи из Microsoft опубликовали программное обеспечение для SIDH, которое работает в постоянном времени (таким образом защищая от атак по времени) и является наиболее эффективной реализацией на сегодняшний день. Они пишут: «Размер открытых ключей составляет всего 564 байта, что значительно меньше, чем у большинства популярных альтернатив постквантового обмена ключами. кандидат на обмен ключами, и мы надеемся, что эти результаты будут стимулировать более широкие усилия по криптоанализу». Код имеет открытый исходный код (MIT) и доступен на GitHub: https://github.com/microsoft/PQCrypto-SIDH .

В 2016 году исследователи из Атлантического университета Флориды разработали эффективные реализации SIDH для ARM и провели сравнение аффинных и проективных координат. В 2017 году исследователи из Атлантического университета Флориды разработали первые реализации SIDH на FPGA.

Суперсингулярный метод изогении Диффи-Хеллмана

Хотя несколько этапов SIDH включают сложные вычисления изогении, общий поток SIDH для сторон A и B прост для тех, кто знаком с обменом ключами Диффи-Хеллмана или его вариантом эллиптической кривой.

Настраивать

Это общедоступные параметры, которые могут быть общими для всех в сети или могут быть согласованы сторонами A и B в начале сеанса.

1. Простое число формы $p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\pm 1.$
2. Суперсингулярная эллиптическая кривая $E$ над $\mathbb {F} _{p^{2}}$.
3. Фиксированные эллиптические точки $P_{A},Q_{A},P_{B},Q_{B}$ на $E$.
4. Порядок $P_{A}$ и $Q_{A}$ является $(w_{A})^{e_{A}}$. Порядок $P_{B}$ и $Q_{B}$ является $(w_{B})^{e_{B}}$.

Обмен ключами

При обмене ключами каждая из сторон A и B создаст изогению из общей эллиптической кривой E. Каждая из них сделает это, создав случайную точку в том, что будет ядром их изогении. Ядро их изогении будет охватывать $R_{A}$ и $R_{B}$ соответственно. Использование разных пар точек гарантирует, что стороны A и B создают разные некоммутирующие изогении. Случайная точка ( $R_{A}$, или $R_{B}$) в ядре изогений создается как случайная линейная комбинация точек $P_{A}$, $Q_{A}$ и $P_{B}$, $Q_{B}$.

С использованием $R_{A}$, или $R_{B}$Затем стороны A и B используют формулы Велу для создания изогений. $\phi _{A}$ и $\phi _{B}$ соответственно. Отсюда они вычисляют изображение пар точек $P_{A}$, $Q_{A}$ или $P_{B}$, $Q_{B}$ под $\phi _{B}$ и $\phi _{A}$ изогении соответственно.

В результате у A и B теперь будет две пары точек. $\phi _{B}(P_{A})$, $\phi _{B}(Q_{A})$ и $\phi _{A}(P_{B})$, $\phi _{A}(Q_{B})$ соответственно. Теперь A и B обмениваются этими парами точек по каналу связи.

Теперь A и B используют полученную пару точек в качестве основы для ядра новой изогении. Они используют те же линейные коэффициенты, которые они использовали выше, с полученными точками, чтобы сформировать точку в ядре изогении, которую они создадут. Каждый из них подсчитывает баллы $S_{BA}$ и $S_{AB}$ и использовать формулы Велу для построения новых изогений.

Чтобы завершить обмен ключами, A и B вычисляют коэффициенты двух новых эллиптических кривых при этих двух новых изогениях. Затем они вычисляют j-инвариант этих кривых. Если при передаче не было ошибок, j-инвариант кривой, созданной A, будет равен j-инварианту кривой, созданной B.

Условно обмен ключами SIDH между сторонами A и B работает следующим образом:

1А. A генерирует два случайных целых числа $m_{A},n_{A}<(w_{A})^{e_{A}}.$

2А. генерирует $R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A}).$

3А. А использует точку $R_{A}$ создать карту изогении $\phi _{A}:E\rightarrow E_{A}$ и кривая $E_{A}$ изогенный для $E.$

4А. А применяется $\phi _{A}$ к $P_{B}$ и $Q_{B}$ образовать две точки на $E_{A}:\phi _{A}(P_{B})$ и $\phi _{A}(Q_{B}).$

5А. А отправляет Б $E_{A},\phi _{A}(P_{B})$, и $\phi _{A}(Q_{B}).$

1B–4B: То же, что и от A1 до A4, но с заменой индексов A и B.

5Б. Б отправляет А $E_{B},\phi _{B}(P_{A})$, и $\phi _{B}(Q_{A}).$

6А. А имеет $m_{A},n_{A},\phi _{B}(P_{A})$, и $\phi _{B}(Q_{A})$ и формы $S_{BA}:=m_{A}(\phi _{B}(P_{A}))+n_{A}(\phi _{B}(Q_{A})).$

7А. А использует $S_{BA}$ создать карту изогении $\psi _{BA}$.

8А. А использует $\psi _{BA}$ создать эллиптическую кривую $E_{BA}$ который изогенен $E$.

9А. Вычисляет $K:={\text{ j-invariant }}(j_{BA})$ кривой $E_{BA}$.

6Б. Аналогично, B имеет $m_{B},n_{B},\phi _{A}(P_{B})$, и $\phi _{A}(Q_{B})$ и формы $S_{AB}=m_{B}(\phi _{A}(P_{B}))+n_{B}(\phi _{A}(Q_{B}))$.

7Б. Б использует $S_{AB}$ создать карту изогении $\psi _{AB}$.

8Б. Б использует $\psi _{AB}$ создать эллиптическую кривую $E_{AB}$ который изогенен $E$.

9Б. Б вычисляет $K:={\text{ j-invariant }}(j_{AB})$ кривой $E_{AB}$.

Кривые $E_{AB}$ и $E_{BA}$ гарантированно имеют один и тот же j-инвариант. Функция $K$ используется в качестве общего ключа.

Примеры параметров

Следующие параметры были взяты в качестве примера Де Фео и др.:

p = простое число для обмена ключами с w _A = 2, w _B = 3, e _A = 63, e _B = 41 и f = 11. Таким образом, p = (2 ⁶³ ·3 ⁴¹ ·11) - 1.

E ₀ = базовая (начальная) кривая обмена ключами = y ² = х ³ + х

Лука Де Фео, один из авторов статьи, определяющей обмен ключами, опубликовал программное обеспечение, которое реализует обмен ключами для этих и других параметров.

Похожие системы, подписи и использование

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

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