Российская компания «Криптонит» представила на «РусКрипто’2024» криптографический механизм «Кодиеум». Он устойчив ко всем известным атакам и останется стойким даже в случае появления мощного квантового компьютера.
В экспертном сообществе не раз обсуждалась «квантовая угроза». Её суть в том, что стойкость ряда популярных криптографических механизмов базируется на математических задачах, вычислительно сложных для классических компьютеров, но решаемых с помощью квантовых алгоритмов за сравнительно небольшое время. Поэтому разработка квантовых компьютеров создаёт вызовы для криптографии.
На квантовых компьютерах уже решают ряд прикладных задач из области оптимизации, но пока их производительность недостаточна, чтобы взламывать современные криптографические алгоритмы.
Всё изменится после появления достаточно мощного квантового компьютера. Такого, на котором можно будет запустить квантовый алгоритм Шора и найти разложение на множители целого числа большого размера. Сложность этой задачи в настоящее время используется для защиты наших коммуникаций через интернет.
Нарушитель, обладающий таким квантовым компьютером, сможет успешно подделать электронные подписи под сообщениями, а также читать нашу переписку в режиме реального времени. Это станет возможным после взлома процедуры обмена ключами по протоколу Диффи — Хеллмана, которая используется для установления защищённой связи между абонентами.
Протокол Диффи – Хеллмана нашёл самое широкое применение. Без него не обходится ни установление защищённого подключения к сайтам, ни сохранение тайны переписки в мессенджерах, ни защита банковских операций. Последствия взлома этого механизма будут просто катастрофическими.
Работа на упреждение
О том, насколько важны постквантовые разработки, говорит тот факт, что Национальный институт стандартов США (NIST) с 2016 года проводит масштабный многолетний конкурс по этой тематике. Работы по созданию новых стандартов и механизмов защиты интернета от появления мощного квантового компьютера ведутся и в России. Так, в составе Технического комитета № 26 РФ с 2019 года разработкой стандартов постквантовой криптографии занимается рабочая группа 2.5. Руководителями этой группы являются сотрудники компании «Криптонит». В качестве превентивной меры специалисты компании совместно с другими участниками ТК26 разрабатывают набор криптографических механизмов, которыми можно будет заменить классические алгоритмы.
Ранее в «Криптоните» уже представили первую российскую постквантовую схему электронной подписи «Шиповник» на замену классического алгоритма ГОСТ 3410-2018, а сейчас сотрудники лаборатории криптографии Виктория Высоцкая и Иван Чижов представили «Кодиеум» — постквантовую схему инкапсуляции ключа как потенциальную замену протоколу Диффи — Хеллмана.
В отличие от него, схема «Кодиеум» вместо «квантово-неустойчивых» задач факторизации и дискретного логарифмирования использует задачу декодирования. Известно, что эта задача является вычислительно сложной для случайного кода не только для суперкомпьютеров классической архитектуры, но и для квантовых компьютеров. Считается, что никакая вычислительная система не сможет быстро исправить ошибку в сообщении, которое ранее было закодировано случайным кодом.
Подходы к созданию KEM
По своей сути протоколы инкапсуляции ключа (KEM) являются функциональными аналогами протокола Диффи — Хеллмана, однако в KEM ключ не создаётся совместно участниками, а генерируется одной стороной, шифруется и передаётся второй.
Для выработки ключа в KEM используются алгоритмы шифрования, с открытым ключом. С их помощью можно зашифровать сообщение, не зная ключа расшифрования. Это как закрыть замок, не имея ключа, который его откроет.
Стойкость схемы «Кодиеум» основа на сложности решения задачи синдромного декодирования (кода Гоппы). При шифровании такой криптосистемой сообщение представляется как вектор ошибки малого веса. Весь процесс моделирует канал связи с помехами, приводящими к искажению сообщения.
За то, каким образом «Кодиеум» преобразовывает сообщение в кодовое слово, отвечает код, исправляющий ошибки. От его выбора зависит стойкость всей схемы. Это самый важный этап разработки. Здесь требуется изучить разные классы кодов, сравнить их, выбрать нужные преобразования. Именно эта сложная исследовательская работа и была выполнена в «Криптоните».
Особенности «Кодиеума»
В ходе исследования специалисты компании отметили, что зачастую в зарубежных алгоритмах не приводится обоснование выбора компонентов схемы инкапсуляции ключа. Если же изучить аргументы за и против каждого компонента и выбрать на каждом шаге наилучший математически обоснованный подход, то можно построить оптимальную схему. «В нашей схеме используется код, задачам на котором мы доверяем. Преобразование обосновано в классической и квантовой моделях», — пояснила ведущий автор исследования Виктория Высоцкая. «Кодиеум» разрабатывался в том числе для защиты сетей связи. Значит, нужно было выбрать его параметры так, чтобы снизить накладные расходы и не жертвовать скоростью передачи данных.
«Кодиеум» построен на основе кодов Гоппы. Это широкий класс кодов, разработанный советским учёным-математиком Валерием Денисовичем Гоппой. За эту работу он в 1972 году получил престижную премию Общества проблем теории информации Института инженеров по электротехнике и электронике (IEEE).
Помимо кодов Гоппы для криптографии представляют интерес и другие классы кодов. Например, обобщённые коды Сриваставы, или более широкий класс альтернативных кодов, получающихся из широко используемых на практике кодов Рида — Соломона (например, для защиты от потери данных, записанных на DVD, используются именно эти коды). При этом на сегодня схемы инкапсуляции ключа, построенные на альтернативах кодам Гоппы, считаются малоизученными, поэтому их применению должны предшествовать дополнительные исследования.
Заключение
Разработке «Кодиеума» предшествовал длительный анализ существующих подходов к построению криптографических схем, основанных на кодах, исправляющих ошибки. По его результатам описаны преимущества и недостатки различных подходов к проектированию схем инкапсуляции ключа на основе кодов. Предварительные результаты этого исследования были впервые представлены на конференции «РусКрипто’23», а сейчас они дополнены и готовятся к публикации в рецензируемом научном журнале.
Переход на постквантовые криптографические алгоритмы актуален уже сейчас, поскольку многие данные требуется сохранять в секрете длительное время. Сейчас они передаются через интернет в зашифрованном виде и могут собираться промежуточными узлами злоумышленника с целью расшифровать их позже, после создания квантового компьютера достаточной производительности. Чем раньше мы внедрим постквантовые криптографические механизмы, тем больше циркулирующих в сети данных мы сможем сохранить в секрете, чтобы обезопасить своё будущее.
Источник информации и фото: НПК «Криптонит»