Разработка новых кодов в ранговой метрике и криптосистем с открытым ключом

2.2 Оценка стойкости криптосистемы ГПТ.59.

2.2.1 Описание криптосистемы ГПТ со строковым и столбцевым скремблерами и шумовой матрицей 60.

2.2.2 Анализ представлений открытого ключа. 61.

2.2.3 Построение атаки.65.

2.2.4 Выбор стойких параметров.73.

2.3 Разработка криптосистемы с ошибками высокого веса 75.

2.3.1 Криптосистема.75.

2.3.2 Криптоанализ.79.

2.3.3 Пример.82.

2.4 Выводы.83.

3 Криптосистемы в мнимом квадратичном поле 85.

3.1 Введение.85.

3.2 Математические основы.88.

3.3 Известные криптосистемы.104.

3.3.1 Аналоги схем Диффи-Хеллмана, RSA и Эль-Гамаля.104.

3.3.2 NICE-X с квадратичным временем расшифрования .105.

3.4 Реализация и анализ криптосистемы NICE-X.109.

3.4.1 Описание реализации криптосистемы.109.

3.4.2 Достоинства и недостатки.111.

3.5 Новая модификация криптосистемы NICE-X.111.

3.5.1 Оптимизация шифрования .111.

3.5.2 Генерирование стойких ключей.ИЗ.

3.5.3 Программная реализация.114.

3.5.4 Замечания по цифровой подписи.116.

3.6 Выводы.118.

Заключение

119.

Литература

121.

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

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

Наиболее распространены помехоустойчивые коды, построенные в метрике Хэмминга, например, коды Рида-Соломона. Одни и те же шумы в кодах с разными метриками могут быть исправлены в разных количествах из-за разного веса ошибки. Особый интерес представляют метрики, в которых часть физических шумов имеет низкий вес.

Матричные коды в ранговой метрике [1] при передаче сигнала одновременно по нескольким частотам хорошо подходят для исправления ошибок, вызванными импульсными широкополосными или постоянными узкополосными шумами. Ошибки, обусловленные такими шумами, имеют более низкий вес в ранговой метрике, чем в метрике Хэмминга. Ранговые коды были предложены в 1985 г. Расширение классов кодов и создание новых кодов является важной задачей теорией кодирования. Новые коды могут обладать лучшей корректирующей способностью и быть более эффективными в частных применениях.

Теоретическими аспектами защиты информации от несанкционированного доступа занимается криптография. Современные криптосистемы делятся на два типа: симметричные (ключи шифрования и расшифрования — секретные) и с открытым ключом (один ключ — секретный, второй — публично доступный). Симметричные криптосистемы используются для шифрования большого объема данных из-за высокой скорости работы. В основе работы симметричных криптосистем, как правило, находится принцип перемешивания информации, скрытие статистики.

Криптосистемы с открытым ключом используются для электронных цифровых подписей (ЭЦП) и протоколов аутентификации и распределения ключей. Криптосистемы с открытым ключом оперируют с математическими объектами в дискретном пространстве, например, в группе или поле. Они существенно медленнее симметричных криптосистем и поэтому не используются для шифрования большого объема данных. В то же время они более универсальны и более защищены, чем симметричные криптосистемы, с позиции, что один из ключей публичный, а публичный ключ не требует защиты и может использоваться всеми пользователями.

Особый интерес представляют криптосистемы с открытым ключом, построенные на линейных кодах и основанные на трудности решения задачи декодирования сообщения с добавленными искусственными ошибками и при неизвестных порождающей/проверочной матриц кода. Вместе с искусственно добавленными ошибками они могут исправлять и обычные ошибки, возникающие при передаче информации. Открытый ключ может быть построен либо на порождающей матрице (криптосистема типа Мак-Элиса), либо на проверочной матрице (криптосистема типа Нидер-райтера). В 1991 году была опубликована криптосистема с открытым ключом, основанная на ранговых кодах (Габидулин, Парамонов, Третьяков, 1991, [22]). Она получила название ГПТ по фамилиям авторов в русскоязычной литературе и ОРТ в англоязычной. По сравнению с другими криптосистемами, основанными на линейных кодах, ее преимуществом является маленькая длина открытого ключа и, как следствие, высокая скорость шифрования/расшифрования из-за быстрого алгоритма декодирования. К сожалению, для исходных заявленных параметров криптосистема ГПТ была взломана Гибсоном [23,24]. Одновременно, Гибсон показал, как выбирать параметры криптосистемы. В дальнейшем были предложены модификации, использующие столбцевой и строковый скремблеры [25] и приводимые ранговые коды [6]. В 2005 г. Овербек предложил расширенную атаку Гибсона в [27,28] для исходного варианта ГПТ.

В практических приложениях число выполняемых шифрований данных существенно меньше числа выполняемых расшифрований. Интерес представляют криптосистемы, имеющие быстрое расшифрование. Криптосистема ШСЕ-Х [48,49] в отличие от стандартных криптосистем типа RSA, Эль-Гамаля с кубическим временем расшифрования по битовой длине параметров характеризуется квадратичным временем расшифрования. Криптосистема построена в мнимом квадратичном поле.

Актуальность темы

исследования.

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

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

Актуальной задачей является построение и анализ криптосистем с открытым ключом, обладающих высокой скоростью шифрования/расшифрования с тем, чтобы использовать криптосистемы с открытым ключом для шифрования большого объема данных. Особенно важно обеспечить высокую скорость расшифрования, так как данные шифруются реже, чем расшифруются.

Целью настоящего исследования является:

1. построение новых ранговых кодов и новых алгоритмов декодирования,.

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

В соответствии с поставленной целью были определены следующие задачи и вопросы.

1. Расширение класса кодов в ранговой метрике и построение новых алгоритмов декодирования.

2. Проведение криптоанализа криптосистем с открытым ключом, основанных на ранговых кодах, и построение криптосистем с улучшенными характеристиками.

3. Криптоанализ и анализ эффективности криптосистем с открытым ключом, построенных в мнимом квадратичном поле, имеющих быстрое расшифрование.

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

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

1. Для построения ранговых кодов в качестве порождающей матрицы выбрана (к х п) матрица Фробениуса над конечным полем вида Ц^ГИСо'.'.'Г-р Ш е с константой т, gcd (ra, ЛГ) = 1. Обычная матрица Фробениуса определяется как \iZo k-iИспользование матрицы нового вида как порождающей матрицы линейного рангового (п, к, с?)-кода позволило обобщить и расширить единственную известную конструкцию ранговых кодов 1985 г. с максимальным ранговым расстоянием.

2. Сделано предположение, что степени (п х п)-матриц над полем СгР (2), порождающих поле С^(2П), имеют равномерное распределение элементов над полем (?.Р (2). На основе гипотезы построен метод исправления ошибок стирания веса п для линейных ранговых (п, 1, п)-кодов алгоритмом декодирования по информационным совокупностям. Проведенное моделирование подтвердило гипотезу и показало эффективность алгоритма декодирования.

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

4. Предложен метод выбора столбцевого скремблера специального вида для криптосистемы на приводимых ранговых кодах. Что позволило создать криптосистему на линейных кодах с искусственной ошибкой веса большего, чем корректирующая способность кода. Одновременно криптосистема может исправлять ошибки, возникающие при передаче по каналу с шумами.

5. Разработан метод быстрого генерирования псевдослучайного целого примитивного идеала мнимого квадратичного поля. Использование метода в алгоритме шифрования криптосистемы ШСЕ-Х позволило снизить асимптотическую битовую сложность шифрования с четвертой степени до кубической по битовой длине параметров.

Теоретическая и практическая ценность.

Для коррекции ошибок в каналах с многолучевым распространением используются матричные коды. Матричные коды, построенные в ранговой метрике, успешно исправляют ошибки, вызванные импульсными шумами и эффектом замирания. С 1985 г. была известна только одна конструкция ранговых кодов с максимальным ранговым расстоянием и быстрым алгоритмом декодирования. Предложенные новые ранговые МРР коды расширяют класс известных МРР кодов с быстрым алгоритмом декодирования. Использование новых МРР кодов немного повышает стойкость криптосистем на ранговых кодах с открытым ключом. Декодирование по информационным совокупностям для ранговых кодов представляет интерес для исправления ошибок за пределами корректирующей способности кода.

Криптосистемы с открытым ключом составляют основу защищенных транзакций в сети посредством электронной цифровой подписи (ЭЦП), алгоритмов аутентификации и распределения ключей. В работе исследованы нетрадиционные криптосистемы с открытым ключом, так как они имеют важные в практическом применении специальные свойства. Одновременное шифрование и исправление ошибок криптосистемами на ранговых кодах уменьшает вычислительные ресурсы, число требуемых вычислительных модулей и экономит потребляемую энергию при беспроводной передаче данных. Быстрое расшифрование криптосистемы в мнимом квадратичном поле имеет значение, так как обычно расшифрование данных выполняется большее число раз, чем шифрование. Быстрое расшифрование экономит вычислительные ресурсы.

Апробация работы.

Результаты диссертационной работы докладывались на российских и международных конференциях:

• International Symposium on Information Theory, ISIT, Adelaide,.

Australia, 2005.

• International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2005.

• Algebraic and Combinatorial Coding Theory, ACCT, Kranevo, Bulguria, 2004.

• International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2003.

• Algebraic and Combinatorial Coding Theory, ACCT, Tsarskoe Selo, Russia, 2002.

• XLIX, XLVIII, XLVII, XLVI, XLIV ежегодных научных конференциях Московского физико-технического института, Москва-Долгопрудный, 2001;2006.

Основные результаты диссертации неоднократно обсуждались и были одобрены на научных семинарах:

• на научном семинаре в School of Information Science and Technology, Southwest Jiatong University, Китай, 2006 г.;

• на научных семинарах по теории кодирования Института Проблем Передачи Информации РАН, 2005 г.;

• на научных семинарах кафедры радиотехники Московского физико-технического института (ГУ) 2002;2007 гг.;

• на научном семинаре в Department of Information Technology, Lund University, Швеция, 2002 г.

Публикации. По теме диссертации опубликовано 12 работ, из них 1 статья в журнале из списка ВАК, 1 статья в рецензируемом сборнике научных статей МФТИ, 5 статей в сборниках трудов рецензируемых международных научных конференций, 5 докладов в Трудах научных конференций МФТИ.

Научные положения, выносимые на защиту.

1. Линейные ранговые (тг, fc, d = п—к+1) коды новой конструкции с максимальным ранговым расстоянием.

2. Декодирование ранговых кодов для плохого канала с мощными узкополосными и импульсными широкополосными шумами по методу информационных совокупностей.

3. Условия существования и оценка сложности полиномиальных и экспоненциальных атак на разные варианты криптосистемы ГПТ на основе ранговых кодов в зависимости от параметров криптосистемы.

4. Криптосистема на основе ранговых кодов с искусственной ошибкой высокого веса и наименьшей длиной открытого ключа.

5. Ускорение шифрования криптосистемы с открытым ключом ШСЕ-Х, построенной в мнимом квадратичном поле, и выбор более безопасных параметров схемы.

Содержание работы.

Первая глава содержит конструкции ранговых кодов и алгоритм кодирования/декодирования. Вначале описываются известные конструкции ранговых кодов вместе с быстрыми алгоритмами декодирования. Затем приводится новая конструкция ранговых кодов, алгоритм декодирования и обсуждается отличие новой конструкции от ранее известной. В конце главы приводятся алгоритмы декодирования по информационным совокупностям для ранговых кодов для исправления ошибок стирания за пределами кодового расстояния и результаты моделирования исправления ошибок стираний методом информационных совокупностей. Полученные результаты, изложенные в первой главе, опубликованы в [2,3,4,5].

Вторая глава описывает криптосистемы с открытым ключом на ранговых кодах. Глава начинается с оценки криптостойкости криптосистем типа ГПТ. Показывается эквивалентности разных форм.

ГПТ одной форме открытого ключа. Детально разрабатывается атака на общую форму открытого ключа на основе атаки Овербека для исходной ГПТ. Оценивается сложность атаки в зависимости от параметров криптосистемы. Предлагается способ для создания стойких параметров. Далее разрабатывается новая криптосистема на ранговых кодах, в которой искусственная ошибка имеет вес не меньше кодового расстояния. Глава заканчивается сравнением новой криптосистемы и ранее известных. Полученные результаты, изложенные во второй главе, опубликованы в [18,19,20,21].

Третья глава содержит описания криптосистем с открытым ключом с быстрым расшифрованием, построенных в мнимых квадратичных полях. Вначале даются необходимые математические основы, затем приводятся опубликованные криптосистемы. Производится анализ свойств криптосистемы, приводится модификация криптосистемы с ускорением шифрования. Полученные результаты, изложенные в третьей главе, опубликованы в [29,30,31,32].

В заключении сформулированы основные результаты диссертационной работы.

Основные результаты, полученные в данной работе.

1. Разработаны новые линейные ранговые коды с максимальным ранговым расстоянием вместе с алгоритмом быстрого декодирования. Коды являются (п, к, (I = п — к + 1) кодами с максимальным ранговым расстоянием на границе Синглтона. Новые коды являются обобщением единственных ранее известных ранговых кодов 1985 г.

2. Построен алгоритм декодирования ранговых (п, 1, п)-кодов для плохого канала с мощными узкополосными и импульсными широкополосными шумами, вызывающими стирания строк и столбцов в передаваемой кодовой матрице. Найдена доля информационных совокупностей — 29%. Проведено моделирование стираний строк и столбцов и показана возможность декодирования ошибок веса п с шансами 80−100%.

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

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

5. Построена модификация криптосистемы ШСЕ-Х с открытым ключом, построенной в мнимом квадратичном поле с ускоренным шифрованием. Исследована стойкость схемы. Предложен способ выбора более безопасных ключей.

Заключение

.

Результаты, выносимые на защиту.