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

Криптосистема Мак-Элиса — это асимметричная криптосистема с открытым ключом, основанная на теоретико-кодовых конструкциях, в частности, на сложности декодирования произвольного линейного кода. Предложена американским математиком Робертом Мак-Элисом в 1978 году, что делает её одной из старейших криптосистем с открытым ключом, наряду с криптосистемой RSA. В отличие от RSA, безопасность которой основана на сложности факторизации больших целых чисел, стойкость системы Мак-Элиса опирается на NP-полную задачу декодирования общего линейного кода, что делает её потенциально устойчивой к атакам с использованием квантовых компьютеров.

История

Криптосистема была разработана Робертом Мак-Элисом, профессором Калифорнийского технологического института, и впервые опубликована в 1978 году в статье «A public-key cryptosystem based on algebraic coding theory». В то время она не получила широкого распространения из-за большого размера открытого ключа (порядка сотен килобайт) по сравнению с RSA (единицы килобайт). Однако с развитием вычислительных мощностей и появлением угрозы квантовых вычислений интерес к системе возродился в 2000-х годах в рамках постквантовой криптографии.

Устройство и принцип работы

Система основана на использовании линейных кодов, исправляющих ошибки. Основная идея заключается в том, что открытый ключ представляет собой «замаскированный» генераторную матрицу кода Гоппы (Goppa code), который эффективно декодируется. Злоумышленник, не зная структуры маскировки, вынужден решать NP-полную задачу декодирования.

Основные компоненты

• Код Гоппы: частный случай линейного кода, для которого существуют эффективные алгоритмы декодирования (например, алгоритм Паттерсона). Код задаётся параметрами \( n \) (длина кодового слова), \( k \) (размерность) и \( t \) (максимальное число исправляемых ошибок).
• Генераторная матрица \( G \): матрица размера \( k \times n \), строки которой образуют базис кода.
• Маскирующие матрицы: секретная матрица перестановки \( P \) (размера \( n \times n \)) и невырожденная матрица \( S \) (размера \( k \times k \)), используемые для сокрытия структуры кода.

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

1. Выбирается код Гоппы с параметрами \( (n, k, t) \), для которого известна эффективная процедура декодирования.
2. Вычисляется генераторная матрица \( G \) этого кода.
3. Выбираются случайные матрицы: \( S \) (невырожденная, \( k \times k \)) и \( P \) (перестановочная, \( n \times n \)).
4. Вычисляется открытый ключ: \( G' = S \cdot G \cdot P \).
5. Закрытый ключ состоит из троек \( (S, G, P) \), а также алгоритма декодирования для кода Гоппы.

Шифрование

Чтобы зашифровать сообщение \( m \) (длины \( k \)), отправитель:

1. Представляет сообщение как вектор длины \( k \).
2. Вычисляет зашифрованный текст: \( c = m \cdot G' + e \), где \( e \) — случайный вектор ошибок веса \( t \) (то есть содержащий ровно \( t \) единиц).

Дешифрование

Получатель, зная закрытый ключ:

1. Вычисляет \( c' = c \cdot P^{-1} = (m \cdot S) \cdot G + e \cdot P^{-1} \). Поскольку \( P \) — перестановочная матрица, вес \( e \cdot P^{-1} \) остаётся равным \( t \).
2. Применяет алгоритм декодирования кода Гоппы к \( c' \), получая \( m' = m \cdot S \).
3. Вычисляет исходное сообщение: \( m = m' \cdot S^{-1} \).

Безопасность

Стойкость системы основана на сложности задачи синдромного декодирования (Syndrome Decoding Problem), которая является NP-полной. Для практических параметров (например, \( n = 1024 \), \( k = 524 \), \( t = 50 \)) взлом системы требует экспоненциального времени на классических компьютерах. Однако система уязвима к атакам, использующим структуру кода, если маскировка выполнена некорректно.

Квантовая устойчивость

В отличие от RSA и ECC, криптосистема Мак-Элиса не подвержена атакам с использованием алгоритма Шора, который эффективно решает задачи факторизации и дискретного логарифмирования. Известные квантовые алгоритмы не дают существенного ускорения для задачи синдромного декодирования, что делает систему перспективной для постквантовой криптографии.

Размер ключей и производительность

Основным недостатком системы является большой размер открытого ключа. Для обеспечения стойкости, эквивалентной 128-битному симметричному шифрованию, открытый ключ может занимать от 0,5 до 1 мегабайта. Закрытый ключ также велик, но обычно меньше. Скорость шифрования и дешифрования высока: шифрование требует только умножения матрицы на вектор и добавления ошибки, а дешифрование — эффективного декодирования кода Гоппы.

Модификации и варианты

Криптосистема Нидеррайтера

В 1986 году Харальд Нидеррайтер предложил вариант системы, основанный на синдромном декодировании, который позволяет уменьшить размер открытого ключа. В этой версии открытый ключ — проверочная матрица кода, а шифротекст — синдром ошибки.

Криптосистема на основе кодов LDPC и MDPC

Для уменьшения размера ключей были предложены варианты с использованием кодов с малой плотностью проверок на чётность (LDPC) или умеренной плотностью (MDPC). Эти коды допускают эффективное декодирование и позволяют сократить размер открытого ключа до нескольких килобайт. Однако такие варианты менее изучены и могут быть уязвимы к структурным атакам.

Криптосистема Classic McEliece

В 2017 году проект Classic McEliece был представлен как кандидат в стандарты постквантовой криптографии Национального института стандартов и технологий США (NIST). Он использует коды Гоппы с фиксированными параметрами и предлагает уровни безопасности, соответствующие 128, 192 и 256 битам. В 2024 году NIST выбрал Classic McEliece для стандартизации в качестве одного из постквантовых алгоритмов.

Применение

Из-за большого размера ключей система Мак-Элиса редко используется в массовых приложениях, но находит применение в:

• Постквантовой криптографии: как один из наиболее изученных и надёжных кандидатов.
• Системах с высокой степенью безопасности: где размер ключа не является критическим фактором.
• Исследованиях в области теории кодирования: система стимулировала развитие алгоритмов декодирования и анализа стойкости кодов.

Критика и ограничения

Основные недостатки системы:

• Большой размер открытого ключа: затрудняет использование в устройствах с ограниченной памятью (например, смарт-карты).
• Низкая скорость генерации ключей: требует выбора случайного кода Гоппы и вычисления маскирующих матриц.
• Уязвимость к атакам по побочным каналам: при неправильной реализации возможно извлечение секретных параметров через анализ времени выполнения или энергопотребления.

Интересные факты

• В 2010 году была предложена атака на основе алгебраического анализа, которая позволила взломать некоторые варианты системы с малыми параметрами, но не затронула классические коды Гоппы.
• Криптосистема Мак-Элиса вдохновила создание нескольких других постквантовых схем, включая схемы на основе кодов Рида — Соломона и решётчатые криптосистемы.
• В 2022 году российские исследователи из МГУ имени М. В. Ломоносова опубликовали работу по анализу стойкости Classic McEliece к атакам с использованием квантовых компьютеров, подтвердив её высокую надёжность.

Источники

• McEliece, R. J. (1978). «A public-key cryptosystem based on algebraic coding theory». DSN Progress Report.
• Niederreiter, H. (1986). «Knapsack-type cryptosystems and algebraic coding theory». Problems of Control and Information Theory.
• Bernstein, D. J., et al. (2017). «Classic McEliece: conservative code-based cryptography». NIST Post-Quantum Cryptography Standardization.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.