Русская Википедия:Протокол обмена ключами с использованием суперсингулярных изогений

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Протокол обмена ключами с использованием суперсингулярных изогений (Шаблон:Lang-en) — взломанныйШаблон:Переход постквантовый криптографический алгоритм, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Он основан на протоколе Диффи-Хеллмана с использованием суперсингулярной изогении (Шаблон:Lang-en Supersingular isogeny Diffie-Hellman key exchange, SIDH) — аналоге протокола Диффи-Хеллмана, основанном на блуждании в суперсингулярном изогенном графе. Он был предназначен противостоять криптоаналитической атаке противника, владеющего квантовым компьютером. Из всех постквантовых протоколов обмена ключами SIDH имеет наименьшую длину ключа; с учетом сжатия, SIDH использует 2688-битный[1] публичный ключ на 128-битном квантовом криптографическом уровне. Также SIDH отличается от других похожих систем, таких как NTRU и Ring-LWE тем, что поддерживает совершенную прямую секретность, которая гарантирует, что сессионные ключи, полученные при помощи набора ключей долговременного пользования, не будут скомпрометированы при компрометации одного из долговременных ключей. Эти свойства SIDH сделали его одним из кандидатов на замену Диффи-Хеллмана (DHE) и Диффи-Хеллмана на эллиптических кривых (ECDHE), которые используются при защите данных, передаваемых через сеть. Однако после взлома обнаруженных в SIDH уязвимостей эта криптосистема не рекомендуется к применению.

Введение

Для некоторых классов задач алгоритмы, выполняющиеся на квантовом компьютере, способны достичь меньшей временной сложности, чем при выполнении на классическом компьютере. Использование квантовых алгоритмов существенно влияет на открытую криптографию. Например, алгоритм Шора может разложить целое число N за полиномиальное время, в то время как наиболее эффективный факторизующий классический алгоритм, общий метод решета числового поля, работает за субэкспоненциальное время. При этом под угрозу попадает защищенность RSA, основывающаяся на сложности задачи факторизации целых чисел. Алгоритм Шора может так же эффективно решить задачу дискретного логарифмирования, от сложности которой зависит защищенность Диффи-Хеллмана, Диффи-Хеллмана на эллиптических кривых, ECDSA, Curve25519, ed25519 и Эль-Гамаля. Таким образом, как задача факторизации целых чисел, так и задача дискретного логарифмирования будут легко разрешимы на достаточно больших квантовых компьютерах. В настоящее время ведется разработка постквантовой криптографии, которая использует алгоритмы, независимые от квантовых вычислений, то есть устойчивые к квантовым атакам.[2]

SIDH был создан De Feo, Jao и Plut в 2011 году[3]. Он использует стандартные операции на эллиптических кривых и не запатентован. SIDH предоставляет совершенную прямую секретность и не полагается на защищенность закрытых ключей долговременного пользования. Прямая секретность улучшает долговременную защищенность шифрованных соединений, помогает защититься от mass surveillance и уменьшает влияние таких уязвимостей, как Heartbleed.[4][5]

Описание алгоритма

j-инвариант эллиптической кривой, заданной уравнением <math>y^2 = x^3 + ax + b</math>, имеет вид:

<math>j(E) = 1728\frac{4a^3}{4a^3 + 27b^2} </math>

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

SIDH использует множество суперсингулярных эллиптических кривых и их изогений. Для изоморфных кривых стоит рассматривать изогении между различными классами изоморфных кривых. Изогения <math>\phi\colon E \to E'</math> между эллиптическими кривыми, <math>E</math> и <math>E'</math> — это рациональное отображение, являющееся гомоморфизмом. Если <math>\phi</math> сепарабельно, то оно определено своим ядром с точностью до изоморфизма кривой <math>E'</math>.

Для работы SIDH необходима характеристика поля — простое число типа <math>p = l_A^{e_A} \cdot l_B^{e_B} \cdot f \mp 1</math>, c небольшими простыми числами <math>l_A</math> и <math>l_B^{e_B}</math>, большими степенями <math>e_A</math> и <math>e_B</math> и небольшим сомножителем <math>f</math>; а также суперсингулярная кривая <math>E</math>, заданная над <math>\mathbb{F}_{p^2}</math>. Такая кривая имеет две большие подгруппы кручения, <math>E[l_A^{e_A}]</math> и <math>E[l_B^{e_B}]</math>, которые предназначены Алисе и Бобу, соответственно. Каждая сторона начинает протокол тем, что выбирает (секретную) случайную циклическую подгруппу из соответствующей подгруппы кручения и вычисляет соответственную (секретную) изогению. Затем они обмениваются уравнениями преобразованных кривых, которые являются результатами действия их изогений на кривую <math>E</math>, а также значениями их изогений, посчитанных по группе кручения другой стороны. Это позволяет обеим сторонам секретно вычислить новые изогении из <math>E</math>, чьи ядра совместно сгенерированы с использованием двух секретных циклических подгрупп. Так как ядра этих изогений согласованы, их новые преобразованные кривые изоморфны. В этом случае совместный j-инвариант преобразованных кривых может быть использован как необходимый общий секрет.

Более подробную информацию по этой теме можно найти в статье De Feo «Mathematics of Isogeny Based Cryptography.»[6]

Криптографическая стойкость

Множество изогений суперсингулярных эллиптических кривых вместе с композицией образуют неабелеву группу и защищенность SIDH основывается на этой неабелевой структуре.[3] Защищенность SIDH тесно связана с задачей нахождения изогенных отображений между двумя суперсингулярными эллиптическими кривыми, имеющих одинаковое число точек. De Feo, Jao и Plut предположили, что защищенность SIDH будет <math>O(p^{\frac{1}{4}})</math> для классического компьютера и <math>O(p^{\frac{1}{6}})</math> для квантового. Получается, что SIDH с 768-битным простым числом будет иметь криптостойкость на уровне 128 бит.[3] В 2014 году при изучении проблемы изогенных отображений Delfs и Galbraith подтвердили <math>O(p^{\frac{1}{4}})</math> защищенность для классического компьютера.[7] Уровень стойкости <math>O(p^{\frac{1}{4}})</math> был также подтвержден в работе Biasse, Jao и Sankar, и в работе Galbraith, Petit, Shani и Bo Ti.[8][9]

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

В процессе обмена ключами, каждой из сторон А и В будут переданы <math>2 (\text{mod} p^2)</math> коэффициентов, задающих эллиптическую кривую, и 2 точки эллиптической кривой. Для каждого коэффициента эллиптической кривой требуется <math>\log_2 p^2</math> бит. Каждая точка эллиптической кривой может быть передана за <math>\log_2 p^2 + 1</math> бит. Всего передается <math>8\log_2 p + 2</math> бит. Получается 6144 бит для 768-битной длины характеристики поля <math>p</math> (128-битная криптографическая стойкость). Однако это число может быть уменьшено до 2640 бит (330 байт) с использованием техники сжатия ключей, последнюю версию которой можно найти в работе авторов Costello, Jao, Longa, Naehrig, Renes и Urbanik.[10] С учетом сжимающей техники SIDH имеет требования к ширине канала, близкие традиционной 3072-битной RSA сертификации или обмену ключей Диффи-Хеллмана. Благодаря малым требованиям к длине ключа, SIDH может быть использован в контексте ограниченного доступного места, например в Bitcoin и Tor. Размер ячейки данных в Tor должен быть меньше, чем 517 байт и SIDH с длиной ключей в 330 байт туда помещается, в то время как NTRUEncrypt должен обменяться примерно 600 байтами, чтобы достичь 128-битного уровня защищенности и не может быть использован в Tor без увеличения размера ячейки данных.[11]

В 2014 году исследователи из университета Уотерлу разработали программную реализацию SIDH. Она была запущена на процессоре x86-64 с частотой 2.4 GHz. Для длины характеристики в 768 бит они смогли выполнить обмен ключами за 200 миллисекунд, показывая практичность вычисления SIDH.[12]

В 2016 году исследователи из Microsoft опубликовали программное обеспечение для SIDH, которое работает за константное время (тем самым устойчиво к атакам по времени) и является наиболее эффективной реализацией на сегодняшний день.[13] Их реализацию можно найти по ссылке.

В 2016 году исследователи из Флоридского Атлантического университета разработали эффективную реализацию SIDH под ARM архитектуру и сделали сравнение для аффинных и проективных координат.[14][15] В 2017 году в этом же университете была разработана первая ПЛИС реализация SIDH.[16]

Протокол Диффи-Хеллмана с использованием суперсингулярной изогении

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

Доменные параметры

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

  1. Характеристика поля — простое число вида <math>p = w_A^{e_A}\cdot w_B^{e_B}\cdot f \pm 1. </math>
  2. Суперсингулярная эллиптическая кривая <math>E</math> над <math> \mathbb{F}_{p^2}</math>.
  3. Фиксированные точки <math>P_A, Q_A, P_B, Q_B</math> на эллиптической кривой <math>E</math>.
  4. Точки <math>P_A</math> и <math>Q_A</math> имеют порядок <math> (w_A)^{e_A}</math>, а <math>P_B</math> и <math>Q_B</math> порядок <math>(w_B)^{e_B}</math>.

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

При обмене ключами каждая из сторон А и В должна сгенерировать изогению из общей эллиптической кривой <math>E</math>. Это делается с помощью генерации случайной точки, в которой будет ядро их изогении. Базисными векторами для этого ядра будут пары точек <math>P_A</math>, <math>Q_A</math> и <math>P_B</math>, <math>Q_B</math> соответственно. Использование разных пар точек гарантирует, что стороны сгенерировали разные, некоммутирующие изогении. Случайная точка (<math>R_A</math>, или <math>R_B</math>) в ядре изогений генерируется как случайная линейная комбинация точек <math>P_A</math>, <math>Q_A</math> и точек <math>P_B</math>, <math>Q_B</math>.

Используя <math>R_A</math>, или <math>R_B</math>, стороны A и B применяют формулу Велю для получения изогений <math>\phi_A</math> и <math>\phi_B</math> соответственно. После этого они вычисляют образы пар точек <math>P_A</math>, <math>Q_A</math> или <math>P_B</math>, <math>Q_B</math> при действии изогений <math>\phi_A</math> и <math>\phi_B</math> соответственно.

В результате, у A и B есть две пары точек <math>\phi_B(P_A)</math>, <math>\phi_B(Q_A)</math> и <math>\phi_A(P_B)</math>, <math>\phi_A(Q_B)</math> соответственно. Теперь A и B обмениваются посчитанными парами точек через канал связи.

А и В используют пары точек, полученные от другой стороны в качестве базиса для ядра их новой изогении. Взяв те же линейные коэффициенты, которые использовались ранее для генерации случайной точки (<math>R_A</math>, или <math>R_B</math>), каждый из них генерируют точку в ядре изогении, которую они хотят построить. Каждая из сторон вычисляет точки <math>S_{BA}</math> и <math>S_{AB}</math> и использует формулу Велю для построения новых изогений.

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

Обмен ключей между сторонами А и В, используя SIDH, можно записать в следующем виде:

1A. A генерирует два случайных целых числа <math>m_A, n_A < (w_A)^{e_A}.</math>

2A. A генерирует <math>R_A  := m_A \cdot (P_A)+ n_A\cdot (Q_A).</math>

3A. A использует точку <math>R_A</math> для построения изогении <math>\phi_A: E\rightarrow E_A</math> и кривой <math>E_A</math>, изогенной <math>E.</math>

4A. A применяет <math>\phi_A</math> к <math>P_B</math> и <math>Q_B</math> для получения двух точек на <math>E_A: \phi_A(P_B) </math> и <math>\phi_A(Q_B). </math>

5A. A передает B <math> E_A, \phi_A(P_B)</math> и <math>\phi_A(Q_B). </math>

1B — 4B: Аналогично A1 — A4, заменив А на В (и наоборот).

5B. B передает A <math>E_B,\phi_B(P_A)</math> и <math>\phi_B(Q_A).</math>

6A. У A есть <math>m_A, n_A, \phi_B(P_A)</math> и <math>\phi_B(Q_A)</math>. А находит <math>S_{BA} := m_A(\phi_B(P_A)) + n_A(\phi_B(Q_A)).</math>

7A. A использует <math>S_{BA}</math> для построения изогении <math>\psi_{BA}</math>.

8A. A использует <math>\psi_{BA}</math> для построения эллиптической кривой <math>E_{BA}</math>, которая изогенна <math>E</math>.

9A. A вычисляет <math> K := \text{ j-invariant } (j_{BA})</math> кривой <math>E_{BA}</math>.

6B. Аналогично, у B есть <math>m_B, n_B, \phi_A(P_B)</math> и <math>\phi_A(Q_B)</math>. В находит <math>S_{AB} = m_B (\phi_A(P_B)) + n_B(\phi_A(Q_B))</math>.

7B. B использует <math>S_{AB}</math> для построения изогении <math>\psi_{AB}</math>.

8B. B использует <math>\psi_{AB}</math> для построения эллиптической кривой <math>E_{AB}</math>, которая изогенна <math>E</math>.

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

Кривые <math>E_{AB}</math> и <math>E_{BA}</math> обязаны иметь одинаковый j-инвариант. Функция от <math>K</math> используется как общий ключ.[3]

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

Следующие параметры были использованы De Feo et al.:[3]

p = характеристика поля(простое число) для обмена ключами с wA = 2, wB = 3, eA = 63, eB = 41, и f = 11. Получается p = (263·341·11) — 1.

E0 = основная (начальная) кривая для обмена ключами = y2 = x3 + x

Luca De Feo, один из авторов статьи описывающей обмен ключей, опубликовал программную реализацию обмена ключей для этих и других параметров.[17]

Похожие системы

Предшественником SIDH был метод, опубликованный в 2006 году Ростовцевым и Столбуновым. Они создали первый аналог Диффи-Хеллмана, использующий изогении эллиптических кривых. В отличие от метода De Feo, Jao, и Plut, метод Ростовцева и Столбунова использовал обычные эллиптические кривые[18] и был подвержен субэкспоненциальным квантовым атакам.[19]

В марте 2014 года, исследователи из Chinese State Key Lab for Integrated Service Networks и Xidian University расширили защищенность SIDH до формы цифровой подписи со строго заданными верификаторами.[20] В октябре 2014 года, исследователи Jao и Soukharev из университета Уотерлу представили альтернативным способ получения явных подписей с заданными верификаторами, используя эллиптические кривые.[21]

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

Активная атака

Активные атаки — это стандартный тип атак на криптосистемы со статическим закрытым ключом. Если у А есть фиксированный закрытый ключ <math>(m_A, n_A)</math>, то злоумышленник В может отправить <math>(E, P_B, Q_B)</math> и А вычислит изогению <math>\phi : E\rightarrow E'</math> с ядром <math>\langle m_AP + n_AQ\rangle</math>. Злоумышленник может попытаться вычислить закрытый ключ <math>(m_A, n_A)</math>, зная <math>E'</math>. Для предотвращения данного типа атак необходимо проверять корректность <math>(E, P_B, Q_B)</math>:[13]

  1. <math>E</math> является суперсингулярной эллиптической кривой,
  2. <math>P_B</math> и <math>Q_B</math> лежат на этой кривой, имеют правильный порядок и независимы.

Для проверки корректности <math>(E, P_B, Q_B)</math> можно использовать условие сопряжения Вейля (Weil pairing)

<math>e_{2^n}(\phi_B (P_A),\phi_B (Q_A)) = e_{2^n}(P_A , Q_A)^{3^m}.</math>

Однако, данная проверка не сможет защитить от всех адаптивных атак.[9]

Адаптивная атака

Galbraith, Petit, Shani и Ti показали, что для статических закрытых ключей существует адаптивная атака, которая требует менее log 2 (p) обращений к А, которая будет проходить проверку сопряжением Вейля и проверку на степень изогении. При этой атаке злоумышленник B итерационно находит биты секретного ключа А, подбирая передаваемые параметры и смотря ответ А. Однако метод верификации, предложенный Kirkwood, может распознать данную атаку.[9]

Метод проверки Kirkwood

Метод проверки, предложенный Kirkwood и др.[22], использует преобразование Fujisaki-Okamoto[23]. Идея этого метода заключается в том, что стороны обмениваются ключами, а потом обмениваются зашифрованными случайными числами, которые использовались для генерации ключа для подтверждения корректности обмена ключами. Протокол можно записать в следующем виде:

1. В получает статический ключ А <math>(E_A, \phi_A(P_B), \phi_A(Q_B))</math>.

2. B выбирает случайное число <math> r_B</math> и получает закрытый ключ, используя псевдослучайную функцию G:

<math>(b_1, b_2) = \text{G}(r_B)</math>.

Затем В вычисляет сообщение <math>(E_B, \phi_B(P_A), \phi_B(Q_A))</math>, где <math>\phi_B</math> имеет ядро <math>\langle[b_1]P_B + [b_2]Q_B\rangle</math>.

3. В получает общий секрет <math>E_{AB}</math> из <math>(E_A, \phi_A(P_B), \phi_A(Q_B))</math> и <math>(b_1, b_2)</math> и вычисляет сессионный <math>(SK)</math> и проверочный <math>(VK)</math> ключи, используя функцию K:

<math>SK | VK = \text{K}(j(E_{AB}))</math>.

4. B передает A <math>(E_B, \phi_B(P_A), \phi_B(Q_A))</math> и <math> c_B = \text{ENC}_{VK}(r_B\oplus SK)</math>.

5. Из <math>(a_1, a_2)</math> и <math>(E_B, \phi_B(P_A), \phi_B(Q_A))</math> А получает <math>E'_{AB}</math>, а затем <math>(SK')</math> и <math>(VK')</math>.

6. A вычисляет

<math>r'_B = \text{Dec}_{VK'}(c_B)\oplus SK'.</math>

Для гипотетического числа <math>r'_B</math> А может повторно выполнить все операции В. Если получившееся сообщение совпадает с <math>(E_B, \phi_B(P_A), \phi_B(Q_A))</math>, которое изначально отправил В, то А завершает протокол и использует <math>SK=SK'</math> для дальнейшей коммуникации с В. Если сообщения различаются, протокол прерывается с ошибкой, без дальнейшей коммуникации.

При использовании данного протокола В открывает свой секретный ключ А, поэтому ему приходится менять его после каждой проверки. Это проверочный метод может применим как к протоколам обмена ключей, так и шифрующим протоколам.[9]

Атака внесением изменений

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

Прерывающая цикл атака

Данная атака использует итерационную структуру вычисления изогении. Можно внести изменение, которое заставит А вычислить изогению только частично, раскрывая информацию о секретном ключе <math>(a_1, a_2)</math>. Данная атака не может быть найдена проверкой Kirkwood, так как злоумышленник использует правильные данные. Закрытый ключ А раскрывается побитово, используется статус завершения протокола при успешном прерывании вычисления кривой стороной А. Сложность данной атаки примерно <math>\log_2p/\mu</math>, где <math>\mu</math> — вероятность удачного прерывания вычислений.[24]

Атака Кастрика и Декру

В 2022 году была опубликована работа Кастрика и Декру с чрезвычайно эффективной атакой, даже не требующей квантового компьютера. Последующие исследования показали, что их подход применим ко всем криптоалгоритмам на основе протокола Диффи—Хеллмана с использованием суперсингулярных изогений. В результате SIKE и SIDH консенсусно считаются небезопасными и не рекомендуются к применению[25].

Примечания

Шаблон:Примечания