Содержание к диссертации
Введение
1 Особенности аутентификации в распределенных системах и принцип кластеризации 14
1.1 Типы аутентификации в распределенных системах 14
1.2 Групповая подпись 17
1.3 Малоресурсные приложения 22
1.4 Эллиптические кривые
1.4.1 Группа точек эллиптической кривой и задача дискретного логарифмирования 24
1.4.2 Билинейные отображения эллиптических кривых 31
1.4.3 Изогении эллиптических кривых 41
Выводы 45
2 Иерархия математических задач и принцип сложностной однородности
2.1 Исчислительный подход к анализу безопасности 47
2.1.1 Упорядоченность множеств возможностей нарушителя и безопасных систем 48
2.1.2 Множества возможностей нарушителя и иерархия математических задач
2.2 Принцип сложностной однородности 56
2.3 Сравнение протоколов аутентификации, основанных на задаче дискретного логарифмирования на эллиптической кривой 58
2.3.1 Протокол цифровой подписи ГОСТ Р 34.10–2012 59
2.3.2 Протокол шифрования с открытым ключом
на эллиптических кривых 63
2.4 Способы снижения сложностной неоднородности протоколов на эллиптических кривых 65
2.4.1 Оптимальный генератор случайных чисел для схемы подписи на эллиптической кривой 65
2.4.2 Способы построения хэш-функций 71
2.4.3 Дополнительные способы усиления протокола подписи 74
Выводы 78
3 Разработка протоколов аутентификации на отображениях эллиптических кривых 79
3.1 Протокол подписи на билинейных отображениях 79
3.2 Динамическая групповая подпись на билинейных отображениях
3.2.1 Классификация схем групповой подписи 84
3.2.2 Параметры и предположения в схеме BBS 87
3.2.3 Протокол с нулевым разглашением доказательства знания решения задачи SDH 90
3.2.4 Групповая подпись BBS, основанная на доказательстве знания пары SDH 91
3.2.5 Динамическая схема ED-BBS 95
3.2.6 Схема EDR-BBS с отзывом права подписи 104
3.3 Протоколы на изогенных эллиптических кривых 110
3.3.1 Протокол короткой подписи 112
3.3.2 Протоколы групповой подписи 112
3.3.3 Протокол упорядоченной подписи 116
Выводы 118
4 Генерация параметров протоколов аутентификации и вычислительные алгоритмы 120
4.1 Генерация эллиптических кривых над конечными полями 120
4.1.1 Эллиптические кривые над простыми полями 122
4.1.2 Примеры эллиптических кривых 140
4.1.3 Эллиптические кривые над расширенными полями 153
4.2 Генерация эллиптических кривых для протоколов на билинейных отображениях 167
4.2.1 Метод Кокса–Пинча 168
4.2.2 Методы, дающие круговые семейства
4.3 Генерация эллиптических кривых для протоколов на изогениях 174
4.4 Вычислительные алгоритмы на эллиптических кривых
4.4.1 Арифметика эллиптических кривых над простым полем и комплексное умножение 178
4.4.2 Использование полей псевдомерсенновых характеристик
4.5 Параллельные вычислительные алгоритмы 200
4.6 Использование аутсорс-технологий для реализации протоколов на билинейных отображениях 2
4.6.1 Модель аутсорсинга 204
4.6.2 Аутсорс-алгоритмы вычисления билинейного отображения 206
4.6.3 Аутсорс-реализация трехстороннего протокола установления ключа 210
Выводы 212
5 Применение протоколов групповой аутентификации 214
5.1 Применение групповой подписи для аутентификации
субъектов в распределенных вычислительных сетях типа «грид» 214
5.2 Применение групповой подписи для аутентификации субъектов в Интернете вещей 221
5.3 Использование в учебном процессе 225
Выводы 227
Заключение 228
Список использованных источников 231
- Малоресурсные приложения
- Принцип сложностной однородности
- Динамическая групповая подпись на билинейных отображениях
- Примеры эллиптических кривых
Введение к работе
Актуальность темы исследования. В современных условиях четвертой промышленной революции практически любая технология, влияющая на ее формирование, строится на распределенных системах, примерами которых являются глобальные промышленные сети, геоинформационные системы, киберфизические системы, сети межмашинного взаимодействия, системы автоматической идентификации и сбора данных, грид-системы, крупномасштабные сети электронных потребительских устройств (Интернет вещей) и т.д. Построение протоколов аутентификации, которые во многом определяют эффективность обеспечения защищенности таких систем, з а т р у д н е н о ввиду их многообразия и отсутствия единой концепции разработки. Это определяет научную проблему создания общих положений разработки протоколов аутентификации в распределенных системах. Основными факторами, усложняющими решение данной проблемы, являются: большое число участников взаимодействия, различные вычислительные возможности участников, иногда существенно ограниченные, постоянное изменение числа и состава участников, возможное перемещение участников во время обмена данными, большое число разнородных механизмов защиты.
Перечисленные особенности предопределяют ряд дополнительных задач, возникающих при организации протоколов аутентификации, многие из которых требуют специальных технологических решений. В настоящей работе предпринята попытка создать единую системную концепцию обеспечения безопасности межсетевого взаимодействия в системах с дифференцированными вычислительными ресурсами, что определяет актуальность настоящего исследования. Основу подхода составляют принципы, которые позволяют выделить участников распределенной системы, обладающих схожими правами и выполняющих однотипные функции, минимизировать число разнородных математических задач, лежащих в основе безопасности защитных механизмов, и сохранить защитные свойства в условиях ограниченных вычислительных ресурсов на примере систем, построенных на эллиптических кривых и их отображениях.
Степень разработанности. Разработке теории эллиптических
кривых, а также вопросам их применения в системах аутентификации
посвящены труды таких отечественных и зарубежных ученых, как
О.Н. Василенко, А . Г. Ростовцев, И.А. Семаев, С.А. Степанов,
А . Г. Столбунов, И .Р. Шафаревич, М. Белларе, К. Бойен, Д. Бонэ,
С. Га л бр а й т, Н. Коблиц, Р. Лерсье, А. Менезес, В. Миллер, Ф. Моран, Дж. Сильверман, Д. Чаум, Е. ван Хейст, Х. Шахам. В данной работе, помимо обобщения и развития отдельных положений этих исследований, предлагаются новые подходы к построению протоколов аутентификации на эллиптических кривых в современных распределенных системах с различными, в том числе ограниченными, вычислительными ресурсами, направленные на совершенствование технологий обеспечения безопасности.
Объектом исследования диссертационной работы являются распределенные системы с изменяемым числом участников, обладающих различными вычислительными возможностями.
Предметом исследования диссертационной работы являются процессы аутентификации в распределенных системах, учитывающие состав участников и реализуемые с использованием различных, в том числе малоресурсных, вычислительных устройств.
Цели и задачи. Целью диссертационного исследования является обеспечение защищенного взаимодействия в разнородных распределенных системах путем создания единой концепции построения протоколов аутентификации на эллиптических кривых, реализующей принципы сложностной однородности, кластеризации и алгоритмической оптимизации.
Для достижения поставленной цели в работе решались следующие задачи.
-
Разработка единой концепции построения протоколов аутентификации в системах с дифференцированными вычислительными ресурсами и переменным числом участников, включающей принципы сложностной однородности, кластеризации и алгоритмической оптимизации.
-
Формулирование принципа сложностной однородности на основе исчислительного подхода к описанию множества возможностей нарушителя, задание упорядоченности на множествах возможностей нарушителя и подсистем безопасности, разработка способов построения хэш-функций и генераторов случайных чисел на эллиптических кривых на основе указанного принципа.
-
Анализ специфики построения систем аутентификации в разнородных распределенных системах, классификация типов аутентификации в распределенных системах, анализ протоколов групповой аутентификации и разработка принципа кластеризации.
-
Разработка протоколов аутентификации на эллиптических кривых и их отображениях на основе принципов кластеризации и сложностной однородности.
-
Разработка алгоритмов генерации эллиптических кривых и вычислительных алгоритмов для реализации протоколов аутентификации с учетом ресурсных ограничений на основе принципа алгоритмической оптимизации.
-
Разработка рекомендаций по применению предложенных принципов, методов и алгоритмов для аутентификации в распределенных вычислительных сетях типа «грид», в самоорганизующихся сетях и крупномасштабных сетях электронных потребительских устройств (Интернет вещей), а также в учебном процессе.
Научная новизна результатов, изложенных в диссертации, определяется тем, что:
- впервые сформулированы принципы построения протоколов
аутентификации, обеспечивающие:
формирование минимально достаточного набора математических задач, обосновывающих безопасность;
кластеризацию участников взаимодействия;
выбор математических структур и вычислительных алгоритмов с учетом вычислительных возможностей участников;
впервые предложен исчислительный подход к анализу безопасности информационных систем, задающий упорядоченность на множестве возможностей нарушителя и подсистем безопасности;
разработаны протоколы аутентификации и вычислительные алгоритмы на эллиптических кривых над конечными полями, в том числе для малоресурсных приложений;
предложены решения по применению протоколов групповой подписи в сетях гибкой архитектуры на примере распределенных вычислительных сетей типа «грид», самоорганизующихся сетей и крупномасштабных сетей электронных потребительских устройств.
Теоретическая и практическая значимость работы. Теоретическая значимость диссертационного исследования заключается в разработке оригинального методологического подхода к построению на основе принципов сложностной однородности, кластеризации и алгоритмической оптимизации протоколов аутентификации в распределенных системах, дифференцированных по составу участников и вычислительным ресурсам.
Практическая значимость определяется возможностью создания протоколов аутентификации для повышения защищенности разнородных
распределенных систем, используемых в энергетических, транспортных, финансовых и оборонных отраслях. Предложенные методы и алгоритмы позволяют:
разрабатывать протоколы аутентификации для рассматриваемых систем;
оценивать и прогнозировать защищенность систем аутентификации;
генерировать параметры и разрабатывать алгоритмы для систем аутентификации с учетом вычислительных ресурсов и иерархии участников информационного взаимодействия;
обеспечивать учебный процесс по подготовке и переподготовке специалистов по защите информации.
Методология и методы исследования. Для решения поставленных задач использовались методы алгебры, теории чисел, алгебраической геометрии, математической логики, теории вероятностей, криптографии и теории сложности.
Положения, выносимые на за щ и т у.
-
Функционально целостная концепция построения протоколов аутентификации в системах с дифференцированными вычислительными ресурсами, основанная на принципах сложностной однородности, кластеризации и алгоритмической оптимизации.
-
Исчислительный подход к анализу безопасности, согласно которому формализована упорядоченность на множествах возможностей нарушителя и доказано существование минимальной системы аутентификации по отношению к заданному множеству возможностей нарушителя.
-
Протоколы групповой подписи, использующие билинейные отображения эллиптических кривых, в том числе на основе изогений эллиптических кривых.
-
Алгоритмы генерации эллиптических кривых и вычислительные алгоритмы для протоколов аутентификации на отображениях эллиптических кривых.
-
Архитектура системы групповой аутентификации в распределенной вычислительной сети типа «грид».
Степень достоверности и апробация результатов. Достоверность результатов, полученных в диссертационной работе, подтверждается их практическим применением при выполнении научно-исследовательских работ в рамках федеральной целевой программы «Развитие единой образовательной информационной среды (2001–2005 годы)» по разделам
«Развитие информационных технологий сферы образования» (2002) и «Создание интегрированной автоматизированной информационной системы сферы образования для решения задач управления образовательными учреждениями и отраслью. Информационная поддержка государственного экзамена» (2003); при выполнении научно-исследовательских работ «Быстрые вычислительные алгоритмы для стандарта электронной цифровой подписи и их программная реализация» (2004), «Алгоритмы укороченной цифровой подписи на основе билинейного отображения эллиптической кривой» (2005), «Быстрые вычислительные алгоритмы для укороченной цифровой подписи» (2006– 2007); при выполнении научно-исследовательской работы «Разработка технологии высокопроизводительной обработки и визуализации больших массивов данных в крупномасштабных сетях электронных потребительских устройств (Internet of Things)» в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014–2020 годы» (2014–2016); в рамках государственного задания образовательным организациям высшего образования, подведомственным Минобрнауки России, в сфере научной деятельности (Государственное задание № 2.1778.2014/К от 15.07.2014 г. Шифр заявки 1778).
Основные результаты и положения работы и отдельные ее вопросы докладывались и обсуждались на следующих научных семинарах и конференциях: Санкт-Петербургском семинаре «Информационная безопасность» (Санкт-Петербург, 1994, 1995), Республиканской научно-технической конференции «Теория и практика обеспечения безопасности информационных технологий» (Санкт-Петербург, 1994), Третьей межведомственной научно-технической конференции (Пушкин, 1997), Межрегиональной конференции «Информационная безопасность регионов России, ИБРР» (1999, 2005, 2007, 2009, 2011, 2013), Санкт-Петербургской международной конференции «Региональная информатика» (Санкт-Петербург, 2002, 2008, 2010), семинаре Eighth International Workshop on Algebraic and Combinatorial Coding Theory Proceedings (Tsarskoe Selo, 2002), международной конференции «Mathematical Methods, Models and Architectures for Computer Network Security, MMM-ACNS» (Saint-Petersburg, 2003), конференции «Математика и безопасность информационных технологий, МаБИТ» (Москва, 2003), конференции Fourth Wo r l d Conference «Information Security Education» (Moscow, 2005), межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада «Технологии Microsoft в теории и практике программирования» (2005), конференции «Проведение научных
исследований в области обработки, хранения, передачи и защиты информации» (Москва, 2011), Всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (2003, 2004, 2007–2011, 2015), Всероссийской межвузовской научно-технической конференции «Неделя науки СПбГПУ» (2005, 2007, 2009– 2015), XI международной научно-практической конференции «Информационная безопасность» (Таганрог, 2010), международной научно-практической конференции «РусКрипто» (Москва, 2015, 2016), научно-технической конференции «Методы и технические средства обеспечения безопасности информации» (Санкт-Петербург, 1996–2016).
Публикации. По материалам диссертации опубликовано 125 работ (из них 18 статей в изданиях, рекомендованных ВАК РФ), в том числе 7 монографий и разделов в монографиях.
Структура и объем. Диссертация состоит из введения, пяти глав, заключения, списка использованных источников из 325 наименований и двух приложений. Общий объем работы – 272 страницы.
Малоресурсные приложения
В некоторых схемах групповой подписи в качестве менеджеров GM, IM и OM (либо в качестве GM и IM) может выступать один субъект, либо менеджеры могут быть вовсе исключены из схемы, при этом формирование группы происходит по договоренности пользователей, а проверка и раскрытие подписи производятся посредством диалога между проверяющей и доказывающей сторонами. В ряде схем роль менеджеров исполняют обычные члены группы.
При наличии в схеме координатора GM предполагается, что он является доверенной стороной и взаимодействует с остальными субъектами только при инициализации группы для передачи им их закрытых ключей по защищенным каналам.
Некоторые схемы накладывают ограничения на проверяющих, предоставляя доступ к открытым ключам только авторизованным пользователям, что может быть реализовано на основе неоспоримой подписи.
Обычно схема групповой подписи состоит из следующих процедур [37]: – формирование группы (Setup) — генерация параметров групповой подписи и основных ключей группы: личного закрытого ключа ik (issuing key) выпускающего менеджера IM (если не используется алгоритм Join; в этом случае менеджеры GM и IM представлены одним субъектом), открытого ключа gpk (group public key) группы, ключа ok (opening key) раскрывающего менеджера OM и личных ключей gsk (group secret key) членов группы; – добавление участника в группу (Join) — протокол между выпускающим менеджером IM и субъектом, желающим вступить в группу. В ходе выполнения протокола происходит формирование и доставка личного ключа будущего члена группы. При этом исключается возможность вычисления этого ключа менеджером группы; – формирование подписи (Sign) одним из членов группы; – проверка подписи (Verify) на основании сообщения и открытого ключа группы; – определение автора подписи (Open) раскрывающим менеджером OM группы; - проверка правильности раскрытия (Judge) менеджером ОМ группы автора подписи, не требующая знания какого-либо секрета; - отзыв права подписи (Revoke) у некоторого члена группы, осуществляемый выпускающим менеджером IM.
Различают статические и динамические схемы групповой подписи. В статических схемах число участников группы задается при ее формировании, а личные ключи генерируются менеджером GM (он же IM) на этапе инициализации. Динамические схемы подразумевают включение членов в группу и исключение из нее по мере необходимости.
К протоколам групповых подписей предъявляются следующие основные требования [37]: - корректность (correctness): подпись, сформированная честным членом группы, должна успешно проходить проверку; алгоритм раскрытия подписи должен корректно идентифицировать автора; алгоритм проверки правильности раскрытия должен принять доказательство правильности раскрытия подписи; - анонимность (anonymity): только на основании подписи невозможно установить личность члена группы-автора подписи; - отслеживаемость (traceability): с помощью своего закрытого ключа раскрывающий менеджер может узнать идентификатор члена группы-автора подписи.
Кроме того, могут на практике могут потребоваться такие свойства как [37]: - невозможность фальсификации (unforgeability): только члены группы могут подписывать сообщения от лица группы. При этом они не должны иметь возможность подписать сообщение так, чтобы раскрывающий менеджер не смог восстановить личность автора подписи; - устойчивость к сговору, «нефабрикуемость» (coalition-resistance, non-frameability): если несколько пользователей вступили в сговор (в более строгом варианте в нем может участвовать и менеджер ОМ), они не должны иметь возможность сформировать подпись, которая была бы неотслеживаемой или указывала на пользователя, не участвующего в сговоре. Если это требование выполня 21 ется, никого нельзя будет ложно обвинить в создании подписи некоторого сообщения, которую тот не создавал; - несопоставимость (неразличимость, unlinkability): для двух произвольных подписей нельзя определить, были ли они сформированы одним и тем же пользователем; - невозможность ложного обвинения (exculpability): ни члены группы, ни выпускающий и раскрывающий менеджеры не могут создать подпись от имени других членов группы. При этом, однако, менеджер /М может создать подставного пользователя, после чего формировать подписи от его имени.
Следует отметить, что перечисленные требования являются неформализованными и частично перекрываются. Впервые формальные требования безопасности для статической схемы групповой подписи — полная анонимность (full-anonymity) и полная отслеживаемость (fullraceability) — были сформулированы в работе [175]. Эти требования являются ключевыми в модели безопасности статической схемы групповой подписи BMW (Bellare, Micciancio, Warinschi) и влекут за собой все остальные неформальные требования за одним исключением: в этой модели используется более слабое требование к невозможности ложного обвинения. Подразумевается, что ни члены группы, ни раскрывающий менеджер не могут выпустить подписи от лица других пользователей (не включается требование относительно менеджера IM).
Согласно свойству полной анонимности нарушитель не способен восстановить по подписи идентификатор выпустившего ее автора, не зная ключ раскрывающего менеджера. При этом считается, что нарушитель может: - вступать в сговор с членами группы, что моделируется предоставлением нарушителю закрытых ключей всех членов группы; - видеть результаты предыдущих раскрытий подписи менеджером группы, что моделируется предоставлением нарушителю доступа к раскрывающему оракулу, то есть к функции, которая для любой подписи, кроме целевой, без использования личного закрытого ключа раскрывающего менеджера указывает на члена группы, ее сформировавшего. Полная отслеживаемость подразумевает, что любая подпись, созданная какой-либо коалицией вступивших в сговор членов группы, при раскрытии укажет на одного из участников сговора. Необходимость проверки выполнения всего двух свойств безопасности и возможность оперировать строгими определениями значительно упростили процесс формального доказательства безопасности новых схем подписи.
Однако применимость статических моделей ограничена, поскольку они не позволяют добавлять пользователей в группу. Помимо этого они наделяют слишком высоким доверием менеджера IM, генерирующего ключи (он не отделен от координатора GM, который является доверенной стороной), так как он знает личные ключи всех членов группы и может сгенерировать подпись от чужого имени.
Эти трудности преодолены в модели безопасности динамической схемы групповой подписи BSZ (Bellare, Shi, Zhang), где на этапе формирования группы не задано ни число участников, ни их идентификаторы [176]. Ключевыми требованиями безопасности в этой модели являются анонимность, отслеживаемость и невозможность фальсификации, которые должны соблюдаться, даже если нарушителю предоставлен доступ к различным оракулам. Эти три требования влекут за собой выполнение и всех остальных неформальных требований безопасности, в том числе строгую невозможность ложного обвинения.
Иерархическая структура самоорганизующихся сетей позволяет организовать в них аутентификацию с использованием примитива групповой подписи.
Принцип сложностной однородности
Совокупность всевозможных действий нарушителя (атак) определяется его возможностями. Модель нарушителя определяется множеством его возможностей, которые позволяют (но не предписывают) нарушителю действовать так или иначе для достижения своей цели [90, 146, с. 181]. Поэтому атаки могут быть описаны в терминах теории исчислений. В отличие от алгоритма, который предполагает получение решения (или останова) из условия, принадлежащего области применимости алгоритма, исчисление на каждом шаге разрешает то или иное действие в рамках заданных правил вывода (алгоритм предписывает такое действие) [78, с. 62, 252]. В алгоритме поиск решения выполняется дискретно, каждый шаг имеет ограниченную сложность и использует результаты, полученные на предыдущих шагах. Исчисление отражает и обобщает интуитивное представление об индуктивном порождении множества [156].
Подобно тому, как алгоритм задает алгоритмический (или вычислительный) процесс, исчисление задает исчислительный (или порождающий) процесс. Этот процесс разбивается на отдельные шаги, каждый из которых состоит в получении нового объекта из уже полученных к началу этого шага объектов путем применения произвольного разрешительного правила. Всякое исчисление работает с элементами некоторого множества, называемого рабочей средой исчисления. Все состояния исчислительного процесса лежат в этом множестве. Работа исчисления состоит в образовании новых допустимых элементов, или допустимых состояний, рабочей среды.
Алгоритмы и исчисления связаны друг с другом [156]. Для каждого исчисления, порождающего пару (x, y), существует алгоритм, для которого x является входом, а y — выходом.
Таким образом, модель (возможностей) нарушителя задает правила вывода исчисления, а атака является результатом исчисления. Множество возможностей нарушителя в рамках формальной логики является аналогом системы аксиом некоторой теории, а совокупность атак — аналогом совокупности истинных или доказуемо истинных утверждений этой теории.
Множества истинных и доказуемо истинных утверждений не совпадают: существуют истинные утверждения, которые невозможно доказать (а также опровергнуть, поскольку доказательный аппарат считается непротиворечивым). Аналогично существуют ложные утверждения, для которых невозможно доказать ложность (а также истинность, поскольку аппарат доказательства непротиворе 50 чив). При этом каждое утверждение является либо истинным, либо ложным [76, 156].
Можно задать следующую классификацию информационных систем [90; 146, с. 181]: - система безопасна, если ни одна атака, нарушающая безопасность, не может быть реализована в рамках данного исчисления; - система доказуемо безопасна, если существует доказательство того, что ни одна атака, нарушающая безопасность, не может быть реализована в рамках данного исчисления; - система уязвима, если в рамках данного исчисления существует атака, нарушающая безопасность; - система доказуемо уязвима, если в рамках данного исчисления существует вывод для данной атаки, нарушающей безопасность. Термины «система» и «безопасность» задают интерпретацию соответствующего исчисления, замена терминов «система» на «утверждение», «безопасность» на «истинность» задает изоморфизм интерпретаций. Поэтому можно утверждать, что множества безопасных и доказуемо безопасных систем, а также уязвимых и доказуемо уязвимых систем различны, то есть существуют информационные системы, которые не являются ни доказуемо безопасными, ни доказуемо уязвимыми.
Чем уже (шире) множество возможностей нарушителя, тем легче (труднее) противостоять этому нарушителю. При пустом множестве возможностей любая система является безопасной; если, наоборот, нарушитель обладает уникальными (экстрасенсорными) способностями, то ни одна система не является безопасной.
С точки зрения теории множеств, частичная упорядоченность по включению на множествах возможностей нарушителя порождает упорядоченность моделей нарушителя, то есть модель нарушителя с большими возможностями будет больше модели с меньшими возможностями.
Упорядоченность моделей нарушителя порождает упорядоченность множества атак и обратную упорядоченность множества безопасных информационных систем, согласно которой система, безопасная по отношению к меньшей модели нарушителя, может не являться безопасной для большей модели. Таким образом, понятие безопасности информационной системы подразумевает указание соответствующей модели нарушителя.
Модель нарушителя можно задать множеством, элементы которого могут сопровождаться численными значениями, характеризующими возможности нарушителя (например, соответствовать производительности вычислительного устройства). Назовем модели (возможностей) нарушителя однотипными, если их элементы одинаковы с точностью до численных значений. На однотипных моделях можно установить отношение порядка, например, упорядочив возможности по степени их воздействия на безопасность системы, а затем упорядочив возможности одного типа по их количественным характеристикам. Справедливы следующие утверждения [90; 146, с. 182].
Динамическая групповая подпись на билинейных отображениях
Поскольку билинейные отображения эллиптических кривых являются основной математической структурой для построения протоколов групповой подписи, целесообразно проанализировать сложностную неоднородность типового протокола. В качестве примера рассмотрим протокол подписи, построенный по принципу схемы Бонэ-Линна-Шахама (BLS) [149, с. 190; 183].
Параметрами схемы подписи являются эллиптическая кривая Е(р), заданная уравнением в форме Вейерштрасса у2 = хъ + Ах + В, удовлетворяющая требованиям ГОСТ Р 34.10-2012 [47] и содержащая подгруппу простого порядка г, где число точек кривой E(FP); h — хэш-функция по ГОСТ Р 34.11-2012 [48], Q є (Р) — ключ проверки, где точка Р єE(F к)\Е(р) — образующая циклической группы простого порядка г; целое число d — ключ подписи, при этом Q = dP.
Теорема 3.1. Для любых аффинных точек Т, Q порядка г, лежащих в разных циклических группах порядка г, значение билинейного отображения отлично от 1.
Доказательство. Предположим, что e(T, Q) = 1. Тогда e(dT, Q) = 1 и е(Т, dQ) = 1 для всех /. Это противоречит свойству 2 билинейного отображения.
Поэтому изменение сообщения или подписи вызывает непредсказуемое изменение билинейного отображения. Число возможных значений билинейного отображения равно г» 1, поэтому вероятность того, что измененное сообщение или подпись пройдут проверку, пренебрежимо мала. Безопасность протокола подписи на билинейных отображениях определяется следующими предположениями: 1. Задача дискретного логарифмирования на эллиптической кривой является сложной (решение этой задачи ведет к вычислению ключа подписи). 2. Задача дискретного логарифмирования в группе F p (по данным элементам а, Ъ найти такой показатель /, что Ъ = ad) является сложной. Решение этой задачи позволяет вычислить ключ подписи, если положить а = е(Р, Р), Ъ = е(Р, Q). 3. Задача обращения спаривания Вейля (по данным Р є E(FP\ e(R, P) є F\ найти точку К) является сложной. Решение этой задачи позволяет сформировать подпись для произвольного сообщения без знания ключа. 4. Задача обращения хэш-функции является сложной (в противном случае можно подменить подписанное сообщение другим). 5. Задача нахождения коллизии хэш-функции является сложной (в противном случае можно заготовить пару сообщений, составляющих коллизию, и после подписи заменить подписанное сообщение другим).
Рассмотрим сложность этих задач, используя аппарат полиномиальной сводимости задач. Теорема 3.2. Задача дискретного логарифмирования на эллиптической кривой не сложнее задачи дискретного логарифмирования в группе k. Доказательство. Билинейное отображение задает гомоморфное вложение группы Е(р) в группу k и может быть вычислено с полиномиальной сложно стью. Поэтому для вычисления дискретного логарифма на эллиптической кривой достаточно вычислить е(Р, Р), е(Р, Q) = (е(Р, P))d и затем вычислить дискретный логарифм d в группе F p .Теорема 3.3. Задача обращения билинейного отображения не сложнее задачи Диффи-Хеллмана в группе Гk. Доказательство. Предположим, что задача обращения билинейного отображения решена. Тогда задача Диффи-Хеллмана (по данным а, с?, с? найти сГ) может быть решена последовательным выполнением следующих шагов. 1. Выбрать произвольную точку R є E(FP). 2. По значению а вычислить точку S, такую, что e(S, R) = а. 3. По значению а вычислить точку Sx, такую, что e(Sx, R) = f. 4. По значению с? вычислить точку Sy, такую, что e(R, Sy) = ct. 5. Вычислить билинейное отображение e(Sx, Sy) = сґ. На последнем шаге получаем решение задачи Диффи-Хеллмана.Теорема 3.4. Задача Диффи-Хеллмана в мультипликативной группе Fp k сводится к задаче дискретного логарифмирования в этой же группе. Эти задачи эквивалентны, если число г - 1 (где г — порядок циклической группы) имеет гарантированно малые простые делители. Доказательство. Предположим, что задача дискретного логарифмирования решена. Тогда по данным значениям а, с? можно найти х, и далее по данному значению с? возведением в степень х можно найти сР .
Предположим, что число г - 1 имеет только малые простые делители (максимальный из них ограничен полиномом от log;?), а — образующая группы Fr и h є Fr. Тогда задача вычисления такого показателя у, что g y = h (mod г), не является сложной и может быть решена алгоритмом Гельфонда (см., например [120]) с полиномиальной от log;? сложностью.
Покажем, что если в этом случае можно решить задачу Диффи-Хеллмана, то можно решить и задачу дискретного логарифмирования. Задачу нахождения образующей g по известному разложению порядка группы Fr можно решить с полиномиальной сложностью с использованием китайской теоремы об остатках. Вычисление логарифма на основании решенной задачи Диффи-Хеллмана выполняется аналогично алгоритму Гельфонда.
Пусть g\ — образующая подгруппы простого порядка q в группе Fr. Положим a x = b, ay=bg1 ,az=bgr1 . Решая задачу Диффи-Хеллмана, находим c = ayz =ах . Затем полагаем ау = cg1, az = г , находим с1 = ayz =ах и т. д. Вы полняя такие действия, можно вычислить а " для произвольного п. Придавая чис лу п значения делителей числа г - 1 и сравнивая а " с а, находим наименьшее п такое, что ах" = а, при этом хп = 1 (mod г). Определяем множество возможных зна чений х. Далее, полагая Ъх = dti для случайных s, t и повторяя указанные опера ции, находим наименьшее натуральное ЩФП такое, что (s + tx)"1 = 1 (mod г), и оп ределяем множество возможных значений х и т. д. Затем восстанавливаем х по аналогии с китайской теоремой об остатках как пересечение указанных множеств. Таким образом, при указанных выше ограничениях на максимальный про стой делитель числа г - 1 задача дискретного логарифмирования полиномиально эквивалентна задаче Диффи-Хеллмана.
Примеры эллиптических кривых
Повторив такой процесс г раз, можно отозвать право подписи у всех пользователей, попавших в список отзыва. Пользователь, чей сертификат отозван, не может вычислить новый закрытый ключ в соответствии с приведенными выше правилами. Смена ключей требует коррекции базы данных членов группы. Записи в этой базе имеют вид (upk,A,x,h y ,5) , где ирк — личный сертифицированный ключ пользователя, S — подпись значения А на закрытом ключе владельца сертификата. При смене ключей все записи становятся неактуальными, однако выпускаю щий менеджер может вычислить новое значение А для каждой такой записи, так как знает ключ it A —((gl-hyyiy+Xl)/Ayix Xl), но не может скорректировать подпись S. Тем не менее, это не повлияет на возможность проверки корректности раскрытия групповой подписи, так как из новых открытого и закрытого ключей, а также из элемента списка отзыва можно выразить старое значение А, подпись для которого действительна: А - & hy Ач х. Таким образом, достоверно зная все факты отзыва членских сертификатов, всегда можно модифицировать алгоритм проверки правильности раскрытия под 108 писи для работы со значением A, выраженным через новые значения ключей и записей списка отзыва. Если когда-либо производились операции отзыва, то при проверке правильности раскрытия придется отслеживать всю историю изменения части A закрытого ключа пользователя, оставшегося в группе.
Благодаря тому, что в списке отзыва публикуется только часть сертификата отзываемого участника, ни один из участников не может воспользоваться этой информацией, чтобы сформировать подпись с помощью раскрытого менеджером группы сертификата и обмануть тех проверяющих, которые еще не успели обновить локальную копию открытого ключа группы.
Данный протокол отзыва права подписи в схеме ED-BBS не решает некоторых прикладных проблем: – нет возможности отозвать право подписи с определенного момента времени. Нужно, чтобы подписи, сформированные членом группы до того, как его сертификат попал в список отзыва, сохраняли полный набор свойств, обеспечиваемых базовой схемой, — корректность, анонимность и отслеживаемость; – не ясно, как запретить членам группы использовать свои старые сертификаты для формирования групповой подписи; – не ясно, как обеспечить корректность, анонимность и отслеживаемость всех подписей, сформированных членами группы до изменения открытого ключа группы.
Таким образом, все возникающие трудности имеют временной характер, поскольку запись отзыва не привязана ко времени ее формирования. Кроме того, ко времени не привязаны открытый ключ группы, закрытые ключи членов группы и записи в базе данных членов группы. Для преодоления этих недостатков предлагается добавить временные метки [22, 37]: – к открытому ключу группы gpk — время его создания tgpk ; – к каждой записи (upk ji , Aji ,xji ,hy ji ,Sji ) в базе данных членов группы — время tRL i прекращения действия записи j-го пользователя ввиду отзыва у него права подписи, либо ввиду ее изменения в связи с отзывом права подписи у дру 109 гого члена группы. Действительная в настоящий момент времени запись имеет нулевую временную метку; - к каждой групповой подписи а — время ґа ее формирования.
Таким образом, каждая групповая подпись привязывается к определенному /-му моменту времени t , в который был действителен определенный открытый ключ группы gpfc, и сама групповая подпись была сформирована членом группы с действующим на тот момент сертификатом gsk]t, то есть с любой групповой подписью а ассоциирована связка (gpki,tgpkj)-(a,ta)-(gskjntRL ), при этом: - в подписи а зашифровано значение Ajt, то есть ее сформировал й пользователь, обладающий членским сертификатом gskjt = (А]Пх]Пу}і), действующим в /-й период, с которым связано время прекращения его действия tRL ; - выполняются неравенства tgpk Ф ta, tс Ф t . Это означает, что формирование группы (либо исключение какого-либо члена из группы, сопровождающееся изменением открытого ключа группы), добавление члена в группу и фомирование им подписи сообщения — не могли произойти одновременно; - tgpkj ta — группа должна быть сформирована раньше, чем могут быть созданы подписи от ее имени; - не существует другой пары (gpkk,tgpk), относящейся к этой группе и такой, что tgph tgpk ta, то есть gpt — актуальный открытый ключ группы на момент формирования подписи а; - ta 1Щ и не существует другой пары (gskjk, ґщ ), относящейся ку-му члену группы и такой, что ta ґщ t , то есть gsk]t — актуальный закрытый ключу-го члена группы на момент формирования подписи а.
Такую связку можно назвать окружением подписи а. Для выполнения проверки подписи, ее раскрытия и доказательства корректности раскрытия нужно использовать ключи из окружения этой подписи.
Если за поддержание временных меток открытых ключей и записей базы данных членов отвечает выпускающий менеджер, то за установку временной метки в подписи отвечает член группы. Таким образом, требуется ввести нового доверенного участника — временного менеджера TM, ставящего временную метку и удостоверяющего ее своей личной подписью. На этого участника возлагается и обязанность удостоверения временных меток, проставляемых на открытом ключе группы и записях базы данных членов группы.
В разработанной схеме EDR-BBS (extended dynamic revocable BBS, [22, 37]) временной менеджер фиксирует время создания группы, а также время и факт включения пользователя в группу, заверяет время создания групповой подписи, удостоверяет запись отзыва, поддерживает базы данных в актуальном состоянии, обеспечивает атомарность операции отзыва.