РАСШИРЕНИЕ ФУНКЦИОНАЛЬНОСТИ АЛГОРИТМОВ АУТЕНТИФИКАЦИИ И МЕХАНИЗМЫ ЗАЩИТЫ ИНФОРМАЦИИ НАД КОНЕЧНЫМИ ГРУППАМИ ВЕКТОРОВ Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» Молдовян Дмитрий Николаевич Диссертация на соискание ученой степени кандидата технических наук по специальности по специальности – методы и системы защиты информации, информационная безопасность Научный руководитель заслуженный деятель науки и техники РФ, доктор технических наук, профе ссор Советов Борис Яковлевич

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

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

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

Задание конечных групп над векторными пространствами для криптографических применений Описание векторов: (a,b,…,c) a e + b i +…+ c j a,b,…,c – элементы конечного поля e,i,…,j – базисные вектора Сложение (+) выполняется как сложение одноименных координат, т.е. «покоординатно» Умножение ( ) выполняется по правилу перемножения каждой компоненты одного вектора с каждой компонентой другого вектора с использованием таблиц умножения базисных векторов

Задание умножения векторов как групповой операции Умножение векторов a 1 e + a 2 i + … + a m w и b 1 e + b 2 i + … + b m w можно выразить в виде следующей формулы (a 1 e + a 2 i + … + a m w) (b 1 e + b 2 i + … + b m w) = = a 1 b 1 (e e) + a 1 b 2 (e i) + …+ a 1 b m (e w) + a 2 b 1 (i e) + a 2 b 2 (i i) + … …+ a 2 b m (i j) + … + a m b 1 (w e) + a m b 2 (w i) + … + a m b m (w w), где произведения всех возможных пар базисных векторов заменяются на однокомпонентные вектора в соответствии с таблицей умножения базисных векторов (ТУБВ)

Пример таблицы умножения базисных векторов При размерности m=4 может использоваться такая таблица eijk eeijk ii e k j jj k e i kkj i e Свойства коммутативности и ассоциативности операции умножения базисных векторов «переносятся» (правилом умножения векторов) на операцию умножения векторов

Таблиц умножения базисных векторов общего типа (коммутативные ТУБВ) Для получения нужной структуры порядка групп векторов используются структурные коэффициенты eijkuvw e e i j k u v w i i j k u v w e j j k u v w e i k k u v w e i j u u v w e i j k v v w e i j k u w w e i j k u v

Назначение структурнх коэффициентов Получение циклических подгрупп большого простого порядка (случай формирования полей GF(p m )) Получение нециклических групп порядка Nq s для большого простого q Получение некоммутативных конечных групп Снижение сложности групповой операции (умножение векторов) При заданной ТУБВ значения структурных коэффициентов влияют на строение конечной группы векторов, благодаря чему можно обеспечить следующее:

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

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

Способ уменьшения сложности групповой операции за счет пересечения распределений двух структурных коэффициентов eijkuvw eeijkuvw ii j k u v w e jj k u v w e k kk u v w e ij uu v w e v j k vv w e ijku ww e kj ku v Уменьшение числа структурных коэффициентов для случая m = 7 (, GF(p); = 1)

Способ задания некоммутативных групп векторов :e:e:i:i:j:j:k:k:u:u:v:v:w:w:x:x :e:e:e:e:i:i:j:j:k:k:u:u:v:v:w:w:x:x :i:i:i:i e :x:x w :v:v u :x:x x :j:j:j:j:k:k:u:u:v:v:w:w:x:x:e:e:i:i :k:k:k:k j :i:i e :x:x w :v:v u :u:u:u:u:v:v:w:w:x:x:e:e:i:i:j:j:k:k :v:v:v:v u :k:k j :i:i e :x:x w :w:w:w:w:x:x:e:e:i:i:j:j:k:k:u:u:v:v :x:x:x:x w:v:v u:k:k j:i:i e Общий способ построения некоммутативных ТУБВ для четных значений размерности векторов (при произвольном ).

Способ задания некоммутативных групп векторов $e$e:i:i:j:j:k:k:u:u:v:v:w:w:x:x $:e::e:i:i:j:j:k:k0000 :i:i:i:i:e:e:k:k:j:j0000 :j:j0000$:e:i:i:j:j:k:k :k:k0000:i:i:e:e:k:k:j:j :u:u:u:u:v:v:w:w:x:x0000 :v:v:v:v:u:u:x:x:w:w0000 :w:w0000:u:u:v:v:w:w:x:x :x:x0000:v:v:u:u:x:x:w:w Специальный случай некоммутативной исходной ТУБВ для m = 8.

Условия образования полей в явной векторной форме 1)m|p-1, где m – размерность векторного пространства; 2) структурный коэффициент в ТУБВ должен быть таким, что уравнение x d =, где d > 1 и d|m, не имеет решений для всех делителей d |m.

Формула, описывающая порядок примарной группы в общем случае Пусть базис примарной группы включает i элементов Z ij (j = 1, 2, …, i ) порядка, i = 1, 2, …, t. где 1 2 … i … t. Строение примарной группы задается формулой, описывающей число элементов порядка, где t.

Формула, описывающая порядок некоммутативных групп 4-мерных векторов, заданных над полем GF(p) = p(p 1)(p 2 1) Базисные векторы eijk eeijk ii e k j jj k e i kkj i e Доказаны утверждения о числе обратимых векторов, равном Умножение задано с использованием ТУБВ 1)p = 4k + 1 (целое число k 1) и 1 p 1 2)p = 4k + 3 (целое число k 1) и -- квадратичный невычет по mod p

Результаты по исследованию конечных групп векторов Доказательство общего гомоморфизма групп векторов в мультипликативную группу конечного поля, над которым заданы векторы Способ задания сопрягающего элемента для задачи скрытого дискретного логарифмирования в конечной некоммутативной группе Доказательство теоремы об уникальности открытых ключей вида Y=Q j G i Q -j Алгоритм коммутативного шифрования на основе конечных полей, заданных в явной векторной форме Схемы ЭЦП над конечными группами с многомерной цикличностью

Доказательство теоремы об уникальности открытых ключей вида Y=Q w G x Q -w ( x;w – секретный ключ ) Доказательство теоремы об уникальности открытых ключей вида Y=Q w G x Q -w ( x;w – секретный ключ ) Утверждение 3.1. Пусть G и Q элементы некоммутативной группы, имеющие простые порядки g и q, соответственно, такие что Q G G Q и Z G G Z, где Z = Q G Q 1. Тогда все элементы Z ij = Q j G i Q j, где i = 1, 2,…, g 1 и j = 1, 2,…, q, попарно различны. Данное утверждение дает обоснование предложенного механизма задания выбора сопрягающего элемента в задаче скрытого дискретного логарифмирования при построении протокола открытого распределения ключей.

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

Общая схема формирования ЭЦП в схемах на основе сложности логарифмирования Формирование ЭЦП Вычисление R - рандомизирующего элемента ЭЦП Генерация случайного числа Электронный документ (ЭД), Представленный обычно значением Хэш-функции H Электронный документ (ЭД), Представленный обычно значением Хэш-функции H Секретный ключ X ключ X ЭЦП: (R,S)

Общая схема проверки подлинности ЭЦП Проверка подлинности ЭЦП Электронный документ (ЭД), Представленн ый обычно значением Хэш-функции H Электронный документ (ЭД), Представленн ый обычно значением Хэш-функции H Да / нет Справочник ОК – открытых ключей ЭЦП (R,S) Y Y=G x G - известно

Применение коллективной ЭЦП с восстановлением сообщения Структура машиночитаемой метки наносимой на бумажный документ --- При известной коллективной ЭЦП (без восстановления сообщения) Ключевые слова документа|| эталонный образ текстуры бумаги ||коллективная ЭЦП --- При коллективной ЭЦП с восстановлением сообщения - Ключевые слова документа|| коллективная ЭЦП - коллективная ЭЦП

Общая схема формирования КЭЦП Формирование доли S 1 Вычисление коллективного рандомизирующего элемента ЭЦП R=f(R 1,…,R m ) СообщениеСообщение X1X1X1X1 КЭЦП: (R,S) Генерация индивидуальн ый значений R 1,…, R m R 1,…, R m XmXmXmXm ключи X2X2X2X2 Секретныe Формирование доли S 2 Формирование доли S m Интеграция долей S 1,…, S m в единую КЭЦП

Схема проверки подлинности КЭЦП Проверка подлинности КЭЦП (восстановление сообщения) ЭДЭД Да / нет Справочник ОК – открытых ключей КЭЦП (R,S) Формирование коллективного ОК Y Y1Y1Y1Y1 Y2Y2Y2Y2 YmYmYmYm Y

Коллективная ЭЦП с восстановлением сообщения над эллиптическими кривыми Формирование коллективной подписи (r, s) к сообщению M < q: 1. Каждый пользователь генерирует случайное целое число k i (0 < k < q) и вычисляет точку C i = k i G (i = 1, 2,…, m). Значения C i (i = 1, 2,…, m) рассылаются всем пользователям. 2. Пользователи вычисляют точку C=C 1 +C 2 +…+C m и значение r = Mx C mod q, где x C координата точки С. 3. Каждый i-ый пользователь вычисляет значение s i = k i rd i mod q. Значения s i (i = 1, 2,…, m) рассылаются всем пользователям. 4. Пользователи вычисляют значение s=s 1 +s 2 +…+s m mod q Коллективной подписью является пара чисел (r, s). Проверка подлинности коллективной ЭЦП : 1. Вычисляется точка C = rQ + sG и значение M = r/x C mod q. 2. Если M = M, то подпись признается подлинной, в противном случае подпись отвергается. (Q -- коллективнй открытый ключ, равнй сумме открытых ключей подписывающих Q i =d i G )

Формирование подписи вслепую Генерация ослепляющих множителей Пользователь (сообщение) Генерация разового случайного открытого ключа R ключ X Секретный Вычисление рандомизирующего элемента слепой ЭЦП: E* Вычисление рандомизирующего элемента подлинной ЭЦП: E Вычисление второго элемента подлинной ЭЦП: S ПодписывающийПодписывающий Вычисление второго элемента слепой ЭЦП: S*

ЗаключениеЗаключение Основные результат опубликованы в 16 публикациях, включая 11 статей в журналах из списка ВАК Сформулировано 11 полученных результатов

СПАСИБО ЗА ВНИМАНИЕ !