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

4853686

ГУРЬЯНОВ ДЕНИС ЮРЬЕВИЧ

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

РАЗМЕРНОСТИ

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

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

О 3 013 ¿3 ¡1

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

4853686

Работа выполнена на кафедре автоматизированных систем обработки информации и управления Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И.Ульянова (Ленина)

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

Молдовян Александр Андреевич

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

Коробейников Анатолий Григорьевич

кандидат технических наук Пилькевич Сергей Владимирович

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

Защита диссертации состоится «JЬ_» ср&^рв-ЛА 2011г. в 5~0 на заседании совета по защите докторских и кандидатских диссертаций Д 212.227.05 Санкт-Петербургского государственного университета информационных технологий, механики и оптики по адресу: 197191, г. Санкт-Петербург, пр. Кронверкский, д. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан « № » ^ибард 2011г.

Ученый секретарь

диссертационного совета Д 212.227.05 /и?/ Поляков В. И.

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

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

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

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

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

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

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

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

1) изучение известных подходов к синтезу алгоритмов и протоколов аутентификации информации на основе вычислений в конечных группах векторов и матриц;

2) разработка схем потенциальных атак на известные схемы, основанные на сложности задачи дискретного логарифмирования;

3) выработка способов задания конечных групп векторов, порядок которых делится на квадрат большого простого числа, что требуется для синтеза схем ЭЦП на основе сложности задачи извлечения корней большой простой степени;

4) разработка альтернативных схем ЭЦП, основанных на сложности вычисления корней большой простой степени в случаях специальных значений порядка векторов;

5) оценка размера безопасных параметров разработанных и известных алгоритмов и протоколов ЭЦП на основе вычислений в конечных группах векторов и матриц малой размерности.

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

1) предложен способ построения конечных групп векторов с требуемой структурой их порядка для построения стойких схем ЭЦП, основанных на сложности извлечения корней большой простой степени в группах известного порядка;

2) разработан алгоритм ЭЦП, основанный на сложности извлечения корней большой простой степени в случаях делимости порядка конечной группы векторов на квадрат степени корня;

3) выполнен анализ стойкости разработанных схем ЭЦП на основе установленного изоморфизма конечных групп двухмерных векторов (КГДВ) в поле, над которым они определены;

4) выполнен анализ стойкости разработанных схем ЭЦП на основе гомоморфизма КГДВ в поле, над которым они определены;

5) на основе выполненного анализа стойкости схем, ЭЦП даны рекомендации по выбору безопасных размеров параметров и дана сравнительная оценка эффективности схемотехнической реализации криптосхем на основе КГДВ;

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

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

1. Разработка алгоритмов ЭЦП на основе сложности извлечения корней большой простой степени в КГДВ.

2. Анализ стойкости криптохем над КГДВ, основанный на изоморфизме КГДВ в поле, над которым задано векторное пространство.

3. Анализ стойкости криптохем над КГДВ, основанный на использовании гомоморфизма КГДВ в базовое поле, над которым задано векторное пространство. *

4. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи извлечения корней большой простой степени.

5. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи дискретного логарифмирования.

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

1. Анализ стойкости схем ЭЦП, основанных на сложности извлечения корней большой простой степени в случае делимости' порядка группы на квадрат степени корня и использующих вычисления в нециклических КГДВ, заданных над конечным простым полем СЩр), отличающийся использованием гомоморфизма КГДВ в поле СР'(р) для сведения задачи дискретного логарифмирования по «двухмерному основанию» к задаче дискретного логарифмирования в поле и требование выбора размера характеристики поляр, равного 1024 бит и более.

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

3. Алгоритм вычисления гомоморфизма нециклических КГДВ, заданных над конечным простым полем в поле СДр).

4. Алгоритм вычисления корней большой простой степени в случае делимости порядка нециклических КГДВ на квадрат степени корня.

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

Апробация работы. Основные положения работы докладывались и обсуждались на конференциях:

«IV Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2007)»,Санкт-Петербург, 2007. -

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

«Научно-технические проблемы в промышленности», Санкт-Петербург, 2008.

«XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008)», Санкт-Петербург, 2008.,

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

«VI Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2009)», Санкт-Петербург, 2009.

Внедрение. Результаты диссертационной работы внедрены в учебный процесс СПбГЭТУ при преподавании дисциплин «Технические средства и методы защиты информации», «Криптографические методы защиты информации» и «Защита компьютерных сетей и телекоммуникаций» на кафедре Автоматизированных систем обработки информации и управления.

Диссертационная работа изложена на 133 страницах, в том числе приложение на 17 страницах, включает 4 главы, 5 рисунков и список литературы (65 наименований).

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

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

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

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

1) задаче факторизации составного числа;

2) задаче дискретного логарифмирования в конечной алгебраической структуре;

3) задаче дискретного логарифмирования в конечной мультипликативной подгруппе большого порядка;

4) задаче дискретного логарифмирования на эллиптической кривой;

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

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

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

Глава завершается постановкой задач диссертационного исследования.

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

Двухмерные векторы записываются в виде а = а ¡с + a2i. Пусть даны векторы а = ate + а2\ и b = ¿>ie + b2i. Умножение векторов определяется по формуле а°Ь = (аф) + ва2Ь2)е + (аф2 + a2èi)i, где аь а2, Ьь Ь2, s е F. Данная операция является ассоциативной и существует нейтральный вектор по умножению, которым является базисный вектор е = (1,0). Всевозможные обратимые вектора образуют мультипликативную группу векторов. Обратимым называется вектор а = a\t + а2\, такой что в векторном пространстве существует вектор a~1=xe+yi, удовлетворяющий условию а°а~1 = е. Из последнего условия получаем:

а°а-1 = {й\х + s Д2у)е + (а,у + а2х) i = (1,0). (1)

Если уравнение (1) имеет решение относительно неизвестных х и у для данного вектора a = a¡e + a2i, то вектор а является обратимым. Последнее уравнение эквивалентно системе из следующих двух линейных уравнений:

ахх + еагу = 1 mod р и аху + а2х = lmod р. (2)

Приравнивая к нулю главный определитель системы сравнений (2), получаем уравнение:

а1 -т2 = 0 . (3)

Для каждого вектора а = (аь Дг), координаты которого удовлетворяют уравнению (3), не существует обратного вектора а-1. Решения этого уравнения зависят от значения б. Рассмотрим следующих три основных случая, в которых используется понятие квадратичного вычета и квадратичного невычета. Квадратичным вычетом (невычетом) называется элемент а поля р, для которого уравнение х2 = а имеет решение в поле Р, т. е. существует; решение х б Р.

Случай 1. Значение £ является .квадратичным невычетом в тюле над

которым задано векторное пространство. Уравнение (3) преобразуется к виду 1/2 и Д] = а2в , из которого видно, что для всех ненулевых векторов решении не

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

Множество векторов представляет собой конечное поле, являющееся

расширением второй степени" базового поля. Пусть в качестве базового поля .Р

используется конечное поле многочленов ОР(р5), где 5 - степень расширения и

р - характеристика поля.: Тогда поле двоичных векторов представляет, собой

поле СР((р!)2) = СР(ръ), порядок которого равен 0.р = рь. В случае простого

базового поля Р=СР(р) имеем векторное конечное поле СР(р2),

мультипликативная группа которого имеет порядок С1=р2 -1.

Случай 2. Если б — квадратичный вычет в поле Р, то все ненулевые векторы обратимы и порядок группы векторов равен:

П = -2(0^.-1)-1 ='(¿2^-I)2

Если группа векторов задана над простым конечным полем ОДр), то конечная мультипликативная группа двухмерных векторов имеет порядок П = (р-I)2.

Случай 3. При е = 0, □ = О/ - О/г = П/{Пр -1).

В криптосхемах на основе сложности задачи извлечения корней большой простой степени используются конечные группы двухмерных векторов, содержащих элементы, порядок которых делится на квадрат достаточно большой степени корня. Учитывая, что значение порядка конечных групп двухмерных векторов, заданных над конечным простым полем характеристики р равен Л = (р- I)2 или О =р2 — 1 в зависимости от значения структурного коэффициента, построение таких групп связано с генерацией простых чисел вида р = 1 ир = N1^ — 1, где достаточно большое простое число. Генерация простых чисел вида р = М2 + 1 и . При разработке

алгоритмов генерации чисел такого вида следует учитывать, что не для всех значений N могут быть найдены простые к, при которых значение Л'А2 + 1 также является простым. Такая же ситуация имеет место и для случая р = М2 - 1. Для повышения производительности процедуры генерации простых чисел указанного вида следует учитывать эти случаи." Доказаны следующие 2 утверждения. ■ ■ ■

Утверждение 1. Простых чисел вида М2 + 1, где к - простое нечетное число w.N=2 mod 6, не существуют, кроме числа 19.

Доказательство. Пусть Nk1 + 1 = р. При к-3 я N=2 получаем р = 19 -простое число. Известно, что любое нечетное простое число имеет вид 6/ ± 1 для некоторого целого положительного t. Пусть к>Ъ - простое, тогда при N = 6g + 2 и некоторых целых g и G имеем:

p = (6g + 2)(61 ± I)2 + 1 = 6G + 3 = 3(2G + 1), следовательно число р делится на 3, т.е. не является простым. Утверждение 1 доказано.

Утверждение 2. Простых чисел вида ЛТс2 - 1, где к> 3 - простое число и N= 4 mod 6, не существует.

Доказательство. Пусть Ж2 -\=р як>Ъ. Пусть к>Ъ ~ простое число, тогда при N = 6g + 4 и некоторых целых g и G 'имеем:

р = (6g + 4)(6f ± I)2 - 1 = 6G + 3 = 3(2G + 1), следовательно, число р делится на 3, т.е. не является простым. Утверждение 2 доказано.

Эксперимент показал, что для случаев N=0 mod 6 и N = 4 mod 6, сравнительно легко можно найти простое число к, такое, что Ж2 +1 - тоже простое. Также для случаев N=0 mod 6 и N=2 mod 6 сравнительно легко можно найти простое число к, такое, что М2 -1 - тоже простое. В обоих случаях это можно сделать для любых длин числа к в интервале 8< \к\ <5 ] 2 бит, который представляет практический интерес для разработки алгоритмов ЭЦП.

Для различных значений размера числа р и к могут быть достаточно легко сгенерированы. Это можно сделать двумя путями: 1) генерируется простое число к требуемого размера, а затем подбирается 16-битовое число N, при котором значение р 1 является простым, 2) фиксируется значение

N, например N = 6, и генерируется случайные простые числа к до тех пор, пока не будет получено простое число р = NIC + 1. Кроме того, значения р и к являются долговременными элементами алгоритма ЭЦП, поэтому требуемые для генерации несколько секунд не являются критичными на практике. В случае 3 главы 2 на структуру простого числа никаких новых дополнительных требований не накладывается.

Построение алгоритма ЭЦП на основе сложности вычисления корней большой простой степени в Гр. В качестве секретного ключа используется элемент X е Гр, порядок которого <в(Х) удовлетворяет условию а(Х) > к;2. Открытый ключ генерируется по формуле Y=Хк.

Процедура генерации ЭЦП состоит в следующем.

1. Выбирается случайный элемент Т е Тр такой, что со(7) > к2.

2. Вычисляется значение R = Тк.

3. Вычисляется значение хэш-функции Н от подписываемого документа М, к которому предварительно присоединяются координаты г\ и г2 пары R:

ё—Hr^ г2 mod р. Значение е является первым элементом ЭЦП.

4. Вычисляется второй элемент ЭЦП: S = Т-Хе.

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

1. Вычисляется значение R' = Yp 1 е Sк.

2. Вычисляется значение хэш-функции е mod р, где г \ и г 2 - координаты пары R' е Г.

3. Сравниваются значения е и е'. Если е = е', то ЭЦП признается подлинной.

Схему ЭЦП данного типа можно реализовать над группами векторов, относящихся к случаям 1, 2 и 3. Особенностью случая 3 (в э этом случае

алгоритм ЭЦП включает операции над элементами групп типа ) является

возможность использования простых чисел произвольного вида, тогда как для случаев 1 и 2 требуется генерация простых чисел р специального вида. При этом во всех формулах, присутствующих в описании алгоритма ЭЦП значение к заменяется на р; например, открытый ключ будет вычисляться по формуле Y=XP. Стойкость таких алгоритмов ЭЦП определяется сложностью задачи извлечения корней.

Рассмотренная схема построения алгоритма ЭЦП может быть реализована с использованием конкретной циклической группы Г, порядок которой делится на А2. В качестве такой группы могут быть использованы группы, относящиеся к трем рассмотренным выше типам (см. случаи 1,2 и 3).

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

(случай групп типа Г^) или уравнение

(случай групп типа

^рг) имеет решение. Рассмотрим для определенности случай 2. Пусть решением является нехоторая пара X = Gj' ° G{x. Поскольку

= (Gj' 0 Gi*) = Gf" о Gf' = Y t то вычисление корня можно свести к

вычислению дискретного логарифма по двухмерному основанию (G\, Gi). Решение последней задачи даст значение двухмерного логарифма от 7, равное

(А' Jy (Р1'' Pi*) >из которого легко найти (ix,jx) и X = G'{ °G2'* =y/Y.

Таким образом, решая задачу вычисления двухмерных логарифмов, мы решаем одновременно и задачу извлечения корней большой простой степени. Как было показано, задача дискретного логарифмирования имеет экспоненциальную сложность, поэтому этот способ вычисления корней также будет иметь экспоненциальную сложность. С целью поиска более эффективных алгоритмов рассмотрим алгоритм другого типа для вычисления корня р-й степени в случае групп . Легко видеть, что Ха = Yn/p = Е, где Е - единичная пара, поэтому имеем /р = Е1/р. В рассматриваемой группе типа Г рг

содержится нециклическая подгруппа Г* порядка р2, все элементы которой, кроме единичного, имеют порядок р и являются корнями р-й степени из единичного элемента. Две случайных пары бд е Г и 0Е2 е Г порядка р с вероятностью близкой к -1 будут принадлежать различным подгруппам и составят двумерный генератор подгруппы Г . Пары Си и Оп можно найти по способу, описанному в [8, с. 20-21] в виде С/д = В1а/р и Сщ = ¿?г"р, где Б] и В2 -

к

пары порядка О'. При некоторых степенях 1 и] выполняется У' - в[л°С'Е2. Это

соотношение лежит в основе следующего алгоритма:

Я. ' " .

1. Вычислить значения У* °0~Е[ для всех г <р и запомнить их в некотором

массиве М1 (трудоемкость этого шага Щ примерно равна р операций возведения в степень).

2. Упорядочить массив М1 по значениям У' °СЕ[ (¡¥2 ~ рЩ2р операций сравнения).

3. Последовательно для} = 0,1,2...,р вычислить <3£у2 и проверить, имеется

ли такое значение в массиве М1, пока для некоторого ]о не будет получено ,

а_

присутствующее в М1 и как значение У'°, соответствующее показателю г'о (Ж3<р 1о§2 р операций сравнения ир операций возведения в степень).

В целом трудоемкость этого алгоритма равна О(р) операций возведения в степень. Рассмотренный алгоритм применим также и для нахождения корней степени к в случае 1, при этом его трудоемкость равна О (к). При значениях > 80 бит (для случая 2) и > 80 бит (для случая 2) нахождение корней простых степеней р и к в рассматриваемых нециклических группах вычислительно невыполнимо, поскольку это требует выполнения более 280 операций возведения в степень. После выполнения алгоритма имеем: а а, п' п' а. а.

Т Т'о Р —1аР —*Р —к,Р —1аР

Г" =С*1°С£=В1Р оВ2р => У = ВР о Вр о Г", (4)

_ П'

Легко видеть, что НОД(£У, ¿)=\, где 2 ^ + - целое число, поэтому

существует и легко вычисляется значение ¿^г^тосШ'. Из (4) получаем формулу для определения искомого корня:

(а.. п\, V п'

Г =

—у —ы

5/ оВр о Г

г- тл'

€ = вр оВр о г. (5)

\

Завершающие вычисления по формулам (4) и (5) не влияют на полученную оценку трудоемкости алгоритма непосредственного вычисления корней. Формула (5) дает одно значение корня, все остальные корни из У могут быть найдены путем умножения полученного корня у[у на все корни из единичной пары Е. Это легко доказывается. Очевидно, что все корни

эквивалентны для рассмотренной ниже схемы ЭЦП, но это не критично для ее

стойкости, поскольку их доля как элементов группы составляет при

используемых длинах простого числа р пренебрежимо малую величину, равную:

Р2 Р2 _ 1

о(г,2) РЧР- 1) р(р-1)-

Также предложены схемы ЭЦП на основе сложности дискретного логарифмирования в Гр.

Построение алгоритма ЭЦП на основе сложности дискретного логарифмирования в

Процедура генерации параметров алгоритма состоит в следующем:

1. Задать размер простого числа q (до 320 бит);

2. Генерация простого числа p=nq+1; о Ввести число т (т=е);

о Сгенерировать т (генерируется случайное число w и вычисляется m=w2 mod р);

3. Вычисляется значение G (gi;g2);

(выбрать случайное B=(b\,b2) и вычислить G'=В2. Если G'^£=(1;0), то G=G');

4. Сгенерировать секретный ключ х (размер х не менее 100 бит);

5. Вычисляется открытый ключ Y=G'= (уйу2). Процедура генерации ЭЦП (h; 5)состоит в следующем:

1. Ввести значение хэш-функции Я;

2. Сгенерировать случайное число к (размер = 150 бит);

3. Вычисляется вектор R=Gk = (^ьгг);

4. Вычисляется первый элемент ЭЦП h=H(r\\r2) mod q;

5. Вычисляется второй элемент ЭЦП s=k - xh mod q . Процедура проверки подлинности ЭЦП (/г; 5)состоит в следующем:

1. Вычисляется значение R '=7* G'= (r'\;r'2);

2. Вычисляется значение хэш-функции h'=H(r\\\r'2) mod q, где || -операция конкатенации;

3. Сравниваются значения h' и h. Если h = h\ то ЭЦП признается подлинной.

Второй вариант построения алгоритма ЭЦП на основе сложности дискретного логарифмирования в Гр.

Процедура генерации подписи к сообщению М выполняется следующим образом:

1. Выбрать два случайных 80-битовых значения t\ и i2 и вычислить вектор

2. Используя некоторую специфицированную 160-битовую хэш-функцию

тт е-Н о к о /•, , .

Н, вычислить значение е, 1 2 mod р;

3. Вычислить значения «1 и s2 по формулам:

Sl=tl +Х1е1+Х1Х2е2 и s2 = t2+ x2et+ (x; -r .\i)c>2 mod q.

Подписью является четверка чисел еь е2, ii и s2, общий размер которой равен примерно 320 бит.

Процедура проверки ЭЦП состоит в выполнений следующих шагов:

1. По открытому ключу (Fi, Y2) вычислить вектор:

*

2. Вычислить значение е ~ ^°ri°r2 modр\

3. Сравнить значения е и е'. Если е = е' , то подпись к сообщению М признается подлинной. В противном случае подпись отвергается.

Также предложен алгоритм ЭЦП, основанной на сложности задачи нахождения корней большой простой степени к в нециклических конечных группах, в случае использования групп типа Гр. В качестве секретного ключа используется элемент X е Тр, порядок которого о(Х) удовлетворяет условию со(А) > к2. Открытый ключ генерируется по формуле У = Хк.

Процедура генерации ЭЦП состоит в следующем:

1. Выбирается случайный элемент Г е Тр такой, что со(7) > к2;

2. Вычисляется значение R - Тк;

3. Вычисляется значение хэш-функции Н от подписываемого документа М, к которому предварительно присоединяются координаты п и г2 пары R:

Q — fff р

1 2 mod р. Значение е является первым элементом ЭЦП;

4. Вычисляется второй элемент ЭЦП: S = Т-Хе,

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

1. Вычисляется значение R' = YP Sk;

1 *

Q = Y

2. Вычисляется значение хэш-функции 1 2 mod р,

где г \ и г 2 - координаты пары R' е Г;

3. Сравниваются значения е и е'. Если е = е\ то ЭЦП признается подлинной. ■ -

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

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

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

умножения векторов: (ae + bi)p =

= I СР(¿0* = ПР + (¿¡)Р =ape + bP(i2р1/2i = ае + b^2i = ас + Ы. (6)

k=0

Все векторы, принадлежащие группе Гр являются обратимыми, т. е. существует вектор (ае + 6i)-1. Умножая левую и правую части выражения (6) на (ае + bi)~ \ получаем (ае + bff '1 = Е mod р. То есть порядок любого вектора не превышает значение р- 1. Максимальное значение порядка равно р-1. Такой порядок имеют, например, векторы (g, 0), где g - примитивный элемент поля GF(p). Группа является нециклической. Более детальное строение группы можно установить, используя описанный ниже гомоморфизм ср группы Гр в множество всех упорядоченных пар [А, В] элементов поля GF(p), т. е. Ф: Гр -» Fp хFp, над которыми определена операция умножения пар (•) как

независимое умножение первых и вторых элементов пар-сомножителей. Отображение вектора (а, Ь) зададим в пару элементов поля GF(p), равных линейным комбинациям координат вектора (а, Ь), т. е. по формуле

ф(а,Ь) = \А,В\ = \кха + к2Ъ,къа + кАЬ\.

Некоторый другой вектор (с, d) по заданному правилу отображается в

пару:

(p(c,d) = \C,D\ - \кгс + k2d,k3c + k^d]. Произведение пар [А, В] и [С, D] равно: [А,В] ® [C,D\ = [к^а + кф,къа + кАЬ\• \кхс + k2d, къс + kAd\ = = ^klac + klk2ad + kji2bc + k2bd, к2 ас + k3k4ad + k2kAbc + k]hd J. ^

Произведение векторов (a, b) °{c,d) = (ac + bd\i, ad + be) согласно заданному правилу отображается в пару:

[кл(ас + Ьс1\\) + к2(ас! + Ьс),к2(ас + Ьс1ц) + к4(ас! + Ьс)] =

(О)

= \кхас + ^Мц + к2ас! + к2Ьс,кгас + къЬс1\х. + к.са! + кАЬс\.

Выражения (6) и (7) равны для произвольных значений а,Ь,сис! при следующих значениях коэффициентов линейного представления:

к\ - к3 = 1 и кг = к2 = ц.

Последнее соотношение показывает, что построенный гомоморфизм относится к случаю, когда коэффициент ц является квадратичным вычетом. При этом имеются два варианта такого гомоморфизма. В первом варианте коэффициенты = к3 = 1, к2 = ¡л,/2 и к4 = ц1/2, а во втором— кх = к3 = 1, к2 = (х1/2 и к\ = -цш. В первом варианте каждый вектор рассматриваемой группы двухмерных векторов отображается в пару, включающую два одинаковых ненулевых элемента ср(д, Ь) = [а + ¿р.1''2, а + Ьцш], т. е. фактически имеет место гомоморфизм в поле Б , над которым определено векторное пространство. Во

втором варианте имеет место отображение ф вектора (а, Ъ) в пару [а + 6ц1/2, а -6ц1/2]. Поскольку для всех обратимых векторов имеет место соотношение а Ф + 6ц1'2, то в обоих вариантах образами векторов являются упорядоченные пары (А, В), в которых оба элемента отличны от нуля. Второй вариант гомоморфизма является изоморфизмом, поскольку он задает взаимно однозначное отображение. Действительно, произвольной паре [А, В] соответствует вектор-прообраз (а, Ь) с координатами:

а = (^ + 5)/2Л/ц; Ь = (А-В)/2^. (9)

В силу установленного изоморфизма строение группы Гр и строение множества х ^ с операцией • являются одинаковыми, следовательно, все

векторы группы Тр порождаются некоторым базисом, включающим два вектора порядка р- 1. Базис может быть легко вычислен по формуле (8), в которую следует подставить в качестве чисел А и В две пары значений различных примитивных элементов поля Рр. Все элементы нециклических групп порождаются произведением всевозможных степеней некоторых двух векторов С] и Сг порядка р- 1, т. е. любой вектор V может быть представлен в виде V = (ЗУ о при некоторых целочисленных значениях г и/.

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

элемент.поля ¥р, <р(У) = [у1,у2], ф(<30 = [Яь&Ь ф(С2) = [и-ь н>2], ^ = и", %г = «Р>

И'1 = г/и и>2 = и. Тогда имеем:

[л,з--2] - [а ]* =[&',£>[<',<]=[аЧ.&Ч] = •

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

Гах + ух' — 2 ¡J3.x-r8.vW ,

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

В четвертой главе рассмотрены подходы к синтезу схем ЭЦП на основе конечных групп невырожденных матриц (КГМ) размерности пхп, заданных над конечными простыми полями и конечными расширенными полями. В случае простого поля GF(^?) формула, описывающая порядок КГМ имеет вид:

о = (рп-\)(р«-р)(рп-р2)...(рп-рп~1) =

1=0

По ней можно определить возможные значения порядка циклических подгрупп КГМ для заданных значений п и р. Представляет интерес получение максимального значения размера \д[ простого делителя q\Q. при заданном размере \р\ или минимального размера ]р\ при заданном значении Первым важным фактором, который следует учесть, является четность значения п. При п > 3 потенциально возможное значение д содержится в первом множителе при нечетных и и во втором множителе - при четных п.

В случае задания КГМ над расширенным полем GF(pm) - полем многочленов степени т - 1 порядок КГМ равен:

О' = (р™- 1)(ртп-рп)(ртп-р2т)...(ртп-рт(п'1) = 1).

1-0

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

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

Построение схем ЭЦП на основе сложности дискретного логарифмирования в КГМ осуществляется следующим образом. Пусть секретным ключом некоторого пользователя является число х<д, тогда его открытым ключом является матрица У = 0х. Для формирования рандомизирующего параметра алгоритма ЭЦП (на основе задачи дискретного логарифмирования обычно строятся рандомизированные схемы ЭЦП) генерируется случайный разовый секретный ключ к и формируется по нему разовый открытый ключ Я = Ск. Разовый секретный ключ подлежит уничтожению сразу после вычисления ЭЦП. Матрица Л используется либо

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

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

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

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

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

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

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

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

7. Для всех возможных вариантов строения групп двухмерных векторов, заданных над простым полем СР(р), показано, что задача дискретного логарифмирования в группе векторов сводится к задаче дискретного логарифмирования в поле GF(p).

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

9. Рассмотрены случаи задания КГМ над конечными:.простыми и расширенными полями. : .

10. Сформулированы требования к выбору параметров задания КГМ для построения схем ЭЦП.

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

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

Публикации в журналах, входящих в перечень ВАК

1. Гурьянов Д.Ю., ДерноваЕ.С., Избаш В.И., Молдовян Д.Н. Алгоритмы электронной цифровой подписи на основе сложности извлечения корней в конечных группах известного порядка // Информационно-управляющие системы. 2008. № 5. С.33-40.

2. Гурьянов Д.Ю., Молдовян Д.Н., Цехановский В.В. Конечные группы двухмерных векторов: варианты задания и синтез алгоритмов цифровой подписи // Вопросы защиты информации. 2010. № 1. С. 7-13.

Прочие публикации

1. Гурьянов Д.Ю., ДерноваЕ.С, Костина A.A., МоддовянН.А. Построение алгоритмов электронной цифровой подписина основе групп малой размерности // Информационная безопасность регионов России (ИБРР-2007): Труды конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: СПОИСУ, 2007. - С. 167-172.

2. Гурьянов Д. Ю., Дернова Е.С., Нгуен Ле Минь. Схема цифровой подписи над нециклическими группами со специальным значением порядка // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конф., г. Санкт-Петербург, 20-21 ноября 2008г. - СПб.: ВАС, 2008. - С.212-217.

3. Гурьянов Д. Ю., Мирин А.Ю., Синев В. Е.. Метод решения задачи дискретного логарифмирования в конечных группах двухмерных векторов // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конф., г. Санкт-Петербург, 10-11 декабря 2009г. - СПб.: ВАС, 2009. - С. 188-193.

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

5. Гурьянов Д.Ю. Конечные группы двухмерных векторов, варианты задания и сложность задачи дискретного логарифмирования // Материалы VI Санкт-Петербургской межрегиональной конф. «Информационная безопасность регионов России (ИБРР-2009)», г. Санкт-Петербург, 28-30 октября 2009г. -СПб.: СПОИСУ, 2009. - С.94-95.

6. Гурьянов Д.Ю., Молдовян Д.Н., Молдовяну П.А. Варианты реализации конечных групп с многомерной цикличностью // Материалы VI С-Петербургской межрегиональной конф. «Информационная безопасность

регионов России (ИБРР-2009)», г. Санкт-Петербург, 28-30 октября 2009г. -СПб.: СПОИСУ, 2009. - С.95.

7. Гурьянов Д.Ю., Захаров Д.В., Молдовян H.A. Строение Мультипликативных групп векторов над кольцами вычетов по модулю, равному квадрату простого числа // Материалы VI Санкт-Петербургской межрегиональной конф. «Информационная безопасность регионов России (ИБРР-2009)», г. С-Петербург, 28-30 октября 2009г. - СПб.: СПОИСУ, 2009. -С.95-96.

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

9. Ананьев М.Ю., Гортинская JI.B., Гурьянов Д.Ю. Реализация доказуемо стойких протоколов коллективной подписи // Труды конф. «Научно-технические проблемы в промышленности», г. С-Петербург, 12-14 ноября 2008г. - СПб., 2008. - С. 272-276.

10. Ананьев М.Ю., Гортинская Л.В., Гурьянов Д.Ю. Реализация доказуемо стойких протоколов коллективной подписи // Материалы конф. «Научно-технические проблемы в промышленности», г. Санкт-Петербург, 1214 ноября 2008г. - СПб., 2008. - С. 37.

11. Гурьянов Д.Ю., ДерноваЕ.С., Молдовян H.A. Построение алгоритмов электронных цифровых подписей на основе групп матриц малой размерности // Информационная безопасность регионов России (ИБРР-2007): Материалы конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: 2007. - С. 79-80.

Подписано в печать 28.12.2010. Формат 60x84/16 Отпечатано с готового оригинал-макета в типографии ЗАО «КопиСервис». Печать ризографическая. Заказ № 1/1228. П. л. 1.00. Уч.-изд. л. 1.00. Тираж 100 экз.

ЗАО «КопиСервис» Адрес: 197376, Санкт-Петербург, ул. Проф. Попова, д. 3. тел.: (812) 327 5098

Содержание.

Определения.

Введение.

Глава 1. Аутентификация информации в проблематике информационной безопасности.

1.1. Методы обеспечения аутентификации.

1.2. Алгоритмы электронной цифровой подписи.

1.3. Элементы эллиптической криптографии.

1.3.1. Основные свойства эллиптических кривых.

1.3.2. Цифровая подпись ГОСТ Р 34.10-2001.

1.4. Использование конечных коммутативных и некоммутативных групп векторов в синтезе криптосхем.

1.5. Постановка задачи диссертационного исследования.

Глава 2. Криптосхемы на основе конечных групп векторов.

2.1. Конечные векторные пространства и задание операции умножения векторов.

2.2. Конечные группы двухмерных векторов.

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

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

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

2.6. Сравнение производительности разработанных и известных алгоритмов ЭЦП.

Выводы по главе 2.

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

3.1. Первый вариант задания умножения векторов.

3.2. Второй вариант задания умножения векторов.

3.3. Задача дискретного логарифмирования в конечном кольце двухмерных векторов.

3.4. Уточнение стойкости схем ЭЦП на основе сложности задачи нахождения «двухмерного» логарифма.

Выводы по главе 3.

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

4.1. Способы задания конечных групп матриц.

4.2. Особенности синтеза схем ЭЦП и гомоморфизм конечных групп матриц.

4.3. Синтез схем ЭЦП на основе сложности дискретного логарифмирования в конечных группах матриц.

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

Выводы по главе 4.

В настоящее время широко применяется технология электронной цифровой подписи (ЭЦП). Известно достаточно большое число различных подходов к построению алгоритмов и протоколов ЭЦП [1-5]. Среди криптографических механизмов схемы ЭЦП отличаются высокой сложностью аппаратной реализации и сравнительно низкой производительностью, что объясняется использованием открытых ключей, связанных с секретным ключом известными математическими соотношениями [6-9]. Параметры алгоритмов ЭЦП должны иметь достаточно большой размер, чтобы обеспечить приемлемый уровень стойкости ЭЦП, что ведет к снижению производительности. Повышение производительности алгоритмов ЭЦП может быть достигнуто использованием новых вычислительно трудных задач, лежащих в основе схем ЭЦП [10-12], а также использованием конечных алгебраических структур с вычислительно эффективными операциями [13-16] и распараллеливаемыми операциями умножения [17,18]. Важность для практики проблемы повышения производительности и снижения стоимости аппаратной реализации обусловливает интерес исследователей к разработке новых схем ЭЦП. В последнее время большое внимание исследователей посвящено построению алгоритмов ЭЦП, использующих вычисления в нециклических конечных группах [19,20]. Предложен ряд схем ЭЦП, основанных на вычислениях в конечных группах векторов и матриц, однако вопрос о целесообразности их практического применения остается открытым ввиду отсутствия оценки безопасных размеров параметров этих криптосхем. Это определяет актуальность темы данного диссертационного исследования, направленного на оценку достигаемого выигрыша в производительности и снижении стоимости аппаратной реализации при практическом использовании в средствах информационной безопасности схем ЭЦП, основанных на трудных задачах извлечения корней большой простой степени в специальных случаях и дискретного логарифмирования, формулируемых над нециклическими конечными группами векторов и матриц, на оценку безопасных параметров этих схем ЭЦП в случае малой размерности векторов и матриц.

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

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

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

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

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

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

1) изучение известных подходов к синтезу алгоритмов и протоколов аутентификации информации на основе вычислений в конечных группах векторов и матриц;

2) разработка схем потенциальных атак на известные схемы, основанные на сложности задачи дискретного логарифмирования;

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

4) разработка альтернативных схемы электронной цифровой подписи, основанных на сложности вычисления корней большой простой степени в случаях специальных значений порядка векторов;

5) дать рекомендации к выбору безопасных параметров разработанных и известных алгоритмов и протоколов электронной цифровой подписи.

Получены следующие новые научные результаты:

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

2. Разработка атак, основанных на использовании изоморфизма конечных групп векторов в базовое поле, над которым задано векторное пространство.

3. Разработка атак, основанных на использовании гомоморфизма конечных групп векторов в базовое поле, над которым задано векторное пространство.

4. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи извлечения корней большой простой степени.

5. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи дискретного логарифмирования.

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

1. Разработка алгоритмов ЭЦП на основе сложности извлечения корней большой простой степени в КГДВ.

2. Разработка атак, основанных на использовании изоморфизма конечных групп векторов в поле, над которым задано векторное пространство.

3. Разработка атак, основанных на использовании гомоморфизма КГДВ в базовое поле, над которым задано векторное пространство.

4. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи извлечения корней большой простой степени.

5. Формулировка рекомендаций по выбору безопасных размеров параметров схем ЭЦП, основанных на вычислениях в КГДВ и использующих трудность задачи дискретного логарифмирования.

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

1. Анализ стойкости схем ЭЦП, основанных на сложности извлечения корней большой простой степени в случае делимости порядка группы на квадрат степени корня и использующих вычисления в нециклических КГДВ, заданных над конечным простым полем отличающийся использованием гомоморфизма КГДВ в поле СЕ(р) для сведения задачи дискретного логарифмирования по «двухмерному основанию» к задаче дискретного логарифмирования в поле GF(p), и требование выбора размера характеристики поля р, равного 1024 бит и более.

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

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

4. Алгоритм вычисления корней большой простой степени в случае делимости порядка нециклической КГДВ на квадрат степени корня.

Диссертационная работа изложена на 133 страницах, включая приложение на 17 страницах, 4 главы, 5 рисунков и список использованной литературы из 65 наименований.

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

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

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

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

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

Выводы по главе 4

1. Рассмотрены случаи задания КГМ над конечными простыми и расширенными полями.

2. Сформулированы требования к выбору параметров задания КГМ для построения схем ЭЦП.

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

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

104

Заключение

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

Основными результатами выполненного исследования являются следующие:

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

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

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

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

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

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

7. Для всех возможных вариантов строения групп двухмерных векторов, заданных над простым полем GF(p) показано, что задача дискретного логарифмирования в группе векторов сводится к задаче дискретного логарифмирования в поле GF(p).

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

9. Рассмотрены случаи задания КГМ над конечными простыми и расширенными полями.

10. Сформулированы требования к выбору параметров задания КГМ для построения схем ЭЦП.

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

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

Список опубликованных работ по теме диссертационного исследования i

1. Гурьянов Д.Ю., ДерноваЕ.С., Избаш В.И., Молдовян Д.Н. Алгоритмы электронной цифровой подписи на основе сложности извлечения корней в конечных группах известного порядка // Информационно-управляющие системы. 2008. № 5. С. 33-40.

2. Гурьянов Д.Ю., Молдовян Д.Н., Цехановский В.В. Конечные группы двухмерных векторов: варианты задания и синтез алгоритмов цифровой подписи // Вопросы защиты информации. 2010. № 1. С. 7-13.

3. Гурьянов Д.Ю., Дернова Е.С, Костина A.A., Молдовян H.A. Построение алгоритмов электронной цифровой подписина основе групп малой размерности // Информационная безопасность регионов России (ИБРР-2007): Труды* конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: СПОИСУ, 2007. - С. 167-172.

4. Гурьянов Д. Ю., Дернова Е.С., Нгуен Jle Минь. Схема цифровой подписи над нециклическими группами со специальным значением порядка // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конф., г. Санкт-Петербург, 20-21 ноября 2008г. - СПб.: ВАС, 2008. - С.212-217.

5. Гурьянов Д. Ю., Мирин А.Ю., Синев В. Е. Метод решения задачи дискретного логарифмирования в конечных группах двухмерных векторов // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конф., г. Санкт-Петербург, 10-11 декабря 2009г. - СПб.: ВАС, 2009. - С. 188-193.

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

7. Гурьянов Д.Ю. Конечные группы двухмерных векторов, варианты задания и сложность задачи дискретного логарифмирования // Материалы VI Санкт-Петербургской межрегиональной конф. «Информационная безопасность регионов России (ИБРР-2009)», г. Санкт-Петербург, 28-30 октября 2009г. - СПб.: СПОИСУ, 2009. - С.94-95.

8. Гурьянов Д.Ю., Молдовян Д.Н., Молдовяну П.А. Варианты реализации конечных групп с многомерной цикличностью // Материалы VI С-Петербургской межрегиональной конф. «Информационная безопасность регионов России (ИБРР-2009)», г. Санкт-Петербург, 28-30 октября 2009г. -СПб.: СПОИСУ, 2009. - С.95.

9. Гурьянов Д.Ю., Захаров Д.В., Молдовян Н.А. Строение Мультипликативных групп векторов над кольцами вычетов по модулю, равному квадрату простого числа // Материалы VI Санкт-Петербургской межрегиональной конф. «Информационная безопасность регионов России (ИБРР-2009)», г. С-Петербург, 28-30 октября 2009г. - СПб.: СПОИСУ, 2009. - С.95-96.

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

11. Ананьев М.Ю., Гортинская Л.В., Гурьянов Д.Ю. Реализация доказуемо стойких протоколов коллективной подписи // Труды конф. «Научно-технические проблемы в промышленности», г. С-Петербург, 12-14 ноября 2008г. - СПб., 2008. - С. 272-276.

12. Ананьев М.Ю., Гортинская Л.В., Гурьянов Д.Ю. Реализация доказуемо стойких протоколов коллективной подписи // Материалы конф. «Научно-технические проблемы в промышленности», г. Санкт-Петербург, 12-14 ноября 2008г. - СПб., 2008. - С. 37.

13. Гурьянов Д.Ю., Дернова Е.С., Молдовян Н.А. Построение алгоритмов электронных цифровых подписей на основе групп матриц малой размерности // Информационная безопасность регионов России (ИБРР-2007): Материалы конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: 2007. - С. 79-80.

1. Венбо Мао. Современная криптография. Теория и практика. - М., СПб, Киев. Издательский дом «Вильяме», 2005. - 763 с.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. М.: ТРИУМФ, 2002. - 816 с.

3. Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М., КомКнига, 2006.- 274 с.

4. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2002. - 480 с.

5. Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1997. 780 c.

6. Черемушкин A. В. Лекции по арифметическим алгоритмам в криптографии М.: МЦНМО, 2002 - 104 с.

7. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии М.: МЦНМО, 2003 - 326 с.

8. Молдовян Н.А. Практикум по криптосистемам с открытым ключом. -СПб.: БХВ-Петербург, 2005. 286 с.

9. Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. СПб.: БХВ-Петербург, 2010. - 290 с.

10. Moldovyan N.A. Digital Signature Scheme Based on a New Hard Problem // Computer Science Journal of Moldova. 2008, Vol.16, No.2(47), pp.163182.

11. Молдовян А.А., Молдовян H.А. Коллективная ЭЦП специальный криптографический протокол на основе новой трудной задачи // Вопросы защиты информации. 2008. № 1. С. 14—18.

12. Ко К. H., Lee S. J., Cheon J. H., Han J. W., Kang J. S., Park C. New Public-Key Cryptosystems Using Braid Groups // Advances in Cryptology —

13. Crypto 2000 / Lecture Notes in Computer Science. Springer-Verlag, 2000. Vol. 1880. P. 166—183.

14. Баженов А. А., Костина А. А., Молдовян H. А., Молдовяну П. A. Реализация схем цифровой подписи на основе сложности извлечения корней в группах известного порядка // Вопросы защиты информации. 2009. № 1(84). С. 12—18.

15. Молдовяну П.А., Дернова Е.С., Молдовян Д.Н. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации // Вопросы защиты информации. 2008. № 3(82). С. 2-7.

16. Moldovyan N.A., Moldovyanu Р.А. New primitives for digital signature algorithms // Quasigroups and related systems. 2009. Vol. 17. P. 271-282.

17. Moldovyan N.A. Fast Signatures Based on Non-Cyclic Finite Groups // Quasigroups and related systems. 2010. Vol. 18. P. 83-94.

18. Доронин С. E., Молдовян Н. А., Синев В. Е. Конечные расширенные поля для алгоритмов электронной цифровой подписи // Информационно-управляющие системы. 2009. № 1. С. 33—40.

19. Moldovyan N.A. Acceleration of the Elliptic Cryptography with Vector Finite Fields // Int. Journal of Network Security. 2009. V.9, No 2. PP. 180185.

20. Дернова E.C., Костина A.A., Молдовян H.A., Молдовяну П.А. Направления применения конечных векторных пространств в криптографии // Вопросы радиоэлектроники, сер. ОТ, 2009, вып. 2. С. 165-174.

21. Молдовян Н.А. Аутентификация информации в АСУ на основе конечных групп с многомерной цикличностью // Автоматика и телемеханика. 2009. № 8. С. 177-190.

22. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. — М.: Радио и связь, 1999. — 328 с.

23. Фергюсон H., Шнайер Б. Практическая криптография. // М., СПб, Киев. Издательский дом «Вильяме», 2005. 424 с.

24. Молдовян А.А., Молдовян Н.А. Введение в криптосистемы с открытым ключом. СПб, «БХВ-Петербург», 2005.-286 с.

25. Петров А. А. Компьютерная безопасность. Криптографические методы защиты. М.: ДМК, 2000;-445с.

26. Соколов А. В., Шаньгин В. Ф. Защита информации в распределенных корпоративных сетях и системах —М.: ДМК, 2002. 328 с.

27. Иванов М. А. Криптографические методы защиты информации в компьютерных системах и сетях.- М.: Кудиц-Образ, 2001.- 386с.

28. Федеральный закон от 10.01.2002 № 1-ФЗ Об электронной цифровой подписи.

29. Смарт Н. Криптография. М.: Техносфера, 2005. - 528 с.

30. Delfs Н., Knebl Н. Introduction to Cryptography. Principles and Applications. Berlin, Heidelberg, New York, Milan, Paris, Tokyo: Springer-Verlag . 2002. - 310 p.

31. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. 1985. -V. IT - 31. - N. 4. - P. 469-472.

32. Молдовян H. А., Молдовян А. А., Еремеев M. А. Криптография: от примитивов к синтезу алгоритмов. Спб.: БХВ — Петербург, 2004. — 446 с.

33. Schnorr С. P. Efficient signature generation by smart cards // J. Cryptology. 1991. — V. 4.-P. 161-174.

34. V. Miller. Use of elliptic curves in cryptography // Advances in cryptology: Proceedings of Crypto'85. Lecture Notes in Computer Sciences. Berlin. Springer-Verlag. 1986. Vol. 218. PP. 417-426.

35. Koblitz N. A. Elliptic curve cryptosystems // Mathematics of Computation Advances. 1987. Vol. 48. PP. 203-209.

36. Koblitz N. A. Course in Number Theory and Cryptography.—Berlin, Heidelberg, New York: Springer, 1994. —235 p.

37. Болотов А. А., Гашков С. Б., Фролов А. Б.,Часовских А. А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. —М., КомКнига, 2006. — 324 с.

38. Б.Я. Рябко, А.Н. Фионов. Криптографические методы защиты информации. М., Горячая линия Телеком, 2005.-229 с.

39. Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях.- Минск, «Вышэйшая школа», 1986.- 272 с.

40. Дернова Е.С., Костина А.А., Молдовяну П.А. Конечные группы матриц как примитив алгоритмов цифровой подписи // Вопросы защиты информации. 2008. № 3(82). С. 8-12.

41. Бухштаб А.А. Теория чисел. — М. Просвещение, 1966. —384с.

42. Курош А.Г. Курс высшей алгебры.- М., «Наука», 1971.- 431 с.

43. J. Lee, Н. Kim, Y. Lee, S.-M. Hong, H. Yoon. Parallelized Scalar Multiplication on Elliptic Curves Defined over Optimal Extension Field // International Journal of Network Security. 2007. Vol. 4. No. 1. PP. 99-106, 2007.

44. G.B. Agnew, R.C. Mullin, I.M. Onyszchuk, and S.A. Vanstone. An implementation for a fast public key cryptosystem // Journal of Cryptology. 1991. Vol. 3. PP. 63-79.

45. G.B. Agnew, R.C. Mullin, and S.A. Vanstone. An implementation ofelliptic curve cryptosystems over f1S5 // IEEE Journal on Selected Areas in

46. Communications // 1993. Vol. 11. No. 5. PP. 804-813.

47. G.B. Agnew, T. Beth, R.C. Mullin, and S.A. Vanstone. Arithmetic Operations in GF(2m) I I Journal of Cryptology. 1993. Vol. 6. PPp. 3-13.

48. Молдовян Д.Н., Молдовяну П.А. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. № 3(82). С. 12-17.

49. Доронин С.Е., Молдовяну П.А., Синев В.Е. Векторные конечные поля: задание умножения векторов большой четной размерности // Вопросы защиты информации. 2008. № 4(83). С.2-7.

50. Moldovyanu Р.А., Moldovyan N.A.Vector Form of the Finite Fields GF(pAm) // Bulletinul Academiei de Stiinte a Republicii Moldova. Matematica. 2009. No 3 (61). P. 1-7.

51. Молдовян Д.Н. Примитивы схем цифровой подписи: строение мультипликативных конечных групп векторов // Вопросы защиты информации. 2009. № 4. С. 18-24.

52. Moldovyan N.A., Moldovyan А.А. Vector Finite Groups as Primitives for Fast Digital Signature Algorithms // 4th Int. Workshop IF&GIS'09 Proc. St.Petersburg, May 17-20, 2009. St. Petersburg, Russia / Springer-Verlag LNGC. 2009. PP. 301-315.

53. Молдовяну П. А., Молдовян Д. H., Дернова Е. С. Гомоморфизм и многомерная цикличность конечных групп векторов в синтезе алгоритмов ЭЦП // Вопросы защиты информации. 2009. № 3. С. 2-8.

54. Молдовян А.А., Молдовян Н.А. Новые алгоритмы и протоколы для аутентификации информации в АСУ // Автоматика и телемеханика. 2008. №7. С. 157-169.

55. Молдовян Н.А. Вычисление корней по простому модулю как криптографический примитив // Вестник СПбГУ. Серия 10. 2008, вып. 1, с. 101-106.

56. Молдовян Д.Н. Конечные некоммутативные группы как примитив криптосистем с открытым ключом // Информатизация и связь. 2010. №1. С. 61-65.

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

58. Дернова Е.С., Костина A.A., Молдовян H.A., Молдовяну П.А. Направления применения конечных векторных пространств в криптографии // Вопросы радиоэлектроники. Серия общетехническая. 2009. Выпуск 2. С. 164-174.

59. Б.Л. ван дер Варден. Алгебра.- СПб, М., Краснодар. Лань, 2004.- 623 с.

60. Каргаполов М. И., Мерзляков Ю.И. Основы теории групп. -М.: Физматлит, 1996. 287 с.

61. Дернова Е.С. Построение алгоритмов электронной цифровой подписи на основе групп матриц малой размерности // Известия СПбГЭТУ «ЛЭТИ». 2009. №4. С. 16-20.

62. Дернова Е.С. Механизмы аутентификации информации, основанные на двух вычислительно трудных задачах // Автореферат дисс. канд. тех. наук. СПб, 2009.

63. Ко Kihyoung, Lee Sangjin, Cha Jaechoon, Choi Dooho. Cryptosystems Based on Non-commutativity // Patent Application # W02001KR01283.

64. Publication # W003013052 (Al). Publication date: February 13, 2003. International classification: H04L9/30; H04L9/32; H04L9/28; H04L9/32.i