McEliece

McEliece — криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году . Это была первая схема, использующая в процессе шифрования. Алгоритм не получил широко признания в криптографии, но в то же время является кандидатом для постквантовой криптографии, так как устойчив к атаке с использованием Алгоритма Шора. Алгоритм основан на сложности декодирования полных линейных кодов (общая задача декодирования является NP-сложной). Для описания закрытого ключа выбран код исправляющий ошибки, для которого известен эффективный алгоритм декодирования и который может исправить ошибок. Алгоритм использует двоичные коды Гоппа, которые легко декодируются благодаря алгоритму Петерсона. Открытый ключ получается при помощи маскировки выбранного кода как полного линейного. Для этого порождающая матрица сначала умножается справа на , а затем на невырожденную матрицу слева (см. ). Существует несколько вариантов криптосистемы, использующих различные типы кодов. Большинство из них оказываются менее защищенными. Отдельного рассмотрения заслуживает вопрос выбора параметров криптосистемы. До сих пор McElice с кодами Гоппы не поддается криптоанализу. Наиболее известные атаки используют алгоритм . Последние работы описывают как атаки на систему, так и её защиту. В других работах показано, что для квантовых вычислений размер ключа должен быть увеличен на четыре порядка из-за усовершенствования декодирования множества данных. Криптосистема имеет несколько преимуществ, например, над RSA. Шифрование и дешифрование проходит быстрее и с ростом длины ключа степень защиты данных растет гораздо быстрее. Долгое время считалось, что McEliece не может быть использована для ЭЦП. Однако оказалось возможным построить схему для ЭЦП на основе криптосистемы Нидеррайтера (модификация МcEliece). Поскольку в зависимости от используемых кодов, эти две криптосистемы выражают одну и ту же кодовую задачу, на сегодняшний день, можно утверждать, что McEliece применим в задачах аутентификации. Из-за McEliece используется редко. Одно из исключений — использование McElice для шифрования в Freenet-подобной сети ENTROPY.