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

005051512

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

КУПРИЯНОВ ИВАН АЛЕКСАНДРОВИЧ

МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ НА ОСНОВЕ ВЫЧИСЛЕНИЙ В КОНЕЧНЫХ ГРУППАХ МАТРИЦ

Специальность 05.13.19 - Методы и системы защиты информации, информационная безопасность

Автореферат

диссертации на соискание ученой степени кандидата технических наук

11 АПР 2013

Санкт-Петербург 2013

005051512

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

Научный доктор технических наук, профессор

руководитель: Молдовян Николай Андреевич

Официальные Яковлев Виктор Алексеевич, доктор технических наук, оппоненты: профессор ВАС им. С.М. Буденного

Пилькевич Сергей Владимирович, кандидат технических наук, доцент BKA им. А.Ф. Можайского

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» (НИУ ИТМО)

Защита диссертации состоится «23» апреля 2013 г. в 15.00 часов на заседании диссертационного совета Д 218.008.06 на базе Петербургского государственного университета путей сообщения по адресу: 190031, Санкт-Петербург, Московский пр., д. 9, ауд. 1-217.

С диссертацией можно ознакомиться в библиотеке Петербургского государственного университета путей сообщения.

Автореферат разослан «22» марта 2013 г.

Ученый секретарь диссертационного совета кандидат технических наук,

профессор 0 Кудряшов Владимир Александрович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Объектом исследования являются системы защиты информации, объектов и субъектов информационно-коммуникационных технологий.

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

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

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

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

Для достижения поставленной цели в ходе выполнения исследований решались следующие частные задачи:

1. Анализ особенностей, потенциальных слабостей и производительности криптосистемы МОЯ, как одной из наиболее распространенных систем, заданных над некоммутативными группами.

2. Определение сложности задачи поиска сопрягающего элемента в конечной некоммутативной группе путем ее сведения к решению системы линейных уравнений.

3. Анализ возможности применения задачи дискретного логарифмирования в конечных группах матриц для построения криптографических протоколов.

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

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

6. Разработка метода нахождения группы матриц заданного простого порядка р.

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

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

Теоретическая основа и методологическая база исследования: научные труды отечественных и зарубежных ученых в области разработки

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

На защиту выносятся:

1. Метод открытого распределения ключей на основе конечных групп матриц.

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

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

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

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

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

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

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

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

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

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

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

Практическая реализация и внедрение результатов работы.

Результаты диссертационного исследования использованы при выполнении научно-исследовательских работы «Новый подход к построению схем электронной цифровой подписи, стойких к квантовым атакам» по гранту РФФИ № 11-07-00004-а. Результаты работы внедрены на кафедре комплексного обеспечения информационной безопасности (КОИБ) Санкт-Петербургского государственного университета водных коммуникаций в учебный процесс по специальности «Комплексное обеспечение информационной безопасности автоматизированных систем» при преподавании дисциплин «Теоретические основы криптографии» и «Криптографические методы защиты информации».

Апробация работы. Основные результаты диссертационной работы докладывались на Всеармейской научно-практической конференции «Инновационная деятельность в Вооруженных силах Российской Федерации» (Санкт-Петербург, 2008); XI Санкт-Петербургской международной конференции Региональная информатика-2008 (РИ-2008) (Санкт-Петербург, 2008); Всеармейской научно-практической конференции «Инновационная деятельность в Вооруженных силах Российской Федерации» (Санкт-Петербург, 2009); XII Санкт-Петербургской международной конференции Региональная информатика «РИ-2010» (Санкт-Петербург, 2010); Всеармейской научно-практической конференции «Инновационная деятельность в Вооруженных силах Российской Федерации» (Санкт-Петербург, 2010).

Публикации. По теме диссертации опубликованы 10 научных работ, из них 4 статьи, опубликованные в журналах из списка ВАК, и 6 работ в сборниках трудов международных и российских научно-технических конференций.

Структура и объем работы. Диссертационная работа изложена на 132 страницах, включая 4 главы, 5 рисунков, 1 таблицу, 126 формул и список использованной литературы из 84 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Кроме указанной уязвимости следует отметить некоторые особые требования к группе Г, выбираемой в качестве примитива для построения криптосистемы MOR. Наиболее важным является то, что произвольный элемент данной группы должен вычислительно просто выражаться в виде произведения степеней элементов базиса. Однако, при этом возникает ситуация, при которой элементы базиса ((Pg(Pi)> ФсО3^), — > Vci^s)) эффективно представляются в виде

<?>с(А) = ГТ b^.J = 1,2.....s (1)

i i¡=i

Отображение <Pg(x) на произвольный заданный элемент группы Г может быть выполнено путем разложения данного элемента по исходному базису и применению формулы (1) к каждому сомножителю данного разложения. Квадратная матрица А, содержащая значения aif¡, i,j — 1,2однозначно задает отображение <pG(jx). Следовательно, задача дискретного логарифмирования в группе автоморфизмов может быть сведена за полиномиальное время к задаче дискретного логарифмирования в конечной группе матриц.

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

Действие автоморфизма <р на базис {(¿i), (b2), (bs)> дает следующее соотношение:

(В,) = G'HbdG =

/5п 512^"1 v /Sil 9i2\ (2)

V021 д2г) W Víhi 9гг)

Решение данного выражения относительно неизвестного G = (¿7у) приводит к решению системы линейных уравнений, которая имеет

ненулевые решения, по крайней мере, р решений (одно из решений является нулевым), которые можно записать в следующем виде Mfln *3i2\ = (Я 0\ (9п 9и\

U921 Л922) V0 X) \92i 922> к }

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

Решая задачу поиска сопрягающего элемента при помощи данного метода, приходим к следующему уравнению с неизвестным показателем к:

(Хк 0\(9и 3i2\k = (A 0\(Чи (4)

V 0 Лк/ ^521 522/ V0 ЛJ УЧ21 Чгг) Которое легко преобразуется к виду (9и 9i2\k = (A' 0 Win Ч12 \ = (А'Чи A'q12\ V5zi 522/ VO AVWzi Ч22) U 'q21 A'q22)

fdii 9i2\ /Л'о-м A'q12\ Очевидно, что матрицы g^j и j принадлежат

одной и той же циклической подгруппе КГНМ порядка q(p- 1). Также очевидно, что не для всех значений Л' уравнение (5) имеет решения. Например, рассматриваемые две матрицы могут иметь различный порядок. Поскольку решение существует для некоторого частного варианта выбора значений этих матриц, то принципиально его можно найти. Для этого

M'qn A'q12\

воспользуемся тем обстоятельством, что порядок матрицы ^д,^ д,^ J

(9и 9i2\

должен быть равен порядку матрицы ^ g^J при некотором значении Л".

Следует отметить, что вычисление порядка матрицы в рассматриваемой КГНМ не представляет трудностей. Действительно, порядок КГНМ размера 2x2 равен 0.2х2 = (р2 - 1)(р - 1)р. Поэтому /Л'оц A'q12\

порядок матрицы ., I легко можно определить путем ее

\Д q2i Aq22;

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

равен порядку матрицы fw^11 w^12). Аналогичная ситуация имеет

VA q2i Л q22/

место и для матрицы 522)' П° КОТОРОЙ слеДУет сгенерировать

матрицу (У,11 ^,12 ) порядка q. 21 9 22'

/Vil a12\ M"<711 Л q12\ Матрицы V , и д,, 1 принадлежат одной и той

V5 21 5 22/ VA"Í21 Л д22/ же циклической подгруппе порядка q, поэтому значение к можно определить, решая задачу дискретного логарифмирования, задаваемую уравнением

M"qn A"q12) = (a'n a'i2\k (б)

\A"q21 A "q22J \д'21 д'гг) В соответствии с методом дискретного логарифмирования в КГНМ решение последнего уравнения сводится к решению задачи дискретного логарифмирования в поле GF(p'), где i < 2. Таким образом, показано, что стойкость криптосистемы MOR является субэкспоненциальной.

В третьей главе рассматриваются методы защиты информации, основанные на вычислениях в конечных группах некоммутативных матриц (КГНМ) с применением новой задачи - задачи дискретного логарифмирования в скрытой подгруппе некоммутативной группы.

Метод открытого распределения ключей на основе некоммутативной группы. В качестве секретного ключа первого и второго пользователей используются пары (х,^) и (x2,s2) и формирования открытого ключа Yj и Y2 по формулам

Yí = Х^Х-Г1 и У2 = X2GS2X2~1 (7)

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

к12 = ад5^-1 = X^X^X^Y'X^1 = (8)

= X^G^X^X-l'1 а у второго - по формуле

■ -i - vJY.r.SiY-П^у--1 =

(9)

К21 = Х^Х^1 = х^х^х^У'х^1 =

= вдс^яг1^-1 = = ^12

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

Данный метод открытого распределения ключей основан на сложности задачи вычисления ключа в виде числа 5 и элемента некоммутативной конечной группы X по открытому ключу

У = ХС^"1 (10)

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

Для реализации протоколов открытого распределения ключей, основанных на данном методе, требуется выбрать значения р достаточно большого размера, причем такие, что разложение порядка КГНМ содержит большой простой делитель. Поскольку р входит как множитель в формулу для порядка КГНМ, то такой делитель имеется для произвольных значений р. Эффективный метод нахождения группы матриц простого порядка р задается следующим утверждением (Рис. 1).

Пусть С - треугольная матрица порядка р, V - произвольно выбранная обратимая матрица, заданная над СГ(р), тогда

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

Невырожденные треугольные матрицы, на главной диагонали которых находятся единицы, размерности пхп, п > 2, заданные над конечным полем С/Г(р) имеют простое значение порядка, равное р. Данное утверждение доказывается путем выражения элементов матрицы Ак, значения которых соответствуют следующей формуле:

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

С =КоСоГ1

(И)

о, г >)

(12)

Быстродействие алгоритмов,

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

В широко применяемых алгоритмах, построенных на вычислениях в конечном поле GF(p), размер используемых чисел достигает 1024 бит. При сохранении того же уровня стойкости алгоритмы, построенные на базе предложенного метода открытого распределения ключей, обладают большим быстродействием за счет использования в качестве элементов матриц чисел длиной от 80 до 160 бит.

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

являются необратимыми для

произвольных пар значений (Ь, с).

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

У = ХСХ-1 = ХХХСХ~1 = АХ(ХСХ~1) (13)

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

10

С

Рисунок 1. Метод нахождения группы матриц простого порядка Р

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

Очевидно, что использование необратимой матрицы повышает быстродействие криптосистемы, т.к. операция возведения такой матрицы в степень сводится к возведению в степень элемента поля А.

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

Рисунок 2. Система открытого шифрования и расшифрования на основе необратимых матриц

Процедура шифрования:

1. Генерируется случайная матрица и й Гкомм и случайное число

и\

2. Вычисляются элементы Я = = Яи{/СУ-1 и К =

иуии~1 = и^хсх-^и-1 = л^ихсх^и-1-,

3. Зашифровывается сообщение М с использованием в качестве секретного ключа элемента К в криптограмму С = ЕК(М), где Ек -некоторый алгоритм симметричного шифрования;

4. Производится передача по открытому каналу связи криптограммы С и элемента Д.

Процедура расшифрования:

1. Принимается по открытому каналу связи элемент Я и криптограмма С;

2. Вычисляется ключ шифрования:

к* = Х^Х-1 = хугиви^ух-1 = я^хиси^х-1 = ^ихвх^и-1 = К\

3. Производится расшифрование криптограммы С как М =

где Е? - некоторый алгоритм симметричного расшифрования,

соответствующий алгоритму шифрования Ек.

Рассмотрим метод аутентификации пользователей с нулевым разглашением, разработанной над вычислительно трудной задачей скрытого дискретного логарифмирования, заданной над необратимой матрицей N. Параметрами являются две некоммутирующие матрицы Т и Л/, где Т - треугольная матрица порядка (р — 1)р.

Открытые ключи генерируются по формуле

у - тымхт-»> (14)

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

1. На стороне пользователя (А), желающего убедится в подлинности удаленного пользователя (Б), который представил первому цифровой сертификат по телекоммуникационному каналу):

a. генерируется пара случайных чисел г и к;

b. вычисляется матрица И = ТгМкТ~г;

c. производится передача пользователю (Б) по открытому каналу связи матрицы Я.

2. На стороне пользователя (Б):

а. принимается по открытому каналу связи от пользователся (А) матрица И;

b. вычисляется матрица Ъ — тш11хТ-™;

c. производится передача пользователю (А) по открытому каналу связи матрицы Ъ.

3. На стороне пользователя (А):

a. вычисляется матрица Ъ' = ТгУкТ_г, где У - открытый ключ пользователя (Б), взятый из его цифрового сертификата;

b. принимается по открытому каналу связи от пользователя (Б) матрица Ъ\

c. производится сравнение матрицы Z' и Ъ. Если Z' = Z, то делается вывод о подлинности пользователя (Б).

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

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

Шифруемые сообщения разбиваются на блоки размером 512 бит, которые рассматриваются как матрицы 2x2 М = (ту), элементы которой рассматриваются как элементы конечного поля С/7^), где р1 - случайное 129-битовое простое число. Ложное осмысленное сообщение, предназначенное для совместного шифрования с сообщением М также разбивается на 512-битовые блоки, рассматриваемые как матрицы 2x2

о =

Для выполнения совместного шифрования предполагается использование двух различных секретных ключей. Первый из них выбирается в виде случайной матрицы размером 2x2 К' = (к'ф, заданной над полем GF(p1), и простого числа р1. Второй ключ выбирается в виде случайной матрицы размером 2x2 К" = (^"¡у)> заданной над полем

и случайного 129-битового простого числа р2.

Предлагаемый метод совместного шифрования сообщений М и £) включает следующие шаги:

1. Вычисление матрицы К'по формуле

Я' = (г';/) = К'{М ® К'^К'-1 (15)

где ® - операция поэлементно-поразрядного суммирования элементов матриц-операндов.

2. Вычисление матрицы R" по формуле

R" = (г= K"{D © К'^К"-1 (16)

3. Вычисление криптограммы в виде матрицы С = (Сц) размером 2x2, в которой элементы вычисляются как

Су = (r'ijíp^mod рОРг + г"и(р^тоа р2)рг)той ptp2 (17)

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

М = (К'~1СК') © К' (18)

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

D = (К'^СК") ® К" (19)

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

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

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

2. Задача поиска сопрягающего элемента в конечной некоммутативной группе не является вычислительно трудной, и ее решение сводится к решению системы линейных уравнений.

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

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

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

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

7. Разработан метод нахождения группы матриц простого порядка р.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

(публикации в изданиях, рекомендованных ВАК Минобрнауки России, выделены курсивом)

/. Куприянов И.А. Матрицы специального порядка для алгоритмов аутентификации информации в автоматизированных системах водного транспорта //Журнал университета водных коммуникаций. 2011 №3(11). СПб, С.92-96.

2. Горячев A.A., Молдовян Д.Н., Куприянов И.А. Выбор параметров задачи скрытого дискретного логарифмирования для синтеза криптосхем // Вопросы защиты информации. 2011. 1. С. 19-23.

3. Е.С. Дернова, И.А.Куприянов, Д.Н. Молдовян, A.A. Молдовян. Протоколы слепой подписи с новыми свойствами // Информатизация и связь. 2010. № 1. С. 72-76.

4. Молдовян Д.Н., Куприянов И.А., Костина A.A., Захаров Д.В. Задание некоммутативных конечных групп векторов для синтеза алгоритмов цифровой подписи // Вопросы защиты информации. 2009. N° 4. С. 12-18.

5. Горячев A.A. , Захаров Д.В., Куприянов И.А., Сухов Д.К. Генерация элементов специального порядка в конечных некоммутативных группах //

Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 2526 ноября 2010, г. Санкт-Петербург. СПб.: ВАС, 2010. С. 169-174.

6. Куприянов И.А., Горячев A.A., Костина A.A., Сухов Д.К. Варианты алгоритмов коммутативного шифрования с использованием конечных некоммутативных групп // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. с. 117-118.

7. Захаров Д.В., Куприянов И.А., Синев В.Е., Цехановский В.В. Схемы разделения секрета на основе конечных колец векторов // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции, 10-11 декабря 2009, г. Санкт-Петербург. СПб.: ВАС, 2009. С. 228-233.

8. Куприянов И.А., Молдовян H.A., Молдовяну П.А.. Влияние выбора характеристики поля на порядок мультипликативных групп, формируемых в конечных векторных пространствах // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 20-21 ноября 2008, г. Санкт-Петербург. СПб.: ВАС, 2008. С.345-349.

9. Бутурлинов А.И., Куприянов И.А., Молдовян Д.Н. Экспериментальное исследование условий образования векторных полей // XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008) СПб, 22-24 октября 2008 г. Материалы конференции. СПб, 2008. с. 94-95.

10. Дернова Е.С., Куприянов И.А., Молдовяну П.А. Варианты реализации алгоритмов цифровой подписи и выбор размерности векторного поля // XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008) СПб, 22-24 октября 2008 г. Материалы конференции. СПб, 2008. с. 97.

Подписано к печати 19.03.2013 г

Печать - ризография. Бумага для множит, апп. Формат 60x84 1/16

Тираж 100 экз. Заказ №309. Печ. л.-1.0

Отпечатано в типографии «ПГУПС» (190031, г. Санкт-Петербург, Московский пр., 9)

Федеральное агентство морского и речного транспорта

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

образования

Санкт-Петербургский государственный университет водных коммуникаций

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

04201358174 Куприянов Иван Александрович

МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ ИА ОСНОВЕ ВЫЧИСЛЕНИЙ В КОНЕЧНЫХ ГРУППАХ МАТРИЦ

05.13.19 - Методы и системы защиты информации, информационная

безопасность

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук профессор Молдовян Н.А.

Санкт-Петербург 2012

Содержание

СОДЕРЖАНИЕ...........................................................................................................2

ВВЕДЕНИЕ..................................................................................................................5

ГЛАВА 1. ЗАЩИТА ИНФОРМАЦИИ И АУТЕНТИФИКАЦИИ В НАСТОЯЩЕЕ ВРЕМЯ.............................................................................................11

1.1 Защита информации в информационных системах и телекоммуникационных сетях............................................................................................................................11

1.2 Аутентификация в информационных системах...............................................19

1.3 Аутентификация информации с помощью ЭЦП.............................................22

1.4 История постквантовой криптографии.............................................................27

1.5 Проблемы, сложные для квантовых компьютеров..........................................29

1.5.1 Задачи теории алгебраических решеток........................................................29

1.5.2 Задачи теории кодов, исправляющих ошибки..............................................31

1.5.3 Системы квадратных уравнений с несколькими переменными, заданные над конечным полем.................................................................................................33

1.5.4 Группы кос (переплетения).............................................................................35

1.5.5 Криптосистемы, основанные на вычислениях в некоммутативных группах .....................................................................................................................................37

1.6 Отрицаемое шифрование...................................................................................39

1.7 Постановка задачи...............................................................................................40

ГЛАВА 2. АНАЛИЗ КРИПТОСИСТЕМЫ MOR...................................................43

2.1 Недостатки криптосистемы MOR.....................................................................43

2.2 Сведение задачи дискретного логарифмирования над группой автоморфизмов к задаче дискретного логарифмирования в конечной группе матриц.........................................................................................................................45

2.3 Взлом криптосистемы MOR сведением к решению системы линейных уравнений...................................................................................................................47

2.4 Выводы ко второй главе.....................................................................................54

ГЛАВА 3. МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ, ОСНОВАННЫЕ НА ГРУППАХ МАТРИЦ................................................................................................55

3.1 Выбор трудной задачи, формулируемой над конечными группами матриц 55

3.2 Метод открытого распределения ключей на основе групп матриц...............62

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

3.3.1 Генерация треугольных матриц определенного порядка малых размерностей..............................................................................................................68

3.3.2 Генерация треугольных матриц определенного порядка произвольной размерности...............................................................................................................75

3.3.3 Генерация треугольных матриц, с равными неединичными элементами на главной диагонали.....................................................................................................83

3.3.4 Определение требований к параметрам криптосистемы.............................84

3.4 Группы матриц, заданных над конечными полями многочленов..................92

3.5 Система открытого шифрования на основе конечных групп матриц...........94

3.6 Метод аутентификации пользователей с нулевым разглашением................98

3.7 Выводы к главе 3...............................................................................................100

ГЛАВА 4. СИСТЕМЫ СОВМЕСТНОГО ШИФРОВАНИЯ ДВУХ СООБЩЕНИЙ.........................................................................................................102

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

4.2 Выводы к главе 4...............................................................................................105

ЗАКЛЮЧЕНИЕ.......................................................................................................106

СПИСОК НАУЧНЫХ ПУБЛИКАЦИЙ................................................................108

СПИСОК ЛИТЕРАТУРЫ.......................................................................................110

ПРИЛОЖЕНИЯ.......................................................................................................118

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

ключей......................................................................................................................118

А.1. Описание пользовательского интерфейса....................................................118

A.2. Функциональная схема...................................................................................121

Приложение Б. Программная реализация системы открытого шифрования на

основе необратимых матриц..................................................................................124

Б.1. Описание пользовательского интерфейса.....................................................124

Б.2. Функциональная схема....................................................................................128

Приложение В. Программная реализация системы аутентификации с нулевым разглашением...........................................................................................................129

B.1. Описание программного интерфейса............................................................129

В.2. Функциональная схема...................................................................................132

Ввеление

Г 1 ~

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

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

В 1994 году Шор [79] показал, что квантовые компьютеры способны взломать все используемые в настоящее время криптографические системы с открытым ключом, в том числе ЭЦП, и в 2001 году Чуанг и др. реализовал алгоритм Шора на 7-кубитном квантовом компьютере. Ученые предсказали, что в течение следующих 15-20 лет будут изобретены квантовые компьютеры, которые будут иметь достаточное количество кубитов для реализации идей Шора по взлому используемых на практике криптосистем.

Соответственно возникают следующие вопросы: Какие криптографические системы можно будет использовать, когда создадут квантовые компьютеры? Что мы знаем об их безопасности и эффективности? Каков их статус стандартизации?

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

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

Объектом исследования являются системы защиты и аутентификации информации, объектов и субъектов информационно-коммуникационных технологий.

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

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

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

Для достижения поставленной цели в ходе выполнения исследований решались следующие частные задачи:

1. Анализ особенностей, потенциальных слабостей и производительности криптосистемы МСЖ, как одной из наиболее распространенных систем, заданных над некоммутативными группами.

2. Определение сложности задачи поиска сопрягающего элемента в конечной некоммутативной группе путем ее сведения к решению системы линейных уравнений.

3. Анализ возможности применения задачи дискретного логарифмирования в конечных группах матриц для построения криптографических протоколов.

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

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

6. Разработка метода нахождения группы матриц заданного простого порядка р.

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

Основные положения, выносимые на защиту:

1. Метод открытого распределения ключей на основе конечных групп

матриц.

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

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

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

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

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

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

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

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

Диссертационная работа изложена на 132 страницах, включая 4 главы, 5 рисунков, 1 таблицу, 126 формул и список использованной литературы из 84 наименований.

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

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

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

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

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

Глава 1. Зашита информации и аутентификации в настоящее время

1.1 Защита информации в информационных системах и телекоммуникационных сетях

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

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

В информационных системах для обеспечения защиты от несанкционированного доступа к информации и неправомерного вмешательства во внутренние процессы используется ряд защитных механизмов [79]:

• идентифик