Криптосистема Мак-Элиса: Асимметричное шифрование и постквантовая криптография

Введение

Асимметричный алгоритм шифрования, разработанный Робертом МакЭлисом.

В криптографии криптосистема МакЭлиса — это асимметричный алгоритм шифрования, разработанный в 1978 году Робертом МакЭлисом. Это была первая схема такого рода, использующая рандомизацию в процессе шифрования. Алгоритм не получил широкого признания в криптографическом сообществе, но является кандидатом на "постквантовую криптографию", поскольку устойчив к атакам с использованием алгоритма Шора и, в более общем случае, к измерению состояний косета с использованием выборочного преобразования Фурье. Алгоритм основан на сложности декодирования общего линейного кода (которая, как известно, является NP-трудной задачей). Для описания секретного ключа выбирается код, исправляющий ошибки, для которого известен эффективный алгоритм декодирования, способный исправлять ошибки. Оригинальный алгоритм использует двоичные коды Гоппа (коды подполей алгебраико-геометрических кодов кривой рода 0 над конечными полями характеристики 2); эти коды могут быть эффективно декодированы благодаря алгоритму, разработанному Паттерсоном. Открытый ключ выводится из секретного ключа путем маскировки выбранного кода под общий линейный код. Для этого матрица-генератор кода возмущается двумя случайно выбранными невырожденными матрицами и (см. ниже). Существуют варианты этой криптосистемы, использующие различные типы кодов. Большинство из них оказались менее безопасными и были взломаны с помощью структурного декодирования. МакЭлис с кодами Гоппа пока успешно противостоит криптоанализу. Наиболее эффективные известные атаки используют алгоритмы декодирования информационных множеств. В статье 2008 года описывается как атака, так и способ ее устранения. Другая статья показывает, что для квантовых вычислений размеры ключей необходимо увеличить в четыре раза из-за усовершенствования алгоритмов декодирования информационных множеств. Криптосистема МакЭлиса имеет некоторые преимущества по сравнению, например, с RSA: шифрование и расшифрование выполняются быстрее. Долгое время считалось, что МакЭлис нельзя использовать для создания цифровых подписей. Однако схему подписи можно построить на основе схемы Нидеррайтера — двойственного варианта схемы МакЭлиса. Одним из основных недостатков МакЭлиса является то, что секретные и открытые ключи представляют собой большие матрицы. При стандартном выборе параметров открытый ключ имеет длину 512 килобит.

In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling. The algorithm is based on the hardness of decoding a general linear code (which is known to be NP hard). For a description of the private key, an error correcting code is selected for which an efficient decoding algorithm is known, and which is able to correct errors. The original algorithm uses binary Goppa codes (subfield codes of algebraic geometry codes of a genus 0 curve over finite fields of characteristic 2); these codes can be efficiently decoded, thanks to an algorithm due to Patterson. The public key is derived from the private key by disguising the selected code as a general linear code. For this, the code's generator matrix is perturbated by two randomly selected invertible matrices and (see below). Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by structural decoding. McEliece with Goppa codes has resisted cryptanalysis so far. The most effective attacks known use information set decoding algorithms. A 2008 paper describes both an attack and a fix. Another paper shows that for quantum computing, key sizes must be increased by a factor of four due to improvements in information set decoding. The McEliece cryptosystem has some advantages over, for example, RSA. The encryption and decryption are faster. For a long time, it was thought that McEliece could not be used to produce signatures. However, a signature scheme can be constructed based on the Niederreiter scheme, the dual variant of the McEliece scheme. One of the main disadvantages of McEliece is that the private and public keys are large matrices. For a standard selection of parameters, the public key is 512 kilobits long.

Определение схемы

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

Структурные атаки

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

Кандидат на постквантовое шифрование

Вариант этого алгоритма, объединенный с NTS KEM, был представлен и отобран в ходе третьего раунда конкурса NIST по постквантовой криптографии.