Содержание к диссертации
Введение
1 Необходимые сведения о системах защиты информации и теории кодирования 12
1.1 Основные понятия криптографии 12
1.1.1 Симметричные криптосистемы 14
1.1.2 Алгоритмы с открытым ключом 15
1.1.3 Криптоанализ 17
1.1.4 Стойкость криптосистем 19
1.2 Основные понятия теории кодирования 21
1.2.1 Блоковое и поточное кодирование 21
1:2.2 Нормы, метрики и кодовые расстояния 22
1.2.3 Линейные коды 23
1.2.4 Ранговые коды 27
1.2.5 Стирания 34
2 Классические криптосистемы, построенные на линейных кодах 38
2.1 Криптосистема МакЭлиса 40
2.2 Криптоанализ системы МакЭлиса 42
2.3 Криптосистема Нидеррайтера 45
2.4 Атака на криптосистему Нидеррайтера 45
2.5 Сравнение систем МакЭлиса и Нидеррайтера 52
3 Проективные метрики 54
3.1 Проективные метрики 54
3.2 Примеры проективных метрик 56
3.3 Коды в проективных метриках 59
3.3.1 Коды в метрике на основе матрицы Вандермонда . 62
3.3.2 Коды в метрике на основе матрицы Фробениуса . 63
3.3.3 Декодирование в метрике на основе матрицы Фробениуса 64
4 Анализ модификаций криптосистем на линейных кодах 67
4.1 Модификация криптосистемы МакЭлиса 69
4.1.1 Криптосистема ГПТ 69
4.1.2 Криптоанализ системы ГПТ 71
4.1.3 Атака Гибсона 73
4.1.4 Атака Овербека 79
4.2 Модификации классической схемы Нидеррайтера 82
4.2.1 Криптосистема с дополнительной шумовой матрицей 83
4.2.2 Криптоанализ системы с дополнительной шумовой матрицей 84
4.2.3 Криптосистема на основе метрики Вандермонда . 85
4.2.4 Криптоанализ системы, основанной на метрике Вандермонда 86
5 Новая криптосистема на основе метрики, ассоциированной с матрицей Фробениуса 87
5.1 Структура новой криптосистемы 88
5.2 Алгоритм реализации новой криптосистемы 89
5.2.1 Модуль инициализации 90
5.2.2 Модуль шифрования 91
5.2.3 Модуль расшифрования 92
5.3 Моделирование криптосистемы на основе метрики Фробениуса 93
5.4 Криптоанализ новой системы 94
6 Построение системы передачи и защиты от несанкционированного доступа 102
6.1 Новая криптосистема в канале с шумами 105
6.2 Ограничения работы криптосистемы при исправлении ошибок канала 106
6.3 Сравнение с комплексом систем 108
6.4 Применение новой интегрированной системы для защиты передаваемых видеоизображений 111
6.4.1 Результаты применения алгоритмов новой криптосистемы 111
6.4.2 Согласование новой системы со стандартами . 112
6.4.3 Возможные способы увеличения быстродействия . 114
6.4.4 Применение симметричного алгоритма ГОСТ 28147-89 116
6.4.5 Применение симметричного алгоритма AES 119
Заключение 121
Список литературы 122
Приложение 127
- Алгоритмы с открытым ключом
- Криптоанализ системы МакЭлиса
- Коды в метрике на основе матрицы Вандермонда
- Модификации классической схемы Нидеррайтера
Введение к работе
Целью диссертационной работы является построение и исследование систем защиты информации с открытым ключом, основанных на алгоритме Нидеррайтера с использованием новых метрик и новых кодов для применения в составе интегрированных систем защиты от помех и несанкционированного доступа.
Для достижения поставленной цели в работе рассматриваются следующие ЗАДАЧИ.
Исследование и криптоанализ существующих модификаций системы Нидеррайтера.
Моделирование и исследование новой криптосистемы, построенной
по принципу криптосистемы Нидеррайтера. '-. |
Разработка, реализация и оценка эффективности криптографических атак на предлагаемую новую криптосистему.
Моделирование новой криптосистемы в составе экспериментальной интегрированной системы защиты от помех и несанкционированного доступа.
Моделирование и исследование новой криптосистемы в составе си- 1 стемы передачи и защиты меняющихся изображений от помех и несанкционированного доступа.
Для решения поставленных задач в работе использовались МЕТОДЫ теории информации, дискретной математики, а также имитационного моделирования, линейной алгебры и теории алгебраического кодирования.
ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ Научная новизна результатов, полученных в диссертации, заключается в следующем:
1. Введен класс проективных метрик, позволяющих модернизировать криптосистемы, основанные на линейных кодах.
Выбрана новая метрика, используемая при построении криптосистемы с открытым ключом, усиливающая криптостойкость этой системы.
Предложена криптосистема с открытым ключом, использующая новую метрику, ассоциированную с матрицей Фробениуса, и ранговые коды.
Разработан алгоритм, позволяющий использовать особенности новой криптосистемы для исправления ошибок канала.
Получены характеристики интегрированной системы помехо- и крип-тозащиты применительно к передаче видеоизображений.
Полученные в работе результаты внедрены и использованы в рамках следующих научно-исследовательских работ:
Проект №3969 аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы, 2006-2008 гг.».
Контракт номер 32/07 от 18.05.2007, заключенный с Институтом проблем управления имени акад. А.А. Харкевича во исполнение государственного контракта номер 02.514.11.4025 от 1 мая 2007 г. на выполнение научно-исследовательских работ между Федеральным агентством по науке и инновациям и Институтом проблем управления имени акад. А.А. Харкевича.
Результаты диссертационной работы используются в учебном процессе на кафедре радиотехники МФТИ (ГУ) в рамках курса «Защита Информации».
На основе разработанной модели интегрированной системы защиты от помех и несанкционированного доступа сделана оценка эффективности применения новой криптосистемы для исправления ошибок канала.
Новая криптосистема в широком диапазоне параметров в рамках интегрированной системы передачи данных более эффективна по сравнению со стандартными системами. Дополнительное увеличение крипто-стойкости в бесшумном канале может быть достигнуто за счет совместного применения симметричных алгоритмов.
АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации были доложены и обсуждены на следующих конференциях и семинарах:
Международная конференция «International Symposium on Communication Theory and Applications» (ISTA)2005, Ambleside, Lake District, UK, July, 2005.
Конференция «Математика и безопасность информационных технологий» (МаБИТ-05). МГУ им. М.В. Ломоносова (2005 г., г. Москва).
Конференция Российской криптографической ассоциации «РусКрипто 2008» (2008 г., г. Москва).
Научные конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (в 2004-2008 гг., г. Долгопрудный).
Научные семинары кафедры радиотехники МФТИ (в 2004-2008 гг., г. Долгопрудный).
ПУБЛИКАЦИИ. По теме работы опубликовано 11 работ, из них 4 статьи в журналах и сборниках научных статей, 7 тезисов докладов на научных конференциях. Две статьи в рецензируемых журналах, утвержденных в перечне ВАК.
НАУЧНЫЕ ПОЛОЖЕНИЯ, выносимые на защиту
Описание и исследование новой метрики и построение кодов в этой метрике.
Алгоритмы шифрования и расшифрования новой криптосистемы, построенной по принципу Нидеррайтера.
Криптоанализ новой криптосистемы. Выбор параметров криптосистемы.
Интегрированная система защиты от множественных помех и несанкционированного доступа.
Работа построена следующим образом. В первой главе приводится описание основных криптографических понятий, которые нужны для изложения материала остальных глав. Также приводятся необходимые сведения из теории кодирования.
Рассмотрены симметричные и асимметричные криптосистемы, разобраны основные подходы к криптоанализу систем и дано определение стойкости криптосистемы. Среди линейных кодов выделены коды Рида-Соломона и приводится описание построения ранговых кодов. Основное внимание уделяется алгебраическим методам кодирования и декодирования ранговых кодов. Особое внимание обращено на тип кодов с максимальным ранговым расстоянием (МРР-коды). Описаны алгоритмы коди-
рования и декодирования ранговых кодов. В качестве примеров рассмотрены различные варианты ошибок и методы их исправления ранговыми кодами.
Вторая глава посвящена описанию криптосистем, построенных на линейных кодах. Рассматриваются основные принципы построения криптосистем. Приводится сравнение криптосистем, построенных на линейных кодах, с другими типами криптосистем с открытым ключом. Описываются успешные атаки на существующие классические криптосистемы, построенные на основе линейных кодов. Формулируются основные проблемы, возникающие при практическом использовании криптосистемы Нидеррайтера.
В системе с открытым ключом МакЭлиса основная идея построения криптосистемы состоит в том, чтобы создать код и замаскировать его под обычный линейный код. Алгоритм МакЭлиса довольно скор и работает на порядок быстрее стандартной системы RSA, но он имеет основной недостаток - большой размер открытого ключа. Из-за большого размера открытого ключа шифртекст получается вдвое длиннее открытого ключа, это вызывает увеличение размера передаваемого сообщения и затрудняет практическое использование системы.
Криптосистема Нидеррайтера лишена описанных выше недостатков системы МакЭлиса и также основана на линейных кодах. Несмотря на все достоинства система Нидеррайтера оказалась нестойкой и была взломана Сидельниковым и Шестаковым [16]. Криптоаналитикам удалось по открытому ключу построить матрицы, схожие по структуре с матрицами закрытого ключа за небольшое количество операций. Этого оказалось достаточно для восстановления открытого текста из шифртекста.
Третья глава посвящена проективным метрикам и примерам построения кодов в различных проективных метриках.
В первом параграфе главы дается определение нормы и расстояния в проективной метрике. Рассмотрены примеры проективных метрик, особое внимание уделено метрике, ассоциированной с матрицей Фробениу-совского типа.
Далее в главе дается определение кода, оптимального в проективной метрике, а также родительского кода. На основании примеров проективных метрик рассмотрены примеры кодов в метриках на основе матрицы Вандермонда и Фробениуса. Приведено подробное описание алгоритма быстрого декодирования кода в метрике, ассоциированной с матрицей
Фробениуса.
В четвертой главе подробно описываются основные подходы к модификации кррштосистемы Нидеррайтера.
Основная идея модификаций последних лет заключается в том, чтобы как можно лучше скрыть структуру синдрома. Это делается для того, чтобы избежать структурных атак, подобных атакам Сидельникова-Шестакова.
Структура закрытого ключа в некоторых модификациях криптосистем усложняется так, чтобы синдром родительского кода выступал в роли искусственно созданной ошибки нового кода в новой метрике. В главе описываются примеры модификаций системы Нидеррайтера, делается заключение о возможности практического их применения.
Пятая глава посвящена описанию повой криптосистемы на основе метрики, ассоциированной с матрицей Фробениуса.
Подробно рассматривается структура криптосистемы в целом. Особое внимание уделяется построению кода и доказательству существования алгоритма быстрого декодирования. Описан алгоритм построения криптосистемы. Основная идея криптосистемы заключается в том, чтобы замаскировать кодовый вектор вектором искусственной ошибки, которая имеет большой ранг в новой метрике.
Далее проводится криптоанализ предлагаемой новой криптосистемы. К рассмотренной криптосистеме применимы два основных вида атак: прямые и структурные атаки. Структурные атаки - это различные модификации атаки Гибсона, адаптированные к модификациям криптосистемы, и варианты атаки Сидельникова-Шестакова. При оценке трудоемкости каждой из атак необходимо учитывать размер открытого ключа.
Проведенный криптоанализ показал, что для самого успешного структурного алгоритма атаки вычислительная сложность составит порядка 2140 при размере открытого ключа 2048 байт. На сегодняшний день это является более чем достаточным, чтобы считать, что криптосистема является стойкой.
Шестая глава посвящена применению криптосистемы на основе метрики, ассоциированной с матрицей Фробениуса в системах передачи и защиты от несанкционированного доступа. Приводится описание системы одновременной помехозащиты и защиты от несанкционированного доступа. Рассматривается работа новой криптосистемы в системе защиты информации при передаче видеоизображений.
Для исправления ошибок канала нужно наложить дополнительные ограничения на выбор матриц в модуле инициализации. Необходимо собрать статистику и, предварительно проанализировав ее, определить характер ошибок и осуществить модификацию криптосистемы с целью исправления ошибок.
Новая криптосистема использована в работе над контрактом номер 32/07 от 18.05.2007 в главе «Разработка и исследование сигнально-кодовых конструкций для передачи и защиты меняющихся изображений». В работе показано, что криптосистема может успешно применяться как часть системы с открытым ключом для передачи и защиты меняющихся изображений.
В шестой главе представлены результаты исследования алгоритмов новой криптосистемы как части системы для передачи и защиты меняющихся изображений в каналах с шумами. Быстродействие новой криптосистемы превышает быстродействие стандартной криптосистемы RSA в 20 раз и позволяет осуществлять не только защиту передаваемой информации от нелегального доступа, но и исправлять ошибки канала.
Скорость шифрования в системе можно заметно увеличить, осуществляя шифрование изображения с помощью более производительных симметричных алгоритмов, а шифрование сеансового ключа осуществлять уже при помощи предлагаемой системы. Но такая модификация может быть применена только для случая канала без шума. Например, при использовании в качестве симметричного алгоритма AES или ГОСТ 28147-89. При применении одного из симметричных алгоритмов и выборе соответствующих параметров ассиметричной криптосистемы можно гарантировать передачу изображения в формате стандарта телевидения высокой четкости.
Алгоритмы с открытым ключом
Алгоритмы с открытым ключом, также называемые асимметричными алгоритмами, используют два различных ключа для зашифрования и расшифрования [21]. Ключ, используемый при расшифровании, не может быть вычислен из ключа зашифрования. Ключ зашифрования может быть открытым (открытый ключ): кто угодно может воспользоваться этим ключом для зашифрования сообщения, но расшифровать сообщение может только легальный пользователь, знающий ключ расшифрования (закрытый ключ).
Сторона В выбирает пару (е, d) и шлет ключ шифрования е (открытый ключ) стороне А по открытому каналу, а ключ расшифрования d (закрытый ключ) защищен и секретен. Закрытый ключ не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом). Чтобы послать сообщение т стороне В, сторона А применяет функцию шифрования, определенную открытым ключом е : Ее(т) = с, где с - полученный шифртекст. Затем сторона В расшифровывает шифртекст с, применяя обратное преобразование Dd, однозначно определенное значением d.
Основная задача криптографических алгоритмов - сохранение открытого текста в тайне от злоумышленников. Предполагается, что злоумышленники располагают неограниченным доступом к линиям связи между отправителем и получателем. Основной задачей криптоанализа является восстановление открытого текста без доступа к ключу (дешифрование). Успешный криптоанализ позволяет восстановить отрытый текст или открытый ключ. Средствами криптоанализа можно обнаружить слабые места в криптосистемах. Попытка криптоанализа называется крипто-атакой (или просто атакой).
Основное допущение криптоанализа состоит в том, что секретность сообщения полностью зависит от ключа [2]. Это допущение основывается на предположении о том, что криптоаналитик располагает полным описанием алгоритма и его реализации. В реальных условиях криптоана-литики не всегда обладают подобной информацией. Но такое допущение вполне допустимо, так как если противник не может взломать алгоритм, зная, как он работает, значит, ему не удастся это сделать, если он не обладает какими-либо знаниями об алгоритме.
Существует четыре основных типа криптоатак, в каждом из них предполагается, что криптоаналитику полностью известен алгоритм шифрования:
Атака на основе только шифртекста. Криптоаналитик располагает шифртекстами нескольких сообщений, зашифрованных одним и тем же алгоритмом. Задача состоит в том, чтобы дешифровать как можно больше сообщений. В лучшем случае, он сумеет найти ключи, использованные для шифрования сообщений. Это позволит расшифровывать другие сообщения, зашифрованные теми же ключами.
Атака на основе открытого текста. Криптоаналитик располагает доступом не только к шифртекстам, но и к открытому тексту этих сообщений. Задача состоит в определении ключей, примененных для шифрования сообщений. Целью является дешифрование других сообщений, зашифрованных теми же ключами.
Атака на основе подобранного открытого текста. Криптоаналитик располагает доступом не только к шифртекстам и соот ветствующим им открытым текстам, но и обладает возможностью выбирать открытый текст для шифрования. Такой случай предоставляет больше возможностей, чем вскрытие с использованием открытого текста, так как можно выбирать для шифрования блоки открытого текста специальной структуры. Такой подход может предоставить дополнительную информацию о ключе. Задача криптоана-литика состоит в раскрытии ключей, примененных для шифрования сообщений, или алгоритма, позволяющего дешифровать все новые сообщения, зашифрованные теми же ключами.
Атака на основе адаптивного подобранного открытого текста. Криптоаналитик может выбирать шифруемый текст, а также уточнять свой последующий выбор на основе полученных ранее результатов шифрования. При вскрытии с использованием подобного подхода криптоаналитик может выбрать для шифрования небольшой блок открытого текста, затем выбирать следующий блок, используя результаты первого выбора.
В зависимости от сложности взлома разные криптоалгоритмы обеспечивают различные степени защиты. Если время, необходимое для взлома алгоритма, больше времени, в течение которого зашифрованные данные должны сохраняться в тайне, алгоритм можно считать стойким. Если объем данных, зашифрованных одним ключом, меньше, чем объем данных, необходимых для взлома алгоритма, алгоритм можно считать стойким. Но всегда есть шанс появления новых достижений в области криптоанализа. Ларе Кнудсен [10] классифицировал сложность взлома алгоритмов по четырем категориям:
1. Полное вскрытие. Криптоаналитик находит ключ (ключи) такой, что DK{C) = М.
2. Глобальная дедукция. Криптоаналитик находит альтернативный алгоритм А, эквивалентный DK{C) без знания ключа К.
3. Случайная или частичная дедукция. Криптоаналитик получает открытый текст для перехваченного шифрованного сообщения.
4. Информационная дедукция. Криптоаналитик получает некоторую информацию о ключе или открытом тексте. Под информаци . ей понимается несколько битов ключа, дополнительные сведения о структуре и форме открытого текста и тому подобное. 1.1.4 Стойкость криптосистем
Стойкость криптосистем может быть оценена через теоретико-информационный подход, или может быть строго доказана се стойкость, или же подсчитана вычислительная стойкость. В случае теоретико-информационного подхода подразумевается, что криптоаналитик обладает неограниченными вычислительными и временными ресурсами. В таком случае производится попытка вычислить, какой объем информации об открытом тексте доступен противнику при перехвате, например, шифртекста. Применение теоретико-информационного подхода связано с большими вычислительными трудностями. Никакая система с открытым ключом не может быть совершенной, так как теоретически всегда возможно подобрать открытый текст, соответствующий перехваченному шифртек-сту.
Определение 1. Система называется доказуемо стойкой, если построено доказательство того, что раскрытие криптосистемы также слооїсно, как и решение некоторой трудной математической задачи.
Это означает, что любой алгоритм решения этой задачи приводит к раскрытию системы, и наоборот. Поэтому система надежна до тех пор, пока не существует эффективной реализации алгоритма атаки. Число доказуемо стойких систем очень мало. Наиболее часто используемым на практике является вычислительный подход к определению стойкости, который состоит в вычислении сложности наиболее эффективных на текущий момент атак, раскрывающих систему. При этом предполагается, что система достаточно хорошо изучена, и наиболее эффективные атаки на нее уже найдены.
Определение 2. Система называется вычислительно стойкой, если лучшие известные атаки имеют сложность выше заранее определенного порога.
Как правило, надежность вычислительно стойкой системы напрямую связана с некоторой трудноразрешимой задачей. Тем не менее следует понимать, что эквивалентность между разрешимостью этой задачи и стойкостью системы в большинстве случаев не может быть строго доказана.
Стойкость большинства известных симметричных криптосистем и криптосистем с открытым ключом оценивают, используя вычислительный подход. Практически все криптосистемы (кроме одноразовых блокнотов [2]) можно вскрыть с использованием только шифртекста простым перебором возможных ключей и проверкой осмысленности полученного открытого текста. Такой метод называется лобовой атакой.
Криптоанализ системы МакЭлиса
Вернемся к описанию криптосистемы МакЭлиса с помощью кодов Гоп-пы. Матрица G, являющаяся порождающей матрицей кода Гоппы, и ее элементы имеют между собой определенную алгебраическую связь, которая и определяет код как код Гоппы. Матрица S необходима, чтобы разрушить имеющиеся связи так, чтобы матрица G имела вид матрицы без видимых закономерностей. Тогда код, заданный матрицей Gmb, будет выглядеть как случайный. Любой алгоритм декодирования произвольного кода дает возможность осуществить прямую атаку на систему МакЭлиса.
Рассмотрим пример. Выберем код Гоппы со следующими параметрами: п = 1024, к = 524, t = {d — 1)/2 50. Что касается атаки перебором, параметры в примере МакЭлиса подобраны так, что ее невозможно применить. Действительно, существует порядка 10149 возможных полиномов G(x), более 103 векторов упорядочения и около 10750 различных матриц S. При таких параметрах никакая атака грубой силой не выполнима за приемлемое время.
Для приведенного примера сложность атаки, рассмотренной МакЭлисом, составит порядка W\ = 289 операций.
Авторы [23] несколько оптимизировали предложенный МакЭлисом алгоритм и получили для параметров кода п = 1024, к = 654, t = 37 вычислительную сложность атаки порядка W\ = 275. Е.А. Крук в своих работах 24] и [25] показал, как можно значительно улучшить алгоритм восстановления открытого текста по пніфртексту без знания секретных ключей.
Для рассматриваемого примера количество операций в алгоритме Крука составит порядка W\ = 259. Этот результат является лучшим для рассматриваемого вида атак на классическую криптосистему МакЭли-са. Если отказаться от декодирования всех сообщений, а ограничиться небольшой, но заметной их частью, то сложность можно понизить еще больше.
Другой идеей взлома криптосистемы МакЭлиса является восстановление закрытого ключа по открытому. Известные на сегодняшний день структурные атаки на систему МакЭлиса заметно менее успешны, чем прямые атаки. К тому же структурным атакам посвящено существенно меньше работ, чем прямым. Гибсон в работе [31] показал, что если известен вектор упорядочения, то взлом системы МакЭлиса может быть упрощен.
Другой подход к нахождению секретных ключей основан на поиске родительского ОРС-кода для заданного кода Гоппы. Шамир и Хейман [29] построили систему уравнений, позволяющую найти секретный ключ. Однако эта система имеет слишком много побочных решений, кроме секретного ключа. В работе [30] исследовались слабые ключи (ключи особого вида, для которых иногда возможно восстановление проверочной матрицы кода). Однако число таких ключей экспоненциально мало относительно их общего числа. Значит, слабые ключи можно легко выделить на стадии генерирования ключей системы.
Следует отметить попытку модификации криптосистемы МакЭлиса. В работе [36] описана идея воспользоваться группой автоморфизмов кода Гоппы и добавлять искусственные ошибки веса, превосходящего корректирующую способность кода. При этом криптоаналрітику придется решать задачу практически полного декодирования кода, вместо декодирования в пределах корректирующей способности, тем самым повысив стойкость системы к прямым атакам.
Для осуществления первого вида атак необходимо решить уравнение 2.5.0.21. Для нахождения вектора е, удовлетворяющего уравнению 2.5.0.21 с весом w(e) t, необходимо выполнить экспоненциальное от длины п этого вектора число операций. При п 100 на сегодняшний день практически реализовать такую атаку невозможно.
Две рассматриваемые системы различаются скоростью передачи. Если код характеризуется низкой скоростью, т.е. к/п - малое число, то скорость передачи в системе Нидеррайтера всегда выше по сравнению с системой МакЭлиса. Поэтому архитектуру криптосистемы Нидеррайте-ра можно назвать более оптимальной. Дальнейшая работа посвящена в основном построению систем по принципу Нидеррайтера.
Шифрование сообщения е в системе Нидеррайтера состоит в вычислении его синдрома, шифрование можно произвести за 0((п — к)п) операций. Сложность расшифрования равна сложности восстановления вектора е и определяется, в основном, трудоемкостью алгоритма декодирования (п, й)-кода и не превосходит 0(п3) операций.
В криптосистеме Нидеррайтера в качестве открытой информации выступают векторы е веса t и менее. Для ее реализации необходимо иметь алгоритм, который отображает множество всех r-значных векторов длины s в множество Wt, векторов длины п и веса не выше t. Причем s r(t, N) = [logr Х =о( )(г -О ] логарифм числа возможных сообщений.
Система Нидеррайтера полностью определяется как проверочной матрицей В , так и ортогональной к ней порождающей матрицей А . Поэтому открытым ключом этой системы естественно считать матрицу, которая содержит меньшее число строк, хотя шифртекст с = еВ на практике обычно строится с помощью матрицы В .
Коды в метрике на основе матрицы Вандермонда
В примере 4 рассмотрена метрика, построенная на обобщенной матрице Вандермонда. Родительским кодом для такой метрики является обобщенный код Рида-Соломона (ОРС-код).
Далее будем выбирать yi так, чтобы они не совпадали ни с одним ХІ из 3.2.0.2. В этом случае объединение матриц U и G также будет иметь структуру обобщенной матрицы Вандермонда. Так как максимально возможное число столбцов обобщенной матрицы Вандермонда над полем GF(q) составляет q + 1, то размерность кода к должна удовлетворять соотношению к + N q + 1. гр
Код С, задаваемый матрицей G из 3.3.1.2, является кодом с максимальным расстоянием в метрике, рассмотренной в примере 4: dF(C)=n-k+l. Рассматриваемый код может исправлять вплоть до tk = l(dF(C) - 1)/2] = [(n - k)/2] ошибок в рассматриваемой в примере 4 проективной метрике, ассоциированной с матрицей Вандермонда.
Декодирование рассмотренных кодов в метрике из примера 4 можно свести к декодированию ОРС-кодов. В свою очередь для ОРС-кодов существуют быстрые алгоритмы декодирования. Пусть с = д + е, где д -кодовый вектор, а е - вектор ошибки. Пусть норма вектора ошибки равна t. Тогда е можно представить в виде линейной комбинации векторов гщ: е = mi/i + m2/2 + ... + mNfN, причем d#(m) = t, я т = (т,і,т2, ...,гадг)т. Авторами работы [12] при рассмотрении конкатенации матриц U и G доказано, что быстрый алгоритм декодирования существует, если t t .
Элементы матрицы G/. выбираются так, чтобы элементы матрицы Q в совокупности были независимы над базовым полем. Если верхняя часть матрицы в 3.3.2.1 используется для определения метрики, то нижнюю часть будем использовать для построения кода.
Если некоторый вектор а рассматривать как набор к информационных символов, то кодовый вектор можно определить из следующего уравнения: y = aGk. (3.3.2.2)
При условии, что ранг матрицы F равен п, получаем s+m п. Таким образом, минимальное расстояние кода не меньше п—к+1. С другой стороны, согласно границе Сипглтона, кодовое расстояние в любой метрике не может превосходить п — к + 1. В результате приходим к выводу, что dp = п — к + 1. В работе [12] авторы показали, что для предложенного выше кода существует алгоритм быстрого декодирования.
Будем рассматривать шифртекст как сумму: с = д_ + е, где д_ - кодовый вектор, е - вектор ошибки. N Будем считать, что норма вектора е в новой метрике равна t. Тогда вектор ошибки можно представить в следующем виде:
На сегодняшний день существует несколько модификаций криптосистемы, среди которых можно выделить три основных подхода. Во-первых, зашумление проверочной матрицы кода введением дополнительной скрывающей матрицы. Например, в работе [13] в качестве скрывающей матрицы была предложена матрица единичного ранга. В работе [12] использовались скрывающие матрицы ранга больше единицы. Второй подход к модификации заключается в использовании различных метрик, отличных от классической хэмминговой метрики.
Третий вариант модифицирования классического алгоритма Нидер-райтера - это построение кодов с набором специфических свойств. Стоит отметить, что в последнее время довольно успешно применяется сочетание сразу двух или более из описанных выше способов модификаций.
Основная идея модификаций последних лет заключается в том, чтобы как можно лучше скрыть структуру закрытого ключа. Это делается для того, чтобы избежать структурных атак, подобных атакам Сидельникова-Шестакова. Структура закрытого ключа усложняется так, что родительский синдром также выступает в роли искусственно созданной ошибки нового кода в новой метрике. В модификации, предложенной авторами [12], шифртекст, имеющий вид с = HpublR = S(F + GrU)Pm, можно представить в виде суммы векторов д + е, умноженной на некоторую шумовую матрицу S. Для расшифрования легальному пользователю необходимо сначала найти вектор ошибки, применив алгоритм быстрого декодирования некоего нового кода. А затем уже применять алгоритм быстрого декодирования в родительском коде, получая в результате открытый текст. Таблица 4.1: Примеры модификаций криптосистем на линейных кодах N Код Метрика Вид шифртекста ГКриптосистема Коды с Рассмотрена максима- Ранговая авторами Вег 1 льным ранговым расстоянием метрика тНр„(, = mSH ger Т. и Loi-dreau P. в 2004 г. Обобщен- Метрика на основе Предложена 2 ные коды матрицы Габидулиным Рида- Вандермонда ПриьШ = S(F + GrU)Pm Э.М. и Оберни Соломона хиным В.А. в 2002 г. 3 Моди- Метрика на основе Предложена фицирован- матрицы П ып = S(F + GTU)Pm Габидулиным ные ранго- Фробениуса Э.М. и Самохи вые коды ной М.А. в 2005 г.
Криптосистема с ранговой метрикой и кодами с максимальным ранговым расстоянием (первая строка в таблице 4.1) была предложена Т. Berger и P. Loidreau в 2004 году на конференции [32] INDOCRYPT. Криптосистема с обобщенными кодами Рида-Соломона, построенными в метрике на основе матрицы Вандермонда (вторая строка в таблице 4.1), была предложена Габидулиным Э.М. и Обернихиным В.А. в 2002 году, полное ее описание приведено в работе [12]. Последняя модификация криптосистемы Нидеррайтера с модифицированными ранговыми кодами в проективной метрике на основе матрицы Фробениуса была подробно описана впервые в работе [40] в 2005 году.
Кроме использования кодов Гогшы и Рида-Соломона в криптосистемах с открытым ключом, основанных на линейных кодах, предлагалось использовать и другие коды. Например, было предложено использовать двоичные коды Рида Маллера [18], алгеброгеометрические коды [19], низкоплотностные коды с проверками на четность [20]. Но все эти модификации не были подробно исследованы или имели существенные недостатки.
В данной главе будут рассмотрены модификации классических криптосистем с открытым ключом, основанные на линейных кодах. При описании криптосистем используется понятие проективных метрик, определения и примеры, подробно разобранные в главе 3.
Модификации классической схемы Нидеррайтера
Для обобщенных кодов Рида-Соломона в оригинальной системе Нидеррайтера оказалось невозможно скрыть их структуру, несмотря на использование матрицы-скремблера S. Однако семейство ОРС кодов - одно из немногих семейств, для которых известен быстрый алгоритм де кодирования. Поэтому возникла естественная идея починить систему, т. е. модернизировать с целью усиления криптостойкости. Существует несколько различных модификаций.
Для получения открытого текста легальный пользователь сначала рассматривает вырожденный случай, когда Л = 0. Если нельзя расшифровать шифртекст с таким предположением или обнаруживается ошибка, вес которой превышает допустимый (для исправления), тогда выбирается следующее значение параметра Л. Эти операции следует выполнять до тех пор, пока при помощи алгоритма быстрого декодирования не будет найдено истинное значение открытого текста. Параметр Л может принимать q — 1 различных значений. 4.2.2 Криптоанализ системы с дополнительной шумовой матрицей
Для системы с дополнительной шумовой матрицей была предложена структурная атака, основывающаяся на особенностях структуры проверочной матрицы. Открытый ключ можно представить в систематическом виде:
Полное количество уравнений в системе 4.2.2.3 равно С С _Г, которые содержат r(N — г) переменных. Такая система может быть решена за сравнительно небольшое время.
В рассмотренной криптосистеме для открытого ключа размером в 12 килобит вычислительная сложность структурной атаки составила порядка 275, при этом количество кодовых слов равно 2136. Таким образом, предложенная структурная атака оказалась успешной, а построенную криптосистему па сегодняшний день нельзя считать стойкой. 4.2.3 Криптосистема на основе метрики Вандермонда
В работе [12] авторами предложена криптосистема, построенная по принципу системы Нидеррайтера, в которой впервые применяются сразу все рассмотренные типы модификации. В данной модификации используется проективная метрика, ассоциированная с матрицей Вандермонда, которая была подробно рассмотрена в главе 2.
После получения шифртекста легальный пользователь умножает его на (ST) l и применяет алгоритм быстрого декодирования в F-метрике. В результате легальному пользователю становятся известны векторы д и е по отдельности. Далее к вектору е необходимо применить алгоритм быстрого декодирования родительского кода для получения вектора т. Затем необходимо вектор т умножить на Р- , в результате чего легальному пользователю станет известен вектор исходного открытого текста т. 4.2.4 Криптоанализ системы, основанной на метрике В ан дермонда
На первый взгляд рассмотренную модификацию криптосистемы Нидеррайтера, основанную на метрике Вандермонда, молено назвать стойкой, так как рассмотренные выше атаки классической системы для нее не будут иметь успеха. Но при выборе определенных параметров можно построить успешную атаку.
Другим примером нестойкой модификации является случай, когда код С состоит только из нулевого вектора. В этом случае модификация сводится к классической системе Нидеррайтера, которая нестойка к атаке Сидельникова-Шестакова.
Из рассмотренных примеров следует, что при построении новых модификаций классических криптосистем, основанных на линейных кодах, следует тщательно выбирать параметры модифицированных систем. Это накладывает дополнительные ограничения на выбор порождающих (проверочных) матриц линейных кодов. Тем самым уменьшается мощность множества всех открытых ключей, что может привести к понижению стойкости криптосистемы к прямым атакам. В свою очередь для повышения стойкости будут выбираться другие параметры криптосистемы так, что размер ключей увеличится. Глава 5
Новая криптосистема на основе метрики, ассоциированной с матрицей Фробениуса Большой объем открытого ключа - одна из двух основных проблем, возникающих при практическом использовании классических криптосистем, построенных на основе линейных кодов. Оригинальная система Ма-кЭлиса на кодах Гоппы при стойкости порядка 260 двоичных операций для взлома имеет открытый ключ более 500 килобит. Вторая проблема - успешная реализация быстрых алгоррітмов атак, не позволяющих считать криптосистему стойкой. Наиболее актуальна эта проблема для криптосистемы Нидеррайтера и ее модификации. Размер ключа в таких системах будет меньше, чем в системах макэлисовского типа, построенных с теми же параметрами, но стойкими их назвать нельзя.
Использование в криптосистемах ранговых кодов позволяет решить первую проблему, а именно существенно уменьшить длину ключа системы. Применение дополнительных шумовых матриц и построение кодов специального вида в различных метриках позволяет качественно улучшить стойкость криптосистемы.
В первых двух параграфах данной главы приводится полное описание структуры новой криптосистемы, подробно описывается алгоритм ее построения и проводится криптоанализ.
Моделирование криптосистемы проведено при различных параметрах, выбранных исходя из требований оптимальности практического применения. На основе полученных рекомендаций и значений параметров делается заключение о возможности практического применения новой криптосистемы.
Для выяснения стойкости новой криптосистемы в пятом параграфе разбирается наиболее успешный на сегодняшний день алгоритм атаки и показывается, что его вычислительная сложность велика и криптосистему можно считать стойкой.
Новая криптосистема строится на основе новой проективной метрики, описанной в пункте 3.2. Используемая метрика подробно описана в примере 3.3.2. Построение системы осуществляется по принципу Нидер-райтера с применением всех известных на сегодняшний день способов повышения криптостойкости и быстродействия системы.
Разработка протоколов и алгоритмов несколько отличается от их реализации на основе определенной операционной системы. С теоретической точки зрения практика и теория неотличимы, но в действительности различие между ними всегда есть. Очень часто возникают дополнительные задачи, которые необходимо решать, учитывая специфику новых алгоритмов и типов систем. Причины могут быть различными - например, в предложенном методе слишком велики требования к скорости канала, или протокол работает слишком медленно, или для применения непосредственно самого алгоритма необходимо входные данные приводить к стандартизованному (или специальному) виду.
В случае рассматриваемой новой криптосистемы для применения модуля шифрования необходимо поставить в соответствие открытому тексту последовательность слов, таких, что их вес в заданной метрике не превышает некоторого значения t. Существует множество способов реализации. Например, самым простым способом поставить в соответствие открытому тексту блоки с дополнительным ограничением имеет следующий алгоритм.
