Из песочницы Криптосистема McEliece на базе LDPC кодов

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

Содержание

1. Введение
2. Линейные коды
3. Кодовая криптография
4. Низкоплотностые (LDPC) коды
5. Криптография на LDPC кодах
6. Заключение
7. Литература

Введение

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

Линейные коды

Матричное кодирование

Назовём порождающей матрицей $inline$G$inline$ линейного пространства $inline$С$inline$ матрицу вида:

На этом месте условимся, что все вычисления проводятся в $inline$GF(2)$inline$, поэтому все $inline$x_{ij}$inline$ принимают значения 0 или 1.

В систематическом виде матрица $inline$G$inline$ представляет собой конкатенацию единичной матрицы $inline$I$inline$ и чётность части матрицы $inline$P$inline$. Из систематического вида легко получить соответствующую проверочную матрицу $inline$H$inline$, которая имеет вид:

На самом деле, матрице $inline$G$inline$ не обязательно быть в систематической форме. В этом смысле важно, чтобы между $inline$H$inline$ и $inline$G$inline$ сохранялось отношение: $inline$GH^{T}=0$inline$. Тогда кодирование имеет вид: $inline$с = mG$inline$, где $inline$m$inline$ исходное слово, $inline$c$inline$ полученное кодовое слово.

Проблема декодирования

Проверочная матрица служит для контроля того, что при передачи сообщения не произошло ошибок. Назовём синдромом $inline$s$inline$ вектор, полученный после вычисления $inline$s = Hc^{T}$inline$. Если синдром представляет собой нуль-вектор, то ошибок при передаче не произошло. В ином случае вместо $inline$c$inline$ мы получаем $inline$с'=с+е$inline$, где $inline$e$inline$ вектор ошибки (в позициях, где произошли ошибки, он принимает значения 1).

Чтобы декодировать кодовое слово $inline$c'$inline$, необходимо сначала освободить его от ошибок. Декодирование максимального правдоподобия (maximum likelihood decoding) представляет собой задачу поиска такого $inline$e$inline$, что $inline$He^{T} = s$inline$. Это следует из:

Эквивалетная задача: для данного кода $inline$c'$inline$ найти ближайшее корректное кодовое слово $inline$c$inline$ (ближайшее в смысле метрики расстояния Хэмминга). Проблема решается только полным перебором всех векторов ошибки (либо всех кодовых слов).

Для многих линейных кодов изобретены алгоритмы эффективного декодирования (например, для LDPC кодов, рассмотренных ниже, применяются алгоритмы belief propagation и bit-flipping, позволяющие декодировать код с ошибками за линейное время). Но в общем случае декодирование произвольного линейного кода это NP-трудная задача.

Кодовая криптография

Основная идея

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

Подход здесь является следующим:

• Давайте спрячем структуру кода с известным алгоритмом декодирования при помощи некоторых линейных преобразований (например, перестановок) над $inline$G$inline$ и получим новую порождающую матрицу $inline$G'$inline$
• Используем $inline$G'$inline$, чтобы закодировать слово со случайным вектором ошибки $inline$e$inline$
• Зная те операции, которые мы применили к $inline$G$inline$, мы можем применить обратные операции к $inline$G'$inline$ и декодировать кодовое слово эффективным алгоритмом, освобождая его от ошибок
• Для атакующего этот код будет выглядеть случайным

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

Самые популярные криптосистемы в кодовой криптографии были предложены Мак-Элиасом и немного позже Нидеррайтером. Алгоритмы носят соответсвующие названия.

Для них характерно:

• Ассимитричное шифрование: имеется открытый и закрытый ключ
• В качестве основы может быть использован любой линейный код с известным эффективным алгоритмом декодирования
• Криптосистемы устойчивы к атаке квантового компьютера
• Основной недостаток: огромный размер ключей (исчисляется в Мб)

В дальнейшем мы подробнее остановимся только на криптосистеме Мак-Элиаса.

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

Ключи генерируются по следующему алгоритму:

1. Пусть $inline$G$inline$ порождающая (k, n)-матрица (n, k)-линейного кода, исправляющего $inline$t$inline$ ошибок
2. Возьмём случайную невырожденную (k, k)-матрицу $inline$S$inline$
3. Возьмём случайную (n, n)-матрицу перестановки $inline$P$inline$
4. Публичный ключ: пара $inline$(SGP, t)$inline$, где $inline$SGP = G'$inline$
5. Приватный ключ: тройка $inline$(S, G, P)$inline$

Пояснение: невырожденность матриц $inline$S$inline$ и $inline$P$inline$ является обязательный условием, потому что по ним ищутся обратные матрицы, и умножение на них происходит при дешифровании, а t необходимо для того, чтобы не получилось добавить в код больше ошибок, чем он может исправить, при шифровании.

Интересным является простота алгоритма (оригинальная статья автора занимала всего 3 страницы!), но при этом и его потенциал. Думаю, написана уже не одна сотня текстов, продолжающих эту идею.

Шифрование

Зашифровываем сообщение следующим образом:

1. Берём случайный вектор ошибки $inline$е$inline$ длины $inline$n$inline$ и веса $inline$w$inline$ не больше $inline$t$inline$
2. Кодируем сообщение следующим образом: $inline$c = mG + e$inline$

Теперь расшифруем наш шифротекст c:

1. Рассчитаем $inline$c = cP^{-1}$inline$
2. Декодируем $inline$c'$inline$ извеcтным алгоритмом, получим сообщение $inline$m'$inline$
3. Восстановим исходное сообщение $inline$m = mS^{-1}$inline$

Весь математический концепт можно выписать в виде одной формулы:

Модификации

В оригинале автор предложил использование своего алгоритма на основе двоичных кодов Гоппы, но вскоре математики начали предлагать модификации алгоритма с другими линейными кодами. Перечислю некоторые: недвоичные коды Гоппы, коды Рида-Соломона, Габидуллина, Рида-Маллера, LDPC, LRPC, полярные, алгебро-геометрические коды и многие их вариации.

К сожалению, большинство из этих кодов были довольно быстро взломаны: примерно через несколько лет после публикации идеи другие математики предлагали эффективную атаку. Эксплуатировалась в основном сильная алгебраическая структура многих кодов.

Есть небольшой список линейных кодов, до сих пор не поддавшихся эффективному криптоанализу:

• Двоичные коды Гоппы
• Свёрточные коды
• MDPC коды (вариация LDPC кодов)

Далее рассмотрим вариацию криптосистемы на базе LDPC кодов и их более устойчивой разновидности MDPC кодов.

Низкоплотностые (LDPC) коды

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

Для тех, кто не сталкивался с LDPC кодами ранее, настоятельно рекомендую ознакомиться с замечательной статьёй по ним здесь или на Википедии.

Достоинства LDPC кодов

Для кодов с малой плотностью проверок на чётность характерны:

• Разреженная матрица проверки на чётность: количество единиц в ней стремится к 0 при росте n. Структура матрицы при этом выглядит довольно случайной.
• Они могут быть декодированы за линейное время. Существуют алгоритмы "мягкого" и "жёсткого" декодирования (в англ. литературе "soft-decision" и "hard-decision" decoding).
• Отличная корректирующая способность: нерегулярные LDPC коды очень близки к границе Шеннона.
• Квазициклическая вариация (QC-LDPC) может быть представлена в виде компактной формы полинома.

Криптография на LDPC кодах

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

1. Структуру LDPC кода легко "спрятать" под линейными преобразованиями.
2. Существуют алгоритмы быстрого декодирования.
3. Компактная форма QC-LDPC кодов может существенно уменьшить размер закрытого ключа.

Но есть и недостатки:

1. Корректирующая способность случайно сгенерированного LDPC кода неизвестна (для определения параметра t используется либо моделирование декодирования с ошибками, либо алгоритм density evolution).
2. На код уже известны некоторые атаки (например, атака по дуальному коду).
3. Нужно брать сравнительно большие коды, чтобы достичь достаточного уровня криптостойкости.

Разновидности LDPC кодов

На данный момент в криптографии более применимы модификации LDPC: MDPC и его квазициклическая форма (QC-MDPC).

MDPC коды

MDPC (Moderate Density Parity-Check) коды это более "тяжёлая" разновидность LDPC кодов. Если для генерации LDPC кодов рекомендуется брать вес вектора w не больше 10, то для MDPC кода средний вес строки выбирается из расчёта $inline$w = \sqrt{n\cdot log(n)}$inline$, где n длина вектора-строки (считается, что эта цифра является наиболее оптимальной).

MDPC коды характерны меньшей корректирующей способностью, но большей устойчивостью к структурным криптографическим атакам: в данном случае уже нельзя проэксплуатировать разреженность проверочной матрицы.

Квазициклические коды

Порождающая матрица низкоплостностого квазициклического (QC-LDPC) кода задаётся в виде конкатенации нескольких циркулянт. Циркулянтой называется (n, n)-матрица, в первой строчке которой записан полином, а остальные строки его циклические сдвиги:

Задавая код в таком виде, мы немного теряем в корректирующей способности, но можем хранить порождающую матрицу в компактной форме: теперь нам нужно хранить только порождающие полиномы, а построить порождающую матрицу можно выписав их циклические сдвиги.

Давайте оценим, во сколько раз можно уменьшить наш приватный ключ, используя такой подход для (p, n)-QC-LDPC кода с параметрами n = 9602 и p = 4801 (размер одной циркулянты):

1. Бинарная матрица перестановки P(n, n): ~11 Mb --> целочисленный вектор P(n): ~9.5 Kb. В данном случае мы храним массив переставленных столбцов, избавляясь от огромной размерности.
2. Порождающая матрица G(n, p): ~5.5 Mb --> полиномиальная форма G(n): ~1.2 Kb.
3. Бинарная матрица S(p, p): ~2.75 Mb --> полиномимальная форма S(p): ~0.6 Kb. Используя S тоже в форме циркулянты, мы немного потеряем в криптостойкости, но сильно уменьшим затраты памяти.

Итоговый профит: приватный ключ в 1760 раз меньше! К сожалению, для публичного ключа такой же фокус провернуть не выйдет.

Уровень криптостойкости

Уровнем криптостойкости называется двоичный логарифм от количества итераций, необходимых атакующему для взлома криптосистемы.

Например, Мак-Элиас на базе (1024, 524, 101)-кода Гоппы гарантировал уровень криптостойкости в 50 бит (то есть атакующему потребовалось бы $inline$2^{50}$inline$ итераций для успешной атаки).

Для сравнения: MDPC код с параметрами n = 9602 и w = 90 обеспечивает уровень криптостойкости в 80 бит. В данном случае для криптоанализа не известно других методов, кроме как атаки на произвольный линейный код (например, декодирование по информационной совокупности), и на данный момент этот уровень считается довольно надёжным.

Заключение

Кодовая криптография сравнительно новая и несомненно интересная тема для изучения. Её актуальность подчёркивает увеличение компьютерных мощностей, перед которыми начинают сдаваться классические криптосистемы.

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

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

Литература

1. A Public-Key Cryptosystem Based On Algebraic Coding Theory (R. J. McEliece)
2. An Introduction to Low-Density Parity Check Codes (Daniel J. Costello, Jr.)
3. On the Usage of LDPC Codes in the McEliece Cryptosystem (Marco Baldi)
4. LDPC codes in the McEliece cryptosystem: attacks and countermeasures (Marco Baldi)
5. QC-LDPC Code-Based Cryptography (Marco Baldi)
6. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes (Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S. L. M. Barreto)
7. Modern Coding Theory (Tom Richardson, Rudiger Urbanke)