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

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

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

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

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

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

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

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

Все пользователи в установочном ресурсе МакЭлиса набор общих параметров безопасности: . ${\ Displaystyle п, к, т}$

Генерация ключей [ править ]

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

В частности, шаги следующие:

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

Шифрование сообщений [ править ]

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

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

Расшифровка сообщения [ править ]

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

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

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

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

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

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

Размеры ключей [ править ]

МакЭлис первоначально предложил размеры параметров безопасности , ^{[1], в} результате чего размер открытого ключа составляет 524 * (1024-524) = 262000 бит ^[^{требуется пояснение}^] . Недавний анализ предлагает размеры параметров для 80 битов безопасности при использовании стандартного алгебраического декодирования или при использовании декодирования списка для кода Гоппа, что приводит к размерам открытого ключа 520 047 и 460 647 битов соответственно. ^[5] Для обеспечения устойчивости к квантовым компьютерам были предложены размеры с кодом Goppa, что дает размер открытого ключа 8 373 911 бит. ^[8] $n=1024,k=524,t=50$ $n=2048,k=1751,t=27$ $n=1632,k=1269,t=34$ $n=6960,k=5413,t=119$ В своей 3 -м раунда подачи в 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] описали практическую атаку на оригинальную криптосистему Мак-Элиса с использованием метода декодирования информационного набора Стерна. ^[9] Используя параметры, первоначально предложенные ^{Мак-Элисом} , атака могла быть проведена за 2 ^60,55- битных операций. Поскольку атака до неприличия параллельна (связь между узлами не требуется), она может быть проведена за несколько дней на скромных компьютерных кластерах.

Структурные атаки [ править ]

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

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

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

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

Вариант этого алгоритма в сочетании с NTS-KEM ^[10] был включен и выбран во втором раунде конкурса постквантового шифрования NIST ^[11]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Альфред Дж. Менезес; Скотт А. Ванстон; AJ Menezes; Пол К. ван Оршот (1996). «Глава 8: Шифрование с открытым ключом» . Справочник по прикладной криптографии . CRC Press. ISBN 978-0-8493-8523-0.

"Квантовые компьютеры? Код безопасности Интернета будущего взломан" . Science Daily . Эйндховенский технологический университет . 1 ноября 2008 г.

«Классический МакЭлис» .(Представлено в Проект стандартизации постквантовой криптографии NIST )

[McEliece-1] МакЭлис, Роберт Дж. (1978). «Криптосистема с открытым ключом, основанная на алгебраической теории кодирования» (PDF) . Отчет о проделанной работе DSN . 44 : 114–116. Bibcode : 1978DSNPR..44..114M .

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

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

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

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

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

[7] «eBATS: ECRYPT эталонный анализ асимметричных систем» . bench.cr.yp.to . 25 августа 2018 . Дата обращения 1 мая 2020 .

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

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

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

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

[1]