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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Введение[править | править код]

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

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

Описание алгоритма[править | править код]

j-инвариант эллиптической кривой, заданной уравнением , имеет вид:

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

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

Для работы SIDH необходима характеристика поля — простое число типа , c небольшими простыми числами и , большими степенями и и небольшим сомножителем ; а также суперсингулярная кривая , заданная над . Такая кривая имеет две большие подгруппы кручения, и , которые предназначены Алисе и Бобу, соответственно. Каждая сторона начинает протокол тем, что выбирает (секретную) случайную циклическую подгруппу из соответствующей подгруппы кручения и вычисляет соответственную (секретную) изогению. Затем они обмениваются уравнениями преобразованных кривых, которые являются результатами действия их изогений на кривую , а также значениями их изогений, посчитанных по группе кручения другой стороны. Это позволяет обеим сторонам секретно вычислить новые изогении из , чьи ядра совместно сгенерированы с использованием двух секретных циклических подгрупп. Так как ядра этих изогений согласованы, их новые преобразованные кривые изоморфны. В этом случае совместный j-инвариант преобразованных кривых может быть использован как необходимый общий секрет.

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

Криптографическая стойкость[править | править код]

Множество изогений суперсингулярных эллиптических кривых вместе с композицией образуют неабелеву группу и защищенность SIDH основывается на этой неабелевой структуре.[3] Защищенность SIDH тесно связана с задачей нахождения изогенных отображений между двумя суперсингулярными эллиптическими кривыми, имеющих одинаковое число точек. De Feo, Jao и Plut предположили, что защищенность SIDH будет для классического компьютера и для квантового. Получается, что SIDH с 768-битным простым числом будет иметь криптостойкость на уровне 128 бит.[3] В 2014 году при изучении проблемы изогенных отображений Delfs и Galbraith подтвердили защищенность для классического компьютера.[7] Уровень стойкости был также подтвержден в работе Biasse, Jao и Sankar, и в работе Galbraith, Petit, Shani и Bo Ti.[8][9]

Эффективность[править | править код]

В процессе обмена ключами, каждой из сторон А и В будут переданы коэффициентов, задающих эллиптическую кривую, и 2 точки эллиптической кривой. Для каждого коэффициента эллиптической кривой требуется бит. Каждая точка эллиптической кривой может быть передана за бит. Всего передается бит. Получается 6144 бит для 768-битной длины характеристики поля (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. Характеристика поля — простое число вида
  2. Суперсингулярная эллиптическая кривая над .
  3. Фиксированные точки на эллиптической кривой .
  4. Точки и имеют порядок , а и порядок .

Обмен ключами[править | править код]

При обмене ключами каждая из сторон А и В должна сгенерировать изогению из общей эллиптической кривой . Это делается с помощью генерации случайной точки, в которой будет ядро их изогении. Базисными векторами для этого ядра будут пары точек , и , соответственно. Использование разных пар точек гарантирует, что стороны сгенерировали разные, некоммутирующие изогении. Случайная точка (, или ) в ядре изогений генерируется как случайная линейная комбинация точек , и точек , .

Используя , или , стороны 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-инвариант. Функция от используется как общий ключ.[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]

Криптографические атаки[править | править код]

Активная атака[править | править код]

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

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

Для проверки корректности можно использовать условие сопряжения Вейля (Weil pairing)

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

Адаптивная атака[править | править код]

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

Метод проверки Kirkwood[править | править код]

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

1. В получает статический ключ А .

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

.

Затем В вычисляет сообщение , где .

3. В получает общий секрет из и и вычисляет сессионный и проверочный ключи, используя функцию K:

.

4. B передает A и .

5. Из и А получает , а затем и .

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

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

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

Атака внесением изменений[править | править код]

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

Прерывающая цикл атака[править | править код]

Данная атака использует итерационную структуру вычисления изогении. Можно внести изменение, которое заставит А вычислить изогению только частично, раскрывая информацию о секретном ключе . Данная атака не может быть найдена проверкой Kirkwood, так как злоумышленник использует правильные данные. Закрытый ключ А раскрывается побитово, используется статус завершения протокола при успешном прерывании вычисления кривой стороной А. Сложность данной атаки примерно , где  — вероятность удачного прерывания вычислений.[24]

Примечания[править | править код]

  1. Costello, Craig; Jao, David; Longa, Patrick; Naehrig, Michael; Renes, Joost; Urbanik, David. Efficient compression of SIDH public keys (неопр.). — 2016. — 4 October.
  2. Utsler, Jim Quantum Computing Might Be Closer Than Previously Thought. IBM (сентябрь 2013). Дата обращения: 27 мая 2013. Архивировано 14 мая 2016 года.
  3. 1 2 3 4 5 De Feo, Luca Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. PQCrypto 2011. Springer. Дата обращения: 4 мая 2014. Архивировано 11 февраля 2014 года.
  4. Higgins, Parker Long Term Privacy with Forward Secrecy. Electronic Frontier Foundation. Дата обращения: 4 мая 2014. Архивировано 1 июля 2014 года.
  5. Zhu, Yan Why the Web Needs Perfect Forward Secrecy More Than Ever. Electronic Frontier Foundation. Дата обращения: 4 мая 2014. Архивировано 20 декабря 2017 года.
  6. De Feo, Luca (2017), Mathematics of Isogeny Based Cryptography, arΧiv:1711.04062. 
  7. Delfs, Christina & Galbraith (29 Oct 2013), Computing isogenies between supersingular elliptic curves over F_p, arΧiv:1310.7789. 
  8. biasse A quantum algorithm for computing isogenies between supersingular elliptic curves. CACR. Дата обращения: 11 декабря 2016. Архивировано 13 марта 2016 года.
  9. 1 2 3 4 Galbraith ON THE SECURITY OF SUPERSINGULAR ISOGENY CRYPTOSYSTEMS. IACR. Архивировано 14 декабря 2018 года.
  10. Costello, Craig; Jao, David; Longa, Patrick; Naehrig, Michael; Renes, Joost Efficient Compression of SIDH public keys. Дата обращения: 8 октября 2016. Архивировано 8 октября 2016 года.
  11. Key Compression for Isogeny-Based Cryptosystems. eprint.iacr.org. Дата обращения: 2 марта 2016. Архивировано 7 марта 2016 года.
  12. Fishbein, Dieter Machine-Level Software Optimization of Cryptographic Protocols. University of Waterloo Library - Electronic Theses. University of Waterloo (30 апреля 2014). Дата обращения: 21 июня 2014. Архивировано 14 июля 2014 года.
  13. 1 2 Costello, Craig; Longa, Patrick; Naehrig, Michael. Efficient algorithms for supersingular isogeny Diffie-Hellman (англ.) : journal. — 2016. — 1 January.
  14. Koziel, Brian; Jalali, Amir; Azarderakhsh, Reza; Kermani, Mehran; Jao, David. NEON-SIDH: Efficient Implementation of Supersingular Isogeny Diffie-Hellman Key Exchange Protocol on ARM (англ.) : journal. — 2016. — 3 November.
  15. Jalali, A.; Azarderakhsh, R.; Kermani, M. Mozaffari; Jao, D. Supersingular Isogeny Diffie-Hellman Key Exchange on 64-bit ARM (англ.) // IEEE Transactions on Dependable and Secure Computing : journal. — 2017. — Vol. PP, no. 99. — P. 1—1. — ISSN 1545-5971. — doi:10.1109/TDSC.2017.2723891.
  16. Koziel, Brian; Kermani, Mehran; Azarderakhsh, Reza. Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA (англ.) : journal. — 2016. — 7 November.
  17. defeo/ss-isogeny-software. GitHub. Дата обращения: 29 мая 2015. Архивировано 12 августа 2015 года.
  18. Rostovtsev, Alexander PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES. Springer (2006). Дата обращения: 10 мая 2014. Архивировано 26 июня 2013 года.
  19. Childs, Andrew M; Jao, Soukharev. Constructing elliptic curve isogenies in quantum subexponential time (англ.) // Journal of Mathematical Cryptology : journal. — Vol. 8. — P. 1—29. — doi:10.1515/jmc-2012-0016. — arXiv:1012.4019.
  20. Sun, Xi; Tian. Toward quantum-resistant strong designated verifier signature (неопр.) // International Journal of Grid and Utility Computing. — 2014. — 2 March (т. 5). — С. 80. — doi:10.1504/IJGUC.2014.060187.
  21. Jao, David; Soukharev, Vladimir Isogeny-based quantum-resistant undeniable signatures (3 октября 2014). doi:10.1007/978-3-319-11659-4_10. Дата обращения: 28 апреля 2016. Архивировано 13 марта 2016 года.
  22. Failure is not an option: standardization issues for post-quantum key. Talk at NIST workshop on Cybersecurity in a Post-Quantum (апрель 2015). Дата обращения: 14 декабря 2018. Архивировано 30 октября 2018 года.
  23. Hofheinz, Dennis; Hövelmanns, Kathrin; Kiltz, Eike A Modular Analysis of the Fujisaki-Okamoto Transformation. Theory of Cryptography. Springer(2017) (26 сентября 2017). Дата обращения: 14 декабря 2018. Архивировано 9 июля 2017 года.
  24. Loop-Abort Faults on Supersingular Isogeny Cryptosystems. Springer (4 июня 2017). Дата обращения: 14 декабря 2018. Архивировано 14 июля 2017 года.