В страхе перед квантовым компьютером, способным взломать современные методы шифрования, криптографы всего мира продолжают поиск криптографических систем, устойчивых к атаке квантового компьютера.
Одна из таких криптосистем была изобретена еще в 1978 году и основана на теории алгебраического кодирования.
В этой статье представлен обзор криптографии кода, основанной на кодах проверки четности низкой плотности (или просто кодах LDPC).
Прошу всех интересующихся под катом.
Содержание
- Введение
- Линейные коды
- Криптография кода
- Коды низкой плотности (LDPC)
- Криптография с использованием кодов LDPC
- Заключение
- Литература
Введение
Этот материал предназначен для людей, обладающих базовыми знаниями в области криптографии, теории информации и линейной алгебры, и был написан студентом, которому просто нравилось изучать эту предметную область.Основная терминология, на которую я опираюсь, приведена в первых разделах, но для более глубокого понимания подразумевается самостоятельный поиск и изучение дополнительной информации по теме.
Некоторая литература, способствующая этому, указана в конце статьи.
Линейные коды
Матричное кодирование
Назовем это порождающей матрицей
линейное пространство
матрица вида:
На данный момент мы согласны с тем, что все расчеты проводятся в
, Итак, это все
принимать значения 0 или 1. В систематическом виде матрица
представляет собой объединение единичной матрицы
и четность детали - матрицы
.
С систематической точки зрения легко получить соответствующую проверочную матрицу 
, который выглядит так: 
Фактически, матрица
не обязательно в систематической форме.
В этом смысле важно, чтобы между
И
отношение осталось: 
.
Тогда кодировка выглядит так: 
, Где 
- оригинальное слово 
— полученное кодовое слово.
Проблема с декодированием
Матрица проверки используется для проверки отсутствия ошибок при передаче сообщения.
Назовем это синдромом 
вектор, полученный после расчета 
.
Если синдром представляет собой нулевой вектор, то ошибок передачи не произошло.
В противном случае вместо
мы получаем 
, Где 
— вектор ошибки (в позициях, где произошли ошибки, принимает значение 1).
Чтобы расшифровать кодовое слово 
, необходимо сначала освободить его от ошибок.
Декодирование методом максимального правдоподобия – это проблема поиска таких
, Что 
.
Это следует из: 
Ээквивалентная задача: для этого кода
найти ближайшее допустимое кодовое слово
(ближайший в смысле метрики расстояния Хэмминга).
Решить проблему можно только полным перебором всех векторов ошибок (или всех кодовых слов).
Для многих линейных кодов изобретены эффективные алгоритмы декодирования (например, для кодов LDPC, обсуждаемых ниже, используются алгоритмы распространения доверия и переворота битов, которые позволяют декодировать код с ошибками за линейное время).
А вообще декодирование произвольного линейного кода является NP-трудной задачей .
Криптография кода
Основная идея
Ключевая идея кодовой криптографии — заставить злоумышленника решить NP-сложную задачу, а именно декодировать случайный линейный код. Подход здесь следующий:- Скроем структуру кода известного алгоритма декодирования с помощью некоторых линейных преобразований (например, перестановок) по
и мы получаем новую порождающую матрицу
- Мы используем
закодировать слово со случайным вектором ошибок - Зная операции, к которым мы применили
, мы можем применить обратные операции к
и декодируем кодовое слово с помощью эффективного алгоритма, освобождая его от ошибок - Для злоумышленника этот код будет выглядеть так случайный
Криптосистема Mac-Эlias
Наиболее популярные криптосистемы в криптографии кодов были предложены МакЛисом и чуть позже Нидеррайтером.Алгоритмы имеют соответствующие названия.
Они характеризуются:
- Асимметричное шифрование: есть открытый и закрытый ключ.
- За основу может быть взят любой линейный код с известным эффективным алгоритмом декодирования.
- Криптосистемы устойчивы к атакам квантовых компьютеров
- Основной недостаток: огромный размер ключей (исчисляется в МБ).
Генерация ключей
Ключи генерируются по следующему алгоритму:- Позволять
– порождающая (k, n)-матрица (n, k)-линейного кода, корректирующая
ошибки - Возьмем случайную неособую (k, k)-матрицу
- Возьмем случайную (n, n) матрицу перестановок
- Открытый ключ: пара
, Где
- Закрытый ключ: три
И
является обязательным условием, так как по ним ищутся обратные матрицы, а умножение на них происходит при расшифровке, а t необходимо для того, чтобы в код нельзя было добавить больше ошибок, чем он может исправить при шифровании.
Что интересно, так это простота алгоритма (оригинальная статья автора занимала всего 3 страницы!), а также его потенциал.
Думаю, написано уже не одна сотня текстов, продолжающих эту идею.
Шифрование
Мы шифруем сообщение следующим образом:- Возьмите случайный вектор ошибок
длина
а вес
не более - Мы кодируем сообщение следующим образом:
- Давайте посчитаем
- Декодирование
используя известный алгоритм, получаем сообщение
- Давайте восстановим исходное сообщение
Модификации
В оригинале автор предлагал использовать свой алгоритм на основе двоичных кодов Гоппы, но вскоре математики стали предлагать модификации алгоритма с использованием других линейных кодов.Я перечислю несколько: небинарные коды Гоппы, коды Рида-Соломона, Габидуллина, коды Рида-Мюллера, LDPC, LRPC, полярные, алгебро-геометрические коды и множество их вариаций.
К сожалению, большинство этих кодов были взломаны довольно быстро: примерно через несколько лет после публикации идеи другие математики предложили эффективную атаку.
В основном использовалась сильная алгебраическая структура многих кодов.
Существует небольшой список линейных кодов, которые еще не подверглись эффективному криптоанализу:
- Двоичные коды Гоппы
- Сверточные коды
- Коды MDPC (разновидность кодов LDPC)
Коды низкой плотности (LDPC)
Мы не будем долго останавливаться на этом разделе, потому что хорошее описание этих кодов – тема отдельной статьи.Тем, кто раньше не сталкивался с LDPC-кодами, настоятельно рекомендую прочитать о них эту замечательную статью.
Здесь или в Википедия .
Преимущества кодов LDPC
Коды с низкой плотностью проверок четности характеризуются:- Разреженная матрица проверки четности: количество единиц в ней стремится к 0 по мере роста n. Структура матрицы выглядит довольно случайной.
- Их можно декодировать за линейное время.
Существуют алгоритмы «мягкого» и «жесткого» декодирования (в англоязычной литературе «soft-decision» и «hard-decision» decoding).
- Отличные возможности коррекции: нерегулярные коды LDPC очень близки к границе Шеннона.
- Квазициклическая вариация (QC-LDPC) может быть представлена в виде компактной полиномиальной формы.
Криптография с использованием кодов LDPC
Вышеуказанные преимущества кодов LDPC позволяют им быть прекрасной основой для криптосистемы Мак-Элиаса, поскольку:- Структуру LDPC-кода легко «спрятать» под линейными преобразованиями.
- Существуют быстрые алгоритмы декодирования.
- Компактная форма кодов QC-LDPC позволяет значительно уменьшить размер закрытого ключа.
- Корректирующая способность случайно сгенерированного кода LDPC неизвестна (для определения параметра t используется либо моделирование подверженного ошибкам декодирования, либо алгоритм плотности эволюции).
- Некоторые атаки на код уже известны (например, атака на двойной код).
- Необходимо брать относительно большие коды, чтобы достичь достаточного уровня криптостойкости.
Типы кодов LDPC
На данный момент в криптографии более применимы модификации LDPC: MDPC и его квазициклическая форма (QC-MDPC).
Коды MDPC
Коды MDPC (проверка четности с умеренной плотностью) представляют собой более «тяжелую» версию кодов LDPC. Если для формирования кодов LDPC рекомендуется брать вес вектора w не более 10, то для кода MDPC из расчета выбирается средний вес строки
, где n — длина вектора-строки (считается, что эта цифра является наиболее оптимальной).
Коды MDPC характеризуются меньшей корректирующей способностью, но большей устойчивостью к структурным криптографическим атакам: в этом случае уже невозможно эксплуатировать разреженность проверочной матрицы.
Квазициклические коды
Генерирующая матрица квазициклического кода низкой плотности (QC-LDPC) задается как конкатенация нескольких циркулянтов.
Циркулянтом называется (n, n)-матрица, первая строка которой содержит полином, а остальные строки — ее циклические сдвиги: 
Задавая код в таком виде, мы немного теряем в корректирующей способности, но можем хранить порождающую матрицу в компактном виде: теперь нам нужно хранить только порождающие полиномы, а порождающую матрицу мы можем построить, выписав их циклические сдвиги.
Прикинем, во сколько раз мы сможем уменьшить наш закрытый ключ, используя этот подход для (p, n)-QC-LDPC-кода с параметрами n = 9602 и p = 4801 (размер одного циркулянта):
- Бинарная матрица перестановок P(n, n): ~11 Мб --> целочисленный вектор P’(n): ~9,5 Кб.
В этом случае мы храним массив переставленных столбцов, устраняя огромную размерность.
- Генерирующая матрица G(n, p): ~5,5 Мб --> полиномиальная форма G’(n): ~1,2 Кб.
- Бинарная матрица S(p, p): ~2,75 Мб --> полиномиальная форма S’(p): ~0,6 Кб.
Используя S также в циркулянтной форме, мы немного потеряем криптографическую стойкость, но значительно сократим затраты памяти.
Уровень криптографической стойкости
Уровень криптостойкости представляет собой двоичный логарифм количества итераций, необходимых злоумышленнику для взлома криптосистемы.Например, Mac-Эlias, основанный на (1024, 524, 101) коде Гоппы, гарантировал уровень криптографической стойкости 50 бит (т. е.
злоумышленнику потребуется 
итераций для успешной атаки).
Для сравнения: код MDPC с параметрами n = 9602 и w = 90 обеспечивает уровень криптостойкости 80 бит .
При этом для криптоанализа не известны другие методы, кроме атаки на произвольный линейный код (например, декодирование по набору информации), и на данный момент этот уровень считается вполне надежным.
Заключение
Криптография кода — относительно новая и, безусловно, интересная тема для изучения.Ее актуальность подчеркивается увеличением мощности компьютеров, перед которыми классические криптосистемы начинают уступать.
Широкое развитие кодированных криптосистем сдерживается главным образом огромным размером ключей, но ученые добились успехов в этом направлении: квазициклические коды позволяют существенно уменьшить размер закрытого ключа.
Все факты, утверждения и цифры, использованные в этой статье, были взяты из приведенных ниже источников и из Википедии, свободной энциклопедии.
Надеюсь, этот материал был интересен для изучения.
Любые комментарии, вопросы и уточнения по теме приветствуются.
Литература
- Криптосистема с открытым ключом, основанная на алгебраической теории кодирования (Р.
Дж.
МакЭлис)
- Введение в коды проверки четности с низкой плотностью (Дэниел Дж.
Костелло-младший)
- Об использовании кодов LDPC в криптосистеме МакЭлиса (Марко Бальди)
- Коды LDPC в криптосистеме МакЭлиса: атаки и меры противодействия (Марко Бальди)
- Криптография на основе кода QC-LDPC (Марко Бальди)
- MDPC-McEliece: новые варианты McEliece из кодов проверки четности умеренной плотности (Рафаэль Мисочки, Жан-Пьер Тиллих, Николя Сендрие и Пауло С.
Л.
М.
Баррето)
- Современная теория кодирования (Том Ричардсон, Рюдигер Урбанке)
-
Мифы Об Интернет-Маркетинге
19 Oct, 24 -
Немного О Vpn: Протоколы Удаленного Доступа
19 Oct, 24 -
Алгоритм Быстрой Посадки В Самолет
19 Oct, 24 -
Восемь Способов Демотивировать Сотрудников
19 Oct, 24 -
Как Правильно Печатать Flash В Firefox
19 Oct, 24 -
Начало Работы С Google Go В Azure
19 Oct, 24 -
Seo – Возрождение Золотой Лихорадки
19 Oct, 24
