Применение теории кодирования в криптографии Лось Антон Васильевич

Введение Алгебраическая теория кодирования Линейные коды Криптография Криптосистем а Роберта Мак-Элиса, 1978 год Криптосистем а Гаральда Нидеррайтра, 1986 год Криптосистемы использующие APN-функции DESAESГОСТ Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Основные определения Двоичный код Линейный код Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Исправление ошибок Расстояние Хэмминга Кодовое расстояние Кодовое расстояние равно минимальному расстоянию Хэмминга между различными кодовыми словами. Код, исправляющий t ошибок Код исправляет t ошибок, если его кодовое расстояние не меньше 2t+1 Пример t t 1 x x y Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Линейные коды Порождающая матрица Строки порождающей матрицы G образуют базу линейного кода. Проверочная матрица Порождающая матрица Проверочная матрица Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Коды Гоппы Валерий Денисович Гоппа Первым (1981) осознал связь между алгебраической геометрией и теорией кодирования. Gary L. Peterson Коды Гоппы Линейные коды порожденные несингулярными проективными кривыми над конечными полями. Коды Гоппы имеют важное свойство. Они обладают быстрыми процедурами декодирования по алгоритму Питерсона. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Основы криптографии Односторонняя функция Односторонняя функция (англ. one-way function) – функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Примеры односторонних функций Односторонняя функция с лазейкой Такая односторонняя функция, для которой при знании специальной информации (лазейки) аргумент вычислить по заданному значению функции легко. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции Схема шифрования Криптосистема с открытым ключом АлисаБоб 1. Генерация ключа Текст сообщения Открытый канал связи m e c m d

Криптосистема Мак-Элиса Основа криптосистемы Алгоритм криптосистемы базируется на сложности декодирования линейных кодов, общая задача декодирования линейного кода является NP-трудной Открытый ключ криптосистемы Секретный ключ криптосистемы Для создания секретного ключа выбирается линейный код C, исправляющий достаточно большое число ошибок t, для которого известен эффективный алгоритм декодирования. Представляет собой порождающую матрицу некоторого линейного кода как произвольного линейного кода из заданного ансамбля кодов с фиксированными параметрами [n,k,d], d 2t + 1. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Формирование ключей Секретный ключ G – порождающая матрица кода Гоппы размерности k, S – случайная невырожденная матрица размера k×k, P – случайная матрица перестановки размера n×n. Открытый ключ G=S×G×P – таким образом, исходная матрица G маскируется под матрицу общего положения G из ансамбля кодов с одинаковыми параметрами, t – число ошибок, исправляемых исходным кодом. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Шифрование Исходное сообщение Алисы Алиса представляет свое сообщение в виде последовательностей двоичных символов длины k. Внесение помех Шифрование открытым ключом 1)Алиса вычисляет вектор c=m×G. 2)Алиса генерирует случайный вектор z длины n, имеющий вес t (в нём ровно t единиц). 3)Алиса вычисляет шифротекст как c=c+z и передает его Бобу. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Дешифрование сообщения Обратная перестановка Восстановление сообщения Дешифрование Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Корректность алгоритма Необходимое свойство криптосистемы Боб вычисляет Алиса отправляет Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Криптосистема Нидеррайтера Основа криптосистемы Та же NP-трудная задача декодирования линейных кодов, что и в криптосистеме Мак- Элиса. Шифрование сообщений Основное отличие от криптосистемы Мак-Элиса В качестве базовой матрицы используется проверочная матрица группового кода. Открытый ключ представляет собой множество, состоящее из проверочной матрицы общего положения, оснащенное достаточно большим числом t. Сообщение передается не информационным блоком кодового слова, а вектором ошибок. Шифротекст же получается в виде синдрома – произведения проверочной матрицы на вектор ошибок. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Дополнение Недвоичное поле Возможно определение криптосистем над полем Галуа GF(q), в таком случае для создания открытого ключа используется еще одна матрица – диагональная матрица с элементами из GF(q). Плюсы и минусы Модификации В литературе известно множество различных модификаций этих криптосистем, например, криптосистема Нидеррайтера может быть определена для кодов с ранговой метрикой. + Шифрование и дешифрование быстрее, чем у RSA. + Быстрый рост степени защиты с увеличением длины ключа. - Большие размеры ключей и шифротекста. Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Стандарты шифрования данных DES Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции S-box

APN-функция Пусть APN-функция (почти совершенно нелинейная) Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

APN-функции и коды Пусть Теорема Теория кодированияОсновы криптографии К/с Мак-Элиса К/с Нидеррайтера APN-функции

Применение теории кодирования в криптографии Лось Антон Васильевич