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

редактировать

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

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

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

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

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

СОДЕРЖАНИЕ

1 Определение схемы
- 1.1 Генерация ключей
- 1.2 Шифрование сообщений
- 1.3 Расшифровка сообщения
2 Подтверждение расшифровки сообщения
3 основных размера
4 атаки
- 4.1 Грубая сила / неструктурированные атаки
- 4.2 Структурные атаки
- 4.3 Кандидат на постквантовое шифрование
5 ссылки
6 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ключевые размеры

Первоначально МакЭлис предложил размер параметров безопасности равный, в результате чего размер открытого ключа составляет 524 * (1024-524) = 262000 бит. Недавний анализ предлагает размеры параметров для 80 битов безопасности при использовании стандартного алгебраического декодирования или при использовании декодирования списком для кода Гоппа, что приводит к размерам открытого ключа 520 047 и 460 647 битов соответственно. Для обеспечения устойчивости к квантовым компьютерам были предложены размеры с кодом Гоппа, что дает размер открытого ключа 8 373 911 бит. В своей 3 -м раунда подачи в NIST после квантовой стандартизации самого высокого уровня безопасности, уровень 5 даются для наборов параметров 6688128, 6960119 и 8192128. Этих параметров,, соответственно. ${\ displaystyle n = 1024, k = 524, t = 50}$ $п = 1024, к = 524, т = 50$ ${\ displaystyle n = 2048, k = 1751, t = 27}$ $п = 2048, к = 1751, т = 27$ ${\ displaystyle n = 1632, k = 1269, t = 34}$ $п = 1632, к = 1269, т = 34$ ${\ displaystyle n = 6960, k = 5413, t = 119}$ ${\ displaystyle n = 6960, k = 5413, t = 119}$ ${\ displaystyle n = 6688, k = 128, t = 13}$ ${\ displaystyle n = 6688, k = 128, t = 13}$ ${\ displaystyle n = 6960, k = 119, t = 13}$ ${\ displaystyle n = 6960, k = 119, t = 13}$ ${\ displaystyle n = 8192, k = 128, t = 13}$ ${\ displaystyle n = 8192, k = 128, t = 13}$

Атаки

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

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

Брутфорс / неструктурированные атаки

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

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

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

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

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

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

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

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

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

Рекомендации

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

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

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

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