Криптосистема МакЭлиса

В криптографии криптосистема МакЭлиса представляет собой асимметричный алгоритм шифрования, разработанный в 1978 году Робертом МакЭлисом . ^{[ 1 ]} Это была первая такая схема, в которой использовалась рандомизация в процессе шифрования . Алгоритм никогда не получал большого признания в криптографическом сообществе, но является кандидатом на « постквантовую криптографию », поскольку он невосприимчив к атакам с использованием алгоритма Шора и, в более общем плане, к измерению состояний смежного класса с использованием выборки Фурье. ^{[ 2 ]}

Алгоритм основан на сложности декодирования общего линейного кода (который известен как NP-трудный код) . ^{[ 3 ]}). Для описания закрытого ключа выбирается код, исправляющий ошибки , для которого известен эффективный алгоритм декодирования, способный исправить ошибки. $t$ ошибки. В исходном алгоритме используются двоичные коды Гоппы (коды подполей кодов алгебраической геометрии кривой рода 0 над конечными полями характеристики 2); эти коды можно эффективно декодировать благодаря алгоритму Паттерсона. ^{[ 4 ]} Открытый ключ получается из закрытого ключа путем маскировки выбранного кода под общий линейный код. кода Для этого матрица-генератор $G$ возмущается двумя случайно выбранными обратимыми матрицами $S$ и $P$ (см. ниже).

Существуют варианты этой криптосистемы, использующие разные типы кодов. Большинство из них оказались менее безопасными; они были разбиты путем структурной декодировки .

МакЭлис с кодами Гоппы до сих пор сопротивлялся криптоанализу. Наиболее эффективные из известных атак используют алгоритмы декодирования набора информации . В документе 2008 года описаны как атака, так и ее исправление. ^{[ 5 ]} Другая статья показывает, что для квантовых вычислений размеры ключей необходимо увеличить в четыре раза из-за улучшений в декодировании набора информации. ^{[ 6 ]}

Криптосистема McEliece имеет некоторые преимущества перед, например, RSA . Шифрование и дешифрование выполняются быстрее. ^{[ 7 ]} Долгое время считалось, что McEliece нельзя использовать для создания подписей . Однако схема подписи может быть построена на основе схемы Нидеррайтера , двойственного варианта схемы МакЭлиса. Одним из основных недостатков McEliece является то, что закрытые и открытые ключи представляют собой большие матрицы. Для стандартного выбора параметров длина открытого ключа составляет 512 килобит.

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

McEliece состоит из трех алгоритмов: вероятностного алгоритма генерации ключей, который создает открытый и закрытый ключи, вероятностного алгоритма шифрования и детерминированного алгоритма дешифрования.

Все пользователи в развертывании McEliece имеют общий набор общих параметров безопасности: $n,k,t$ .

Генерация ключей

Принцип заключается в том, что Алиса выбирает линейный код. $C$ из некоторого семейства кодов, для которых она знает эффективный алгоритм декодирования, и сделать $C$ общеизвестно, но держите алгоритм декодирования в секрете. Такой алгоритм декодирования требует не просто знания $C$ , в смысле знания произвольной порождающей матрицы, но требует знания параметров, используемых при указании $C$ в выбранном семействе кодов. Например, для двоичных кодов Гоппы этой информацией будут полином Гоппы и локаторы кода. Следовательно, Алиса может опубликовать соответствующим образом запутанную порождающую матрицу $C$ .

Более конкретно, шаги заключаются в следующем:

Алиса выбирает двоичный файл $(n,k)$ -линейный код $C$ способный (эффективно) исправлять $t$ ошибки какого-либо большого семейства кодов, например двоичных кодов Гоппы. Этот выбор должен привести к созданию эффективного алгоритма декодирования. $A$ . Пусть также $G$ быть любой порождающей матрицей для $C$ . Любой линейный код имеет множество порождающих матриц, но часто существует естественный выбор именно этого семейства кодов. Знание этого раскроет $A$ поэтому это следует держать в секрете.
Алиса выбирает случайный $k\times k$ двоичная несингулярная матрица $S$ .
Алиса выбирает случайный $n\times n$ матрица перестановок $P$ .
Алиса вычисляет $k\times n$ матрица ${\hat {G}}=SGP$ .
Открытый ключ Алисы $({\hat {G}},t)$ ; ее личный ключ $(S,P,A)$ . Обратите внимание, что $A$ могут быть закодированы и сохранены как параметры, используемые для выбора $C$ .

Шифрование сообщений

Предположим, Боб желает послать сообщение m Алисе, открытый ключ которой $({\hat {G}},t)$ :

Боб кодирует сообщение $m$ как двоичную строку длины $k$ .
Боб вычисляет вектор $c^{\prime }=m{\hat {G}}$ .
Боб генерирует случайный $n$ -битовый вектор $z$ содержащий ровно $t$ единицы (вектор длины $n$ и вес $t$ ) ^{[ 1 ]}
Боб вычисляет зашифрованный текст как $c=c^{\prime }+z$ .

Расшифровка сообщения

При получении $c$ , Алиса выполняет следующие шаги для расшифровки сообщения:

Алиса вычисляет обратную величину $P$ (т.е. $P^{-1}$ ).
Алиса вычисляет ${\hat {c}}=cP^{-1}$ .
Алиса использует алгоритм декодирования $A$ декодировать ${\hat {c}}$ к ${\hat {m}}$ .
Алиса вычисляет $m={\hat {m}}S^{-1}$ .

Доказательство расшифровки сообщения

Обратите внимание, что ${\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}$ , и это $P$ является матрицей перестановок, поэтому $zP^{-1}$ имеет вес $t$ .

Код Гоппы $G$ могу исправить до $t$ ошибки и слово $mSG$ находится на расстоянии максимум $t$ от $cP^{-1}$ . Следовательно, правильное кодовое слово ${\hat {m}}=mS$ получается.

Умножение на обратное $S$ дает $m={\hat {m}}S^{-1}=mSS^{-1}$ , которое представляет собой обычное текстовое сообщение.

Размеры ключей

Потому что в матрице есть свободный выбор $S$ , принято выражать ${\hat {G}}$ в «систематической форме», так что последнее $k$ столбцы соответствуют единичной матрице ${\hat {G}}=({\tilde {G}}|I)$ . Это уменьшает размер ключа до $(n-k)\times k$ . ^{[ 8 ]}^{[ 9 ]} МакЭлис первоначально предложил размеры параметров безопасности $n=1024,k=524,t=50$ , ^{[ 1 ]} в результате размер открытого ключа составит 524 × (1024–524) = 262 000 бит . Недавний анализ предполагает размеры параметров $n=2048,k=1751,t=27$ для 80- битной безопасности при использовании стандартного алгебраического декодирования или $n=1632,k=1269,t=34$ при использовании спискового декодирования для кода Гоппы размеры открытого ключа составляют 520 047 и 460 647 бит соответственно. ^{[ 5 ]} Для устойчивости к квантовым компьютерам размеры $n=6960,k=5413,t=119$ с кодом Гоппы, дающим размер открытого ключа 8 373 911 бит . ^{[ 10 ]} В третьем раунде подачи заявки на пост-квантовую стандартизацию NIST самый высокий уровень безопасности, уровень 5, дается для наборов параметров 6688128, 6960119 и 8192128. Параметры: $n=6688,k=128,t=13$ , $n=6960,k=119,t=13$ , $n=8192,k=128,t=13$ соответственно.

Атаки

Атака состоит из злоумышленника, который знает открытый ключ $({\hat {G}},t)$ но не закрытый ключ, выводящий открытый текст из некоторого перехваченного зашифрованного текста $y\in \mathbb {F} _{2}^{n}$ . Такие попытки должны быть неосуществимыми.

Есть два основных направления атак МакЭлиса:

Грубая сила/неструктурированные атаки

Злоумышленник знает ${\hat {G}}$ , порождающая матрица $(n,k)$ код ${\hat {C}}$ который комбинаторно способен исправить $t$ ошибки. Злоумышленник может игнорировать тот факт, что ${\hat {C}}$ на самом деле это запутывание структурированного кода, выбранного из определенного семейства, и вместо этого просто использование алгоритма декодирования с помощью любого линейного кода. Существует несколько таких алгоритмов, например, прохождение каждого кодового слова кода, синдромное декодирование или декодирование набора информации .

Однако декодирование общего линейного кода, как известно, является NP-трудным . ^{[ 3 ]} однако все вышеупомянутые методы имеют экспоненциальное время работы.

В 2008 году Бернштейн, Ланге и Петерс ^{[ 5 ]} описал практическую атаку на оригинальную криптосистему МакЭлиса с использованием метода декодирования набора информации Стерна. ^{[ 11 ]} Используя параметры, первоначально предложенные МакЭлисом, атаку можно было осуществить за 2 ^60.55 битовые операции. Поскольку атака является до неприличия параллельной (никакая связь между узлами не требуется), ее можно выполнить за несколько дней на скромных компьютерных кластерах.

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

Вместо этого злоумышленник может попытаться восстановить «структуру» $C$ , тем самым восстанавливая эффективный алгоритм декодирования $A$ или другой достаточно сильный и эффективный алгоритм декодирования.

Семейство кодов, из которых $C$ Выбор полностью определяет, возможно ли это для злоумышленника. Для МакЭлиса было предложено множество семейств кодов, и большинство из них оказались полностью «сломанными» в том смысле, что были обнаружены атаки, восстанавливающие эффективный алгоритм декодирования, например коды Рида-Соломона .

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

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

Вариант этого алгоритма в сочетании с НТС-КЭМ. ^{[ 12 ]} был заявлен и выбран в третьем туре NIST конкурса постквантового шифрования . ^{[ 13 ]}

Ссылки

^ Jump up to: ^а ^б ^с МакЭлис, Роберт Дж. (1978). «Криптосистема с открытым ключом, основанная на алгебраической теории кодирования» (PDF) . Отчет о ходе работы DSN . 44 : 114–116. Бибкод : 1978ДСНПР..44..114М .
^ Динь, Ханг; Мур, Кристофер; Рассел, Александр (2011). Рогауэй, Филип (ред.). Криптосистемы МакЭлиса и Нидеррайтера, устойчивые к атакам квантовой выборки Фурье . Достижения в криптологии — CRYPTO 2011. Конспекты лекций по информатике. Том. 6841. Гейдельберг: Шпрингер. стр. 761–779. дои : 10.1007/978-3-642-22792-9_43 . ISBN 978-3-642-22791-2 . МР 2874885 .
^ Jump up to: ^а ^б Берлекамп, Элвин Р.; МакЭлис, Роберт Дж.; Ван Тилборг, Хенк, Калифорния (1978). «О присущей неразрешимости некоторых проблем кодирования» . Транзакции IEEE по теории информации . ИТ-24 (3): 384–386. дои : 10.1109/TIT.1978.1055873 . МР 0495180 .
^ Нью-Джерси Паттерсон (1975). «Алгебраическое декодирование кодов Гоппы». Транзакции IEEE по теории информации . ИТ-21 (2): 203–207. дои : 10.1109/TIT.1975.1055350 .
^ Jump up to: ^а ^б ^с Бернштейн, Дэниел Дж.; Ланге, Таня ; Петерс, Кристиана (8 августа 2008 г.). «Атака и защита криптосистемы МакЭлиса». Постквантовая криптография . Конспекты лекций по информатике. Том. 5299. стр. 31–46. CiteSeerX 10.1.1.139.3548 . дои : 10.1007/978-3-540-88403-3_3 . ISBN 978-3-540-88402-6 .
^ Бернштейн, Дэниел Дж. (2010). Сендрие, Николя (ред.). Гровер против МакЭлиса (PDF) . Постквантовая криптография 2010. Конспект лекций по информатике. Том. 6061. Берлин: Шпрингер. стр. 73–80. дои : 10.1007/978-3-642-12929-2_6 . ISBN 978-3-642-12928-5 . МР 2776312 .
^ «eBATS: Бенчмаркинг асимметричных систем ECRYPT» . скамейка.cr.yp.to . 25 августа 2018 года . Проверено 1 мая 2020 г.
^ Классическая команда МакЭлиса (23 октября 2022 г.). «Классический МакЭлис: консервативная криптография на основе кода: спецификация криптосистемы» (PDF) . Обзор заявок на участие в 4-м раунде NIST .
^ Таня Ланге (23 февраля 2021 г.). «Кодовая криптография III — Коды Гоппы: определение и использование» . Ютуб .
^ Даниэль Ого; и др. (7 сентября 2015 г.). «Первоначальные рекомендации по созданию долгосрочных безопасных постквантовых систем» (PDF) . PQCRYPTO: постквантовая криптография для долгосрочной безопасности .
^ Жак Стерн (1989). «Метод поиска кодовых слов малого веса». Теория кодирования и ее приложения . Конспекты лекций по информатике. Том. 388. Спрингер Верлаг. стр. 106–113. дои : 10.1007/BFb0019850 . ISBN 978-3-540-51643-9 .
^ «НТС-КЭМ» . 29 декабря 2017 года. Архивировано из оригинала 29 декабря 2017 года . Проверено 9 декабря 2020 г.
^ «Отчет о состоянии третьего раунда процесса стандартизации постквантовой криптографии NIST» (PDF) . НИСТИР : 31.

Внешние ссылки

Альфред Дж. Менезес; Скотт А. Ванстон; Эй Джей Менезес; Пол К. ван Оршот (1996). «Глава 8: Шифрование с открытым ключом» . Справочник по прикладной криптографии . ЦРК Пресс. ISBN 978-0-8493-8523-0 .
Рамшмид, Клаудия; Адамс, Дэвид (2023). McEliece Messaging: Smoke Crypto Chat — первый мобильный McEliece-Messenger, опубликованный как стабильный прототип во всем мире . Статья на портале ТК Инфо.
«Квантовые компьютеры? Код интернет-безопасности будущего взломан» . Наука Дейли . Эйндховенский технологический университет . 1 ноября 2008 г.
«Классический МакЭлис» . NIST (Представлено в проект стандартизации пост-квантовой криптографии )

[McEliece-1] Jump up to: ^а ^б ^с МакЭлис, Роберт Дж. (1978). «Криптосистема с открытым ключом, основанная на алгебраической теории кодирования» (PDF) . Отчет о ходе работы DSN . 44 : 114–116. Бибкод : 1978ДСНПР..44..114М .

[quantum-fourier-2] Динь, Ханг; Мур, Кристофер; Рассел, Александр (2011). Рогауэй, Филип (ред.). Криптосистемы МакЭлиса и Нидеррайтера, устойчивые к атакам квантовой выборки Фурье . Достижения в криптологии — CRYPTO 2011. Конспекты лекций по информатике. Том. 6841. Гейдельберг: Шпрингер. стр. 761–779. дои : 10.1007/978-3-642-22792-9_43 . ISBN 978-3-642-22791-2 . МР 2874885 .

[intractability-3] Jump up to: ^а ^б Берлекамп, Элвин Р.; МакЭлис, Роберт Дж.; Ван Тилборг, Хенк, Калифорния (1978). «О присущей неразрешимости некоторых проблем кодирования» . Транзакции IEEE по теории информации . ИТ-24 (3): 384–386. дои : 10.1109/TIT.1978.1055873 . МР 0495180 .

[Patterson-4] Нью-Джерси Паттерсон (1975). «Алгебраическое декодирование кодов Гоппы». Транзакции IEEE по теории информации . ИТ-21 (2): 203–207. дои : 10.1109/TIT.1975.1055350 .

[fix-5] Jump up to: ^а ^б ^с Бернштейн, Дэниел Дж.; Ланге, Таня ; Петерс, Кристиана (8 августа 2008 г.). «Атака и защита криптосистемы МакЭлиса». Постквантовая криптография . Конспекты лекций по информатике. Том. 5299. стр. 31–46. CiteSeerX 10.1.1.139.3548 . дои : 10.1007/978-3-540-88403-3_3 . ISBN 978-3-540-88402-6 .

[6] Бернштейн, Дэниел Дж. (2010). Сендрие, Николя (ред.). Гровер против МакЭлиса (PDF) . Постквантовая криптография 2010. Конспект лекций по информатике. Том. 6061. Берлин: Шпрингер. стр. 73–80. дои : 10.1007/978-3-642-12929-2_6 . ISBN 978-3-642-12928-5 . МР 2776312 .

[7] «eBATS: Бенчмаркинг асимметричных систем ECRYPT» . скамейка.cr.yp.to . 25 августа 2018 года . Проверено 1 мая 2020 г.

[NIST-Submission-Overview-8] Классическая команда МакЭлиса (23 октября 2022 г.). «Классический МакЭлис: консервативная криптография на основе кода: спецификация криптосистемы» (PDF) . Обзор заявок на участие в 4-м раунде NIST .

[Code-Based-Cryptography-Lecture-9] Таня Ланге (23 февраля 2021 г.). «Кодовая криптография III — Коды Гоппы: определение и использование» . Ютуб .

[PQcrypto-initial-10] Даниэль Ого; и др. (7 сентября 2015 г.). «Первоначальные рекомендации по созданию долгосрочных безопасных постквантовых систем» (PDF) . PQCRYPTO: постквантовая криптография для долгосрочной безопасности .

[11] Жак Стерн (1989). «Метод поиска кодовых слов малого веса». Теория кодирования и ее приложения . Конспекты лекций по информатике. Том. 388. Спрингер Верлаг. стр. 106–113. дои : 10.1007/BFb0019850 . ISBN 978-3-540-51643-9 .

[12] «НТС-КЭМ» . 29 декабря 2017 года. Архивировано из оригинала 29 декабря 2017 года . Проверено 9 декабря 2020 г.

[13] «Отчет о состоянии третьего раунда процесса стандартизации постквантовой криптографии NIST» (PDF) . НИСТИР : 31.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]