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

Алгоритм асимметричного шифрования, разработанный Робертом МакЭлисом

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

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

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

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

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

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

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

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

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

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

Более конкретно, шаги следующие:

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

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

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

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

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

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

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

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

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

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

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

Размеры клавиш

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

Атаки

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

Для МакЭлиса существует два основных направления атак:

Атаки методом грубой силы/неструктурированные атаки

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

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

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

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

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

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

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

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

Вариант этого алгоритма в сочетании с NTS-KEM ^[12] был представлен и выбран в ходе третьего тура конкурса NIST по постквантовому шифрованию . ^[13]

Ссылки

1. McEliece, Robert J. (1978). "Криптосистема с открытым ключом, основанная на алгебраической теории кодирования" (PDF) . Отчет о ходе работы DSN . 44 : 114–116. Bibcode : 1978DSNPR..44..114M.
2. Динь, Ханг; Мур, Кристофер; Рассел, Александр (2011). Рогауэй, Филип (ред.). Криптосистемы МакЭлиса и Нидеррайтера, устойчивые к атакам квантовой выборки Фурье . Достижения в криптологии — CRYPTO 2011. Конспект лекций по информатике. Том 6841. Гейдельберг: Springer. С. 761–779. doi : 10.1007/978-3-642-22792-9_43 . ISBN 978-3-642-22791-2. МР  2874885.
3. Berlekamp, ​​Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk CA (1978). «О внутренней неразрешимости некоторых проблем кодирования». Труды IEEE по теории информации . IT-24 (3): 384–386. doi :10.1109/TIT.1978.1055873. MR  0495180.
4. NJ Patterson (1975). «Алгебраическое декодирование кодов Гоппы». Труды IEEE по теории информации . IT-21 (2): 203–207. doi :10.1109/TIT.1975.1055350.
5. Bernstein, Daniel J.; Lange, Tanja ; Peters, Christiane (8 августа 2008 г.). «Атака и защита криптосистемы McEliece». Постквантовая криптография. Конспект лекций по информатике. Том 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 Benchmarking of Asymmetric Systems". bench.cr.yp.to . 25 августа 2018 г. Получено 1 мая 2020 г.
8. Classic McEliece Team (23 октября 2022 г.). "Classic McEliece: консервативная кодовая криптография: спецификация криптосистемы" (PDF) . Обзор заявок NIST на 4-й раунд .
9. Таня Ланге (23 февраля 2021 г.). «Кодовая криптография III — коды Гоппы: определение и использование». YouTube .
10. Дэниел Огот и др. (7 сентября 2015 г.). «Первоначальные рекомендации по долгосрочным безопасным постквантовым системам» (PDF) . PQCRYPTO: Постквантовая криптография для долгосрочной безопасности .
11. Жак Стерн (1989). "Метод поиска кодовых слов малого веса". Coding Theory and Applications . Lecture Notes in Computer Science. Vol. 388. Springer Verlag. pp. 106–113. doi :10.1007/BFb0019850. ISBN 978-3-540-51643-9.
12. "NTS-KEM". 29 декабря 2017 г. Архивировано из оригинала 29 декабря 2017 г. Получено 9 декабря 2020 г.
13. «Отчет о состоянии третьего раунда процесса стандартизации постквантовой криптографии NIST» (PDF) . NISTIR : 31.

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

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