Содержание к диссертации
Введение
1. Механизмы аутентификации в системах и средствах информационной безопасности 11
1.1 Аутентификация информации, объектов и субъектов 11
1.2. Аутентификация информации с помощью электронной цифровой подписи 14
1.3 Основные схемы построения электронной цифровой подписи 18
1.3.1 Схемы цифровой подписи, основанные на задаче факторизации 18
1.3.2 Задача извлечения квадратных корней по составному модулю 22
1.3.3 Схемы цифровой подписи, основанные на задаче дискретного логарифмирования в конечном поле 24
1.3.4 Схемы цифровой подписи, основанные на задаче дискретного логарифмирования на эллиптических кривых 27
1.4 Протоколы электронной цифровой подписи 32
1.4.1 Понятие криптографического протокола 32
1.4.2 Виды протоколов электронной подписи 34
1.5 Постановка задачи 36
2. Построение схем электронной цифровой подписи, основанных на двух трудных задачах 39
2.1 Обоснование концепции 39
2.2 Методы построения схем цифровой подписи, основанных на двух трудных задачах 40
2.2.1 Механическое комбинирование схем цифровой подписи 40
2.2.2 Модификация известных схем цифровой подписи 42
2.2.3 Построение схем цифровой подписи на базе нового механизма формирования элементов подписи 44
2.3 Схемы цифровой подписи, построенные путем модификации существующих схем цифровой подписи 47
2.3.1 Комбинирование схем Рабина и Эль-Гамаля 47
2.3.2 Класс доказуемо стойких схем ЭЦП (обобщенная схема Рабина) 52
2.3.3 Комбинирование алгоритмов обобщенной схемы Рабина и Эль-Гамаля. 57
2.4. Схемы цифровой подписи, построенные на базе нового механизма формирования подписи 60
2.4.1 Комбинирование задач дискретного логарифмирования и факторизации. 61
2.4.2 Комбинирование задачи дискретного логарифмирования в конечном поле и задачи извлечения квадратного корня по составному модулю 66
2.4.3 Комбинирование задач дискретного логарифмирования на ЭК и дискретного логарифмирования в простом конечном поле 70
2.4.4 Создание схем ЭЦП на основе нескольких сложных задач 76
Выводы ко второй главе 80
3. Протоколы коллективной подписи, основанные на двух трудных задачах 82
3.1. Описание протокола коллективной цифровой подписи 82
3.2. Схемы протокола коллективной подписи, взлом которого требует решения двух трудных задач одновременно 86
3.2.1. Протокол, основанный на сложности дискретного логарифмирования в конечном поле и на эллиптических кривых 86
3.2.2. Протокол, основанный на сложности дискретного логарифмирования на эллиптических кривых двух типов 89
3.2.3. Реализация протокола коллективной подписи на основе стандартов ЭЦП ГОСТ Р 34.10-94 и ГОСТ Р 34.10-2001 92
3.3 Описание протокола композиционной цифровой подписи 95
3.4. Схема композиционной цифровой подписи, основанная на сложности дискретного логарифмирования в конечном поле и на эллиптических кривых .. 98
Выводы к третьей главе: 101
4. Новые алгебраические структуры для построения алгоритмов ЭЦП 103
4.1 Конечные группы невырожденных матриц 104
4.1.1 Описание конечной группы невырожденных матриц 104
4.1.2 Реализация алгоритмов цифровой подписи на основе конечных групп матриц 108
4.2 Конечные векторные пространства 111
4.2.1 Построение векторных пространств на простым конечным полем 111
4.2.2 Алгоритм построения распределений коэффициентов растяжения 113
4.2.3 Построение конечных векторных полей 118
4.2.4 Алгоритмы цифровой подписи над конечными расширенными полями, заданными в векторной форме 121
4.3. Построение схем подписи, основанных на задаче дискретного логарифмирования в конечной группе невырожденных матриц и конечной группе векторов 123
4.4. Специфика выбора простых чисел для построения алгоритмов ЭЦП, основанных на новых примитивах 125
4.4.1. Выбор простых параметров для схем ЭЦП, построенных на конечных группах матриц 125
4.4.2 Специфика выбора простых чисел для формирования конечных векторных полей над простым полем 131
Выводы к четвертой главе 134
Заключение 136
Литература 143
Приложение А 153
- Схемы цифровой подписи, основанные на задаче дискретного логарифмирования в конечном поле
- Построение схем цифровой подписи на базе нового механизма формирования элементов подписи
- Схема композиционной цифровой подписи, основанная на сложности дискретного логарифмирования в конечном поле и на эллиптических кривых
- Алгоритмы цифровой подписи над конечными расширенными полями, заданными в векторной форме
Введение к работе
Актуальность темы диссертации. Проблема обеспечения защиты
информационных технологий включает следующие три задачи: 1) обеспечение
доступности информационных ресурсов, 2) обеспечение аутентичности
информации и 3) обеспечение конфиденциальности информационных ресурсов.
Криптографические механизмы эффективно применяются для
непосредственного решения второй и третьей задачи и косвенно - для решения первой. Важным моментом для практического применения криптографических алгоритмов является их безопасность, которая во многом определяется некоторой вычислительно трудной задачей, лежащей в основе криптографического алгоритма. Эта задача имеет решение, однако его нахождение требует больших вычислительных ресурсов и временных затрат. Безопасность криптографических алгоритмов связана со сложностью решения трудных задач, лежащих в их основе, и вероятностью нахождения ранее неизвестных эффективных методов их решения. Таким образом, понятие безопасности включает два аспекта - трудоемкость взлома алгоритма на основе использования лучшего известного метода, например, лучшего известного метода решения трудной задачи и вероятность появления ранее неизвестных эффективных, например, новых способов решения этой задачи. Первое значение должно быть достаточно большим, а второе — достаточно малым.
Одним из способов повышения уровня безопасности, обеспечиваемой криптографическими механизмами, является построение криптографических алгоритмов, взлом которых требует одновременного решения двух независимых вычислительно трудных задач. В этом случае вероятность появления эффективных способов взлома криптографических алгоритмов резко уменьшается, что вносит существенный вклад в их безопасность. Вопросу построения таких криптографических алгоритмов и протоколов в настоящее время уделено крайне мало внимания. В связи с этим тема диссертационной работы, посвященная построению криптографических схем и протоколов, основанных на двух трудных задачах, является своевременной и актуальной.
Цель работы и задачи исследования. Основной целью диссертационного исследования является разработка технических решений по построению схем криптографической аутентификации информации, обеспечивающих повышение безопасности за счет снижения вероятности появления новых видов атак.
Задачей диссертационного исследования является разработка механизмов аутентификации, взлом которых требует решения двух вычислительно трудных задач одновременно, что обеспечивает повышение уровня безопасности систем электронного документооборота, в которых они применяются.
Для достижения поставленной задачи в диссертационной работе были поставлены и решены следующие частные задачи:
1) разработка методики построения схем электронной цифровой подписи (ЭЦП), основанных на двух и более вычислительно трудных задачах;
-
построение схем ЭЦП, основанных на двух и более вычислительно трудных задачах;
-
разработка протоколов коллективной и композиционной подписи, основанных на разработанных схемах ЭЦП;
-
поиск новых алгебраических структур для построения криптографических примитивов.
Методы исследования. В работе использованы аппарат и методы
математической статистики, теории вероятности, линейной алгебры, теории чисел, теории сложности и информационной безопасности.
Основные положения, выносимые на защиту:
-
Схемы ЭЦП, взлом которых требует решения двух вычислительно трудных задач разного типа.
-
Класс доказуемо стойких криптосистем на основе извлечения корней к-ой степени по составному модулю.
-
Протокол коллективной электронной цифровой подписи, основанный на схемах ЭЦП, взлом которых требует решения двух вычислительно трудных задач одновременно.
-
Протокол композиционной электронной цифровой подписи, основанный на схемах ЭЦП, взлом которых требует решения двух вычислительно трудных задач одновременно.
-
Обоснование конечных групп различного типа как криптографических примитивов для синтеза алгоритмов ЭЦП, основанных на двух трудных задачах.
Научная новизна. В результате выполнения диссертационной работы получены следующие новые научные результаты:
-
предложена методика построения алгоритмов ЭЦП, основанных на сложности решения двух вычислительно трудных задач;
-
разработаны механизмы аутентификации, обладающие более высоким уровнем безопасности за счет использования схем ЭЦП, основанных на сложности решения двух вычислительно трудных задач;
-
предложен класс доказуемо стойких криптосистем;
-
предложены новые алгебраические структуры для построения криптографических алгоритмов - конечные группы невырожденных матриц и конечные векторные пространства, которые расширяют варианты построения схем ЭЦП, основанных на двух трудных задачах.
Обоснованность и достоверность научных положений обеспечены анализом состояния исследований в данной области на сегодняшний день, подтверждаются математическими доказательствами предложенных схем аутентификации, результатами вычислительных экспериментов, а также апробацией основных теоретических достижений в печатных трудах и докладах на российских и международной конференциях.
Практическая ценность работы. Схемы электронной цифровой подписи, разработанные в данной диссертационной работе, направлены на
повышение безопасности механизмов аутентификации, реализованных на их основе. Это достигнуто за счет построения схем ЭЦП на двух вычислительно трудных задачах разного типа. Использование таких схем и разработанных на их основе протоколов коллективной ЭЦП и композиционной ЭЦП позволит расширить сферу применения ЭЦП, повысить безопасность обработки юридически значимых документов.
Применение в качестве примитивов алгоритмов ЭЦП конечных групп невырожденных матриц и конечных полей и групп векторов позволяет повысить вычислительную эффективность криптоалгоритмов, что особенно важно в случае построения схем ЭЦП на двух вычислительно трудных задачах.
Реализация и внедрение результатов работы. Результаты диссертационного исследования использованы при выполнении научно-исследовательских работ по грантам РФФИ (№ 08-07-90100-Мол_а, 2008-2009гг., № 08-07-00096-а, 2008-2010 гг), гранту Санкт-Петербурга для студентов, аспирантов молодых ученых и молодых кандидатов наук Правительства Санкт-Петербурга, 2008г (диплом № ПСП № 080157), составных частей ОКР «Автоматизированная система управления подготовки и пуска аппаратно-программного комплекса обработки и анализа телеметрической информации»
Полученные результаты диссертационного исследования были внедрены в учебный процесс на кафедре автоматизированных систем обработки информации и управления (АСОИУ) Санкт-Петербургского государственного электротехнического университета в учебный процесс для обеспечения лабораторного и курсового практикума по дисциплинам «Криптографические методы защиты информации» и «Теоретические основы криптографии» по специальности № 090102 («Компьютерная безопасность»).
Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на IV международной конференции Information Fusion & Geographic Information Systems 2009 (Санкт-Петербург, 2009), 62 научно-технической конференции профессорско-преподавательского состава университета СПбГЭТУ «ЛЭТИ» (Санкт-Петербург, 2009); XI Санкт-Петербургской международной конференции «Региональная информатика 2008» (Санкт-Петербург, 2008), IV межрегинальной конференции «Информационная безопасность регионов России 2007» (Санкт-Петербург, 2007), всеармейской научно практической конференции «Инновационная деятельность в вооруженных силах Российской Федерации» (Санкт-Петербург, 2008), научно практической конференции «Научно-технические проблемы в промышленности:», (Санкт-Петербург, 2008), всеармейской научно практической конференции «Инновационная деятельность в вооруженных силах Российской Федерации» (Санкт-Петербург, 2007).
Публикации. Основные результаты диссертации изложены в 22 публикациях, в том числе, в 7 статьях, б из которых опубликованы в ведущих рецензируемых журналах, входящих в перечень ВАК, в 1 докладе на международной конференции, 8 докладах и 8 тезисах докладов на
региональных и всероссийских конференциях. По результатам исследования получены 2 патента РФ и получено положительное решение по 1 патентной заявке.
Структура и объем работы. Диссертационная работа изложена на 162 машинописных страницах, включает 4 главы, 3 приложения, 15 рисунков, 17 таблиц и список литературы (96 наименований).
Схемы цифровой подписи, основанные на задаче дискретного логарифмирования в конечном поле
В современных системах аутентификация информации осуществляется при помощи электронной цифровой подписи (ЭЦП), относящейся механизмам двухключевой криптографии [16, 17]. При этом контролируется целостность сообщения на возможность его подмены или искажения. Инструмент ЭЦП используется также для придания электронной информации юридической силы.
Решение проблемы придания юридической силы информации требует применения механизмов, которые обеспечивают неотказуемость от факта создания сообщений, и включает два важнейших аспекта [18, 19]. Первый аспект является алгоритмическим и относится к разработке и применению таких методов аутентификации информации, с помощью которых автор сообщения может выработать дополнительный блок данных сравнительно малого размера, по которому будет осуществлена процедура аутентификации информации. Указанная дополнительная информация играет роль электронной цифровой подписи (ЭЦП), с использованием которой выполняется аутентификация информации (проверка подлинности ЭЦП). Чтобы процедура проверки ЭЦП была корректной, она должна включать некоторые открытые параметры {открытый ключ), зависящие от личного ключа автора. Второй аспект данной проблемы связан с обеспечением правовой поддержки ЭЦП, т.к. решение алгоритмической проблемы создания систем ЭЦП хоть и создает фундамент, но не является достаточным для придания юридической силы электронным сообщениям. Следовательно, необходимо принятие статей в правовых законах, в которых была бы установлена ответственность за использование ЭЦП [20]. Стойкие алгоритмы ЭЦП и соответствующие нормативные правовые акты образуют системы ЭЦП, обеспечивающие придание юридической силы электронным сообщениям.
Электронная цифровая подпись (ЭЦП) является одним из основных направлений современной криптографии, относится к механизмам защиты целостности и аутентичности данных. В основе ЭЦП лежат двухключевые криптографические алгоритмы, в которых предусмотрено использование двух ключей - открытого и закрытого (секретного) [16,21,22]. Идея использования открытого (т.е. известного всем пользователям криптосистемы и потенциальному злоумышленнику) ключа является фундаментальной, поэтому двухключевые криптосистемы часто называют открытыми шифрами, а выполняемые преобразования - открытым шифрованием. Впервые этот принцип был реализован в работе американских исследователей В. Диффи (W. Diffie), и М. Хеллмана (М. Hellman) в 1975 году [23]. Они ввели понятие однонаправленной функции с секретом, которое стало центральным для криптографии с открытым ключом.
Определение 1.1 Однонаправленная функция [13] Рассмотрим произвольные множества D и R, а также некоторую функцию f(x):D\- R Функция /называется однонаправленной, если ее значение fix) легко вычисляется для всех xeD, тогда как почти для всех yeR нахождение такого xeD, удовлетворяющих условию у—fix) является трудно вычислимым.
Двухключевые криптоалгоритмы позволяют обеспечить строгую доказательность факта составления того или иного сообщения конкретными абонентами (пользователями) криптосистемы. Доказательство основано на том, что двухключевые криптосистемы функционируют в условиях, когда стороны не доверяют друг другу и не сообщают свой секретный ключ какому-либо второму субъекту. Факт использования секретного ключа при выработке подписи к тому или иному электронному документу проверяется с использованием отрытого ключа. При этом знание открытого ключа не дает возможности выработать правильную цифровую подпись. Таким образом, ответственность за сохранность секретного ключа и соблюдение правил его использования лежит на самом владельце этого ключа. Секретный ключ позволяет сформировать подпись к сообщению со специфической внутренней структурой, связанной с подписываемым документом и открытым ключом. Тот факт, что подпись имеет определенную структуру, зависимую от секретного ключа, проверяется с помощью открытого ключа. Эта процедура называется проверкой электронной цифровой подписи. Вероятность того, что некоторое сообщение, составленное нарушителем, может быть принято за сообщение, подписанное каким-либо абонентом системы ЭЦП, является чрезвычайно низкой, порядка 10 30 [21, 24].
Таким образом, процедура проверки ЭЦП с помощью открытого ключа позволяет с высокой вероятностью удостовериться в том, что полученное сообщение было составлено владельцем секретного ключа. Кроме того, поскольку только владелец секретного ключа может создать правильную цифровую подпись к сообщению, которую может проверить кто угодно, легко решить вопрос об авторстве сообщения. Следовательно, применение ЭЦП дает возможность предотвратить отказ от авторства, т.е. отрицание своей связи с посланным сообщением. Неотказуемость от авторства является важным требованием безопасности в электронной коммерции [21, 25].
Общедоступный открытый ключ формируется на основе секретного ключа, или оба ключа вырабатываются одновременно по специальным процедурам, при чем определение секретного ключа по открытому ключу является вычислительно сложной математической задачей.
Построение схем цифровой подписи на базе нового механизма формирования элементов подписи
В криптографии часто используются термины «алгоритм» и «протокол». Интуитивно смысл этих терминов понятен, т.к. они широко используются в других научно-технических областях знаний. Под алгоритмом понимается набор команд, действий, инструкций и вычислений, которые необходимо выполнить для того, чтобы получить из исходных данных тот или иной результат. При этом в процессе выполнения алгоритма могут возникать новые данные как результат преобразования исходных данных, либо как результат случайного выбора на каком- либо шаге алгоритма, либо как результат выполнения (вычислителем) измерений параметров окружения (внешних объектов). Алгоритм выполняется некоторым субъектом (вычислителем) [21, 44]. Под протоколом понимается совокупность действий (инструкций, команд, вычислений, алгоритмов), выполняемых в заданной последовательности двумя и более субъектами с целью достижения определенного результата. Корректность выполнения протокола зависит от действий каждого субъекта (пользователя, абонемента) криптосистемы. Для того, чтобы протокол приводил к желаемой цели, необходимо выполнение следующих условий [45]: 1) корректность протокола - совокупность действий, предусмотренных протоколом, которая должна обеспечить получение требуемого результата при всех возможных ситуациях; 2) полнота и однозначность определения - протокол должен специфицировать действия каждого участника протокола для всех возможных ситуаций; 3) непротиворечивость - результаты, полученные разными участниками протокола, не должны быть противоречивыми; 4) осведомленность и согласие участников протокола - каждый субъект заранее должен знать протокол и все шаги, которые он должен выполнить; все субъекты должны быть согласны играть свою роль. В криптографических протоколах используются криптографические преобразования данных. С помощью криптографических протоколов решается широкий круг задач, который не ограничивается обеспечением секретности передаваемой информации. Они применяются для организации одновременного подписания документов, проведения электронной жеребьевки, идентификации участников телеконференции и т.д. [4, 13, 44, 45]
Следует отметить, что при разработке криптографических протоколов следует учитывать действия потенциальных нарушителей (в практических приложениях это идеальное понятие вполне материально) и стремиться обеспечить выполнение протокола независимо от действий нарушителя.
Роль систем ЭЦП в автоматизированных системах управления, используемых в финансовой и экономической деятельности, сложно переоценить [5,46]. Управление в финансово-экономической сфере сопровождается передачей электронных сообщений для оперативного реагирования на складывающиеся ситуации на биржах или при ведении сложных переговоров. Не менее важным является сопровождение цифровыми подписями приказов и распоряжений в армии и других силовых структурах. Поэтому и в этой области управление процессами также целесообразно сопровождать распоряжения цифровыми подписями. Такие потребности и их актуальность создают предпосылки для создания криптографической поддержки процесса автоматизированного управления. Вариант «один документ - одна подпись» является наиболее широко востребованным, однако не единственным, требуемым для практики. Вопросы передачи документов и распорядительных сообщений от имени некоторого коллегиального органа или от имени совокупности субъектов руководящего звена делают актуальным вопрос разработки систем различных видов ЭЦП: групповой, коллективной, мультиподписи, а хождение электронных денег и разработка систем тайного электронного голосования - слепой подписи .
Протокол мулътиподписи был разработан для тех случаев, когда требуется подписать договор несколькими лицами, при чем следует учесть порядок подписывания документа. Такая потребность может возникнуть, когда главе секции компании необходимо подписать документ только после того, как свою подпись поставили сотрудники компании [48, 49, 50].
Понятие групповой подписи впервые было предложено Д. Чаумом (D Chaum) и Е. ван Хейстом (Е. van Heyst) [51,52]. Групповая подпись позволяет участникам некоторой группы подписать сообщения от лица данной группы таким образом, чтобы каждый мог проверить правильность подписи, но при этом никто не мог определить, кто именно из участников группы ее создал. Протокол групповой подписи подразумевает наличие третьего лица, так называемого менеджера группы, который в спорных случаях, может вскрыть личность подписывающего. В зависимости от реализации протокола [53, 54] менеджером группы может быть как один участник, так и несколько участников группы. Протокол групповой подписи может быть полезен компаниям, которым необходимо сформировать единого корпоративного представителя. Благодаря этому протоколу, сотрудники компании могут подписывать контракты с клиентами таким образом, что клиент не знает, кто конкретно подписал документ. Однако, если в дальнейшем возникает проблема с каким-нибудь конкретным контрактом, компания легко может определить ответственное лицо.
Схема композиционной цифровой подписи, основанная на сложности дискретного логарифмирования в конечном поле и на эллиптических кривых
Среди многообразия различных типов протоколов электронной цифровой подписи отдельный интерес представляют протоколы, известные как схемы коллективной подписи [73, 74]. Они являются востребованными для ряда приложений благодаря тому, что позволяют сократить объем избыточной информации, необходимой для аутентификации информации и электронных документов, исходящих от коллектива подписывающих. Кроме того, они представляют собой эффективный инструмент для решения проблемы одновременного подписания контракта и пакета контрактов [75].
Практическая потребность в протоколах коллективной подписи возникает при создании крупных проектов, над которыми работает множество специалистов разного профиля. Каждый из них готовит какую-то отдельную часть проекта, все эти части и/или некоторые их совокупности желательно подписать. Кроме того, на практике возникает ситуация, когда объем ЭЦП при их обычном формировании становится достаточно большим и в результате усложняется процедура проверки подписей. Эта проблема решается с помощью протоколов композиционной подписи [75,76], представляющей собой модификацию коллективной подписи. Единая интегрированная композиционная подпись содержит информацию, которая позволяет по достаточно простой процедуре удостовериться в наличии подписей указанной группы подписывающих под заданной совокупностью частей электронного документа.
Индивидуальные подписи относятся к индивидуальным частям электронного документа, а некоторые пользователи ставят свои подписи под несколькими частями. При этом коллективная подпись обладает таким свойством как внутренняя целостность подписи, т.е. по коллективной подписи практически невозможно вычислить какую-либо другую подпись. Она едина и неделима: либо все подписали определенные документы в общем проекте, либо вообще никто ничего не подписывал. Ее размер равен размеру одной обычной ЭЦП. Сложности проверки коллективной и обычно подписи равны. Сложность процедур, выполняемых участником процедуры формирования коллективной подписи, такая же как и в случае формирования обычной ЭЦП.
Рассмотрим, как функционирует протокол коллективной электронной цифровой подписи (КЭЦП), предложенный в работе [57]. В нем вводится понятие коллективного открытого ключа некоторой произвольно задаваемой совокупности т пользователей, которое является центральным. Такой ключ представляет собой функцию свертки открытых ключей пользователей Yh Y2,...Ym : Y=fiYb Y2,..., Ym). Общая схема формирования КЭЦП представлена на рисунке 3.1.
В соответствии с протоколом КЭЦП каждый z -й пользователь генерирует разовый секретный ключ ки с помощью которого он затем вычисляет открытый параметр рандомизизации rh выполняющий роль его разового индивидуального открытого ключа. Сформированные параметры г,-рассылаются между участниками протокола, после чего они объединяются в коллективный разовый открытый ключ R, который является общим параметром рандомизации (свертка всех значений rt, і = 1,2,..., т) и используется при формировании коллективной подписи к электронному документу М. Как и в других протоколах, документ М представляется значением хэш-функции Н = F M) для усиления стойкости протокола, где FH - функция хэширования. Значение R является первым элементом коллективной подписи. Вторым элементом коллективной подписи является число S, представляющее собой свертку долей Si, і = 1, 2,..., т, генерируемых каждым подписывающим отдельно. Значение S, зависит от предварительно вычисленного параметра R, секретного ключа пользователя х,- и значения Н. Доли Si также рассылается между пользователями, поэтому любой из участников протокола может вычислить свертку S. Поскольку доли г,- и Заявляются общедоступными, рекомендуется среди участников протокола выбрать координатора группы, ответственного за генерацию общих частей подписи R и S. В протоколе можно предусмотреть процедуры аутентификации индивидуальных значений rt и St, однако этот момент не является критичным, поскольку любое нарушение протокола приведет к неправильному значению КЭЦП, которое не будет удовлетворять проверочному уравнению. При этом полученное значение КЭЦП не будет связано непосредственно с каким-либо пользователем или группой пользователей как в случае обычной цифровой подписи, т. е. будет получено некоторое «постороннее» значение. Это означает, что компрометация секретных ключей не имеет место, а пользователя, который осуществил неправильные действия, легко установить по его индивидуальным значениям г І и St.
Общая схема процедуры проверки КЭЦП представлена на рисунке 3.2. Для проверки правильности коллективной подписи (R, S) к электронному документу М проверяющий должен извлечь из стандартного справочника открытых ключей индивидуальные открытые ключи у І участников протокола, которые создали эту подпись. Коллективный открытый ключ Y вычисляется как свертка всех индивидуальных открытых ключей подписывающих (например, в зависимости от реализации протокола в некоторых схемах КЭЦП свертка вычисляется как произведение индивидуальных открытых ключей по модулю большого простого числа, а в других алгоритмах - как сумма точек эллиптической кривой) [77]. Далее коллективный открытый ключ Y и КЭЦП (R, S) подставляются в обычное уравнение проверки подписи, которое при т=\ совпадает с уравнением проверки индивидуальной ЭЦП.
Алгоритмы цифровой подписи над конечными расширенными полями, заданными в векторной форме
Следовательно, максимальное значение простого порядка подгруппы векторного поля GF(pM) ограничено значением. Выполненные эксперименты показали, что найти такие значения простого р, для которых это значение q также является простым, достаточно легко. Примеры таких чисел приведены в таблице 4.13.
Как показали исследования, наиболее интересными для разработки алгоритмов ЭЦП, основанных на сложности задачи дискретного логарифмирования, являются случаи т є {3,5,7,11,13,17,19,23,27,31}. Выбор конкретного значения т связан с учетом требований к реализации алгоритмов ЭЦП и обеспечиваемому уровню стойкости. Отметим, что при микропрограммной реализации на основе 16-битовых микропроцессоров целесообразно выбирать простые поля с размером характеристики равном 16 бит и размерностью векторов гя = 11,13,17, что позволяет выбрать конкретные значения характеристики, при которой размер простого порядка подгруппы векторов, на основе которой строится алгоритм ЭЦП, равен от 160 до 256 бит. Для реализации на основе 32-битовых процессоров целесообразным является использование значений т = 7,11, обеспечивающих возможность получения подгрупп векторов простого порядка размером от 192 до 320 бит.
В таблице 4.14 приведены результаты эксперимента по выяснению доли простых чисел/? таких, что число q = (p m"1) +/?(m" 2)+...+р+\)/т является простым. Очевидно, что доля простых чисел, отвечающих поставленным условиям, достаточно велика, что позволяет нам говорить о том, что формирование конечных полей векторов размерности т, мультипликативная группа которых содержит простой делитель с размером \q\«(т - 1)\р\, является практически реализуемой задачей для всех практически важных значений размера числа/?.Формирование конечных полей векторов размерности т, заданных над расширенным полем GF(pd) связано с использованием простых чисел, удовлетворяющих следующему условию делимости m\pd — 1. В качестве поля GF(p) предполагается использовать многочлены степени d — 1, заданные над простым полем характеристики р. При этом операции над координатами векторов выполняются по модулю неприводимого многочлена степени d. Однако при задании векторных полей над многочленами имеются существенные ограничения на возможности получения подгрупп большого простого порядка, поскольку в этом случае можно варьировать только параметрами d и р, каждый из которых должен быть простым, причем наиболее интересные для практики значения размера \р\ лежат в пределах от 1 до 64 бит. Порядок мультипликативной группы векторного поля, заданного над многочленами равен.
К этому случаю можно применить результаты исследования выражения, содержащего в первой скобки формулы (4.4). Таким образом, число значениях d и т = d или при т = ct при d = 2, где к - натуральное число. Примеры чисел, удовлетворяющих заданным условиям, приведены в таблицах 4.9, 4.10. Выводы к четвертой главе 1. Обосновано, что конечные группы невырожденных матриц представляют интерес в качестве примитива алгоритмов ЭЦП и могут быть использованы в протоколах ЭЦП, основанных на двух вычислительно трудных задач. 2. Доказано, что конечные группы векторов над конечными полями представляют интерес в качестве примитива алгоритмов ЭЦП и могут быть использованы в протоколах ЭЦП, основанных на двух вычислительно трудных задачах. За счет возможности распараллеливания операции умножения векторов может быть повышена производительность таких протоколов. 3. Разработан алгоритм построения т - 1 различных таблиц умножения базисных векторов, содержащих одно значение растягивающего коэффициента, которые обеспечивают коммутативность и ассоциативность операции умножения векторов для случая произвольной простой размерности т. 4. Получена формула для оценки максимально возможного размера простого делителя группы векторов простой размерности. 5. Экспериментально доказано, что доля простых чисел для задания конечных групп векторов, содержащих подгруппы с требуемым размером простого порядка, и конечных групп матриц достаточно велика, что благоприятствует применению таких групп в качестве примитивов алгоритмов ЭЦП. В рамках диссертационного исследования были достигнуты следующие результаты. 1. Разработана общая методика построения схем аутентификации на базе ЭЦП, взлом которых требует решения двух вычислительно трудных задач одновременно. Использование общего рандомизирующего параметра и двух подгоночных параметров позволяет комбинировать две и более различные схемы ЭЦП в одной, благодаря чему достигается повышение безопасности за счет снижения вероятности появления новых типов атак. 2. В рамках предложенного подхода был разработан ряд схем, стойкость которых зависит от сложности решения двух трудных задач разного типа: схема ЭЦП, основанная на задаче извлечения квадратного корня по составному модулю и задаче дискретного логарифмирования в конечном простом поле; схема ЭЦП, основанная на задаче дискретного логарифмирования в конечном простом поле и задаче дискретного логарифмирования на эллиптических кривых.
