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

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

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

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

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

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

Криптосистема McEliece имеет некоторые преимущества перед, например, RSA . Шифрование и дешифрование выполняются быстрее. ^[7] Долгое время считалось, что 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^{\prime }=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) = 262 000 бит. Недавний анализ предполагает размеры параметров для 80 бит безопасности при использовании стандартного алгебраического декодирования или при использовании декодирования списка для кода Гоппы, что приводит к размерам открытого ключа 520 047 и 460 647 бит соответственно. ^[5] Для устойчивости к квантовым компьютерам были предложены размеры кода Гоппы, что дает размер открытого ключа 8 373 911 бит. ^[10] В третьем раунде подачи в NIST после квантовой стандартизации самый высокий уровень безопасности, уровень 5, дан для наборов параметров 6688128, 6960119 и 8192128. Параметры: , , соответственно . ${\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}$ ${\displaystyle n=2048,k=1751,t=27}$ ${\displaystyle n=1632,k=1269,t=34}$ ${\displaystyle n=6960,k=5413,t=119}$ ${\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, Роберт Дж. (1978). «Криптосистема с открытым ключом, основанная на алгебраической теории кодирования» (PDF) . Отчет о ходе работы DSN . 44 : 114–116. Бибкод :1978ДСНПР..44..114М.
2. Динь, Ханг; Мур, Кристофер; Рассел, Александр (2011). Рогауэй, Филип (ред.). Криптосистемы МакЭлиса и Нидеррайтера, противостоящие атакам квантовой выборки Фурье . Достижения в криптологии — CRYPTO 2011. Конспекты лекций по информатике. Том. 6841. Гейдельберг: Шпрингер. стр. 761–779. дои : 10.1007/978-3-642-22792-9_43 . ISBN 978-3-642-22791-2. МР  2874885.
3. Берлекамп, Элвин Р.; МакЭлис, Роберт Дж.; Ван Тилборг, Хенк, Калифорния (1978). «О присущей неразрешимости некоторых проблем кодирования». Транзакции IEEE по теории информации . ИТ-24 (3): 384–386. дои : 10.1109/TIT.1978.1055873. МР  0495180.
4. Нью-Джерси Паттерсон (1975). «Алгебраическое декодирование кодов Гоппы». Транзакции IEEE по теории информации . ИТ-21 (2): 203–207. дои : 10.1109/TIT.1975.1055350.
5. Бернштейн, Дэниел Дж.; Ланге, Таня ; Петерс, Кристиана (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 г.
8. Классическая команда МакЭлиса (23 октября 2022 г.). «Классический МакЭлис: консервативная криптография на основе кода: спецификация криптосистемы» (PDF) . Обзор заявок на участие в 4-м раунде NIST .
9. Таня Ланге (23 февраля 2021 г.). «Кодовая криптография III - Коды Гоппы: определение и использование». YouTube .
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.

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

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

• Рамшмид, Клаудия; Адамс, Дэвид (2023). McEliece Messaging: Smoke Crypto Chat — первый мобильный McEliece-Messenger, опубликованный во всем мире как стабильный прототип. Статья на портале ТК Инфо.

• «Квантовые компьютеры? Код интернет-безопасности будущего взломан». Наука Дейли . Эйндховенский технологический университет . 1 ноября 2008 г.

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