Криптография основанная на кодах исправления ошибок

Постквантовая криптография: основные подходы и причины использования

Доброго времени суток! Из года в год квантовые компьютеры становятся все более производительными и дешевыми в производстве — например, Zuchongzi использует 56 кубита и способен решать задачи, предполагающие возможность квантового ускорения, за несколько часов, в то время как классические суперкомпьютеры требуют нескольких десятков тысяч лет. На данный момент обычному пользователю даже доступна работа на реальном квантовом компьютере IBM, пусть и с ограничением в несколько кубит. Большинство современных криптосистем основаны на сложности факторизации целых чисел и дискретного логарифмирования классическими алгоритмами, но данные задачи легко решаются с использованием алгоритма Шора. Одни из самых популярных криптографических систем – RSA (факторизация целых чисел), DH (дискретное логарифмирование), и ECDSA (эллиптические кривые над конечными полями) – с приходом достаточно производительных квантовых компьютеров перестанут являться надежным средством шифрования данных. В данной статье мы рассмотрим, каким образом квантовые компьютеры решают задачи, используемые в современных криптографических системах, и какие существуют пост-квантовые криптографические системы. Эта статья подразумевает наличия у читателя базового понимания физических основ квантовых вычислений.

Алгоритм Шора

Квантовый алгоритм Шора позволяет выполнить факторизацию числа M за времяиспользуякубитов. При использовании квантового компьютера с несколькими тысячами кубитов становится возможным взлом криптографических систем с открытым ключом (например, RSA, использующий открытый ключ, являющийся произведением двух больших простых чисел). Одним из методов взлома таких систем является как раз разложение открытого ключа на простые множители. Классические алгоритмы для обычных компьютеров позволяют произвести взлом такой системы за время Алгоритм Шора же способен произвести взлом не просто за полиномиальное время, а за время, сравнимое со временем умножения простых чисел.

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

Принцип работы:

Алгоритм Шора, как и многие другие квантовые алгоритмы, состоит из непосредственно квантовой части и классической части, выполняемой на обычном компьютере. Квантовая часть алгоритма Шора заключается в поиске периода некой функции, который выполняется с помощью квантового преобразования Фурье (QFT). Суть его работы покажем на аналогии. Представим, что есть человек, живущий не 24-часовой день, а, например, 26-часовой. Нам нужно определить, сколько именно часов в сутках у этого человека. В его спальне есть большое количество настенных часов, каждые из которых делают полный оборот за определенное количество времени (одни за 15 за, другие за 17 и так далее, для простоты будем считать, что минутной стрелки нет). Под каждыми часами есть лист, в середине которого прикреплена канцелярская кнопка.

Каждое утро человек встает и переставляет эту кнопку на один сантиметр в направлении стрелки соответствующих часов. Спустя достаточное количество времени мы можем понять, сколько именно часов в сутках у этого человека – на часах, делающих полный оборот за 26 часов, кнопка будет смещена на значительное расстояние от центра, так как каждое утро стрелка этих часов указывает в одном направлении, все же кнопки под остальными часами будут находиться в окрестности центра листа. Таким образом, мы узнали период функции пробуждения этого человека. QFT работает аналогичным образом и может быть эффективно применено на квантовом компьютере, так как он позволяет иметь несколько кубитов (“настенных часов” в рамках описанного выше эксперимента) в состоянии суперпозиции и производить операции над ними одновременно. Амплитудасостояний кубитов, соответствующих искомому периоду, будет расти ввиду интерференции, остальных же сохраняться около нуля (так как изначально все кубиты выставляются в нулевое булево состояние

Теперь перейдем к классической части алгоритма Шора. Допустим, мы хотим факторизовать число Для этого мы берем случайное числои ищем периодфункции В результате получим, что наибольшим делителембудет число

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

Постквантовая криптография

Преимуществами квантовых вычислений не позволят воспользоваться постквантовые алгоритмы – они используют в своей основе задачи, которые сложно решить и обычным, и квантовым компьютерам. Не стоит путать постквантовую и квантовую криптографию – вторая пользуется законами квантовой механики для отправки сообщений, и взломать квантовые системы невозможно. В постквантовой криптографии выделяется 5 различных подходов, исключающих возможность квантовых атак:

• Криптография, основанная на хеш-функциях

• Криптография, основанная на кодах исправления ошибок

• Криптография, основанная на решётках

• Криптография, основанная на многомерных квадратичных системах

• Шифрование с секретным ключом

• Шифрование с использованием суперсингулярной изогении

Рассмотрим наиболее перспективные из них. Часть подходов рассматривать не будем в силу их сложности для понимания.

Криптография, основанная на хеш-функциях

Классическим примером такого подходя является подпись Меркла – алгоритм многоразовой цифровой подписи, основанный на использовании дерева Меркла, и любой одноразовой подписи, основанной на криптостойкой хеш-функции.

Принцип работы алгоритма состоит из 3 шагов:

1. Генерируются массивы секретных ключейи публичныхПарыиспользуются как пары открытый-закрытый ключ для одноразовой подписи. Для генерациииспользуется дерево Меркла: для каждогос использованием криптостойкой хэш-функциивычисляется– нулевой слой дереваКаждый следующий слой вычисляется как(где— конкатенация) до того момента, пока в слое не останется один ключ, который называется открытым и обозначается

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

3. Проверка подписи производится в 2 этапа: сначала получатель проверяет соответствие подписисообщению. Если проверка пройдена, строится путьдо корня дерева. При совпадении полученного корня дерева спроверка подписи считается успешной

   

В отличие от алгоритмов наподобие RSA, подпись Меркла является постквантовой, так как опирается на стойкость криптографической хеш-функциии одноразовой подписи. Существенным недостатком данного алгоритма и схожих, основанных на хеш-функциях, является ограниченное количество подписей, используемых один раз для каждого сообщения, что препятствует массовому использованию такого подхода. Однако уже существуют методы создания аналогичным способом многоразовых подписей.

Криптография, основанная на кодах исправления ошибок

Одним из примеров таких систем является McEliece – криптосистема с открытыми ключами, основанная на сложности декодирования полных линейных кодов и использующая в процессе шифрования элемент случайности. В этой системе всеми пользователями совместно используются параметры безопасности . На данный момент предложено использование следующего набора параметров: , при этом размер открытого ключа достигает 520.047 бит. Для устойчивости против квантовых атак предлагается использовать , размер открытого ключа в этом случае достигает 8.373.911 бит. Главными недостатками систем наподобие McEliece являются большой размер открытого ключа и значительное увеличение длины зашифрованного сообщения в сравнении с исходным. Однако такой подход в постквантовой криптографии считается одним из наиболее перспективных ввиду отсутствия серьезных недостатков (вроде ограниченного количества подписей) и деактулизации проблемы размеров передаваемых сообщений на фоне увеличивающихся скоростей передачи данных.

Криптография, основанная на многомерных квадратичных системах

Наиболее популярным примером такого подходя является стандарт AES (англ. Advanced Encryption Standard) – симметричный алгоритм блочного шифрования, используемый правительством США как достаточно надежный для защиты информации, являющейся государственной тайной.

Принцип работы:

Сообщения при использовании AES разбиваются на блоки по 128 бит, ключ при этом может быть размером в 128, 192 или 256 бит. В 128-битовый блок вмещается 16 байт, запишем в него сообщение “котики очень милые”. Последние два символа будут переданы в следующем блоке, мы рассмотрим только первый.

Далее берется ключ и с помощью расписания ключей AES генерируется набор раундовых ключей (9 для 128-битового ключа). Допустим, начальный ключ был следующим:

К каждому байту блока с помощью XOR прибавляется начальный ключ. Допустим, результат будет следующим:

Далее производится 9 итераций, на каждой из которых выполняются следующие шаги:

• Генерируется таблица замен, по которой происходит замена байтов (например, h3->jb, s8->9f и так далее)

  jb	n3	kf	n2
  9f	jj	1h	js
  74	wh	0d	18
  hs	17	d6	px

• Строки циклически сдвигаются на 1, 2 или 3 шага

  jb	n3	kf	n2
  jj	1h	js	9f
  0d	18	74	wh
  px	hs	17	d6

• К каждому столбцу применяется определенная математическая операция (column mixing)

  ls	j4	2n	ma
  83	28	ke	9f
  9w	xm	3l	m4
  5b	a9	cj	ps

• Прибавляется следующий раундовый ключ

Данные действия повторяются 9 раз для 128-битного ключа, 11 раз для 192-битного и 13 раз для 256-битного + 1 раунд. Дополнительный раунд не включает в себя преобразование столбцов как невыгодную операцию, не повышающую надежность шифра. После этого вместо исходного блока “котики очень мил” мы получаем что-то вроде “ ok23b8a0i3j 293uivnfqf98vs87a”.

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

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

Заключение

На данный момент стоимость создания квантовых сетей даже на 100 пользователей исчисляется миллионами долларов, и общедоступный квантовый интернет еще является туманным будущим. Однако уже в ближайшие несколько лет вычислительные мощности квантовых компьютеров могут достичь уровня, достаточного для создания угрозы современным криптосистемам, и в продаже могут появиться устройства, доступные широкой публике. Поэтому стоит уже сейчас изучать и внедрять постквантовые алгоритмы шифрования данных в повседневную жизнь – в 2017 году Национальным институтом стандартов и технологий США был начат конкурс NIST, призванный стандартизировать набор квантово-устойчивых криптографических схем, в настоящий момент он находится на третьем раунде. Из-за кардинальных различий подходов в постквантовой криптографии прямое сравнение алгоритмов зачастую невозможно, поэтому деятельность NIST направлена на увеличение производительности представленных алгоритмов и получение большей уверенности в их защищенности, победитель же будет выбран на основе совместного анализа NIST и криптографического сообщества. Экспертами NIST из 69 алгоритмов-кандидатов уже выбраны 7 основных и 8 альтернативных (среди них – McEliece, Rainbow, основанный на многомерной криптографии и отличающийся малым размером подписей всего в несколько сотен бит, и NTRU Prime, основанный на решетках), и уже к 2022 году процесс стандартизации может завершиться.

Источники:

1. https://spectrum.ieee.org/quantum-computing-china

2. https://arxiv.org/abs/2109.03494

3. https://quantum-computing.ibm.com

4. https://en.wikipedia.org/wiki/Shor%27s_algorithm

5. What is AES encryption and how does it work?

6. What is the Diffie–Hellman key exchange and how does it work?

7. https://www.quora.com/How-does-Shors-algorithm-work-in-laymans-terms

8. https://en.wikipedia.org/wiki/Post-quantum_cryptography

Подробно

Теория кодирования всегда имела тесную взаимосвязь с криптографией, поэтому неудивительно, что наиболее известная криптографическая система на основе кодов, исправляющих ошибки — система McEliece — появилась в 1978 году, став одной из первых систем с открытым ключом. Значительно уступая по эффективности системе RSA, она не получила такого же широкого распространения. Однако в последнее время, после активизации исследований в области квантовых вычислений и публикации алгоритма Шора, эффективно взламывающего систему RSA на квантовом компьютере, способность системы McEliece противостоять квантовым атакам вновь привлекла внимание исследователей.

Система McEliece и подобные ей (система Нидеррайтера) могут быть реализованы с помощью различных классов кодов. В этой области хорошо известны результаты, полученные отечественной алгебраической школой — так, известный российский исследователь В.М. Сидельников показал нестойкость системы McEliece для некоторых классов кодов. В то же время известно, что применение кодов Гоппы позволяет получить стойкий и эффективный вариант этой системы. При анализе любой атаки на систему McEliece обычно отмечают насколько она применима для кодов Гоппы. В частности, система McEliece на кодах Гоппы — самый широко изученный алгоритм из числа участников конкурса NIST. Это значит, что вряд ли появится новая атака, которая существенно снизит стойкость схемы, в отличие от других классов алгоритмов.

Основанные на теории кодирования криптографические системы, как правило, используют простые двоичные операции и могут быть легко реализованы на программном и аппаратном уровне. В то же время они требуют больших объемов памяти для хранения ключей, представленных как проверочные матрицы линейных кодов большой размерности.

Интересной и актуальной задачей является создание эффективной схемы подписи на основе задач теории кодирования.

Об авторе: Антон Гугля, руководитель QApp — компании-разработчика отечественных решений кибербезопасности на основе постквантовых алгоритмов шифрования.

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

Зачем требуется шифрование

О какой бы криптографии ни заходила речь, окружающие зачастую считают, что это их мало касается. Крупный бизнес — да, а вот нас с вами — едва ли. Конечно, это не так. Покупки в интернет-магазинах, переписки в мессенджерах и социальных сетях, интернет-серфинг по пути на работу — все эти активности неразрывно связаны с шифрованием данных. Простой пример — защищенное соединение https, которое преобразует передаваемые в сети данные в зашифрованный формат и не дает посторонним прямой доступ к конфиденциальной информации.

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

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

Квантовая угроза

Между тем возможность взломать асимметричный шифр существует: алгоритм, способный справиться с этой задачей, еще в 1994 году разработал ученый Питер Шор. Реализовать этот алгоритм позволяет квантовый компьютер. В отличие от обычных устройств, работающих на основе полупроводниковых технологий, мощность квантовых растет экспоненциально. Поэтому их возможности значительно превосходят любые инструменты, которые сегодня используют хакеры.

Современные квантовые компьютеры пока не обладают мощностью достаточной для взлома систем на основе асимметричного шифрования. Но с начала 2000-х такие технологические гиганты, как IBM, Google, Intel ведут разработки по развитию квантовых вычислений, что приближает нас к кибератакам нового типа. По мнению большинства экспертов, первые случаи подобных атак могут быть зафиксированы до 2030 года. Впрочем, аналитики McKinsey предостерегают, что финансовый и государственный секторы, а также страховая индустрия могут столкнуться с ними уже в ближайшие два года.

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

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

Постквантовое шифрование

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

В частности, это алгоритмы, основанные на линейных кодах, теории решеток и хеш-функциях. Первый тип (code-based) основан на гипотезе, что декодировать случайный линейный код очень сложно. Первый алгоритм такого типа появился еще в 1978 году — это была система McEliece, одна из первых систем с открытым ключом. В тот момент об атаках с использованием квантового компьютера не было и речи, однако после появления алгоритма Шора, способного легко взломать используемое повсеместно шифрование, криптографы-исследователи вновь заинтересовались алгоритмом McEliece.

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

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

Пора применять

Над интеграцией и пилотированием криптографических алгоритмов в свои продукты уже работают такие гиганты рынка, как Microsoft, Google, Verizon, Thales, Toshiba, Amazon, Cloudflare.

Так, весной 2022 года IBM представила новое поколение мейнфреймов (универсальных высокопроизводительных серверов) z16, которые используют для защиты данных постквантовую криптографию. z16 оснащен ускорителем на базе искусственного интеллекта, что позволяет быстро обрабатывать огромные объемы информации. Это критично, в частности, для финансовых компаний и медицинских организаций, то есть тех, чьи данные обладают долгим циклом жизни. Именно поэтому для их защиты IBM применяет продукты в области постквантового шифрования, построенные на теории решеток.

В то же время южнокорейский мобильный оператор LG Uplus (принадлежит LG Group) выпустил коммерческий сервис для проводной и беспроводной связи, устойчивый к атакам с помощью квантового компьютера. А уже осенью LG Electronics объявила, что будет использовать этот метод защиты для ряда задач, в том числе в технологии V2X (vehicle to everything) — обмена данными между автомобилями и объектами дорожной инфраструктуры.

В октябре 2022 года компания Cloudflare объявила о запуске поддержки постквантовой криптографии для всех веб-сайтов и API, обслуживаемых через ее сеть. По сути это делает доступным квантовое шифрование для 19% мировых веб-ресурсов. Это наглядно демонстрирует, насколько критично к квантовой угрозе относится одна из крупнейших сетевых инфраструктур.

В России работа по пилотированию постквантовых продуктов также идет полным ходом: в июне 2022 года отечественные специалисты подтвердили совместимость постквантового шифрования с российскими процессорами Baikal-M, в октябре — с процессорами «Эльбрус». Первой в стране финансовой организацией, пилотировавшей постквантовые алгоритмы, стал Газпромбанк — в 2022 году он обеспечил квантово-устойчивую защиту host-to-host соединения при проведении финансовых поручений.

Финальный штрих

На сегодняшний день постквантовая криптография находится на стадии стандартизации. В США этот процесс курирует Национальный институт стандартов и технологий (NIST). На конкурсной основе эксперты выбирают наиболее квантово-устойчивые алгоритмы, которые лягут в основу стандартов постквантового шифрования. В 2022 году институт выбрал четыре алгоритма — они станут частью постквантового криптографического стандарта, окончательная доработка которого ожидается примерно через два года. В то же время Белый дом обязал госструктуры уже к маю 2023 года совершить всецелую подготовку к переходу на постквантовые алгоритмы.

В России разработкой стандартов постквантовых алгоритмов занялись в 2019 году под руководством Технического комитета 26, куда входят представители государственных и коммерческих организаций. Ожидается, что отечественные стандарты будут утверждены к 2024–2025 году. Рынок вступил в фазу активного формирования, а значит уже в ближайшие один-два года число пилотных проектов мирового уровня вырастет в разы.

In cryptography, post-quantum cryptography (PQC) (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor’s algorithm.^[1][2]

Even though current quantum computers lack processing power to break any real cryptographic algorithm,^[3] many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat. This work has gained greater attention from academics and industry through the PQCrypto conference series since 2006 and more recently by several workshops on Quantum Safe Cryptography hosted by the European Telecommunications Standards Institute (ETSI) and the Institute for Quantum Computing.^[4][5][6] The rumoured existence of widespread harvest now, decrypt later programs has also been seen as a motivation for the early introduction of post-quantum algorithms, as data recorded now may still remain sensitive many years into the future.^[7][8]

In contrast to the threat quantum computing poses to current public-key algorithms, most current symmetric cryptographic algorithms and hash functions are considered to be relatively secure against attacks by quantum computers.^[2][9] While the quantum Grover’s algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks.^[10] Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography.

Algorithms[edit]

Currently post-quantum cryptography research is mostly focused on six different approaches:^[2][5]

Lattice-based cryptography[edit]

This approach includes cryptographic systems such as learning with errors, ring learning with errors (ring-LWE),^[11][12][13] the ring learning with errors key exchange and the ring learning with errors signature, the older NTRU or GGH encryption schemes, and the newer NTRU signature and BLISS signatures.^[14] Some of these schemes like NTRU encryption have been studied for many years without anyone finding a feasible attack. Others like the ring-LWE algorithms have proofs that their security reduces to a worst-case problem.^[15] The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU be studied for standardization rather than the NTRU algorithm.^[16][17] At that time, NTRU was still patented. Studies have indicated that NTRU may have more secure properties than other lattice based algorithms.^[18]

Multivariate cryptography[edit]

This includes cryptographic systems such as the Rainbow (Unbalanced Oil and Vinegar) scheme which is based on the difficulty of solving systems of multivariate equations. Various attempts to build secure multivariate equation encryption schemes have failed. However, multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature.^[19] There is a patent on the Rainbow Signature Scheme.

Hash-based cryptography[edit]

This includes cryptographic systems such as Lamport signatures, the Merkle signature scheme, the XMSS,^[20] the SPHINCS,^[21] and the WOTS schemes. Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number-theoretic digital signatures like RSA and DSA. Their primary drawback is that for any hash-based public key, there is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact had reduced interest in these signatures until interest was revived due to the desire for cryptography that was resistant to attack by quantum computers. There appear to be no patents on the Merkle signature scheme^{[citation needed]} and there exist many non-patented hash functions that could be used with these schemes. The stateful hash-based signature scheme XMSS developed by a team of researchers under the direction of Johannes Buchmann is described in RFC 8391.^[22]
Note that all the above schemes are one-time or bounded-time signatures, Moni Naor and Moti Yung invented UOWHF hashing in 1989 and designed a signature based on hashing (the Naor-Yung scheme)^[23] which can be unlimited-time in use (the first such signature that does not require trapdoor properties).

Code-based cryptography[edit]

This includes cryptographic systems which rely on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and the related Courtois, Finiasz and Sendrier Signature scheme. The original McEliece signature using random Goppa codes has withstood scrutiny for over 40 years. However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure.^[24] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers.^[16]

Isogeny-based cryptography[edit]

These cryptographic systems rely on the properties of isogeny graphs of elliptic curves (and higher-dimensional abelian varieties) over finite fields, in particular supersingular isogeny graphs, to create cryptographic systems. Among the more well-known representatives of this field are the Diffie-Hellman-like key exchange CSIDH which can serve as a straightforward quantum-resistant replacement for the Diffie-Hellman and elliptic curve Diffie–Hellman key-exchange methods that are in widespread use today,^[25] and the signature scheme SQISign which is based on the categorical equivalence between supersingular elliptic curves and maximal orders in particular types of quaternion algebras.^[26] Another widely noticed construction, SIDH/SIKE, was spectacularly broken in 2022.^[27] The attack is however specific to the SIDH/SIKE family of schemes and does not generalize to other isogeny-based constructions.^[28]

Symmetric key quantum resistance[edit]

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer.^[29] Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient way to get post quantum cryptography today.^[30]

Security reductions[edit]

In cryptography research, it is desirable to prove the equivalence of a cryptographic algorithm and a known hard mathematical problem. These proofs are often called «security reductions», and are used to demonstrate the difficulty of cracking the encryption algorithm. In other words, the security of a given cryptographic algorithm is reduced to the security of a known hard problem. Researchers are actively looking for security reductions in the prospects for post quantum cryptography. Current results are given here:

Lattice-based cryptography – Ring-LWE Signature[edit]

In some versions of Ring-LWE there is a security reduction to the shortest-vector problem (SVP) in a lattice as a lower bound on the security. The SVP is known to be NP-hard.^[31] Specific ring-LWE systems that have provable security reductions include a variant of Lyubashevsky’s ring-LWE signatures defined in a paper by Güneysu, Lyubashevsky, and Pöppelmann.^[12] The GLYPH signature scheme is a variant of the Güneysu, Lyubashevsky, and Pöppelmann (GLP) signature which takes into account research results that have come after the publication of the GLP signature in 2012. Another Ring-LWE signature is Ring-TESLA.^[32] There also exists a «derandomized variant» of LWE, called Learning with Rounding (LWR), which yields » improved speedup (by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) and bandwidth.»^[33] While LWE utilizes the addition of a small error to conceal the lower bits, LWR utilizes rounding for the same purpose.

Lattice-based cryptography – NTRU, BLISS[edit]

The security of the NTRU encryption scheme and the BLISS^[14] signature is believed to be related to, but not provably reducible to, the Closest Vector Problem (CVP) in a Lattice. The CVP is known to be NP-hard. The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU which does have a security reduction be studied for long term use instead of the original NTRU algorithm.^[16]

Multivariate cryptography – Unbalanced Oil and Vinegar[edit]

Unbalanced Oil and Vinegar signature schemes are asymmetric cryptographic primitives based on multivariate polynomials over a finite field . Bulygin, Petzoldt and Buchmann have shown a reduction of generic multivariate quadratic UOV systems to the NP-Hard Multivariate Quadratic Equation Solving problem.^[34]

Hash-based cryptography – Merkle signature scheme[edit]

In 2005, Luis Garcia proved that there was a security reduction of Merkle Hash Tree signatures to the security of the underlying hash function. Garcia showed in his paper that if computationally one-way hash functions exist then the Merkle Hash Tree signature is provably secure.^[35]

Therefore, if one used a hash function with a provable reduction of security to a known hard problem one would have a provable security reduction of the Merkle tree signature to that known hard problem.^[36]

The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers.^[16]

Code-based cryptography – McEliece[edit]

The McEliece Encryption System has a security reduction to the Syndrome Decoding Problem (SDP). The SDP is known to be NP-hard^[37] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the use of this cryptography for long term protection against attack by a quantum computer.^[16]

Code-based cryptography – RLCE[edit]

In 2016, Wang proposed a random linear code encryption scheme RLCE^[38] which is based on McEliece schemes. RLCE scheme can be constructed using any linear code such as Reed-Solomon code by inserting random columns in the underlying linear code generator matrix.

Supersingular elliptic curve isogeny cryptography[edit]

Security is related to the problem of constructing an isogeny between two supersingular curves with the same number of points. The most recent investigation of the difficulty of this problem is by Delfs and Galbraith indicates that this problem is as hard as the inventors of the key exchange suggest that it is.^[39] There is no security reduction to a known NP-hard problem.

Comparison[edit]

One common characteristic of many post-quantum cryptography algorithms is that they require larger key sizes than commonly used «pre-quantum» public key algorithms. There are often tradeoffs to be made in key size, computational efficiency and ciphertext or signature size. The table lists some values for different schemes at a 128 bit post-quantum security level.

Algorithm	Type	Public Key	Private Key	Signature
NTRU Encrypt[40]	Lattice	766.25 B	842.875 B
Streamlined NTRU Prime[citation needed]	Lattice	154 B
Rainbow[41]	Multivariate	124 KB	95 KB
SPHINCS[21]	Hash Signature	1 KB	1 KB	41 KB
SPHINCS+[42]	Hash Signature	32 B	64 B	8 KB
BLISS-II	Lattice	7 KB	2 KB	5 KB
GLP-Variant GLYPH Signature[12][43]	Ring-LWE	2 KB	0.4 KB	1.8 KB
NewHope[44]	Ring-LWE	2 KB	2 KB
Goppa-based McEliece[16]	Code-based	1 MB	11.5 KB
Random Linear Code based encryption[45]	RLCE	115 KB	3 KB
Quasi-cyclic MDPC-based McEliece[46]	Code-based	1,232 B	2,464 B
SIDH[47]	Isogeny	564 B	48 B
SIDH (compressed keys)[48]	Isogeny	330 B	48 B
3072-bit Discrete Log	not PQC	384 B	32 B	96 B
256-bit Elliptic Curve	not PQC	32 B	32 B	65 B

A practical consideration on a choice among post-quantum cryptographic algorithms is the effort required to send public keys over the internet. From this point of view, the Ring-LWE, NTRU, and SIDH algorithms provide key sizes conveniently under 1KB, hash-signature public keys come in under 5KB, and MDPC-based McEliece takes about 1KB. On the other hand, Rainbow schemes require about 125KB and Goppa-based McEliece requires a nearly 1MB key.

Lattice-based cryptography – LWE key exchange and Ring-LWE key exchange[edit]

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper^[49] appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert^[50] presented a key transport scheme following the same basic idea of Ding’s, where the new idea of sending additional 1 bit signal for rounding in Ding’s construction is also utilized. For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert’s scheme.^[51] The corresponding private key would be roughly 14,000 bits.

In 2015, an authenticated key exchange with provable forward security following the same basic idea of Ding’s was presented at Eurocrypt 2015,^[52] which is an extension of the HMQV^[53] construction in Crypto2005. The parameters for different security levels from 80 bits to 350 bits, along with the corresponding key sizes are provided in the paper.^[52]

Lattice-based cryptography – NTRU encryption[edit]

For 128 bits of security in NTRU, Hirschhorn, Hoffstein, Howgrave-Graham and Whyte, recommend using a public key represented as a degree 613 polynomial with coefficients . This results in a public key of 6130 bits. The corresponding private key would be 6743 bits.^[40]

Multivariate cryptography – Rainbow signature[edit]

For 128 bits of security and the smallest signature size in a Rainbow multivariate quadratic equation signature scheme, Petzoldt, Bulygin and Buchmann, recommend using equations in with a public key size of just over 991,000 bits, a private key of just over 740,000 bits and digital signatures which are 424 bits in length.^[41]

Hash-based cryptography – Merkle signature scheme[edit]

In order to get 128 bits of security for hash based signatures to sign 1 million messages using the fractal Merkle tree method of Naor Shenhav and Wool the public and private key sizes are roughly 36,000 bits in length.^[54]

Code-based cryptography – McEliece[edit]

For 128 bits of security in a McEliece scheme, The European Commissions Post Quantum Cryptography Study group recommends using a binary Goppa code of length at least and dimension at least , and capable of correcting errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes bits. The corresponding private key, which consists of the code support with elements from and a generator polynomial of with coefficients from , will be 92,027 bits in length^[16]

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least and dimension at least , and capable of correcting errors. With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes bits. The private key, a quasi-cyclic parity-check matrix with nonzero entries on a column (or twice as much on a row), takes no more than bits when represented as the coordinates of the nonzero entries on the first row.

Barreto et al. recommend using a binary Goppa code of length at least and dimension at least , and capable of correcting errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes bits.^[55] The corresponding private key, which consists of the code support with elements from and a generator polynomial of with coefficients from , will be 40,476 bits in length.

Supersingular elliptic curve isogeny cryptography[edit]

For 128 bits of security in the supersingular isogeny Diffie-Hellman (SIDH) method, De Feo, Jao and Plut recommend using a supersingular curve modulo a 768-bit prime. If one uses elliptic curve point compression the public key will need to be no more than 8×768 or 6144 bits in length.^[56] A March 2016 paper by authors Azarderakhsh, Jao, Kalach, Koziel, and Leonardi showed how to cut the number of bits transmitted in half, which was further improved by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik resulting in a compressed-key version of the SIDH protocol with public keys only 2640 bits in size.^[48] This makes the number of bits transmitted roughly equivalent to the non-quantum secure RSA and Diffie-Hellman at the same classical security level.^[57]

Symmetric–key-based cryptography[edit]

As a general rule, for 128 bits of security in a symmetric-key-based system, one can safely use key sizes of 256 bits. The best quantum attack against generic symmetric-key systems is an application of Grover’s algorithm, which requires work proportional to the square root of the size of the key space. To transmit an encrypted key to a device that possesses the symmetric key necessary to decrypt that key requires roughly 256 bits as well. It is clear that symmetric-key systems offer the smallest key sizes for post-quantum cryptography.

Forward secrecy[edit]

A public-key system demonstrates a property referred to as perfect forward secrecy when it generates random public keys per session for the purposes of key agreement. This means that the compromise of one message cannot lead to the compromise of others, and also that there is not a single secret value which can lead to the compromise of multiple messages. Security experts recommend using cryptographic algorithms that support forward secrecy over those that do not.^[58] The reason for this is that forward secrecy can protect against the compromise of long term private keys associated with public/private key pairs. This is viewed as a means of preventing mass surveillance by intelligence agencies.

Both the Ring-LWE key exchange and supersingular isogeny Diffie-Hellman (SIDH) key exchange can support forward secrecy in one exchange with the other party. Both the Ring-LWE and SIDH can also be used without forward secrecy by creating a variant of the classic ElGamal encryption variant of Diffie-Hellman.

The other algorithms in this article, such as NTRU, do not support forward secrecy as is.

Any authenticated public key encryption system can be used to build a key exchange with forward secrecy.^[59]

Open Quantum Safe project[edit]

Open Quantum Safe (OQS) project was started in late 2016 and has the goal of developing and prototyping quantum-resistant cryptography.^[60][61] It aims to integrate current post-quantum schemes in one library: liboqs.^[62] liboqs is an open source C library for quantum-resistant cryptographic algorithms. It initially focuses on key exchange algorithms but by now includes several signature schemes. It provides a common API suitable for post-quantum key exchange algorithms, and will collect together various implementations. liboqs will also include a test harness and benchmarking routines to compare performance of post-quantum implementations. Furthermore, OQS also provides integration of liboqs into OpenSSL.^[63]

As of March 2023, the following key exchange algorithms are supported:^[60]

Algorithm	Type
CRYSTALS-Kyber	Module Learning With Error
Classic McEliece	goppa codes
BIKE[64]	codes
HQC[65][66]	codes
Frodo[67] [68]	Learning with errors
NTRU[69]	Lattice-based cryptography
CRYSTALS-Dilithium[70][71]	Shortest Integer Solution
Falcon	Shortest Integer Solution
SPHINCS+	hash based

Older supported versions that have been removed because of the progression of the NIST Post-Quantum Cryptography Standardization Project are:

Algorithm	Type
BCNS15[72]	Ring learning with errors key exchange
NewHope[73][44]	Ring learning with errors key exchange
SIDH[74][75]	Supersingular isogeny key exchange
McBits[76]	Error-correcting codes

Implementation[edit]

One of the main challenges in post-quantum cryptography is considered to be the implementation of potentially quantum safe algorithms into existing systems. There are tests done, for example by Microsoft Research implementing PICNIC in a PKI using Hardware security modules.^[77] Test implementations for Google’s NewHope algorithm have also been done by HSM vendors. In August 2023, Google released a FIDO2 security key implementation of an ECC/Dilithium hybrid signature schema which was done in partnership with ETH Zürich.^[78]

Other notable implementations include:

• bouncycastle^[79]
• liboqs^[80]

See also[edit]

• NIST Post-Quantum Cryptography Standardization
• Quantum cryptography – cryptography based on quantum mechanics
• Crypto-shredding — Deleting encryption keys
• Harvest now, decrypt later

References[edit]

Further reading[edit]

• Post-Quantum Cryptography. Springer. 2008. p. 245. ISBN 978-3-540-88701-0.
• Isogenies in a Quantum World
• On Ideal Lattices and Learning With Errors Over Rings
• Kerberos Revisited: Quantum-Safe Authentication
• The picnic signature scheme

External links[edit]

• PQCrypto, the post-quantum cryptography conference
• ETSI Quantum Secure Standards Effort
• NIST’s Post-Quantum crypto Project
• PQCrypto Usage & Deployment
• ISO 27001 Certification Cost

Привет, Вы узнаете про постквантовая криптография, Разберем основные ее виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое
постквантовая криптография, криптография , настоятельно рекомендую прочитать все из категории Криптография и криптоанализ, Стеганография и Стегоанализ.

постквантовая
криптография — часть криптографии, которая остается актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми для криптографических атак. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора. Многие криптографы в настоящее время ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.

Существуют классические криптосистемы, которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от систем указанных выше, из-за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (quantum-resistant), или «постквантовыми» криптосистемами.

Постквантовая криптография в свою очередь отличается от квантовой криптографии, которая занимается методами защиты коммуникаций, основанных на принципах квантовой физики.

1. Основы криптографии ( повторение)

Что такое криптография и для чего она вообще нужна? Скажем, Алиса и Боб хотят обменяться сообщением, да так, чтобы его содержание оставалось в секрете. Очевидно, что у каждой из сторон должен быть свой ключ. И на этом этапе можно выделить два подвида криптосистем.

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

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

Интересная многоходовочка… Ну а как она реализуется, спросит пытливый %username%? Все дело в так называемых односторонних функциях. Пусть есть функция y=f(x). По известному аргументу x вычислить значение функции y проще, чем захватить Вестерос с тремя драконами и армией безупречных. Однако вычисление аргумента x по известному значению функции y является довольно-таки трудоемкой задачей.

Наиболее известными кандидатами в односторонние функции являются задача факторизации числа, которая состоит в разложении числа на простые множители, и задача дискретного логарифмирования, которая заключается в поиске неизвестного k по известным значениям y и g, которые удовлетворяют: y=gk. Первая, например, применяется в широко известной криптосистеме RSA, а вторую можно встретить в схеме установления ключа Диффи-Хэллмана.

Однако с учетом стремительного, как полет дракона, роста производительности вычислительных устройств, возникает необходимость в увеличении длины ключа, ну а это может стать критическим фактором для устройств с ограниченной мощностью…Эх, было бы так здорово, появись такая структура, которая бы позволила сократить размер ключа при таком же уровне стойкости… И, к счастью, она существует! Название сему чуду – эллиптическая кривая.

2 Введение в постквантовую криптографию и закат RSA

3. Введение в использование эллиптических кривых

Эллиптическая кривая — над полем — неособая кубическая кривая на проективной плоскости над (алгебраическим замыканием поля ), задаваемая уравнением 3-й степени с коэффициентами из поля и «точкой на бесконечности».

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

y2+a1xy+a3y=x3+a2x2+a4x+a6

Однако на практике такую форму кривой можно встретить нечасто. Различают формы Лежандра, Монтгомери, Гессе и т.д. Использование той или иной формы может увеличить эффективность операций над точками эллиптической кривой. Например, в форме Монтгомери есть возможность выполнять умножение точки на число за фиксированное время благодаря алгоритму лестницы Монтгомери.

Наверняка многие сталкивались с формой Вейерштрасса, ее называют канонической для полей с характеристикой charK≠2,3:

E(K):y2=x3+ax+b

Важной характеристикой эллиптической кривой является ее дискриминант, который для формы Вейерштрасса вычисляется так:Δ=4a3+27b2.

Дискриминант не должен быть равен нулю, иначе кривая уже не будет эллиптической, так как будут существовать точки перегиба, как на кривой y2=x3−3x+2 на рисунке справа.

Наверняка многим знакомо изображение эллиптической кривой, которое можно увидеть на рисунке слева. Здесь кривая вида y2=x3−3x+5 задана над полем рациональных чисел.

Однако, при использовании рациональных чисел возникает сложность с их округлением, и, как следствие, с неоднозначностью операций зашифрования и расшифрования. Поэтому в криптографии эллиптические кривые задаются над конечным полем, где координаты точек – это элементы поля. График кривой, конечно, потеряет свою былую привлекательность, плавные линии заменятся на точки, но мы же любим эллиптические кривые далеко не за это!

Нельзя не упомянуть еще одну характеристику эллиптических кривых, которая (СПОЙЛЕР!) еще одарит читателей своим присутствием в статье. Речь идет о j−инварианте, постоянной величине. Его вычисление для эллиптической кривой в форме Вейерштрасса тоже не обладает устрашающим воздействием на организм:j=17284a34a3+27b2

Свойства группы

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

• Замкнутость означает, что результат сложения элементов группы тоже является элементом группы. Переведем в термины эллиптической кривой: при сложении точек эллиптической кривой получается точка, принадлежащая этой же кривой.

  

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

• Ассоциативность означает независимость результата сложения от изменения порядка действия.
• В группе должен существовать нейтральный элемент. Результат сложения любого элемента группы g и нейтрального будет равен тому же элементу.В эллиптических кривых роль нейтрального элемента играет бесконечно удаленная точка: P∞:P∞+P=P+P∞=P
  
• К каждому элементу должен существовать обратный к нему (относительно основной операции). При сложении элемента группы и обратного к нему получаем нейтральный элемент.
• Свойство коммутативности нам знакомо еще из школьной математики: от перестановки слагаемых сумма не меняется. Именно данное свойство и делает группу абелевой.

Пара слов о стойкости

Теперь поговорим немного о стойкости криптосистем, основанных на задаче дискретного логарифмирования. Пусть G – конечная циклическая группа, то есть, каждый ее элемент представим в виде степени одного-единственного элемента — образующей g: =G={1,g2,g3,…,gq−1}.

В зависимости от выбора группы G существуют различные методы решения задачи дискретного логарифмирования. Так, для решения задачи дискретного логарифмирования в конечном поле, на общее несчастье существуют не только универсальные алгоритмы (метод Полига-Хеллмана, ρ-метод Полларда и др.), которые имеют экспоненциальную сложность, но и специальные, имеющие субэкспоненциальную сложность (метод базы разложения, метод решета числового поля).

Если же в качестве образующей группы G взять точку эллиптической кривой, то криптожуликам придется довольствоваться лишь универсальными алгоритмами . Об этом говорит сайт https://intellect.icu . Поэтому криптография на эллиптических кривых «балует» пользователей меньшей длиной ключа.

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

Данные кривые уязвимы к MOV атаке, которая позволяет сводить вычисление задачи дискретного логарифмирования в группе точек эллиптической кривой над полем Fq к задаче дискретного логарифмирования в конечном поле Fqk. Учитывая, что длина ключа в криптографии на эллиптических кривых меньше, и что для суперсингулярных кривых значение k не является большим, реализация данной атаки проходит крайне успешно для злоумышленника.

Ну так в чем же проблема? Используем подходящие эллиптические кривые и радуемся жизни! Но не тут-то было…

4 Алгоритмы постквантовой криптографии

Постквантовые криптографические конструкции способны спасти криптографический мир от квантовых атак. Хотя квантовый компьютер и уничтожит большинство традиционных алгоритмов (RSA, DSA, ECDSA), но сверхбыстрыми вычислениями не получится полностью избавиться от криптографии, так как постквантовая криптография, в основном, сосредоточена на пяти различных подходах, решающих проблему квантовых атак.

Криптография, основанная на хеш-функциях

Классическим примером является подпись Меркла с открытым ключом на основе хеш-дерева, Ральф Чарльз Меркл предложил этот алгоритм цифровой подписи в 1979 году, как интересную альтернативу цифровым подписям RSA и DSA. Основной недостаток схемы Меркла состоит в том, что для любого открытого ключа на основе хеш-функции существует ограничение на количество подписей, которые могут быть получены из соответствующего набора закрытых ключей. Этот факт и снижал уровень интереса к подписям такого типа, пока не появилась потребность в криптографии, устойчивой к воздействию квантовых компьютеров.

Криптография, основанная на кодах исправления ошибок

Является одним из наиболее перспективных кандидатов на пост-квантовые криптосистемы. Классическим примером является схемы шифрования McEliece и Niederreiter.

Криптография, основанная на решетках

Классическим примером схем шифрования являются Ring-Learning with Errors или более старые NTRU и GGH .

Криптография, основанная на многомерных квадратичных системах

Одной из самых интересных схем является подпись с открытым ключом Жака Патарина HFE, предложенная им в 1996 году, как обобщение предложений Matsumoto и Imai.

Шифрование с секретным ключом

Ярким примером является шифр Rijndael, предложенный в 1998 году, впоследствии переименованный в AES (Advanced Encryption Standard).

Шифрование с использованием суперсингулярной изогении

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

5 Примеры криптографических атак на RSA

В 1978 году документ, опубликованный разработчиками криптографического алгоритма с открытым ключом RSA (аббревиатура от фамилий Rivest, Shamir и Adleman), упоминал новый алгоритм Ричарда Шреппеля «linear sieve», который факторизовал любой RSA модуль } длины бит, используя простых операций. Таким образом, для того чтобы этот алгоритм требовал по меньшей мере простых операций, необходимо выбирать по крайней мере не меньше чем бит. Так как означает, что что-то сходится к {\displaystyle 0,5} при , то для выяснения правильного размера {\displaystyle n} при конечном {\displaystyle b} требуется более тщательный анализ скорости «linear sieve».

В 1988 году Джон Поллард ] предложил новый алгоритм факторизации, который называется Общий метод решета числового поля. Этот алгоритм факторизовал RSA-модуль размерности бит, используя простых операций. Таким образом, требуется выбирать не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций.

С 2008 года самые быстрые алгоритмы факторизации для классических компьютерных архитектур используют по меньшей мере простых операций. Были некоторые улучшения в значениях и в деталях , но не трудно догадаться, что {\displaystyle 1/3} оптимально, и что выбор модуля длиной примерно равной бит, позволит сопротивляться всем возможным атакам на классических компьютерах.

В 1994 году Питер Шор предложил алгоритм, который факторизовал любой RSA-модуль размерности (точнее ) кубитовых операций на квантовом компьютере размера порядка кубит (и небольшого количества вспомогательных вычислений на классическом компьютере). Пользуясь алгоритмом Шора, необходимо по крайней мере выбирать модуль {\displaystyle n} битовым размером не меньше чем бит, что является слишком большим числом для любого интересующего нас {\displaystyle b} .

6 Практические применения криптографических конструкций

Примеров алгоритмов, устойчивых к квантовым атакам, крайне мало. Но несмотря на больший уровень криптографической устойчивости, постквантовые алгоритмы неспособны вытеснить современные криптосистемы (RSA, DSA, ECDSA и др.).

Рассмотрим нападения на криптосистему с открытым ключом, а именно на алгоритм шифрования McEliece, который использует двоичные коды Гоппы[en]. Первоначально Роберт Мак-Элис ] представил документы, в которых коды длиной {\displaystyle n} взламываются за простых операций. Таким образом, требуется выбирать не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций. Несколько последующих работ сократили количество операций атаки до , но значительно меньше , если {\displaystyle n} большое. Поэтому улучшенные атаки до сих пор используют простых операций. Что касается квантовых компьютеров, то их использование приведет лишь к уменьшению константы {\displaystyle 0,5}, что совсем незначительно сократит количество операций, необходимых для взлома этого алгоритма.

Если система шифрования McEliece так хорошо защищена, то почему она не приходит на смену RSA? Все дело в эффективности — в частности, в размере ключа. Открытый ключ McEliece использует примерно ≈ бит, в то время как открытому ключу RSA достаточно около бит. Если бит для McEliece, будет меньше бит для RSA, но реальные уровни безопасности, такие как , позволяют RSA иметь открытый ключ в несколько тысяч бит, в то время как для McEliece размер ключа приближается к миллиону бит.

7 Квантовая угроза

В последнее время широкую популярность получают квантовые вычисления. Если в классическом компьютере наименьшая единица информации представляется битом, который может принимать значение либо 0, либо 1 в одно время, то в квантовом эту роль выполняют кубиты. Их особенность состоит в том, что кубит может находиться и в состоянии 0, и в состоянии 1 одновременно. Это и дает квантовым компьютерам их превосходящую вычислительную мощь. Например, если мы рассматриваем четыре бита информации, то из всевозможных 16 состояний мы можем выбрать лишь одно в один момент времени. 4 кубита же могут находиться в 16 состояниях одновременно, то есть в суперпозиции, и данная зависимость растет экспоненциально с каждым новым кубитом.

Если в классическом компьютере логические элементы получают на вход биты информации, а на выходе выдают однозначно определенный результат, то в квантовом компьютере в качестве логического элемента берется так называемый квантовый гейт (quantim gate), который манипулирует значением целой суперпозиции.

Важное явление, свойственное кубитам, – это запутанность. Например, имеем два запутанных кубита. Измерение состояния одного из них поможет узнать информацию о состоянии его пары без необходимости какой-либо проверки.

Следует отметить, что квантовый компьютер — это не замена привычным нам классическим, так как они быстрее лишь в выполнении вычислительных операций, где необходимо использовать всевозможные суперпозиции. Так что для просмотра видео с котиками использовать такую машину совсем нецелесообразно.

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

7.1 Об алгоритме Шора

Модификация данного алгоритма позволяет решить и задачу дискретного логарифмирования. Обобщенно метод Шора состоит в сведении сложновычислимой на классическом компьютере задачи к вычислению порядка некой функции. Если рассматривать разложение числа на множители, или задачу факторизации, то в качестве той самой функции берется f(x)=ax(modN), где N− число, которое раскладывается, а a−специально подобранное значение, взаимно простое с N.Далее по ходу алгоритма находится период функции w, который удовлетворяет соотношению:f(x+w)=f(x) и, как следствие, выполняется aw=1(modN). По найденном периоду вычислить собственный делитель числа N можно с помощью алгоритма Евклида: gcd(aw2,N).

Для того, чтобы решить задачу дискретного логарифмирования, то есть, найти такое k по данным y=gk, необходимо вычислить порядок другой функции, а именно: f(x1,x2)=gx1yx2, где g− образующая группы c числом элементов, равным q. Период функции представляется парой чисел (w1,w2): f(w1+x1,w2+x2)=f(x1,x2). Тогда решение задачи дискретного логарифмирования будет иметь вид: k=−w1w2(modq).

Таким образом, в методе Шора можно выделить квантовую и классическую часть, причем задача квантовой части алгоритма состоит в отыскании периода функции с использованием метода суперпозиции.

Неудивительно, что существование подобных алгоритмов и тенденция к разработке квантовых компьютеров подтолкнули специальные организации к размышлениям. Агентством национальной безопасности США, например, еще в 2015 году был анонсирован план перехода к алгоритмам, устойчивым к атаке на квантовом компьютере. А в 2016 году NIST США официально объявил о о запуске конкурса заявок на разработку алгоритмов постквантовой криптографии.

Постквантовая криптография не ограничивается одним примитивом, на самом деле, на данный момент рассматриваются несколько кандидатов. В их число могут, например, входить быстрые криптографические протоколы на решетках, схемы на хэш-функциях (например, подпись Меркла) и криптосистемы, основанные на некоммутативной алгебре (например, на группе кос). Свой выбор мы остановили на альтернативе, тесно связанной с эллиптическими кривыми (ведь мы их так любим!), а именно, с изогениями.

7.2 изогения – рациональное отображение и его использование в криптографии

Для каждой изогении существует единственная дуальная изогения, выполняющая обратное преобразование. То есть, если изогения имеет следующий вид: , то дуальная к ней:

Если перемножить изогению и дуальную к ней, получим точку кривой E2, умноженную на целое число l, которую называют степенью изогении. Изогении простых степеней могут задавать перестановки на множестве j−инвариантов изогенных кривых. А последовательное наложение графов изогенных эллиптических кривых позволяет получить просто космически красивую звезду изогенных кривых, как на рисунке ниже.

Возможность применения изогений для построения криптосистем была предложена сравнительно недавно. В 2003 году автором E. Teske была опубликована работа, где изогении использовались в схеме с возможностью депонирования ключей. В 2006 году А. Г. Ростовцевым и А. Столбуновым схема шифрования Эль-Гамаля была адаптирована под изогении эллиптических кривых. В том же 2006 году для построения хэш-функций было предложено использовать графы изогенных суперсингулярных кривых. Важным и, можно сказать, переломным моментом в исследовании изогений является работа, опубликованная в 2010 году, где предлагается квантовый алгоритм, решающий задачу нахождения изогений несуперсингулярных кривых за субэкспоненциальное время. С этого момента исследования стали больше ориентированы на суперсингулярные кривые. Так, в сети уже можно найти схемы шифрования с открытым ключом, доказательства с нулевым разглашением, схему неоспоримой подписи и подписи вслепую.

7.3. Microsoft SIDH

Компания Microsoft тоже не осталась в стороне и в 2016 году выпустила библиотеку SIDH(Supersingular Isogeny Key Exchange) с открытым исходным кодом. Одним из преимуществ данной библиотеки является возможность использования эллиптических кривых в форме Монтгомери, которые защищают от атак по времени.

SIDH реализована на языке C и поддерживает использование Microsoft Visual Studio на OC Windows и LNU GCC и clang на OC Linux. В библиотеке представлена реализация базовых арифметических функций с возможностью поддержки различных платформ, включая x64, x86 и ARM. Большим плюсом к производительности является оптимизированная реализация операций на эллиптических кривых.
В библиотеке реализован протокол разделения ключа Диффи-Хеллмана на изогениях суперсингулярных кривых.

Эта схема была предложена авторами Jao и DeFeo. Упрощенно ее можно описать следующим образом. В качестве параметров криптосистемы используется общеизвестная суперсингулярная кривая E0 и зафиксированные на ней точки PA,QA,PB,QB. Для удобства за ходом протокола можно следить на рисунке ниже.

Пусть Алиса хочет разделить с Бобом не жизнь, а закрытый ключ. Для этого она генерирует случайные числа mA,nA и строит изогению ϕA:E0→EA, где ядро задается как .
Боб выполняет те же действия, но только строит уже изогению , где в качестве ядра выбирается .

Изогении ϕA и ϕB являются секретными и кому попало не передаются. Однако, и Боб, и Алиса могут без каких-либо последствий разделить точки на своих изогенных кривых, к тому же, переданы могут быть и сами кривые. Так и происходит на самом деле. Данный этап обозначен на рисунке пунктирной линией. Алиса передает Бобу точки ϕA(PB) и ϕA(QB), и саму кривую EA. Боб делает тоже самое: передает Алисе точки ϕB(PA) и ϕB(QA и кривую EB.

А это вообще законно?! Можешь быть спокоен, %username%, зная обе изогенные кривые, злоумышленник не сможет вычислить саму изогению.

Итак, Алиса и Боб обменялись данными, теперь подходим к завершающему и невероятно красивому этапу, а именно, к получению общего ключа. Зная образы точек PA и QA на кривой EB и случайные числа mB и nB, Боб сможет легко построить изогению ϕA′, а Алиса, обладающая тем же объемом информации, сможет построить изогению ϕB′. Изящное решение заключается в том, что изогении ϕA′ и ϕB′ приведут наших собеседников к кривой EAB, и в качестве ключа может быть взят ее j−инвариант.

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

CurveIsogeny = SIDH_curve_allocate(CurveIsogenyData);
    if (CurveIsogeny == NULL) {
        Status = CRYPTO_ERROR_NO_MEMORY;
        goto cleanup;
    }
    Status = SIDH_curve_initialize(CurveIsogeny, &random_bytes_test, CurveIsogenyData);
    if (Status != CRYPTO_SUCCESS) {
        goto cleanup;
    }

Сама структура:

typedef struct
{    
    CurveIsogeny_ID  CurveIsogeny;                             
    unsigned int     pwordbits;                               
    unsigned int     owordbits;                               
    unsigned int     pbits;                                   
    uint64_t         prime[MAXWORDS_FIELD];                   
    uint64_t         A[MAXWORDS_FIELD];                       
    uint64_t         C[MAXWORDS_FIELD];                       
    unsigned int     oAbits;                                   
    uint64_t         Aorder[MAXWORDS_ORDER];                  
    unsigned int     oBbits;                                  
    unsigned int     eB;                                      
    uint64_t         Border[MAXWORDS_ORDER];                   
    uint64_t         PA[2*MAXWORDS_FIELD];                    
    uint64_t         PB[2*MAXWORDS_FIELD];                    
    unsigned int     BigMont_A24;                             
    uint64_t         BigMont_order[BIGMONT_MAXWORDS_ORDER];   
    uint64_t         Montgomery_R2[MAXWORDS_FIELD];           
    uint64_t         Montgomery_pp[MAXWORDS_FIELD];           
    uint64_t         Montgomery_one[MAXWORDS_FIELD];          
} CurveIsogenyStaticData;

Чтобы Алисе и Бобу обменяться ключами, достаточно вызвать пару функций, которые не обязывают знать того, что же творится «под капотом». Генерация ключей происходит с помощью функций:

Status = KeyGeneration_A(PrivateKeyA,PublicKeyA, CurveIsogeny);

и

Status = KeyGeneration_B(PrivateKeyB,PublicKeyAB CurveIsogeny);

Алиса и Боб обмениваются вычисленными открытыми ключами и находят общий ключ:

Status = SecretAgreement_A(PrivateKeyA, PublicKeyB, SharedSecretA, false, CurveIsogeny); 

и

Status = SecretAgreement_B(PrivateKeyB, PublicKeyA, SharedSecretB, false, CurveIsogeny); 

Среди функций в библиотеке можно выделить и базовые арифметические, которые помогут в реализации своих протоколов. Это, например, j_inv, вычисляющая j-инвариант эллиптической кривой, inv_3_way, находящая значение мультипликативно обратного, удвоение точки и сложение точек – xDBLADD, утроение точки – xTPL и т.д. С полным описанием вы можете ознакомиться в публикации.

Выводы

Безусловно, пока сложно судить о необходимости постквантовой криптографии, когда мощного квантового компьютера, по сути, и нет… Однако суета в NSA и NIST не могут не наводить на подозрения. О реальных мотивах такой спешки нам остается только догадываться. В любом случае, никогда не помешает перестраховаться и начать изучение нового и интересного направления в криптографии, тем более, если это вполне осуществимо на практике.

Вау!! 😲 Ты еще не читал? Это зря!

• Криптография на решетках
• Алгоритм Шора

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