01-09-2023
McEliece — криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году Робертом Мак-Элисом[1]. Это была первая схема, использующая рандомизацию в процессе шифрования. Алгоритм не получил широко признания в криптографии, но в то же время является кандидатом для постквантовой криптографии, т.к. устойчив к атаке с использованием Алгоритма Шора [2].
Алгоритм основан на сложности декодирования полных линейных кодов (общая задача декодирования является NP-сложной) [3].
Для описания закрытого ключа выбран код исправляющий ошибки, для которого известен эффективный алгоритм декодирования и который может исправить ошибок. Алгорим использует двоичные коды Гоппа, которые легко декодируются благодаря алгоритму Петерсона. Открытый ключ получается при помощи маскировки выбранного кода как полного линейного. Для этого производящая матрица умножается на две случайных невырожденных матрицы и (см. алгоритм работы).
Существует несколько вариантов криптосистемы, использующие различные типы кодов. Большинство из них оказываются менее защищенными. Отдельного рассмотрения заслуживает вопрос выбора параметров криптосистемы[4].
До сих пор, McElice с кодами Гоппы не поддается криптоанализу. Наиболее известные атаки используют алгоритм декодирования множества данныx. Последние работы описывают как атаки на систему, так и ее защиту[5]. В других работах показано, что для квантовых вычислений размер ключа должен быть увеличен на четыре порядка из-за усовершенствования декодирования множества данных.
Криптосистема имеет несколько преимуществ, например, над bech.cr.yp.to) и с ростом длины ключа степень защиты растет гораздо быстрее. Долгое время считалось, что McEliece не может быть использована для ЭЦП. Однако оказалось возможным построить схему для ЭЦП на основе криптосистемы Niederreiter (модификация МcEliece).
Из-за недостатков McEliece используется редко. Одно из исключений - использование McElice для шифрования в Freenet-подобной сети ENTROPY. Существуют реализации McEliece на ПЛИС[6].
Содержание |
McElice состоит из трех алгоритмов:
Все пользователи в системе совместно используют параметры безопасности:
Пусть Боб хочет передать сообщение Алисе, чей открытый ключ .
После получения сообщения , Алиса выполняет следующие действия для дешифрования сообщения:
Покажем, что выполняется главное свойство криптосистемы, т.е что
Боб посылает . Алиса вычисляет . Поскольку - матрица перестановки, то вес не более, чем .
Код Гоппа исправляет до ошибок. Расстояние Хемминга . Поэтому Алиса получает верное сообщение . После этого Алиса вычисляет исходное сообщение .
Пусть, например, мы пользуемся кодом Хемминга, который исправляет все единичные ошибки. Производящая матрица
Алиса выбирает матрицу
и матрицу перестановки
Тогда
Если Боб хочет послать сообщение Алисе, то он сначала генерирует вектор с весом , например и вычисляет шифротекст и посылает его Алисе.
После получения сообщения, Алиса сначал вычисляет , где
получая .
После этого Алиса расшифровывает используя быстрый алгоритм декодирования (в этом примере - алгоритм Хэмминга. Синдромом является , таким образом ошибка произошла в позиции (подробности опущены). Тогда сообщение будет . получается путем отбрасывания лишних битов у . Вследствии "правильного" выбора , Алиса знает, что и может теперь получить из путем умножения на матрицу
В итоге Алиса получает
В литературе описано достаточно большое количество атак на McElice. Некоторые атаки, называемые структурными атаками, основаны на получении закрытого ключа из открытого [7]. Другие атаки направлены на получения исходного текста сообщения из шифрованного сообщения. Большинство из них основаны на декодировании множества данных (ISD (англ.)) или на алгоритме Дня Рождения, их обобщениях и улучшениях. Существуют такие атаки, как, например, итерационное декодирование [8] и статическое декодирование, но они не являются успешными. Атака ISD оказалась наименее сложной. В последние годы было описано нескольно алгоритмов и их улучшения. Наиболее важные перечислены в таблице вместе с их двоичным показателем затрат для декодирования (1024, 524, 50) кода Гоппа (стандартные параметры для McEliece[1]). Для этих алгоритом известны их предельные показатели [9].
Год | Алгоритм | Сложность () |
---|---|---|
1986 | Адамс-Мейер | 80.7 |
1988 | Ли-Брикелл | 70.89 |
1989 | Штерн | 66.21 |
1994 | Кантеаут-Шабанн | 65.5 |
1998 | Кантеаут-Шабант | 64.1 |
2008 | Бернштейн-Ланг-Петерс | 60.4 |
2009 | Финиаз-Сендреир | 59.9 |
Основные недостатки криптосистемы McEliece:
Степень защиты | Параметры ,кол-во ошибок | Размер открытого ключа в Кбит | Размер секретного ключа в Кбит |
---|---|---|---|
Краткосрочная (60 бит) | (1024, 644,38),38 | 644 | (0.38, 10, 405) |
Среднесрочная (80 бит) | (2048, 1751, 27),27 | 3,502 | (0.30, 22, 2994) |
Долгосрочная (256 бит) | (6624, 5129, 115),117 | 33,178 | (1.47, 104, 25690) |
Это заготовка статьи по криптографии. Вы можете помочь проекту, исправив и дополнив её. |
McEliece.