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

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

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

МЕТОД ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ КРИПТОСХЕМ, ОСНОВАННЫХ НА КОНЕЧНЫХ НЕКОММУТАТИВНЫХ ГРУППАХ

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

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

11 АПР 2013

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

005051772

005051772

Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики на кафедре «Безопасные информационные технологии».

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

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

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

Еремеев Михаил Алексеевич Военно-космическая академия имени А.Ф. Можайского, заведующий кафедрой систем сбора и обработки информации

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

Ведущая организация: Государственный университет

морского и речного флота имени адмирала С.О. Макарова

Защита состоится «24» апреля 2013 г. в 15 часов 50 минут на заседании диссертационного совета Д 212.227.05 Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

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

Автореферат разослан <лЛ.2 » ОТ^ 2013 г.

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

диссертационного совета Д 212.227.05 кандидат технических наук, доцент

2

/Но,

ч

Поляков В.И.

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

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

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

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

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

1) вывод значения порядка конечных некоммутативных групп векторов размерности 4, построенных над кольцом целых чисел

2) вывод значения порядка конечных некоммутативных групп векторов размерности 4, построенных над полем многочленов

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

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

5) оценка производительности криптосхем с распараллеливанием операций

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

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

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

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

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

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

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

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

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

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

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

3) Исследовано строение конечных некоммутативных групп векторов размерности 4.

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

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

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

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

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

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

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

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

«2-я межвузовская научная конференция по проблемам информатики СПИСОК-2011,2011г.»

«XVII Международная научно-методическая конференция «Современное образование: содержание, технологии, качество», 2011г.»

«I Всероссийский конгресс молодых ученых, 2012г.»

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

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

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

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

- Задача факторизации

- Задача дискретного логарифмирования

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

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

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

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

Конечные некоммутативные группы векторов над кольцом Zpa

Важной характеристикой конечных некоммутативных групп является значение их порядка и его связь с параметрами задания таких групп. В случае задания конечных групп четырехмерных векторов над конечными кольцами Zpa и использования операции умножения векторов, заданной по таблице 1, в качестве групповой операции общая формула для порядка группы устанавливается следующим утверждением. (На значение структурного коэффициента v накладывается условие НОД(у, р") = 1, иначе не существует обратного значения v_1 по модулю р".)

Утверждение 1. Для структурных коэффициентов, удовлетворяющих условиям 0<х<р,0<у<рн НОД(у, ра) = 1, при произвольных натуральных значениях степени а группа четырехмерных векторов над конечным кольцом Zpa с умножением векторов, заданным по таблице 1 имеет порядок, равный П = р4(а-1)+1 (р_1)(р2_1)

Доказательство. Множество всех векторов {А}, такое, что каждому вектору А может быть сопоставлен обратный вектор А~1, для которого выполняется соотношение АА ~1 = Е, образует конечную группу. Для вычисления порядка Q заданной некоммутативной группы рассмотрим решение уравнения вида АХ= Е , которое можно представить следующим образом:

(ае + b\ + cj + dk) ° (хс +yi + zj + wk) =(vax — zv~1by — v~1cz — xv_1iAv)e + + (vbx + vay — dz + cw)i + (vex + idy + vai — xbw)j + (vdx — cy + bz + vmv)k =

= v-1e + Oi + 0j+ Ok.

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

'vox — TV-1 by — v~1cz — rv-1dw = v-1 mod pa vbx + vay — dz + cw = 0 mod pa vex + тdy + vaz — tbw = 0 mod pa vdx — cy+bz + vaw = 0 mod pa

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

о е \ j к

е уе VI У| ук

1 VI —ТУ~'с к -ч

\ V] -к -у-'е 1

к ук Ч -1 —ту~'е

Если главный определитель Д(Л) системы (1) является взаимно простым с ра, то существует решение, которое дает значение координат вектора, являющегося обратным к вектору А = (а,Ь,с,с1). Если НОД(Д(Л), ра) Ф 1, то вектор А необратим. Значение С1 определим как число всех четырехмерных векторов, равное (ра)4, за вычетом числа необратимых векторов. Запишем значение определителя А(А):

V а -XV-1 Ь —V -1с —ту_1й хЬ ха —а с хс т^ ха -т Ь \>й —с Ь ха

хЪ —а с хЬ ха с

+ XVус ха —хЬ — у_1с хс хс1 —тЬ + хй Ь ха хс1 —с ха

V Ь ха —<1 +хх-1а ус тd ха . хй —с Ь

Четыре слагаемых в правой части последнего выражения можно переписать в следующем виде:

АСА) =

ха —(1 с х<1 ха —х Ь —с Ь ха

ха —й с хй ха —хЬ —с Ь ха

= ха(ха(х2а2 + тй2) + <1(ута<1 — хЬс) + с(хЬа + хае)) = = у2а2(у2а2 + т Ь2 + с2 + та2)

у Ь -а с

XX'1 Ь хс ха -хЪ

X <1 Ъ ха

х Ь у а с

—X -1с хс у а -хЪ

у а —с ха

хЪ ха -а

ХХ'Ч хс хй ха

ха —с Ъ

= хх~1Ь(хЬ(у2а2 + тЬ2) + й(у2ас + хтЬй) + с(уЬс - х2ай)) = = т Ь2(у2а2 + т Ь2 + с2 + та2) = —у_1с(уЬ(утай — тЬс) — ха(у2ас + утЬО.) + с(—хс2 — туй2)) -= с2 (у2 а2 + тЬ2 + с2 + та2) = хх~г<1(хЬ(гЬс1 + у ас) — ха(хЬс + х2а0.) — с1(—хс2 — туй2)) = = тй2(у2а2 + т Ь2 + с2 + хО2)

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

Д(Л) = (у2 а2 + т Ъ2 + с2 + т d2)2. (2)

Координаты необратимых векторов (а, Ь, с, d) удовлетворяют неравенству НОД(А(Л), ра) ф 1. Это возможно только в случае выполнения следующего сравнения

v2a2 + тЬ2 + c2+rd2 = 0 mod ра (3)

относительно переменных (а, Ь, с, d).

Если главный определитель А(А) системы (1) не сравним по модулю р с нулем, то существует решение, которое дает значение координат вектора, являющегося обратным к вектору А = (а, Ь, с, d). Если А (А) = 0 mod р, то вектор А необратим. Координаты необратимых векторов (а, Ь, с, d) удовлетворяют неравенству НОД(Д(Л), р") Ф 1, поэтому число необратимых векторов найдем как число решений сравнения

v2a'2 +тЬ 2 + с'2 + rd'2 = 0 mod ра (4)

относительно неизвестных а',Ь',с' и d'. Сравнение (4) имеет р1+р2—р различных решений как четверок классов вычетов по модулю р. Остальные четверки классов по модулю р не удовлетворяют сравнению (4), поэтому они и только они соответствуют наборам координат, которые определяют обратимые четырехмерные вектора над кольцом классов вычетов по модулю ра. Число таких наборов четверок классов (a',b',c',d) по модулю р равно П' ~рА-рЪ ~р2 +р ~р(р - 1)(р2 - 1). Каждый из указанных наборов классов вычетов по модулю р, задает р4(а~'' различных наборов классов (а, Ь, с, d) по модулю ра, которые не удовлетворяют сравнению (4), т.е. удовлетворяют равенству НОД(Д(Л), ра) = 1, следовательно, задают обратимые вектора. Наборы классов по модулю ра имеют вид

(a, b,c,d)= (а'+ щр, Ь'+ п2р, с'+ щр, d'+ щр), где натуральные числа п\, п2, пъ и щ принимают все значения от 0 до ра~1 — 1. Таким образом, значение порядка рассматриваемой группы некоммутативных векторов равно

Q = Q'/74(a-1)=p4(a-|, + V-l)(p-D- (5)

Утверждение доказано.

В частном случае для a = 1 получаем известную формулу Q = pip1 — 1)(/> — 1). В таблице представлены экспериментальные результаты по исследованию строения конечных некоммутативных групп четырехмерных векторов при задании операции умножения векторов по таблице 1.

Установлено, что строение не зависит от значений структурных коэффициентов в интервалах их значений 0 < т <р, 0 < V </?. при выполнении условий НОД(т, ра)=1 и НОД(у,ра)=1. Экспериментальные результаты подтверждают полученную общую формулу (5). Для синтеза криптосхем, основанных на трудности скрытой задачи поиска сопрягающего элемента, конечные некоммутативные группы четырехмерных векторов представляют интерес, поскольку при а > 2 в них содержатся примарные коммутативные подгруппы с многомерным циклическим строением, которые могут быть использованы для задания специальных случаев вышеупомянутой задачи. Конечные некоммутативные группы векторов над полем С/ч(/>5)

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

ч2а2+1Ь2+с2+^2=0, (6)

в котором все коэффициенты и переменные являются элементами поля СР(р!). По аналогии с нахождением числа различных решений уравнения (6) в случае д=1, можно легко найти число решений N этого уравнения в случае 5 > 1 и в результате этого доказать следующее утверждение

Утверждение 2. Число решений уравнения (4) над полем GF(pI) равно рЪ! + ръ — р! в следующих случаях: 1) степень расширения поля 5 является четным натуральным числом; 2) простое число р представляется в виде р = 4к+\ при некотором натуральном к> 1; 3) степень расширения поля \ является нечетным натуральным числом и коэффициент т таков, что уравнение х2 = -т имеет решения в поле СР\р!).

Непосредственно из утверждения 2 следует утверждение 3 о порядке некоммутативной группы четырехмерных векторов, заданных над полем

сгад.

Утверждение 3. Порядок некоммутативной группы четырехмерных векторов над полем СР(р*) равен О = р'(р' - 1 )(р2' — 1) в следующих случаях: 1) степень расширения поля « является четным натуральным числом; 2) простое число р представляется в видер = 4к+ 1 при некотором натуральном к> 1; 3) л- является

ю

нечетным натуральным числом и коэффициент т таков, что уравнение хг = -т имеет решения в поле С/^5).

Доказательство утверждения 3 состоит в вычитании из числа всех возможных векторов, задаваемых над полем GF(//), которое равно р4\ значения рь+ръ — р, равного числу необратимых векторов:

П = р* - (РЬ + РЪ ~р) =Р5(Р° ~ 1)(РЪ ~ О- (7)

Утверждение 3 покрывает основные случае выбора параметров задания некоммутативных групп четырехмерных векторов для разработки криптосхем на их основе. Вычислительный эксперимент показал, что и в оставшихся случаях при т ^ 0 формула (7) верна.

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

Синтез конечных некоммутативных колец векторов большой размерности методом вложения. Для синтеза некоммутативных колец векторов большой размерности предлагается метод погружения коммутативного ККВ векторов в некоммутативное ККВ векторов (или некоммутативного ККВ в коммутативное ККВ), позволяющий синтезировать некоммутативные кольца векторов над полем СР(р), содержащие элементы порядка р1"/2 — 1 = (рт/4 — 1)(рт/4 + 1). Для значений размерности векторов, равной т = 2*1 при некотором натуральном значении Л > 2, можно подобрать простое число р таким, что число (о = (рт^4 + 1)/2 является простым. В этом случае существуют вектора порядка ® и их достаточно легко найти.

Пусть задана некоторая некоммутативная ТУБВ, например, для векторов размерности т = 4. Обозначим формальные базисные вектора следующим образом: у1,у2,...,у>1. Переименовывая к раз указанные базисные вектора

сформируем к аналогичных ТУБВ, которые обозначим как Т', £ = 1,2,____ к.

Базисные вектора, соответствующие ТУБВ Т' составляют множество {у1'у2< — <УА}- При этом указанное переименование базисных векторов выполним так, что никакие два различных множества {у|,...,у^}, £ = 1,2,...к, не содержат одинаковых базисных векторов. Очевидно, что, если исходная ТУБВ определяет ассоциативное умножение векторов, то каждая из таблиц Т' также определяют ассоциативное умножение.

Определим класс л^ как множество базисных векторов {vj1, vj1,..., vf] для j = 1,2,..., ft. Зададим операцию умножения «•» над классами у и v^, где j, д 6 {1,2,..., ft}, следующим образом. Выбирается произвольное натуральное число z Е {1,2,..., к}, затем из множества {v^1, v^2, vf} выбирается произвольный элемент \f, а из {vg,vj, — ,Vg} — элемент v|. Над базисными векторами vf и выполняется операция умножения по таблице Tz: °Vg = Vq, где j, g € {1,2,..., ft}. В качестве результата умножения классов vj и v^ берется класс у,, которому принадлежит базисный вектор т. е. vj • = v^". Очевидно, что по построению результат умножения классов не зависит от выбора значения z 6 {1,2,..., к].

Определим операцию умножения «*» таблицы Tl, i = 1,2,..., к, на скаляр Я 6 GF(p), где GF(p) — поле над которым задано рассматриваемое векторное пространство, как процедуру умножения базисных векторов на структурный коэффициент Я в каждой клетке Т1. (Таким образом, ЯТ' уже не принадлежит множеству таблиц Т', i = 1,2,...,к.) Зададим над множеством {Т^Т2, ...,Тк} табличную ассоциативную и коммутативную операцию умножения, результатом которой может явиться таблица ЯТ"' при некотором значении w = 1,2, ...,к. Обозначим таблицу умножения элементов множества {Т1, Т2,..., Т*} как TABLE.

Задавая детальное представление каждой ТУБВ в TABLE, получаем результирующую ТУБВ, определяющую ассоциативную операцию умножения «о» над следующим множеством базисных векторов:

{Vi1, V2\ ..., Vj,, Vl, Vf, ..., Vfo, ..., Vf, Vf, ..., Vfr}. Каждый элемент данного множества, например v^, может быть однозначно задан как элемент, одновременно принадлежащий классу v^ и таблице ТЕ: v£ = (vj7nT£), где «П» — операция нахождения элемента, принадлежащего одновременно двум множествам-операндам. Легко показать, что операция умножения базисных векторов v^j и vj = (y^ Л Тт) может быть выполнена по следующей формуле

vf = (v^ Л Т£) о п Тт) = Л (Т£ * Тт).

Таким образом, вьшолнение операции над векторами размерности ftfc сводится к выполнению операций «•», «*» и «П». Покажем, что если операции «•» и «*» ассоциативны, то операция умножения векторов размерности hk также является ассоциативной. Пусть даны три базисных вектора Vp, v^ и vj. Тогда имеем

(Ур ° V* ) о VI = ((^ П Т") о П Т£)) о п Тг)

= ((^"О Л (Т* * т«)) о П тт) =

= ((О^О***) п (СТ" * т£) * тг)) = = п (т" * (Т£ * то)) =

= П Т") о ((У^) П (Т* * Т1)) =

= (уё Л Т") о ((^ п Т£) о п Тт)) = V/ о о у£)

То есть ассоциативность операции «о» доказана.

Используя некоммутативную ТУБВ для случая т = 4, была построена ТУБВ для случая т = 8 (см. табл. 2), задающая некоммутативное ККВ, в котором максимальный мультипликативный порядок элементов равен р4 — 1 в случае, если структурный коэффициент е является квадратичным невычетом (в данном ККВ единицей является вектор (1,0,0,1,0,0,0,0)). При этом сложность операции умножения векторов уменьшается примерно в два раза за счет наличия в половине клеток ТУБВ структурного коэффициента, равного нулю. В следующем разделе представляется другой способ синтеза некоммутативных ККВ большой размерности, содержащих элементы достаточно большого простого порядка.

Таблица 2. Некоммутативная ТУБВ, синтезированная методом вложения.

о е 1 к и V X

е е 1 0 0 V и 0 0

1 0 0 е I 0 0 V и

] 3 к 0 0 X 0 0

к 0 0 \ к 0 0 \У X

и V и 0 0 е е С 1 0 0

V 0 0 V и 0 0 е е с 1

\У X 0 0 ек 0 0

X 0 0 \У X 0 0 <4 в к

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

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

Данный метод был опробован для случая тп = 8. Для его реализации была разработана компьютерная программа, которая позволила найти достаточно большое число (более 600) различных несимметричных распределений структурного коэффициента —1 для симметричной исходной ТУБВ, представленной в табл. 3, иллюстрирующей частный случай из найденных вариантов задания некоммутативного и ассоциативного умножения восьмимерных векторов. В результате обобщения экспериментальных результатов установлено, что в случае, когда б является квадратичным невычетом, рассмотренные варианты некоммутативных групп восьмимерных векторов содержат элементы, порядок которых со равен нетривиальным делителям числа (р4 — 1 )р.

Таблица 3. Некоммутативная ТУБВ, синтезированная методом

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

О е I ] к и V IV X

е е \ к и V V/ X

I 1 -е к V -и X

) -к е -1 V/ -X и -V

к к ) 1 е X V и

и и V -X ее Е-О -Ек

V V -и -X ш Е1 -ее -ек Е)

-X -и V Ч -ек -ее £1

X X -V -и вк «У -ее

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

Алгоритм ЭЦП на основе схемы Шнорра с использованием конечныж некммутативных групп

Исследование строения конечных некоммутативны групп векторов размерности т-4 показало, что для построения ЭЦП следует воспользоваться подгруппой большого простого порядка q, являющегося делителем числа р2-1. Для того чтобы такой делитель имелся в разложении р2-1, следует генерировать и использовать простые числа р со специальной структурой, а именно, такие что р + 1 = 2q, где q — простое число. Генерация ключа:

1. Сгенерировать простое число q размера 160 бит.

2. Проверить на простоту число р = 2q - 1. Если это число простое, то оно берется в качестве модуля для задания векторов. Если нет, то переходим к шагу 1.

3. Взять вектор G размерности 4 и порядка 6j(G) = q.

4. Случайным образом выбрать число х. |х|>128 бит.

5. Вычислить вектор Y = Gx. Число х является секретным ключом. Вектор Y— открытый ключ.

Подпись сообщения происходит аналогично схеме Шнорра:

1. Сгенерировать случайное число к.

2. Вычислить вектор R = Gk.

3. Объединить подписываемое сообщение М и вектор R в одно сообщение M*=M||R.

4. Вычислить значение хэш-функции от М*: E=Fh(M*) . Е - это первый элемент ЭЦП.

5. Вычислить второй элемент ЭЦП по формуле : S — к + хЕ mod q.

6. Подписью является пара чисел Е и S. Проверка подписи:

1. По открытому ключу /вычислить вектор R = Y~EGS

2. Вычислить значение е '= FH= (M\\R').

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

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

Оценка эффективности распараллеливания операций в векторном поле.

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

затрачиваемое на умножение двух векторов по модулю в двух случаях: без распараллеливания операций и с распараллеливанием. Для примера были взяты вектора размерности 4, 6 и 8, суммарный размер координат которых равнялся 1024 бита, а также отдельный случай 16-мерного вектора размера 512 бит. На рисунке 1 приведены диаграммы сравнения временных затрат на 100000 операций умножения.

Время, мс 800

700 600 500 400 300 200 100 0

III

В

и

а! —

....

111 81 .......т ш

□ Параллельное вычисление координат

Ш Последовательное вычисление координат

4 потока 6 потоков 8 потоков 16 потоков (1024 бит) (1024 бит) (1024 бит) (512 бит)

Рисунок 1. Оценка эффективности распараллеливания операций в конечных некоммутативных группах векторов

Как видно из вышеприведенных диаграмм, распараллеливание операций позволяет сократить время, затрачиваемое на умножение двух векторов в 2-2.5 раза. Отдельно стоит отметить высокую производительность в случае с размерностью вектора 16. Она обусловлена тем, что размер каждой координаты 16-мерного вектора длиной 512 бит равен 32 битам, что позволяет быстро перемножать их в регистрах процессора без использования дополнительных алгоритмов, в отличие от случая, когда размер координат больше размера регистров.

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

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

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

1) представление сообщения М как элемента некоммутативной группы векторов Г;

2) генерация разового случайного секретного ключа К, принадлежащего коммутативной подгруппе Г( с Г, и разового случайного секретного ключа (2, принадлежащего коммутативной подгруппе Гг с Г (задаются подгруппы Г) и Гг такие, что К ° <2 Ф <2 ° К);

3) выполнение шифрования сообщения как вычисления по формуле С = К°М°(?.

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

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

1. Предложен способ нахождения элементов большого простого порядка в конечных некоммутативных группах векторов размерности 4 над кольцами целых чисел ¿Гр<1

2. Предложен способ нахождения элементов большого простого порядка в конечных некоммутативных группах векторов размерности 4 над полями многочленов СР(р5).

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

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

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

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

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

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

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

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

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

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

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

6. Головачев Д.А., Горячев A.A., Молдовяну П.А. Методические аспекты задания конечных колец над конечными векторными пространствами при изучении теоретических основ криптографии. // XVII Международная научно-методическая конференция «Современное образование: содержание, технологии, качество», 20 апреля 2011г. Материалы конференции. Том 2. С. 174-176

7. Горячев A.A., Кишмар Р.В., Хо Нгок Зуй Методические аспекты изложения протоколов с нулевыми знаниями: толкование термина «нулевое разглашение» в дисциплине «Криптографические протоколы» // XVII Международная научно-методическая конференция «Современное

18

образование: содержание, технологии, качество», 20 апреля 2011г. Материалы конференции. Том 2. С. 238-240

8. Васильев И.Н., Горячев A.A., Кишмар Р.В. Протокол аутентификации на основе двух трудных задач. // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 24-25 ноября 2011, - СПб.: ВАС, 2011, С. 61-65

9. Аль-Рахми Р.Я., Горячев A.A., Латышев Д.М. Синтез хэш-функций на основе операций над конечными некоммутативными группами // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 25-56 ноября 2010 года, Санкт-Петербург. СПб.: ВАС, 2010. С. 57-62

10. Горячев A.A. Построение и анализ криптосхем над конечными некоммутативными группами векторов. // Вторая межвузовская научная конференция по проблемам безопасности СПИСОК-2011, 28-29 апреля 2011г. Материалы конференции. СПб.: ВВМ, 2011. С. 448-450

П.Горячев A.A. Методы увеличения быстродействия криптосхем, основанных на скрытой задаче дискретного логарифмирования. // Сборник тезисов докладов конгресса молодых ученых, Выпуск 1. - Спб: НИУ ИТМО, 2012, С. 185

Подписано в печать 21.03.2013 Формат 60x90/16 Бумага офсетная. Усл. печ. л. 1,25 Тираж 100 экз. Заказ 138

Отпечатано в типографии «Адмирал» 199178, Санкт-Петербург, В.О., 7-я линия, д. 84 А

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

Кафедра «Безопасные информационные технологии»

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

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

МЕТОД ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ КРИПТОСХЕМ, ОСНОВАННЫХ НА КОНЕЧНЫХ НЕКОММУТАТИВНЫХ ГРУППАХ

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

СМ

со

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

СО со Ю

см

со °

кандидата технических наук

Т— CD

О ^ Научный руководитель

см ^

v 7 о

доктор технических наук,

о

профессор Молдовян A.A.

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

»

Содержание

Введение...........................................................................................................................4

Глава 1. Проблемы защиты и аутентификации информации в контексте информационной безопасности.....................................................................................9

1.1 Понятие криптографического протокола.........................................................10

1.2 Схема открытого распределения ключей.........................................................13

1.3 Электронная цифровая подпись........................................................................18

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

1.5 Примитивы двухключевых алгоритмов и протоколов....................................35

1.6 Задача скрытого дискретного логарифмирования в криптосхемах с открытым ключом.....................................................................................................37

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

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

2.1 Общий способ задания конечных колец векторов..........................................41

2.2 Конечные некоммутативные группы векторов над кольцом 2р<х.................44

2.3 Конечные некоммутативные группы векторов над полем СТ7^5).................50

Выводы к главе 2...........................................................................................................53

Глава 3. Методы задания конечных некоммутативных колец векторов большой размерности..................................................................................................................54

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

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

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

Глава 4. Повышение производительности криптосхем над конечными некоммутативными группами векторов.....................................................................67

4.1 Общая схема ЭЦП для некоммутативных групп векторов.............................67

4.2 Алгоритм ЭЦП для конечных некоммутативных групп векторов размерности 4............................................................................................................70

4.3 Алгоритм открытого шифрования....................................................................72

4.4 Протоколы с нулевым разглашением...............................................................76

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

4.4.2 Использование протокола с нулевым разглашением для синтеза схем ЭЦП ..............:......................................................................................................................80

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

4.6 Повышение производительности криптосхем методом распараллеливания операций.....................................................................................................................90

Заключение....................................................................................................................94

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

Список терминов...........................................................................................................97

Литература.....................................................................................................................99

Введение

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

В последнее время большой интерес представляют криптосхемы, основанные на новой трудной задаче, - задаче скрытого дискретного логарифмирования[1]. Она объединяет в себе задачу поиска сопрягающего элемента[2] и дискретного логарифмирования в скрытой коммутативной подгруппе[3], которые перспективны для построения протоколов открытого согласования секретного ключа и открытого шифрования повышенной криптостойкости. Однако, криптосхемы, построенные с использованием задачи скрытого дискретного логарифмирования, имеют серьезный недостаток - низкую производительность. Этот недостаток обусловлен необходимостью использования в таких криптосхемах некоммутативных групп, операции в которых требуют больших вычислительных затрат. В связи с этим проблема повышения производительности криптосхем, основанных на некоммутативных конечных группах является актуальной.

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

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

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

2. Вывод значения порядка конечных некоммутативных групп векторов размерности 4, построенных над полем многочленов;

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

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

5. Оценка производительности криптосхем с распараллеливанием операций.

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

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

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

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

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

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

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

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

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

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

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

3) Исследовано строение конечных некоммутативных групп векторов размерности 4.

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

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

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

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

Структура и объем диссертации.

Диссертационная работа изложена на 103 страницах и содержит 4 главы, 18 таблиц, 6 рисунков и список использованной литературы из 49 наименований.

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

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

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

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

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

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

Глава 1. Проблемы защиты и аутентификации информации в контексте

информационной безопасности.

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

Основными задачами информационной безопасности является обеспечение 1) конфиденциальности информации 2) целостности информации 3) доступности информации[4,5].

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

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

Доступность - возможность получения информации субъектами, имеющими на нее право.

Однако существуют также и другие подзадачи информационной безопасности, среди которых выделяется задача аутентификации информации, связанная с проблемой подтверждения принадлежности информации субъекту, ее предоставляющему, а также подтверждение личности самого информационного субъекта. Аутентификация информации широко применяется для придания юридической силы электронным документам[6], в процедурах распознавания пользователей^], протоколах распределения ключей[8-9] и коммутативного шифрования.

1.1 Понятие криптографического протокола

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

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

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

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

- Непротиворечивость - результаты, полученные различными участниками протокола, не должны быть противоречивыми;

- Осведомленность и согласие участников протокола - каждый субъект заранее должен знать протокол и все шаги, которые он должен выполнить; все субъекты должны быть согласны играть свою роль.

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

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

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

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