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

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

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

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

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

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

Определение схемы [ править ]

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

Все пользователи в развертывании 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]