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

На правах рукописи

Кшевецкий Александр Сергеевич

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

Специальное/л. 05.13.17 - Теоретические осноиы информатики

АВТОРЕФЕРАТ диссертации па соискашю ученой степени кандидата физико-математических наук

Москиа - 2007

003056851

Работа выполнена в Московском физико-техническом институте (государственном университете)

Научный руководитель: доктор технических наук,

проф. Габидулин Эрнст Мухамедович

Официальные оппоненты: доктор физико-математических паук,

Зиновьев Виктор Александрович,

кандидат физико-математических наук Соловьева Фаина Ивановна

Ведущая организация: Санкт-Петербургский государственный

университет аэрокосмического 1 ф иборострое! I и я

Защита состоится * Ш » _ 2007 г. в_

часов на заседании диссертационного совета Д.002.077.01 при Институте проблем передачи информации РАН но адресу: 127994, Москва, ГСП-4, Большой Каретный переулок, дом 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан « -3 » 2007 г.

Ученый секретарь диссертационного совета Д.002.077.01 доктор физико-математических наук

И. И. Цитович

Общая характеристика работы

Актуальность темы исследования

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

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

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

Теоретическими аспектами защиты информации от несанкционированного доступа занимается криптография.

Особый интерес представляют криптосистемы с открытым ключом, построенные на линейных кодах и основанные на трудности решения задачи декодировании сообщения с добавленны-

'Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации. 1985, т. 21, N 1, с. 3-14

л

ми искусственными ошибками и при неизвестных порождающей/проверочной матриц кода. Вместе с искусственно добавленными ошибками они могут исправлять и обычные ошибки, возникающие при передаче информации. Открытый ключ может быть построен либо па порождающей матрице (криптосистема типа МакЭ-лиса), либо на проверочной матрице (криптосистема тина Нидеррай-тера). В 1991 году была опубликована криптосистема с открытым ключом, основанная на ранговых кодах2. Она получила название ГПТ по фамилиям авторов в русскоязычной литературе и GPT в англоязычной. По сравнению с другими криптосистемами, основанными па линейных кодах, ее преимуществом является маленькая длина открытого ключа и, как следствие, высокая скорость шифрования/расшифрования из-за быстрого алгоритма декодирования. Важной задачей является построение единых методов совместных помехоустойчивого кодирования и защиты от несанкционированного доступа. Проблема является особенно актуальной для мобильных устройств связи, в которых уменьшение числа вычислительных модулей означает большее энергосбережение.

В практических приложениях число выполняемых шифрований данных существенно меньше числа выполняемых расшифрований. Интерес представляют криптосистемы, имеющие быстрое расшифрование. Криптосистема NICE-X3 в отличие от стандартных криптосистем тина RSA, Эль-Гамаля с кубическим временем расшифрования по битовой длине параметров характеризуется квадратичным временем расшифрования. Криптосистема построена в мнимом квадратичном иоле. Актуальной задачей является построение и анализ криптосистем с открытым ключом, обладающих высокой скоростью шифрования/расшифрования с тем, чтобы использовать криптосистемы с открытым ключом для шифрования большого объема данных.

Целыо настоящего исследования является: 1) построение новых ранговых кодов и новых алгоритмов декодирования, 2) построение и анализ нетрадиционных криптосистем с открытым ключом: а) па

2Е. M. Gabidulin, А. V. Paramonov, О. V. Tretjakov. Ideals over a non-commutative ring and their application in cryptology // Advances in Cryptology - EuroCrypt'91, LNCS 547, D. W. Davies, Ed., Springer-Verlag, 1991, pp. 482-489.

3Paulus S., Tokagi T. A new public-key cryptosystem over a quadratic order with quadratic decryption time // Journal of Cryptography. 2000, vol. 13, no2, pp. 2C3-272.

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

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

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

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

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

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

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

1. Для построения ранговых кодов в качестве порождающей матрицы выбрана (к х п) матрица Фробениуса над конечным полем GF(<J/V) вида ||<7? ||;Го.Х-1> 9; € GF(gЛГ) с константой т, gcd(m, Ы) = 1. Обычная матрица Фробениуса определяется как ||;~0Использование матрицы нового вида как порождающей матрицы линейного рангового (п, к,й)-кода позволило обобщить и расширить единственную известную конструкцию ранговых кодов 1985 г. с максимальным ранговым расстоянием.

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

кодирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертационной работы докладывались на российских и международных конференциях: 1) International Symposium on Information Theory, ISIT, Adelaide, Australia, 2005, 2) International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2005, 3) Algebraic and Combinatorial Coding Theory, ACCT, Kranevo, Bulguria, 2004, 4) International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2003, 5) Algebraic and Combinatorial Coding Theory, ACCT, Tsarskoe Selo, Russia. 2002,

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

Основные результаты диссертации неоднократно обсуждались и были одобрены на научных семинарах: 1) School of Information Science and Technology, Southwest Jiatong University, Китай, 2006 г., 2) по теории кодирования Института Проблем Передачи Информации РАН, 2005 г., 3) кафедры радиотехники Московского физико-технического института (ГУ) 2002-2007 гг., 4) Department of Information Technology, Lund University, Швеция, 2002 г.

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

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы из 65 наименований. Объем диссертации составляет 128 стр.

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

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

Первая глава содержит описание известных и построенных в диссертации конструкций ранговых кодов и алгоритмов кодирования и декодирования.

В первом разделе главы описаны известные конструкции ранговых кодов.

Пусть GF(q) обозначает базовое конечное иоле Галуа, GF(qN) - расширение поля степени N.

Ранговой нормой вектора (ai,..., ап), a* G GF(çA), называется максимальное число линейно независимых координат щ над основным нолем GF(q). Ранговое расстояние между двумя векторами определяется как ранговая норма разности двух векторов. Ранговое расстояние линейного кода над полем GF(qN) определяется как

минимальное ранговое расстояние между кодовыми словами.

Пусть Н - проверочная ((п — к) х п)-матрица, а в - порождающая (к х п)-матрица с элементами из бТ*1^) линейного (п, &)-кода ' С над нолем п <\ЛГ. Для любого линейного (п, к, с?)-кода

расстояние <1 удовлетворяет й < п — к + 1. Ранговые коды, для которых достигается граница Синглтона й = п — к + 1, называются кодами с максимальным ранговым расстоянием, МРР кодами.

Для ноля СГ^) введем символ [г] = пЫ л', ой = а«' яо" \ Пусть Ы £ г = 1 ,...,п - линейно независимы над

Тогда

Н =

/11

(11

/12 /г'1'

а?

М-2] ,[¿-21.

М,4 /Г21

В'

¿=0.^-2 .7 = 1. .п

(1)

проверочная матрица рангового МРР кода С с расстоянием ¿<п.

Порождающей матрицей в для рангового МРР кода С с расстоянием <1 < п является матрица

,И

¡=0..(с-1

3 = 1..п

, снт = о,

(2)

<7; € СР(дК), г = 1,... ,п, линейно независимы над

Пусть ш - информационные символы. Кодовое слово - ё = тС. Быстрое декодирование принятого слова у = g 4- е, искаженного ошибкой е, выполняется алгоритмом деления Евклида для линеаризованных многочленов.

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

Пусть вц, С22, • • • 1 Срр - порождающие матрицы (п;, ¿¡)-кодов в ранговой метрике над нолем г = 1,...,р. Матрицы С,-,-

- порождающие матрицы ранговых кодов. Порождающая матрица для приводимого рангового кода Ср:

С„

Си 0 . 0 0

^21 . 0 0

Ср-1,2 ■ 0

Ср, 2 • Ср.р 1 Срр

(3)

для некоторых {к( х п;)-матриц С^, г = 2,... ,р, ] = 1,... ,р - 1 над

р р

Длина кода Ср - п — размерность - к — ^ расстоя-

>=1 ¡=1 пие - Б — т1п(«/1,... ,йр), где - расстояния кодов, определенных

матрицами С;;.

Пусть т = (т1,...,тр) является информационной последовательностью. Кодовое слово - Е = гав. Быстрое декодирование принятого слова у = Е+е, искаженного ошибкой е, осуществляется блоками. Вначале декодируется последний блок сообщения тр из ур быстрым алгоритмом декодирования кода, заданного (1рр, затем шр_1 из Ур-\ с учетом найденного тр и т.д.

Матричные ранговые (п, 1,п)-коды могут использоваться в условиях мощных импульсных широкополосных и постоянных узкополосных шумов. Матричный код можно построить следующим образом.

Пусть порождающая матрица для кода - вектор § = (<7ь #2, ••• ,9п) — (а"1, а"2,..., ои"), где а - примитивный элемент поля GF(2n). Матрица А на полем GF(2), представляющая поле GF(2n), находится из условия = gA. Тогда кодовое слово в мат-

п

ричном виде выражается как V = ]П:r1•Au,.

1=1

Если матрица А - симметричная матрица, то кодовая матрица также симметричная. Такие ранговые коды называются симметричными.

Во втором разделе главы описана конструкция нового класса ранговых кодов, быстрые алгоритмы кодирования и декодирования.

Рассмотрим матрицу

Нт =

¿=о..<г-2

3 ] = 1..П

(4)

для некоторого целого т с элементами 6 GF(gjV), п < ./V, линейно независимыми над GF(g). Доказаны следующие теоремы.

Теорема 1. Если gcd(m)./V) = 1, то матрица Нт определяет проверочную матрицу МРР кода.

Теорема 2. Для кода над GF(<7;v) с проверочной матрицей

Н,„ порождающая матрица имеет вид

п=0..к-1

Сжт —

-1т

91

7 = 1..п

где к = п — (I + 1 и элементы д, линейно независимы над GF((¡, ).

Теорема 3. Матрица НП1 определяет МРР код (множество кодовых слов), которые не могут быть получены из первоначальной констпрукции проверочной матрицы вида Н. При т — 1 проверочные матрицы совпадают Нт=1 = Н и задают один код. В общем случае коды различны.

Для порождающей матрицы Ст кодовое слово g, соответствующее информационным символам (щ,..., Щ-1), выражается через линеаризованные многочлены F(.г) специального вида g =

№), П92), %)), Р(г) = £

1=0

Алгоритм декодирования новых ранговых кодов основан на алгоритме декодирования известных ранговых кодов. Алгоритм декодирования использует алгоритм деления Евклида для линеаризованных многочленов. В основе модификации находится использование линеаризованных многочленов специального вида: F(z) =

г

^/¡г'""', /г Ф 0. Введем норму многочлена F(г) как число

Г: |Р(*))|=г.

Теорема 4. Линеаризованный многочлен F(г) = /^г^^ с

7=0

/г = 1 над полем СР(дк) имеет не более г линейно независимых над GF(g) корней, если gcd(?7г, /V) = 1.

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

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

Информационная совокупность - это минимальное подмножество символов кодового слова, позволяющее восстановить информационный вектор.

к

Пусть матричный код над определен как: М = ^ ^¿А;,

1=1

где х = (агх,... ,Хк), X; € 2) - информационные символы, и А, - линейно независимые над С/г(2) (п х т)-матрицы.

Множество Бк из к элементов кодового слова М называют информационной совокупностью, если можно найти все первоначальные информационные символы (#1,... ,Хк) из

Теорема 5. Пусть Рзк - вероятность того, что случайная выборка 15к из М является информационной совокупностью. Пусть случайно выбранные матрицы А; имеют однородное распределение элементов над СР{2). Тогда, Р^. равняется вероятности Рк того, что случайная (к х к) матрица с однородным распределением элементов над £7^(2) не вырождена: Р$1с = Рк* 0.29.

Рассмотрим представление конечного поля GF(2n) поля матрицами. Пусть (п х п) матрица А представляет примитивный элемент поля. Пусть ранговый (п, 1,п)-код в матричном виде определяется

У = £><А<\

>=1

Г и и о т е з а 1. Матрицы А', г = 1..2" — 1, имеют почти однородное распределение элементов над СР{2) для большого п. Часть информационных совокупностей среди всех выборок £„ из V составляет Рп ~ 0.29 для большого п.

В основе разработанных алгоритмов декодирования матричных ранговых (п, 1, п)-кодов находится идея случайной выборки тг двоичных элементов из кодового слова (матрицы) и проверке, является ли данная выборка информационной совокупностью. Результаты выполненного численного моделирования подтверждают гипотезу. Показано, что плотность информационных совокупностей среди всех выборок составляет 29%.

Также проведено моделирование на возможность исправления ошибок стирания ранга п, вызванных стертыми линиями, строками и столбцами, для п = 5 и п = 8. Такой ранг ошибки соответствует

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

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

В предположении о равномерном случайном распределении информационных символов х, в кодовой матрице, произведена оценка шансов успешного декодирования для заданного числа случайно стертых линий. Оценено максимальное число стертых линий, которые могут быть исправлены - ~ 2п — 2^/п. Вычисленные оценки согласуются с данными сделанного моделирования.

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

В нервом разделе главы кратко описываются известные результаты о видах и защищенности криптосистем с открытым ключом на ранговых кодах.

Во втором разделе главы производится обобщение разных из-

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

• обычный ранг матрицы А над - г(А|дЛГ),

• столбцевой ранг матрицы А над основным полем GF(g) как максимальное число линейно независимых столбцов над -со1г(А|д).

Для матрицы/вектора А обозначим операцию возведения всех элементов в степень [г] = как А'1'.

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

= 8[Х|С]Р. (6)

• Б - строковый скремблер, обратимая (к х £)-матрица над СР^).

• в - порождающая (к х п)-матрица МРР (п, к, ¿)-кода.

• X - шумовая (к х ¿х)-матрица над СР(д^) с полным столбцевым рангом со!г(Х|д) = íx и рангом г(Х|длг) = Гх, гх < tx■ Матрица

[Х[С] имеет так же полный столбцовой ранг со1г([Х|С]|д) = п + Ьх-

• Р - столбцевой скремблер, ((£х+п) х (¿х+тс))-матрица над

• Ьх + п может быть больше И, п< N.

Строится расширенный открытый ключ Сре как вертикальный

вектор, состоящий из матриц г = 0..и

к-1.

'ре

риЬ

С[Ц

| иЬ

[2)

т риЬ

риЬ

Б 0 0 . . 0 X 1 С

0 БШ 0 . . 0 ХМ | с!1!

0 0 БИ . . 0 X ХИ | СИ 1 хР

0 0 0 . . ЭМ у \ ХМ | ем

(7)

Теорема 6. Матрица [Хе^|Се1{] имеет полный столбцевой ранг со1г([Хех1\Сех1]\д) = п + и ранг /-([Хе^Се*«]!^) < п - 1 + шт(гд:(п - к), ¿х, к{п — к)).

Теорема 7. Если ранг ^Сре^) = п + ¿х - 1, то ключ разлагается на множители за 0((п + tx)3) операций в СР^д^).

В основе атаки находится решение уравнения СреЬт = 0 для вектора Ь. Вектор РЬ оказывается вектором первой строки проверочной матрицы для рангового кода с порождающей матрицей в.

Теорема 8. Если С

ре

ет ранг г(Сре|<зг) = тг + ¿х — 1 — а, тогда сложность разложения открытого ключа составляет 0{даК(п + гх)3) операций нoдGF(gJV).

Для выбора стойких параметров с экспоненциальной атакой следует задавать матрицу X с условиями Ьх - < тт(гх(п — к),Ьх,к(п - к)).

Теорема 9. Если матрица X выбрана над СР(д), то открытый ключ вре имеет ранг г(Сре\дк) = п -\-tx ~ 1 и может быть взломан за 0((п + ¿х)3) операций в СГ(дм).

Например, можно создавать матрицу X над (-¡^(д ) и требова-

ииями:

l<rx =

^ <min (tx,k), (8)

tx > п - к,

Rate =

к

к

n + tx п + гх{п- к) + а

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

Пусть приводимый ранговый код определен порождающей матрицей = ||Оу||, 1,з = 1,...,р. Матрицы - случайные порождающие (щ х матрицы новых построенных в диссертации МРР кодов.

Выберем матрицы 8,Х, Р следующим образом.

Возьмем случайную (к х к) невырожденную матрицу, строковый скремблер, Э над (^(д^).

Сгенерируем случайную шумовую верхнетреугольную матрицу X = ЦХуЦ^'р из (к, х П{) подматриц с Х,-7- = 0 для г > Причем, столбцевые ранги матриц ||Хи||<=1, ||Х^2Ц,=1--2 ,..., ||Х(Д.=1 р должны быть равны ¿1, < Ь - параметр криптосистемы.

Создадим случайную (пхп) невырожденную матрицу Р, столб-цевой скремблер, из основного поля GF(g) так, чтобы Р-1 состояла из подматриц Р,^1 размера (п; х к,)-. Р-1 = ЦРу1 Ц^'* с некоторыми нулевыми блоками как показано на рисунке 1.

Вычислим матрицу Сри(, = Б(СР + Х)Р. Открытый ключ -матрица Сриь. Секретный ключ - матрицы 8,Ср,Х,Р.

Шифрование открытого текста вектора ш длины к над полем СР(дК) выполняется как с = гав^ + е, где искусственная ошибка е ранга со1г(е|д) > Ь выбрана, как показано на рисунке 1. Итого, добавлена искусственная ошибка ранга больше, чем корректирующая способность приводимого кода, заданного Ср.

I I ИМИ 1,1 I I

е

Р"1

Рис. V. Пример матрицы Р 1 и искусственной ошибки е с р — 11 блоками со1г(с!в2... вц|$) > Г) и ]/ = 3 группами блокон со1г(е1езе9е1оеи|^) = со1г(езе.1е7ейМ = ¡г, со1г(е5ес|ч) = §к = I — ¡1-

Криптос-ма Поле р т к, п к 1Ые 1 ¡1 и Ключ Атака

] кходная CF(0 2 23 11 22 0.48 6 1 5 24 КЫ(з 2В7

Ноная 4 13 о 20 0.38 <1 1 9 18.7 КЬНз "258

Таблица 1: Сравнение характеристик криптосистем.

При расшифрований шифротекста с легальный пользователь выполняет декодирование сР-1 и приводимом ранговом коде, получая т8.

Дополнительно, криптосистема может исправлять ошибки ранга со!г(е|д) < t — tl, возникающие при передаче сообщения по каналу с шумами.

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

Эйлера. Ограничивающим фактором па, минимальный размер ключа в построенной криптосистеме становятся не атаки па разложение ключа или декодирование как случайного, а атака перебором ошибки. Битовая сложность атаки - 0(др'^'г'~'х'~2г''>+пг'), где р' - число независимых групп блоков ошибки. На рисунке 1 р' = 3.

В таблице 1 приведено сравнение примера повой криптосистемы с ран её известным опубликованным примером криптосистемы па приводимых ранговых кодах.

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

NICE-X с быстрым расшифрованием.

В нервом разделе главы приведено краткое сравнение наибо- • лее используемых криптосистем с открытым ключом, RSA и Эль-Гамаля, с криптосистемой NICE-X по отношению к скорости алгоритмов и криитостойкости.

Во втором разделе главы изложены математические основы ■классов эквивалентности идеалов в кольцах целых элементов мнимых квадратичных полей.

Пусть число Дх S Z, Ai < 0 является дискриминантом мнимого квадратичного поля, т.е. Ai — 1 mod 4 или = 2,3 mod 4. Пусть число Д, = Aiq2,Aq = 0,1 mod 4 с некоторым q G > 0.

Множество Од, = Z 4- A|42'|/^Z является кольцом целых алгебраических элементов в мнимом квадратичном иоле Q(\/Ai). Множество Од, = Z + является подкольцом Од,, Од, = Z + дОд,.

Определим число Д как Д1 для кольца Од, или Aq для Од,.

Целый примитивный идеал о в Од, или Од, представляется в виде а = (а, Ь) = [аТ + , Ь2 = Д mod 4а, о, Ь € Z, а >

0, Ь G (—а, а]. Норма идеала равна N(a) = а.

Пусть q - простое число и у^Д^/З < q. Идеалы образуют абе-леву группу по умножению. Фактор-группа группы идеалов по подгруппе главных идеалов является группой классов эквивалентности, обозначаемой С1(А). В каждом классе эквивалентности идеал с минимальной нормой называется редуцированным. Обозначим Лейд(а) редуцированный идеал, эквивалентный идеалу а.

Между идеалами в Од и Од, можно определить изоморфизм ф: ф(а С Од,) = аОд, = и с Од,, ф~\и С Од,) = и П Од, = а С Од . Изоморфизм сохраняет норму идеала. Отображение ф также задает гомоморфизм группы классовCl(Aq) в С1(А 1): q-e(Ai,q) = q± 1 классов из группы Cl(Aq) отображаются в один класс группы С7(Дi), где е - символ Якоби. Ядро гомоморфизма представляется группой идеалов в Од,, которые отображаются в подгруппу главных идеалов в Од,.

Каждый класс эквивалентности однозначно представляется редуцированным идеалом. Вычисления в группе классов производятся

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

В третьем разделе главы сжато описаны криптосистемы с открытым ключом, построенные в мнимом квадратичном поле, и подробно описана криптосистема ШСЕ-Х с быстрым расшифрованием.

Криптосистема ШСЕ-Х устроена следующим образом. Определяется гомоморфизм фч идеалов: фч = Лес?д1 о ф. Пусть идеал р принадлежит ядру гомоморфизма Кег(фч), т.е. фч{р) = Яес^ДрОд^ - главный идеал. Открытым ключом является (Д9,р), множители (Дь<7) - секретный ключ.

Шифрование выполняется так. Пусть г - случайный редуцированный идеал в Од? с нормой Л^г) < Д1|/4. Редуцированный идеал г задает элемент С7(Д?), причем фч{г) = ф(г), ф~1(фч{'с)) = г. Определим редуцированные идеалы 1 = Яес¿д,(рЛ), с = ЯейдДН), где к - случайное целое число меньше q — е(Дь д). Шифрование переводит элемент С1(Д9) в один из д — е(Д1,д) классов из С7(Дд), которые гомоморфизмом ф переводятся в один элемент С7(Д1). Идеал г имеет среди редуцированных идеалов этих классов минимальную норму. Шифротекстом битового сообщения т является [С = т 0 /10я/г(1), с].

Зная Д1 и ц, расшифрование шифротекста выполняется как г = 0-1(0<г(О). т-С® Лай/г^).

В четвертом разделе главы подробно описаны процедуры по генерированию параметров криптосистемы, шифрованию и расшифрованию ШСЕ-Х на основе выполненной в диссертации полной программной реализации.

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

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

Открытый NICE-X Модификация NICE-X RSA

Шифро- Расшиф- Шифро- Расшиф- Шифро- Расшиф-

ключ, би- вание, рование, вание, рование, вание, рование,

ты MP мг MP мг M с MP

512 244 0.78 202 0.78 0.24 15

1024 GGG 1.4G 516 1.46 0.71 79

2048 2807 3.30 1492 3.30 2.31 514

Таблица 2: Сравнение скорости криптосистем: исходной NICE-X, сделанной модификации NICE-X и RSA с е = 216 + 1 на Athlon 1133 MHz.

метод генерирования идеала включает генерирование псевдопростого числа битовой длины п, которое имеет битовую сложность порядка 0(l5gn) или немного меньше. Битовая сложность возведения идеала в степень - кубическая. Таким образом, шифрование NICE-X имеет битовую сложность четвертой степени.

Генерирование идеала означает создание пары чисел (а, Ь) : Ь2 = Д? mod 4а, а > 0, -а < b < а. Выбирается простое а = 3 mod 4.

1 ^ С вероятностью ^ решение существует Ь = ±ДЧ4 mod а.

Предлагается вычислить 5 маленьких идеалов с 50-битовыми

простыми di, а большой идеал представить произведением: (а, Ь) = 5

(а*, bi)ki для некоторых /с*. Мощность множества возможных зна-

»= 1

чений а составляет (7г(250))5 ~ 2220, где 7г(п) - число простых чисел меньших п. Такой мощности множества значений а вполне достаточно для защищенности схемы.

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

В исходной криптосистеме NICE-X не заданы ограничения на генерируемые параметры схемы. В диссертации рассмотрена безопасность выбора произвольных параметров.

Порядок ядра является составным числом h = q - е(Дь д) = q ± 1, поэтому не любой идеал р из ядра гомоморфизма является безопасным. Если р принадлежит маленькой подгруппе, то криптосистема легко взламывается, р гарантированно должен быть гене-

ратором всего ядра Кегф или большой подгруппы.

При выборе параметров схемы предлагается генерировать простое число д с известным разложением числа /г = д ± 1 на множители. Тогда можно проверить, является ли р генератором большой подгруппы.

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

Основные результаты работы

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

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

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

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

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

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

Список публикаций по теме диссертации

1. Кшевецкий А. С. Уменьшение размера открытого ключа в криптосистемах па линейных ранговых кодах // Безопасность информационных технологий (БИТ). 2006, т. 3, с. 72-76.

2. Кшевецкий А. С. Выбор стойких ключей для криптосистем на ранговых кодах // Труды XLIX научной конференции МФТИ: Современные проблемы фундаментальных и прикладных паук. Москва-Долгопрудный. 2006, ч. 1, с. 8-8.

3. Кшевецкий А. С., Габидулин Э. М. Декодирование ранговых кодов новой конструкции // В сб. научных трудов «Некоторые проблемы фундаментальной и прикладной математики и их приложениях в задачах физики». М.: МФТИ, 2005, с. 53-61.

4. A. Kshevetskiy, Е. Gabidulin. The new construction of rank codes // Proc. of IEEE International Symposium on Information Theory (ISIT'2005). 2005, pp. 2105-2108.

5. A. Kshevetskiy, E. Gabidulin. High-weight errors in reducible rank codes // Proc. of the 8th International Symposium on Communication Theory к Applications (ISCTA'2005). 2005, pp. 71-76.

6. Кшевецкий А. С. Ошибки высокого веса в криптосистемах, основанных на ранговых кодах // Труды XLVIII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2005, ч. 1, с. 11-12.

7. A. Kshevetskiy. Information set decoding for rank codes // Proc. of the Ninth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2004). 2004, pp. 254-259.

8. Кшевецкий А. С. Построение новых ранговых кодов с максимальным ранговым расстоянием // Труды XLVII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2004, ч. 1, с. 9-10.

9. A. Kshevetskiy. Modification of the public-key cryptosystem ■ NICE-X // Proc. of the Seventh International Symposium on Communications Theory & Applications (ISCTA'03). 2003, pp. 210-214.

10. Кшевецкий A. С. Криптосистемы с открытым ключом, построенные в квадратичных порядках // Труды XLVI научной конференции МФТИ: Современные проблемы фундаментальных и прикладных паук. Москва-Долгопрудный. 2003, ч. 1, с.

И. A. Kshevetskiy. Several properties of public-key cryptosystems based on quadratic orders // Proc. of the Eighth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2002). 2002, pp. 172-175.

12. Кшевецкий А. С. Практическая реализация криптосистемы с открытым ключом в мнимом иоле квадратичного порядка, имеющей квадратичное время расшифрования // Труды XLIV научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2001, ч. 1, с. 9-9.

В работе 3 автору принадлежит идея модификации алгоритма декодирования известных ранговых кодов для декодирования новых ранговых кодов. В работе 4 автору принадлежит конструкция новых ранговых кодов, алгоритмы кодирования и декодирования. В работе 5 автору принадлежит модификация столбцевого скрем-блера для достижения ошибок высокого веса и криптоанализ новой криптосистемы.

8-

-8,

Кшевецкнй Александр Сергеевич

РАЗРАБОТКА НОВЫХ КОДОВ В РАНГОВОЙ МЕТРИКЕ И КРИПТОСИСТЕМ С ОТКРЫТЫМ КЛЮЧОМ

Автореферат

Подписано в печать 25.03.2007. Формат 60x84 1/16. Печать офсетная.

Усл.печ.л. 1,0. Уч.-шд.л. 1,0. Ъфаж 70 экз. Заказ №ф-228

Государственное образовательное учреждение высшего профессионального обрмования

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Введение

1 Ранговые коды

1.1 Стандартные известные конструкции ранговых кодов

1.1.1 Введение.

1.1.2 Конструкция.

1.1.3 Алгоритмы кодирования и декодирования

1.1.4 Приводимые ранговые коды.

1.1.5 Симметричные ранговые (п, 1,п)-коды

1.2 Разработка ранговых кодов новой конструкции

1.2.1 Введение.

1.2.2 Конструкция.

1.2.3 Взаимосвязь с обычными ранговыми кодами

1.2.4 Алгоритмы кодирования и декодирования

1.3 Построение декодирования по информационным совокупностям

1.3.1 Введение.

1.3.2 Информационные совокупности для матричных кодов.

1.3.3 Декодирование для ранговых кодов.

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

Заключение

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

1. Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации. 1985, т. 21, N 1, с. 3-14.

2. Kshevetskiy A., Gabidulin М. The New Construction of Rank Codes // Proc. of IEEE International Symposium on Information Theory (ISIT'2005). 2005, pp. 2105-2108.

3. Кшевецкий А. С., Габидулин Э. M. Декодирование ранговых кодов новой конструкции // В сб. научных трудов «Некоторые проблемы фундаментальной и прикладной математики и их приложениях в задачах физики». М.: МФТИ, 2005, с. 53-61.

4. Кшевецкий А. С. Построение новых ранговых кодов с максимальным ранговым расстоянием // Труды XLVII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2004, ч. 1, с. 9-10.

5. A. Kshevetskiy. Information set decoding for rank codes // Proc. of the Ninth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2004). 2004, pp. 254-259.

6. E. M. Gabidulin, A. V. Ourivski, B. Honary, B. Ammar. Reducible Rank Codes and Their Applications to Cryptography // IEEE Transactions on Information Theory. 2003, 49(12), pp. 3289-3293.

7. E. M. Gabidulin, P. Loidreau. Subfield subcodes of maximal rank distance codes // Proc. of the 7-th Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT'2000, Bansko, Bulgaria, . June 2000. pp. 151-156.

8. E. M. Gabidulin, A. V. Paramonov, О. V. Tretjakov. Rank Errors and Rank Erasures Correction // Proceedings of the 4th International Colloquium on Coding Theory. 1992, Armenia, pp. 11-19.

9. E. M. Gabidulin, N. I. Pilipchuk. Transposed Rank Codes Based on Symmetric Matrices // Proc. of the WCC'2003. March 2003, Versailles (France), pp. 203-211.

10. Э. M. Габидулин, H. И. Пилипчук. Симметричные ранговые коды и применение // Проблемы передачи информации. 2004, № 2, с. 3-18.

11. И. E. M. Gabidulin, N. I. Pilipchuk. Symmetric matrices and codes correcting rank errors beyond the ^J bound // Discrete Applied Mathematic. 2006, 154, pp. 305-312.

12. E. Prange. The use of information sets in decoding cyclic codes // IRE Trans. Inform. Theory. 1962, vol. IT-8, pp. S5-S9.

13. Coffey, J. T. and Goodman, R. M. The complexity of information set decoding // IEEE Transactions on Information Theory. 1990, vol. 36, pp. 1031-1037.

14. E. M. Gabidulin. A Class of Two-Dimensional Codes Correcting Lattice-Pattern Errors // Proceedings of the 2nd International Symposium on Information Theory. 1971, Moscow-Yerevan, pp. 4447.

15. Э. M. Габидулин, В. И. Коржик. Коды исправляющие ошибки решетчатой конфигурации // Известия ВУЗов МВССО СССР Радиоэлектроника. 1972, т. 15, No. 4, с. 492-498.

16. E. М. Gabidulin. A Fast Matrix Decoding Algorithm For Rank

17. Error-Correcting Codes // Lecture Notes in Computer Science No. 573. Eds G. Cohen, S. Litsyn, A. Lobstein, G. Zemor, Algebraic coding. Springer-Verlag, Berlin, 1992, pp. 126-132.

18. MacWilliams F. J., Sloane N. J. A. The Theory of Error Correcting Codes // Amsterdam: North Holland Press, 8th ed, 1993.

19. Кшевецкий А. С. Уменьшение размера открытого ключа в криптосистемах на линейных ранговых кодах // Безопасность информационных технологий (БИТ). 2006, т. 3, с. 72-76.

20. Кшевецкий А. С. Выбор стойких ключей для криптосистем на ранговых кодах // Труды XLIX научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2006, ч. 1, с. 8-8.

21. A. Kshevetskiy, Е. Gabidulin. High-weight errors in reducible rank codes // Proc. of the 8th International Symposium on Communication Theory к Applications (ISCTA'2005). 2005, pp. 71-76.

22. Кшевецкий А. С. Ошибки высокого веса в криптосистемах, основанных на ранговых кодах // Труды XLVIII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2005, ч. 1, с. 11-12.

23. Е. М. Gabidulin, А. V. Paramonov, О. V. Tretjakov. Ideals over a non-commutative ring and their application in cryptology // Advances in Cryptology EUROCRYPT'91. LNCS 547, D. W. Davies, Ed., Springer-Verlag. 1991, pp. 482-489.

24. J. K. Gibson. Severely denting the Gabidulin version of the

25. McEliece public key cryptosystem // Designs, Codes and Cryptography. 1995, 6(1), pp. 37-45.

26. J. K. Gibson. The security of the Gabidulin public-key cryptosystem, in: U. M. Maurer, ed. // Advances in Cryptology EUROCRYPT'96, LNCS 1070. 1996, pp. 212-223.

27. Alexei V. Ourivski, Ernst M. Gabidulin. Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics 128(1). 2003, pp. 207-221.

28. А. Уривский, Т. Йоханссон. Новые методы для декодирования кодов в ранговой метрике и их применение в криптографии // Проблемы передачи информации. 2002, т. 38(3), с. 287-296.

29. R. Overbeck. A new structural attack for GPT and variants //In Proc. of Mycrypt'2005, vol. 3715 of LNCS. Springer-Verlag, 2005, pp. 50-63.

30. R. Overbeck. Extending Gibson's attacks on the GPT cryptosystem // In Proc. of. WCC 2005, volume 3969 of LNCS. Springer Verlag, 2006, pp. 178-188.

31. A. Kshevetskiy. Modification of the public-key cryptosystem NICE-X // Proc. of the Seventh International Symposium on Communications Theory & Applications (ISCTA'03). 2003, pp. 210-214.

32. Кшевецкий А. С. Криптосистемы с открытым ключом, построенные в квадратичных порядках // Труды XLVI научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2003, ч. 1, с. 8-8.

33. A. Kshevetskiy. Several properties of public-key cryptosystemsbased on quadratic orders // Proc. of the Eighth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2002). 2002, pp. 172-175.

34. I. Biehl, S. Paulus, Т. Takagi. Efficient Undeniable Signature Schemes based on Ideal Arithmetic in Quadratic Orders // Designs, Codes and Cryptography archive. 2004, Volume 31, Issue 2, pp. 99123.

35. H. Cohen. A Course in Computational Algebraic Number Theory // Series: Graduate Texts in Mathematics. 2000, Volume 138.

36. H. Cohen, and H. W. Lenstra, Jr. Heuristics on class groups // In Number Theory, vol. 1052 of Lecture Notes in Mathematics. Springer-Verlag, 1984.

37. P. Ebinger, E. Teske. Factoring N = pq2 with the Elliptic Curve Method // ANTS 2002, LNCS 2369.

38. S. Hamdy, B. Moller. Security of Crytosystems Based on Class Groups of Imaginary Quadratic Orders // ASIACRYPT 2000, LNCS 1976. 2000.

39. D. Huhnlein. Faster Generation of NICE-Schnorr-Type Signatures // Progress in Cryptology CT-RSA 2001, LNCS 2020. 2001.

40. D. Hiihlein, J. Merkle. An efficient NICE-Schnorr-type signature scheme // Proceedings of PKC 2000, LNCS 1751. 2000.

41. M. Hartmann, S. Paulus and T. Takagi. NICE New ideal coset encryption // CHES, LNCS 1717. 1999.

42. E. Jaulmes, A. Joux. A NICE Cryptanalysis // EUROCRYPT 2000, LNCS 1807. 2000.

43. M. Joye, P. Paillier, S. Vaudenay. Efficient Generation of Prime Numbers // CHES 2000, LNCS 1965. 2000.

44. P. Karu, J. Loikkanen. Practical Comparison of Fast Public-Key Cryptosystems / / Telecommunications Software and Multimedia Lab. at Helsinki Univ.of Technology. 2001, http://www.tml.hut.fi/Opinnot/Tik-110.501/2000/papers.html.

45. A. K. Lenstra, and E. R. Verheul. Selecting cryptographic keysizes In Practice and Theory in Public Key Cryptography // PKCS 2000, LNCS 1751. 2000.

46. R. Peralta, E. Okamoto. Faster Factoring of Integers of a Special Form // IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences. 1996, v. E79-A, n.4.

47. H. Reisel. Prime numbers and computer methods for factorization, 2nd ed. // Birkhauser, Boston, 1994.

48. D. Shanks. On Gauss and composition I, II in R. A. Mollin, (ed.) // Proc. NATO ASI on Number Theory and Applications. Kluwer Academic, Dordrecht. 1989, pp. 163-179.

49. Paulus S., Takagi T. A new public-key cryptosystem over a quadratic order with quadratic decryption time // Journal of Cryptography. 2000, vol. 13, no2, pp. 263-272.

50. J. Buchmann, K. Sakurai, T. Takagi. An IND-CCA2 Public-Key Cryptosystem with Fast Decryption // ICISC'01, LNCS 2288. 2002.

51. D. Hühlein, M. J. Jacobson, Jr., S. Paulus. A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption // Advances in Cryptology EUROCRYPT'98, LNCS 1403. Spriger-Verlag, Berlin. 1998, pp. 294-307.

52. J. Buchmann and H. C. Williams. Quadratic Fields And Cryptography // London Mathematical Society Lecture Note Series 154, Cambridge University Press, Cambridge. 1990, pp. 9-26.

53. Buchmann J., Dullmann S., Williams H. On the complexity and efficiency of a new key exchange system // Advances in Cryptology EUROCRYPT'89, LNCS 434, Springer-Verlag, Berlin. 1990, pp. 597-616.

54. J. Buchmann and H. C. Williams. A key exchange system based on imaginary quadratic fields // Journal of Cryptology. 1988, vol. 1, pp. 107-118.

55. Jacobson M.J. Computing discrete logarithms in quadratic orders // Journal of Cryptography. 2000, v. 13.

56. Hamdy S., Möller B. Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Fields // T. Okamoto (Ed.):

57. Advances in Cryptology, ASIACRYPT 2000, Springer-Verlag LNCS 1976. 2000, pp. 234-247.

58. Ван дер Варден Б. Jl. Алгебра // Москва «Наука», 1979.

59. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел // 1987.

60. Гекке Э. Лекции по теории алгебраических чисел // Пер. с немецкого Ольшанского Г.И., Райкова Д.А. 1940.

61. D. А. Сох. Primes of the form x2 + ny2 // John Wiley & Songs, Inc.

62. A. Menezes, P. van Ooscort and S. Vanstone. Handbook of Applied cryptography // CRC Press, 1996.

63. Schneier B. Applied cryptography, 2nd edition // John Wiley & Songs, 1996.

64. Коблиц H. Курс теории чисел и криптографии // Научное иза-тельство «ТВП», Москва, 2001.

65. Брассар Ж. Современная криптология. Основы // 1988.

66. Ростовцев А. Алгебраические основы криптографии // СПб.: НПО «Мир и семья», ООО «Интерлайн», 2000.