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

Ирина Рехвиашвили

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

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

Информатика

Дипломы

Вуз: Санкт-Петербургский государственный политехнический университет (ФГБОУ ВПО «СПбГПУ»)

ID: 60ccce31e4dde500015657d0

UUID: d4839cc0-b282-0139-32fc-0242ac180005

Язык: Русский

Опубликовано: больше 3 лет назад

Просмотры: 3

14.06

Ирина Рехвиашвили

Санкт-Петербургский государственный политехнический университет (ФГБОУ ВПО «СПбГПУ»)

Комментировать 0

Рецензировать 1

Скачать - 928,3 КБ

Поделиться работой

Министерство науки и высшего образования Российской Федерации Санкт-Петербургский политехнический университет Петра Великого Высшая школа кибербезопасности и защиты информации Работа допущена к защите Директор Высшей школы кибербезопасности и защиты информации, д.т.н., проф. ________________ Д.П. Зегжда «___»_______________2020 г. ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА ДИПЛОМНАЯ РАБОТА ОТЗЫВ СО СВЯЗЫВАНИЕМ В СХЕМЕ КОЛЬЦЕВОЙ ПОДПИСИ НА РЕШЕТКАХ по направлению подготовки (специальности) 10.05.04 Информационно-аналитические системы безопасности Направленность (профиль) 10.05.04_01 Автоматизация информационно-аналитической деятельности Выполнил студент гр. 3651004/40101 И.Ш. Рехвиашвили Руководитель профессор ВШКиЗИ ИПММ, д.т.н., доцент Е.Б. Александрова Санкт-Петербург 2020

РЕФЕРАТ На 43 с., 8 рисунков, 5 таблиц, 1 приложение. КЛЮЧЕВЫЕ СЛОВА: РЕШЕТКИ, КОЛЬЦЕВАЯ ПОДПИСЬ, ОТЗЫВ ПРАВА ПОДПИСИ, ШИФРОВАНИЕ С ОТКРЫТЫМ КЛЮЧОМ, ТЕСТ НА РАВЕНСТВО Предлагается подход к решению задачи отзыва права подписи у участника группы в схеме кольцевой подписи на решетках путем добавления уполномоченной сущности – центра отзыва, осуществляющего проверку наличия сертификата пользователя в списке отзыва. THE ABSTRACT 43 pages, 8 pictures, 5 tables, 1 application KEY WORDS: LATTICE, RING SIGNATURE, REVOCATION, PUBLIC KEY ENCRYPTION, EQUALITY TEST An approach is proposed to solve the problem of revoking the right to sign from a group member in a lattice-based ring signature scheme by adding a revocation center that checks the presence of a member certificate in the revocation list.

3 СОДЕРЖАНИЕ Введение ............................................................................................................... 4 1. Схема кольцевой подписи на решетках .................................................. 8 1.1 Свойства кольцевых подписей ................................................................ 9 1.2 Криптография на решетках .................................................................... 11 1.2.1 Свойства решеток...................................................................................... 11 1.2.2 Вычислительно трудные задачи .............................................................. 12 1.3 Описание схемы кольцевой подписи на решетках ................................ 13 1.4 Выводы ....................................................................................................... 15 2. Отзыв в схеме кольцевой подписи .......................................................... 16 2.1 Сравнение механизмов отзыва ................................................................ 16 2.2 Отзыв со связыванием .............................................................................. 19 2.2.1 Свойство контролируемой связываемости............................................. 19 2.2.2 Алгоритм шифрования с открытым ключом с тестами на равенство ............................................................................................... 21 2.3 Применение отзыва со связыванием к схеме кольцевой подписи....... 23 2.4 Повышение безопасности и эффективности механизма отзыва .......... 27 2.5 Выводы ....................................................................................................... 30 3. Реализация схемы кольцевой подписи на решетках с отзывом со связыванием .......................................................................................... 31 3.1 Программная реализация схемы.............................................................. 31 3.2 Тестирование и оценка разработанной системы ................................... 34 3.3 Выводы ....................................................................................................... 38 Заключение .......................................................................................................... 39 Список использованных источников ................................................................ 41 Приложение. Исходный код разработанной программы ................................ 44

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

5 Цель исследования – организация отзыва права подписи в схеме кольцевой подписи на решетках. Для достижения поставленной цели необходимо решить следующий ряд задач: − проанализировать свойства схем кольцевой подписи на решетках и выбрать схему подписи в качестве прототипа; − сравнить механизмы отзыва права подписи в схемах со многими участниками; − разработать схему кольцевой подписи на решетках, обеспечивающую возможность отзыва права подписи у участников; − выполнить программную реализацию и оценку времени работы процедур разработанной схемы кольцевой подписи на решетках с механизмом отзыва права подписи. Теоретическая и методологическая базы исследования. Теоретической основой выпускной квалификационной работы послужили исследования в области криптографии на решетках и протоколов кольцевых подписей. В качестве методологии применялись общенаучные (анализ, обобщение, синтез) и частные (криптографические) методы исследования. При подготовке выпускной квалификационной работы были использованы материалы таких учебных дисциплин, как «Криптографические методы защиты информации», «Теоретико-числовые методы в криптографии», «Алгебра и теория чисел», «Методы программирования». Информационную базу исследования составили научные публикации по исследуемой теме, материалы научных конференций, материалы, собранные в процессе прохождения учебной и преддипломной практик. Степень научной разработанности проблемы. Созданию и исследованию схем кольцевой подписи посвящено значительное число работ, основополагающей среди которых является работа Р. Ривеста, А. Шамира и Я. Тауман [1]. Исследования К. Джентри и К. Пейкерта [2], В. Любашевского [3] посвящены разработке схем подписи на решетках. Подход к построению кольцевой схемы

6 подписи на решетках был впервые предложен в работе З. Бракерски [4], после чего нашел развитие в работах П. Кейрела [5], Ч. Вана [6], Ш. Вана и Ж. Чжао [7], в которых предлагаются схемы кольцевой подписи на решетках. Проблема отзыва права подписи в групповых подписях рассматривается в работах Г. Атениза [8], Е. Брессона и Дж. Стерна [9], Д. Боне и Х. Шахама [10], Я. Камениша и А. Лысянской [11], Д. Сламанига, Р. Шпрайтцера и Т. Унтерлуггауэра [12]. Научная новизна выпускной квалификационной работы определяется тем, что для решения задачи организации отзыва права подписи предложено применить механизм отзыва со связыванием, а также решены проблемы безопасности разработанной схемы посредством применения белых и черных списков, неинтерактивного доказательства с нулевым разглашением и пороговой схемы разделения секрета. Практическая значимость. В настоящее время схемы кольцевой подписи находят свое применение в системах электронного голосования, в которых они позволяют реализовать принцип тайного голосования. Также кольцевые подписи применяются в системах электронной валюты для реализации неотслеживаемых транзакций. Помимо этого, такие схемы могут применяться в различных системах контроля доступа к ресурсу, например в системах контроля общественного транспорта, а также системах предоставления пользователям доступа по подписке. Предлагаемый в работе подход позволяет реализовать в указанных системах возможность исключать участников из группы посредством отзыва у них права подписи без необходимости повторной генерации ключей подписи для всех участников, а также обновления списков отзыва для пользователей системы. Апробация результатов исследования. Основные положения и результаты исследований докладывались и обсуждались на 47-й научной конференции с международным участием «Неделя

7 науки СПбПУ» (Санкт-Петербург, 2018 г.). По итогам участия был получен диплом за лучший доклад на секционном заседании. По результатам выполнения научного проекта «Организация отзыва для схемы кольцевой подписи» в рамках конкурса грантов для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2019 года была получена премия Правительства Санкт-Петербурга. Результаты исследований по теме выпускной квалификационной работы отражены в публикации [13].

8 1. СХЕМА КОЛЬЦЕВОЙ ПОДПИСИ НА РЕШЕТКАХ Цифровая подпись является механизмом аутентификации данных и их источника. Она представляет собой данные, присоединяемые к передаваемому сообщению и подтверждающие, что автор подписи составил и заверил данное сообщение. Получатель сообщения (проверяющий) с помощью этой подписи может убедиться, что автором сообщения является именно владелец подписи и что целостность данных не была нарушена в процессе передачи. Кроме того, подпись составляется таким образом, чтобы автор подписи не мог затем отрицать перед проверяющим факт подписания [14]. Дальнейшее развитие схем цифровой подписи привело к появлению класса подписей, в которых авторы подписей являются участниками некоторой группы. К такому классу относятся групповая, пороговая и кольцевая подпись, рассматриваемая в данном исследовании. Безопасность цифровой подписи (то есть трудность подделки, невозможность отказа) обеспечивается сложностью вычислительно трудных задач. Современные исследования показывают, что схемы подписи, основанные на задачах разложения целого числа и дискретного логарифмирования, уязвимы к атакам на квантовом компьютере с использованием полиномиальных алгоритмов разложения числе на множители и дискретного логарифмирования. Это побудило к поиску других вычислительно трудных задачах, позволяющих строить стойкие к подобным атакам криптосистемы. Одним из направлений в решении этой задачи является криптография на решетках. Предполагается, что криптосистемы, основанные на решетках, являются стойкими к атакам на квантовом компьютере, поскольку квантовые алгоритмы решения вычислительно трудных задач на решетках имеют более чем полиномиальную сложность [15]. В данной главе рассматриваются основные свойства кольцевых подписей, характеристики решеток и вычислительно трудные задачи на решетках, а также описывается протокол кольцевой подписи на решетках.

9 1.1 Свойства кольцевых подписей Схема кольцевой подписи была впервые предложена Р. Ривестом, А. Шамиром и Я. Тауман в 2001 году в работе «How to leak a secret» [1] в контексте задачи анонимного раскрытия секретных сведений, в которой один из участников группы (например, лицо, анонимно поставляющее сведения о нелегальных действиях в организации) намерен передать секретную информацию третьему лицу. Получатель должен быть уверен, в том, что сообщение было отправлено одним из участников группы, в то время как отправитель заинтересован в том, чтобы его личность не была раскрыта. Кольцевая подпись является разновидностью групповой подписи. В классической схеме групповой подписи менеджер группы определяет участников группы и предоставляет им ключи, с помощью которых каждый участник может подписать сообщение от лица группы. При этом получатель не может определить по подписи, кем из участников она была создана, однако это может сделать менеджер группы. Кольцевая подпись, так же как и групповая, позволяет каждому участнику подписывать сообщения от лица группы, однако не предоставляет менеджеру группы механизма аннулирования анонимности. Таким образом, данная схема гарантирует, что сообщение было подписано одним из участников группы, и при этом обеспечивает анонимность участника в пределах данной группы. Отсюда вытекают два важнейших свойства безопасности кольцевых схем подписи: − невозможность подделки – заключается в неосуществимости операции подписи от лица группы при отсутствии одного из закрытых ключей; − анонимность автора подписи – заключается в невозможности узнать, какой именно закрытый ключ был использован при создании подписи. Группа из 𝑟 участников называется кольцом. С каждым участником кольца ассоциируется пара: открытый ключ 𝑃𝑘 и закрытый ключ 𝑆𝑘 . Простейшая схема кольцевой подписи состоит из следующих двух алгоритмов:

10 − Ring-sign(𝑚, 𝑃1 , 𝑃2 , … , 𝑃𝑟 , 𝑆𝑘 ) – процедура формирования подписи  для сообщения 𝑚 по данным открытым ключам 𝑃1 , 𝑃2 , … , 𝑃𝑟 участников кольца и закрытому ключу 𝑆𝑘 автора подписи. − Ring-verify(𝑚, ) – процедура проверки подписи, для сообщения 𝑚 и подписи , включающей в себя открытые ключи участников кольца, определяющая, является ли данная подпись действительной. На рис. 1.1 представлено взаимодействие основных сущностей, участвующих в схеме кольцевой подписи. Рисунок 1.1 – Схема кольцевой подписи В отличие от групповых подписей, в кольцевых подписях отсутствует необходимость взаимодействия между участниками: любой член группы может подписать сообщение, используя свой закрытый ключ и открытые ключи других участников, не запрашивая их подтверждения. Проверка подписи должна удовлетворять условию: для кольца размером 𝑟 участников проверяющий не сможет определить настоящего автора подписи с вероятностью больше, чем 1/𝑟.

11 1.2 Криптография на решетках Безопасность большинства схем подписи основывается на вычислительной сложности задачи разложения целого числа на множители и задачи дискретного логарифмирования. Однако с появлением в 1994 году алгоритма Шора, использующего квантовые вычисления и способного эффективно (за полиномиальное время) решать данные задачи, стало ясно, что традиционные криптографические протоколы, основанные на них, являются уязвимыми к атакам с использованием квантового компьютера. Таким образом, актуальной задачей в наше время является разработка криптографических алгоритмов, стойких к атакам квантового компьютера. Их изучением занимается постквантовая криптография. Одной из перспективных математических структур постквантовой криптографии являются решетки. Они лежат в основе таких криптографических примитивов, как: − шифрование с открытым ключом: NTRUEncrypt, GGH, RLWE-HOM; − цифровая подпись: NTRUSign, GGH, RLWE-SIG; − хеш-функции: SWIFFT, LASH. 1.2.1 Свойства решеток Рассмотрим основные свойства решеток. Пусть 𝒃1 , 𝒃2 , … , 𝒃𝑚 – набор линейно независимых векторов в 𝐑𝑛 . Решеткой называется набор линейных комбинаций этих векторов с целочисленными коэффициентами: 𝑚 𝐿(𝒃1 , 𝒃2 , … , 𝒃𝑚 ) = {∑ 𝑥𝑖 𝒃𝑖 | 𝑥𝑖 ∈ 𝒁} = {𝐵𝒙, 𝒙 ∈ 𝒁𝒎 }, 𝑖=1 где 𝐵 – это матрица размерности 𝑛 × 𝑚 со столбцами 𝒃1 , 𝒃2 , … , 𝒃𝑚 . Векторы 𝒃1 , 𝒃2 , … , 𝒃𝑚 называются базисом решетки, а число m – размерностью (или рангом). При 𝑚 = 𝑛 решетка называется полноранговой. Матрицей Грама называется матрица

12 (𝒃1 , 𝒃1 ) Г(𝒃1 , 𝒃2 , … , 𝒃𝑚 ) = ( (𝒃2…, 𝒃1 ) (𝒃𝑚 , 𝒃1 ) (𝒃1 , 𝒃2 ) ⋯ (𝒃1 , 𝒃𝑚 ) (𝒃2 , 𝒃2 ) ⋯ (𝒃2 , 𝒃𝑚 ) ). … … … (𝒃𝑚 , 𝒃2 ) ⋯ (𝒃𝑚 , 𝒃𝑚 ) Число det(𝐿) = √det⁡(Г(𝒃1 , 𝒃2 , … , 𝒃𝑚 )) называется объемом (или определителем) решетки. Определитель решетки равен объему фундаментального параллелепипеда, построенного на векторах 𝒃1 , 𝒃2 , … , 𝒃𝑚 . Для матрицы размерностью ≥ 2 существует бесконечное количество базисов. Матрица перехода между любыми двумя базисами является унимодулярной, то есть ее определитель равен ±1, таким образом, объем решетки не зависит от выбора базиса. Так как решетка дискретная, в ней содержится ненулевой вектор минимальной длины, который называется ее кратчайшим вектором. Евклидова норма данного вектора называется первым минимумом решетки и обозначается 𝜆1 (𝐿) или ‖𝐿‖. Также могут использоваться и другие нормы. 1.2.2 Вычислительно трудные задачи В криптографических системах применяются следующие вычислительно трудные задачи, основанные на решетках [16]: 1. Задача поиска кратчайшего вектора (shortest vector problem, SVP). По заданному базису решетки 𝐿 найти вектор 𝒖 ∈ 𝐿 такой, что ‖𝒖‖ = ‖𝐿‖. Также может использоваться аппроксимированная версия задачи поиска кратчайшего вектора: найти вектор 𝒗 ∈ 𝐿 такой, что ‖𝒗‖ ≤ 𝛾‖𝐿‖. 2. Задача поиска ближайшего вектора (closest vector problem, CVP). По заданному базису решетки 𝐿 и вектору 𝒗 ∈ 𝐑𝑛 найти ближайший к нему вектор решетки 𝒖 ∈ 𝐿, то есть такой, что ‖𝒖 − 𝒗‖ ≤ ‖𝒘 − 𝒗‖⁡⁡∀⁡𝒘 ∈ 𝐿. Аппроксимированная версия задачи: найти вектор 𝒖 ∈ 𝐿 такой, что ‖𝒖 − 𝒗‖ ≤ 𝛾‖𝒘 − 𝒗‖⁡⁡∀⁡𝒘 ∈ 𝐿. 3. Задача поиска наименьшего базиса (smallest basis problem, SBP). Для заданной решетки 𝐿 найти базис с наименьшей длиной его максимального вектора, то есть найти

13 𝐵:⁡∀𝐵′ ∈ {𝐵 ∈ 𝑹𝑛×𝑚 ⁡|⁡𝐿 = 𝐿(𝐵)}⁡ max {‖𝒃𝑖 ‖} ≤ max {‖𝒃′𝑖 ‖}. 1≤𝑖≤𝑚 1≤𝑖≤𝑚 4. Задача обучения с ошибками (learning with errors, LWE). Пусть решетка 𝐿 задана базисом 𝐵 следующим образом: 𝐿 = {𝒛 ∈ 𝒁𝑛 : 𝒛 = 𝐵𝑇 𝒔, 𝒔 ∈ 𝒁𝑛 }. На решетке равномерно распределен шум 𝒆. Задан некоторый исходный вектор без шума 𝒔 ∈ 𝒁𝑛𝑞 и соответствующее значение 𝐵𝒔 + 𝒆. Найти исходную точку в решетке (исключить шум) по некоторому множеству известных 𝐵𝒔𝒊 + 𝒆𝑖 . 5. Задача поиска вектора по норме (short integer solution, SIS). Для заданной матрицы 𝐴 ∈ 𝒁𝑛×𝑚 найти вектор 𝒗 ∈ 𝒁𝑚 \{0} такой, что 𝐴𝒗 = 𝟎 и ‖𝒗‖ ≤ 𝑞 𝛽 для некоторого заданного 𝛽. 1.3 Описание схемы кольцевой подписи на решетках Схема кольцевой подписи на решетках, основанная на модели со случайным оракулом, предложенная в 2014 году Ш. Ваном и Ж. Чжао в работе [7], была выбрана в данной работе в качестве прототипа ввиду того, что она характеризуется меньшим размером сформированной подписи в сравнении с другими рассмотренными схемами кольцевой подписи на решетках [5, 6]. Данная схема является адаптацией схемы подписи, предложенной В. Любашевским в 2012 году в работе «Lattice signatures without trapdoors» [3]. Схема является стойкой к атакам на основе выбранного открытого текста, ее безопасность основывается на задаче поиска вектора по норме (SIS). В процессе формирования подписи сообщения используются только операции перемножения матриц, что делает алгоритм достаточно эффективным. Используемые процедуры: 1) TrapGen(1𝑛 ) – односторонняя функция с лазейкой. Пусть 𝑞 = 𝑝𝑜𝑙𝑦(𝑛) – простое число, 𝑚 > 5𝑛 log 𝑞 – случайное положительное число. На входе: параметр безопасности n. На выходе: матрицы 𝑨 ∈ 𝐙𝑞𝑛×𝑚 и 𝑩𝑨 ∈ 𝐙𝑞𝑛×𝑚 . Здесь𝑩𝑨 – это базис решетки 𝒒 (𝑨) = {𝒗 ∈ 𝐙𝑞𝑚 : 𝑨𝒗 = 0(𝑚𝑜𝑑⁡𝑞)}.

14 2) SamplePr(𝑨, 𝑩𝑨 , 𝑆, 𝒚). На входе 𝑨 ∈ 𝐙𝑞𝑛×𝑚 и 𝑩𝑨 ∈ 𝐙𝑞𝑛×𝑚 , 𝑆≥ ‖𝑩𝑨 ‖𝜔(√log 𝑛), 𝒚 ∈ 𝐙𝑞𝑛 . На выходе: вектор 𝒆 ∈ {𝒆 ∈ 𝒁𝑚 : ‖𝒆‖ ≤ 𝜎 √𝑚}⁡такой, что⁡𝑨𝒆 = 𝒚(𝑚𝑜𝑑⁡𝑞). Основные алгоритмы протокола: 1. Ring-gen – вероятностный алгоритм, принимающий на вход параметр безопасности 𝑛 и выдающий на выходе пару ключей (𝑝𝑘𝑖 , 𝑠𝑘𝑖 ) за полиномиальное время. Шаги алгоритма: 1) Пусть 𝑞 ≥ 3 – простое, 𝑛 ∈ 𝐙 ≫ 64, 𝑚 ∈ 𝐙 > 5n log 𝑞. 𝐻:⁡{0, 1}∗ → {𝒗: 𝒗 ∈ {−1, 0, 1}𝑘 , ‖𝒗‖ ≤ 𝑘′} – стойкая к коллизиям хэшфункция, 𝑘, 𝑘 ′ ∈ 𝐙 > 0. Матрица 𝑻 выбирается случайно из 𝐙𝑞𝑛×𝑚 . 2) В кольце R из 𝑙 участников для каждого i-го участника запускается алгоритм TrapGen(1𝑛 ), чтобы получить 𝑨𝑖 ∈ 𝐙𝑞𝑛×𝑚 и 𝑩𝑖 ∈ 𝐙𝑞𝑛×𝑚 . 3) Для каждого i-го участника запускается алгоритм SamplePr(𝑨𝑖 , 𝑩𝑖 , 𝑆, 𝒕𝑗 ), где вектор 𝒕𝑗 – j-й столбец матрицы 𝑻. На выходе алгоритм выдает вектор 𝒔𝑖𝑗 ∈ 𝒁𝑚 такой, что 𝑨𝑖 𝑺𝑖 = 𝑻 и 𝑺𝑖 ∈ {−𝑑, … , 0, … , 𝑑}𝑚×𝑘 , где 𝑺𝑖 = (𝒔𝑗1 , … , 𝒔𝑗𝑘 ). 𝑨𝑖 – открытый ключ, 𝑺𝑖 – закрытый ключ i-го участника. 2. Ring-sign – вероятностный алгоритм, принимающий на вход набор параметров 𝜌, сообщение 𝑚, ключ автора подписи 𝑠𝑘𝑖 и набор открытых ключей 𝐿 = {𝑝𝑘1 , … , 𝑝𝑘𝑙 } и выдающий на выходе подпись 𝑧 за полиномиальное время. На входе алгоритма дано сообщение 𝑚, кольцо R из 𝑙 участников с открытыми ключами 𝐿 = {𝑨1 , … , 𝑨𝑙 }, закрытый ключ автора подписи 𝑺𝑗 . Шаги алгоритма: 1) Для каждого 𝑖, 1 ≤ 𝑖 ≤ 𝑙 автор подписи генерирует случайный вектор 𝒚𝑖 ∈ 𝒁 𝑚 ; 2) Вычисляет значение хеш-функции 𝒄 = 𝐻(∑𝑖 𝑨𝒊 𝑦𝑖 , 𝐿, 𝑚) 3) Для всех 𝑖, 1 ≤ 𝑖 ≤ 𝑙 вычисляет 𝒚𝑖 , 𝑖 ≠ 𝑗 𝒛𝒊 = {𝑺 𝑐 + 𝒚 , 𝑖 = 𝑗. 𝑗 𝒋,

15 Тогда (𝒛𝒊 :⁡1 ≤ 𝑖 ≤ 𝑙, 𝒄) – кольцевая подпись сообщения m. 3. Ring-verify – детерминированный алгоритм, принимающий на вход набор параметров 𝜌, подпись 𝑧 сообщения 𝑚 и определяющий, является ли подпись корректной. На входе: сообщение 𝑚, кольцо R из 𝑙 участников с открытыми ключами 𝐿 = {𝑨1 , … , 𝑨𝑙 } и подпись (𝒛𝒊 :⁡1 ≤ 𝑖 ≤ 𝑙, 𝒄). Проверяющий принимает подпись тогда и только тогда, когда выполняются два условия: 1) ‖𝒛𝒊 ‖ ≤ 2𝜎√𝑚⁡для⁡всех⁡𝑖, 1 ≤ 𝑖 ≤ 𝑙; 2) 𝒄 = 𝐻(∑𝑖 𝑨𝒊 𝒛𝑖 − 𝑻𝒄, 𝐿, 𝑚). 1.4 Выводы Таким образом, в данной главе рассмотрены основные свойства схем кольцевых подписей, к которым относятся невозможность подделки и анонимность автора подписи, описаны субъекты системы, отношения между ними и используемые алгоритмы. Обоснован выбор решеток в качестве математического аппарата кольцевой подписи, описаны вычислительно трудные задачи, основанные на решетках, и описан протокол выбранной кольцевой подписи на решетках. В следующей главе для данной схемы кольцевой подписи на решетках будет выбран и применен механизм отзыва права подписи.

16 2. ОТЗЫВ В СХЕМЕ КОЛЬЦЕВОЙ ПОДПИСИ Важным свойством всех групповых подписей является возможность удаления участника из группы и отзыв у него права подписи. В существующих схемах применяются различные методы для организации отзыва. Так, у самого участника может быть отозвана возможность создания корректной подписи либо наоборот, проверяющий при проверке подписи производит дополнительные вычисления, чтобы убедиться, что ее автор не был удален из группы. При этом важным является влияние на эффективность схемы подписи. 2.1 Сравнение механизмов отзыва Разные механизмы отзыва отличаются объемом дополнительных вычислений и обновлений, которые должны сделать как участники группы, так и проверяющие, а также влиянием на размер подписи. Рассмотрим существующие механизмы отзыва. − Базовый подход. Наиболее простым методом является отзыв, при котором все участники, которые не должны быть удалены из группы, получают заново сгенерированные ключи (reissuance-based revocation, RBR) [8, 17]. Такой подход требует больших вычислительных затрат во время проведения процедуры отзыва права подписи, поэтому является неудобным в случае, если участников необходимо удалять часто. − Черный список. Этот подход может основываться на списках ото- званных сертификатов (Certificate-based blacklist revocation, BR-C) [9]. От автора подписи требуется предоставить доказательство с нулевым разглашением того, что он не состоит в списке отзыва. При этом возрастают вычислительные затраты для автора подписи и проверяющего при каждом формировании и проверке подписи, а также возрастает размер подписи. Аналогичный подход, основанный на использовании списков ключей подписи [14] приводит к линейному росту вычислительных затрат и размера подписи в зависимости от количества участников. Для организации черного списка можно использовать отзыв с ди-

17 намическим накоплением (Accumulator-based blacklist revocation, BR-A) [11, 19], когда для предоставления списка отзыва используются криптографические «аккумуляторы». − Отзыв, локальный для проверяющего (verifier-local revocation, VLR) [10, 20, 21]. В данном методе записи отзыва не основываются на используемых ключах и обрабатываются только проверяющим, поэтому требуется, чтобы проверяющие обновляли список отзыва при каждом удалении участников. Проверка подписи значительно влияет на объем вычислений, производимых проверяющим. Другим недостатком данной схемы является то, что по подписям отозванных участников группы каждый проверяющий может определить, были они сформированы одним и тем же автором или нет, что нарушает одно из ключевых свойств схемы кольцевой подписи, заключающееся в анонимности автора подписи в пределах группы. − Отзыв со связыванием (linking-based revocation, LBR) [12]. Данный подход основывается на том, что назначенная сущность обладает возможностью определить, были ли две подписи сформированы одним и тем же (анонимным) автором – участником группы. Данная сущность является онлайнсервером, который хранит подписи отозванных участников группы. При проверке подписи проверяющий обращается к серверу. Сервер сравнивает полученную подпись со списком отозванных подписей, после чего отвечает проверяющему, состоит ли автор подписи в списке отзыва. Данный метод не требует от участников группы обновления ключей при отзыве одного из участников, а влияние на время формирования, проверки и размер подписи не зависит от размера группы. Сравнение свойств данных механизмов, влияющих на эффективность схемы подписи, представлено в табл. 2.1. Буквой R обозначено число участников группы, прочерком обозначаются случаи, когда механизм отзыва не оказывает влияния на время работы указанных алгоритмов, на размер ключей и подписи или не требует обновлений. Как видно из таблицы, механизм с перевыпуском ключей требует значительных вычислительных затрат для генерации

18 новых ключей при отзыве права подписи у одного из участников, дополнительные вычислительные затраты линейно зависят от числа участников. Механизм с черными списками требует значительных дополнительных вычислений и на этапе формирования подписи, и на этапе проверки для доказательства того, что автор подписи не состоит в списке отзыва. Отзыв, локальный для проверяющего, не оказывает влияния на размер подписи, но требует частых обновлений от проверяющего для синхронизации списков отзыва между участниками. Механизм отзыва со связыванием также влияет на размер подписи и время ее формирования и проверки, но это влияние не растет с увеличением размера группы участников. Таблица 2.1 – Сравнение механизмов отзыва Тип RBR BR-C BR-A VLR LBR Память Время Размер Размер Автор Проверяключей подписи подписи ющий O(R) O(R) O(R) O(1) O(1) O(1) O(R) O(1) O(1) O(1) O(1) Обновления Автор Проверяющий подписи O(R) O(1) O(R) O(R) O(1) O(1) O(R) - Важным показателем эффективности подписи является необходимость обновления данных для участников группы и для проверяющих. Частые обновления для пользователей, право подписи которых не было отозвано, зачастую сложно реализовать на практике, так как отзыв должен происходить незамедлительно, следовательно, обновления не могут осуществляться с определенной периодичностью, необходима постоянная синхронизация данных между участниками группы и проверяющими. Схема отзыва со связыванием решает эту проблему за счет того, что проверяющий должен постоянно иметь доступ к онлайн-серверу.

19 2.2 Отзыв со связыванием Так как механизм отзыва со связыванием, рассмотренный в разделе 2.1, позволяет производить отзыв права подписи без дополнительных вычислений для участников группы, а влияние выбранного механизма на размер подписи и на объем вычислений, производимых при формировании и проверке подписи, не зависит от числа участников группы, данный метод был выбран в качестве механизма отзыва для схемы кольцевой подписи на решетках. В данном разделе более подробно описываются свойства рассматриваемого метода и способы его реализации для применения к схеме кольцевой подписи на решетках. 2.2.1 Свойство контролируемой связываемости Кольцевые подписи с контролируемой связываемостью отличаются наличием выделенной сущности – менеджера связывания, обладающего возможностью определить, были ли две подписи сформированы одним и тем же пользователем, без возможности идентифицировать этого пользователя. Ключ менеджера связывания (master linking key) обозначим как 𝑚𝑙𝑘. Такая схема содержит следующие алгоритмы [22]: − GkGen(1𝜆 ): На вход принимает параметр безопасности λ, на выходе генерирует открытые параметры схемы 𝑔𝑝𝑘 и ключ менеджера связывания 𝑚𝑙𝑘. − UkGen(1𝜆 ): На вход принимает параметр безопасности λ, на выходе генерирует пары ключей пользователей (𝑝𝑘𝑖 , 𝑠𝑘𝑖 ). − Sign(𝑔𝑝𝑘, 𝑀, 𝑠𝑘𝑖 ): На вход принимает открытые параметры системы 𝑔𝑝𝑘, сообщение 𝑀 и секретный ключ пользователя 𝑠𝑘𝑖 , на выходе генерирует подпись . − Verify(𝑔𝑝𝑘, 𝑀, ): На вход принимает открытые параметры системы 𝑔𝑝𝑘, сообщение 𝑀 и подпись , на выходе возвращает true в случае, если подпись корректна, и false – иначе. − Link(𝑔𝑝𝑘, 𝑚𝑙𝑘, 𝑀, , 𝑀 ′ , ′): На вход принимает открытые параметры системы 𝑔𝑝𝑘, ключ менеджера связывания 𝑚𝑙𝑘, сообщения 𝑀 и 𝑀′ и соот-

20 ветствующие им подписи  и ′. На выходе алгоритм возвращает true в случае, если обе подписи были сформированы одним и тем же пользователем, и false – иначе. К таким свойствам схемы подписи, как невозможность подделки и анонимность автора подписи, добавляется следующее свойство безопасности: ключ менеджера связывания не должен позволять получить какую-либо информацию, с помощью которой можно идентифицировать автора подписи. Отзыв в схеме кольцевой подписи, основанный на идее контролируемой связываемости, организуется следующим образом. Проверяющий, в первую очередь, проверяет корректность подписи с помощью алгоритма Verify(), затем обращается к центру отзыва. Центр отзыва, владея ключом менеджера связывания 𝑚𝑙𝑘 и списком отзыва, который в нашем случае представляет собой список подписей, сформированных пользователями, чье право подписи было отозвано, проверяет подпись, сравнивая ее с каждой записью в списке с помощью алгоритма Link(). Если какая-либо из подписей в списке была сформирована данным пользователем, значит, он был отозван. Затем центр отзыва отправляет проверяющему ответ, был автор подписи отозван или нет. Данный подход представлен на рис. 2.1. Рисунок 2.1 – Отзыв со связыванием

21 Кольцевая подпись с реализованным свойством связываемости должна состоять из следующих блоков: 1) схема подписи DS=(KeyGens, Sign, Verify); 2) схема шифрования с открытым ключом AE=(KeyGene, Enc, Dec). 2.2.2 Алгоритм шифрования с открытым ключом с тестами на равенство Открытый ключ 𝑔𝑝𝑘 (group public key) содержит в себе открытый ключ шифрования 𝑒𝑝𝑘 и открытый ключ, необходимый для проверки подписи, 𝑠𝑝𝑘. Каждый новый участник кольца отправляет выпускающему центру значение 𝑓(𝑥𝑖 ), где 𝑓 – это односторонняя функция, примененная к секретному значению 𝑥𝑖 . Выпускающий центр в ответ отправляет подпись Sign(𝑠𝑘, 𝑓(𝑥𝑖 )) в качестве сертификата участника 𝑐𝑒𝑟𝑡. Тогда кольцевая подпись, сформированная участником при подписании сообщения 𝑀, будет дополнена элементом 𝑇 = Enc(𝑒𝑝𝑘, 𝑐𝑒𝑟𝑡). Для доказательства связанности двух подписей используется шифрование с открытым ключом с тестами на равенство (All-or-Nothing Public Key Encryption with Equality Tests, AoN-PKEET) [23], позволяющее назначенной сущности, владеющей лазейкой, по двум шифртекстам определить, зашифровывают ли они один и тот же открытый текст, при этом не раскрывая его содержания. Протокол шифрования с открытым ключом с тестами на равенство состоит из следующих алгоритмов: 1. PKEET-gen(1𝜆 ): Алгоритм генерации ключей шифрования, принимающий на вход параметр безопасности λ и генерирующий на выходе пару ключей (epk,esk). Пусть G – мультипликативная группа простого порядка p, g – ее образующая, H1, H2, H3 – хеш-функции: 𝐻1 :⁡{0, 1}∗ → {0, 1}𝑚+𝑑 ,⁡ 𝐻2 :⁡{0, 1}∗ → 𝒁𝑝 , 𝐻3 :⁡{0, 1}∗ → {0, 1}𝑘 . Алгоритм вычисляет закрытый ключ 𝑒𝑠𝑘 = (𝑥, 𝑦), где 𝑥, 𝑦 ∈ 𝒁𝑝 выбираются случайно, и соответствующий открытый ключ 𝑒𝑝𝑘 = (𝑔 𝑥 , 𝑔 𝑦 ).

22 2. PKEET-enc(𝑒𝑝𝑘, 𝑚): Алгоритм зашифрования, принимающий на вход открытый ключ 𝑒𝑝𝑘 и сообщение 𝑚 и возвращающий соответствующий шифртекст 𝑐. Шифртекст 𝐶 = (𝐶 (1) , 𝐶 (2) , 𝐶 (3) , 𝐶 (4) , 𝐶 (5) ) вычисляется следующим образом: 𝑢, 𝑣 ∈ 𝒁𝑝 выбираются случайно, 𝐶 (1) = 𝑔𝑢 ,⁡ 𝐶 (2) = 𝑔𝑣 ,⁡ 𝐶 (3) = 𝐻1 (𝑔𝑢𝑥 )𝑚||𝑢,⁡ 𝐶 (4) = 𝑔𝐻2 (𝑔 𝑣𝑦 ) , 𝐶 (5) = 𝐻3 (𝐶 (1) ||𝐶 (2) ||𝐶 (3) ||𝐶 (4) ||𝑚||𝑢). 3. PKEET-dec(𝑒𝑠𝑘, 𝑐): Алгоритм расшифрования, принимающий закрытый ключ 𝑒𝑠𝑘 и шифртекст 𝑐 и возвращающий соответствующее сообщение 𝑚. Шаги: 1) Вычисляется 𝑚′||𝑢′ = 𝐶 (3) 𝐻1 ((𝐶 (1) )𝑥 . 2) Проверяются условия: a. 𝐶 (1) = 𝑔𝑢′ b. 𝐶 (5) = 𝐻3 (𝐶 (1) ||𝐶 (2) ||𝐶 (3) ||𝐶 (4) ||𝑚′||𝑢′) В случае их выполнения 𝑚′ – расшифрованное сообщение. 4. PKEET-aut(𝑒𝑠𝑘): Принимает на вход закрытый ключ 𝑒𝑠𝑘 и возвращает лазейку 𝑡𝑘, используемую для тестов на равенство. Для пользователя, предъявившего закрытый ключ esk, возвращает токен 𝑇𝑖 = 𝑦𝑖 . 5. PKEET-com(С𝑖 , 𝐶𝑗 , 𝑇𝑖 , 𝑇𝑗 ): Принимает на вход два шифртекста С𝑖 , 𝐶𝑗 и токены 𝑇𝑖 и 𝑇𝑗 и возвращает true, в случае если они зашифровывают одно и то же нераскрываемое сообщение, и false – иначе. Алгоритм возвращает (2) 𝑇 (4) −𝐻2 ((𝐶𝑗 ) 𝑗 ⁡𝐶𝑗 𝑔 , и 0 иначе. 1 в случае, если (4) (2) 𝑇 ) 𝑖 𝐶𝑖 𝑔−𝐻2 ((𝐶𝑖 =

23 2.3 Применение отзыва со связыванием к схеме кольцевой подписи Для организации механизма отзыва представленная в разделе 1.3 схема кольцевой подписи должна быть дополнена механизмом обеспечения свойства связности. Для реализации этого свойства каждому участнику кольца выдается сертификат 𝑐𝑒𝑟𝑡. Подпись сообщения дополняется элементом 𝑇, представляющим собой данный сертификат, зашифрованный на ключе 𝑒𝑝𝑘. Затем при проверке сообщения проверяющий сначала проверяет корректность подписи, а затем обращается к центру отзыва, который, владея лазейкой 𝑡𝑘, сравнивает зашифрованный сертификат из подписи с зашифрованными сертификатами из списка отзыва с помощью теста на равенство и отправляет проверяющему ответ, содержится ли данный участник в списке отзыва. Однако в данном методе существует следующая проблема безопасности: автор подписи (нарушитель) может зашифровать и отправить не свой сертификат и таким образом пройти проверку при сравнении подписи со списком отзыва. Для решения данной проблемы предлагается воспользоваться одним из следующих подходов. Первый подход заключается в том, что центр отзыва вместо списка отозванных подписей будет хранить список подписей активных участников группы (белый список). Тогда при проверке подписи сертификат автора должен быть связан с одним из сертификатов из списка. В случае, если право подписи пользователя было отозвано, его подпись удаляется из списка. Преимуществом данного подхода является то, что он не требует дополнительных вычислений от автора подписи или проверяющего, основной нагрузкой является сравнение зашифрованных сертификатов, осуществляемое сервером. Однако для многих систем такой подход не является эффективным, так как количество активных участников зачастую в разы больше, чем количество участников, чье право подписи было отозвано. Таким образом, сервер будет вынужден сравнивать проверяемый сертификат с большим числом сертификатов, состоящих в белом списке.

24 В подобных системах возможно применение другого подхода. Для того, чтобы реализовать схему проверки с помощью списка отозванных подписей, необходимо дополнить подпись неинтерактивным доказательством с нулевым разглашением. Доказательство с нулевым разглашением позволяет одному участнику (доказывающей стороне) доказать другому участнику (проверяющей стороне) истинность утверждения, не раскрывая сущности доказательства. Неинтерактивное доказательство позволяет осуществить эту процедуру без взаимодействия сторон. Для этого может быть использован эвристический метод Фиата–Шамира, обозначаемый SoK (Signatures of knowledge) [24]. Тогда подпись участника должна быть дополнена доказательством 𝜋: 𝜋 ← 𝑆𝑜𝐾{(𝑥𝑖 , 𝑐𝑒𝑟𝑡):⁡𝑐𝑒𝑟𝑡 = Sign(𝑠𝑘, 𝑓(𝑥𝑖 )) ∧ 𝑇 = Enc(𝑒𝑝𝑘, 𝑐𝑒𝑟𝑡)}. Этот подход, в отличие от предыдущего, требует от автора подписи и проверяющего дополнительных вычислений для создания и проверки доказательства, однако позволяет эффективнее производить проверку центром отзыва за счет меньшего размера черного списка сертификатов в сравнении с белым списком. Можно сделать вывод, что в зависимости от параметров реализации системы и ее свойств может быть выбран один из предложенных методов. Например, для систем с конечными устройствами пользователей, обладающими малой вычислительной мощностью, нецелесообразно возлагать на эти устройства дополнительные вычислительные затраты, эффективнее будет воспользоваться подходом, основанным на белом списке. Таким образом, протокол кольцевой подписи на решетках с механизмом отзыва со связыванием состоит из следующих алгоритмов: 1) Алгоритм Gen. a. Для каждого участника группы генерируются ключи подписи (𝑠𝑝𝑘, 𝑠𝑠𝑘) с помощью алгоритма Ring-gen схемы кольцевой подписи.

25 b. Для каждого участника генерируются ключи шифрования (𝑒𝑝𝑘, 𝑒𝑠𝑘) с помощью алгоритма PKEET-gen шифрования с открытым ключом с тестами на равенство. c. Каждому участнику выдается сертификат 𝑐𝑒𝑟𝑡. d. Центру отзыва выдается ключ связывания 𝑡𝑘, который является лазейкой сгенерированной алгоритмом PKEET-aut(𝑒𝑠𝑘). e. В случае реализации схемы с белым списком формируется белый список, состоящий пы⁡{𝑐𝑒𝑟𝑡1 , … , 𝑐𝑒𝑟𝑡𝑙 }, из сертификатов зашифрованных с участников помощью груп- алгоритма PKEET-enc. В случае реализации схемы с черным списком, на данном этапе он остается пустым. 2) Алгоритм Sign. a. Для подписания сообщения 𝑚 участник 𝑖 сначала формирует подпись на ключе подписи 𝑠𝑠𝑘𝑖 и открытых ключах участников группы 𝐿 = {𝑠𝑝𝑘1 , … , 𝑠𝑝𝑘𝑙 } с помощью алгоритма Ring-sign: 𝑆 =⁡Ringsign(𝑚, 𝑠𝑠𝑘𝑖 , 𝐿). b. Затем автор подписи зашифровывает свой сертификат 𝑐𝑒𝑟𝑡𝑖 на открытом ключе шифрования 𝑒𝑝𝑘𝑖 с помощью алгоритма PKEETenc: 𝑇 =⁡PKEET-enc(𝑒𝑝𝑘, 𝑐𝑒𝑟𝑡). Итоговая подпись представляет собой пару: (𝑆, 𝑇). 3) Алгоритм Verify. a. Получатель проверяет подпись 𝑆 сообщения 𝑚 с помощью алгоритма проверки Ring-verify. Если алгоритм вернул значение 1, значит подпись корректна и в пункте b проверяется, не был ли автор подписи исключен из группы. Если алгоритм вернул 0, то подпись признается неверной и проверка завершается. b. После проверки корректности подписи проверяющий обращается к центру отзыва. Центр отзыва проверяет, не был ли автор исключен из списка участников.

26 Обладая лазейкой 𝑡𝑘, центр отзыва сравнивает зашифрованный сертификат 𝑇 со всеми зашифрованными сертификатами в списке отзыва с помощью теста на равенство PKEET-Com(𝑇, ⁡𝑇 ′ , 𝑡𝑘). В случае реализации с белым списком, если сертификат оказался связанным с одним из сертификатов в списке (алгоритм PKEET-Com вернул 1), то центр отзыва возвращает проверяющему значение 1, если же ни одна подпись из списка не соответствует проверяемой – 0. В случае черного списка наоборот: если алгоритм PKEET-Com признает, что сертификат связан хотя бы с одним сертификатом из списка, значит, пользователь был исключен из группы. 4) Алгоритм Revoke. a. В случае белого списка для отзыва права подписи у участника необходимо исключить его зашифрованный сертификат из списка отзыва. Поиск необходимого сертификата происходит путем сравнения сертификат 𝑇 участника со всеми сертификатами из белого списка с помощью теста на равенства PKEET-Com(𝑇, ⁡𝑇 ′ , 𝑡𝑘). b. В случае черного списка зашифрованный сертификат 𝑇 просто добавляется в список отзыва. На рис. 2.2 представлена схема взаимодействия субъектов описанной кольцевой подписи: участников группы, проверяющих и центра отзыва, указаны открытые и закрытые ключи подписи и шифрования, которыми они владеют, и алгоритмы формирования и проверки подписи, которыми они оперируют, а также данные, которыми они друг с другом обмениваются.

27 Рисунок 2.2 – Схема взаимодействия участников в разработанной схеме 2.4 Повышение безопасности и эффективности механизма отзыва Так как данный механизм отзыва основывается на участии в процессе проверки подписи онлайн-сервера, он может быть подвержен атакам по сети со стороны злоумышленников. В случае компрометации центра отзыва злоумышленник получит возможность сравнивать любые две подписи и определять, были ли они сформированы одним и тем же пользователем. Для обеспечения безопасности в случае компрометации центра отзыва предлагается применить метод разделения ключа связывания между несколькими центрами связывания. (𝑡, 𝑛)-пороговая схема разделения секрета, предложенная А. Шамиром в работе [25], позволяет распределить секрет 𝑠 между 𝑛 участниками таким образом, чтобы для восстановления секрета 𝑠 необходимо было взаимодействие как минимум 𝑡 участников. Тогда для сравнения подписей центр отзыва должен будет связаться минимум с 𝑡 центрами связывания, чтобы воспользоваться ключом связывания 𝑡𝑘. Для реализации данной идеи предлагается использовать пороговое шифрование с открытым ключом с тестами на равенство (Threshold AoN-PKEET), что позво-

28 лит достичь снижения требуемого уровня доверия к центру отзыва и повысить надежность схемы. (𝑡, 𝑛)-пороговая схема А. Шамира позволяет разделить некоторый секрет 𝐷 (в нашем случае – ключ связывания) на 𝑛 долей 𝐷1 , … , 𝐷𝑛 таким образом, чтобы выполнялись следующие свойства: − знания любого набора из 𝑡 или более долей 𝐷𝑖 достаточно для вычисления 𝐷; − знания любого набора из (𝑡 − 1) или менее долей 𝐷𝑖 не позволяет раскрыть никакую информацию о значении 𝐷. Данная (𝑡, 𝑛)-пороговая схема разделения ключа основывается на задаче интерполяции полиномов. Для заданных 𝑡 точек (𝑥1 , 𝑦𝑛 ), … , (𝑥𝑡 , 𝑦𝑡 ) существует ровно один полином 𝑞(𝑥) степени 𝑡 − 1 такой, что 𝑞(𝑥𝑖 ) = 𝑦𝑖 для 1 ≤ 𝑖 ≤ 𝑡. Для разделения секрета 𝐷 на доли 𝐷𝑖 , выбирается случайный полином степени 𝑡 − 1: 𝑞(𝑥) = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑡−1 𝑥 𝑡−1 , в котором 𝑎0 = 𝐷 и вычисляются: 𝐷1 = 𝑞(1), … , 𝐷𝑖 = 𝑞(𝑖), … , 𝐷𝑛 = 𝑞(𝑛). При наличии любого набора из 𝑡 значений 𝐷𝑖 можно найти коэффициенты 𝑞(𝑥) с помощью метода интерполяции, после чего оценить 𝐷 = 𝑞(0). При этом 𝑡 − 1 значений недостаточно для вычисления 𝐷. Предлагаемая к использованию пороговая схема T-AoN-PKEET отличается от классической схемы AoN-PKEET следующими алгоритмами: − DKAut(𝑡𝑘, 𝑡, 𝑛): принимает на вход лазейку 𝑡𝑘, порог 𝑡 и общее число разделения 𝑛 и возвращает разделение (𝑡𝑘𝑖 ), 1 < 𝑖 < 𝑛 такое, что для восстановления 𝑡𝑘 требуется взаимодействие минимум 𝑡 сущностей. − TShare(𝑇, 𝑇′, 𝑡𝑘𝑖 ): принимает на вход два шифртекста⁡𝑇 и , 𝑇′ и долю лазейки 𝑡𝑘𝑖 и возвращает соответствующие доли 𝐶 и 𝐶′ для проведения теста на равенство. − TSCom({𝐶𝑖 , 𝐶′𝑖 }𝑡≤𝑖≤𝑛 ): принимает на вход наборы долей {𝐶𝑖 , 𝐶′𝑖 }𝑡≤𝑖≤𝑛 двух шифртекстов и возвращает true, в случае если они

29 зашифровывают одно и то же нераскрываемое сообщение, и false – иначе. Тогда проверка подписи центром отзыва с учетом применения механизма разделения лазейки и хранения токенов в списке отзыва проводится в соответствии со следующим алгоритмом. CheckStatus(RL, L, 𝜎): Принимая на вход список отзыва RL, набор центров связывания L и подпись 𝜎, алгоритм определяет статус участника, являющегося автором подписи. Для этого он связывается с 𝑡 центрами связывания 𝐿𝑖 ∈ 𝐿 с помощью алгоритма TShare, получая от каждого соответствующие доли 𝐶𝑖 токена проверяемого участника, после чего применяет к данному набору долей алгоритм TSCom, чтобы восстановить итоговый токен участника. Если данный токен состоит в списке отзыва, алгоритм возвращает true, иначе – false. Взаимодействие участников схемы при проверке подписи представлено на рис. 2.3. Рисунок 2.3 – Схема с разделением ключа связывания

30 Такой метод разделения ключа связывания между несколькими центрами связывания позволяет требовать меньшего уровня доверия к центру отзыва, чем в случае схемы с единым сервером. Другим недостатком системы является то, что время проверок, производимых центром отзыва, линейно зависит от размера списка отзыва, то есть имеет сложность O(R), где R – число пользователей в списке. Чтобы время проверки не зависело от размера списка, процедура сравнения двух подписей может быть заменена процедурой формирования токена. То есть алгоритм Com(𝑇, ⁡𝑇 ′ , 𝑡𝑘) модифицируется таким образом, чтобы вместо проведения теста на равенство для двух шифртекстов он возвращал значение, вычисляемое из заданного шифртекста 𝑇 и лазейки 𝑡𝑘, то есть токен участника tCom(𝑇, ⊥, 𝑡𝑘). Тогда в списке отзыва вместо подписей будут храниться такие токены в виде хеш-таблицы, что при проверке за время O(1) можно будет определить, принадлежит ли проверяемый токен списку. При этом сам токен не раскрывает никакой информации об авторе подписи. При отзыве права подписи участник остается анонимным, так как для вычисления токена требуется только его подпись и ключ связывания. 2.5 Выводы В данной главе рассмотрены варианты реализации отзыва права подписи в кольцевой схеме, произведено сравнение механизмов отзыва и выбран предпочтительный – механизм отзыва со связыванием. Предложено два варианта применения выбранного метода: с белым и черным списками пользователей. В результате разработана схема кольцевой подписи на решетках с отзывом со связыванием, использующая шифрование с открытым ключом с тестами на равенство для реализации свойства связываемости. В следующей главе будет приведена программная реализация и оценка разработанной схемы.

31 3. РЕАЛИЗАЦИЯ СХЕМЫ КОЛЬЦЕВОЙ ПОДПИСИ НА РЕШЕТКАХ С ОТЗЫВОМ СО СВЯЗЫВАНИЕМ Для оценки влияния механизма отзыва на эффективность схемы было решено осуществить программную реализацию разработанной схемы подписи с отзывом со связыванием, а также схемы, использующей базовый подход, – перевыпуск ключей пользователей при отзыве права подписи у одного из участников. Необходимо протестировать и замерить время работы всех реализованных алгоритмов схемы подписи. 3.1 Программная реализация схемы В разрабатываемой системе можно выделить два основных компонента: − протокол кольцевой подписи на решетках; − протокол шифрования с открытым ключом с тестами на равенство. В связи с тем, что реализуемые алгоритмы предполагают работу с такими математическими структурами, как решетки, было решено использовать для разработки программы продукт, содержащий встроенные модули для удобной работы с ними. В качестве такого продукта был выбран Sage [26] – математическое программное обеспечение с открытыми исходными кодами для исследовательской работы в таких областях, как алгебра, геометрия, теория чисел, криптография и других. Sage позволяет создавать скрипты на языке Python, которые затем обрабатываются на локальном сервере Sage. В ходе выполнения практической части работы была написана программа на языке Python [27], реализующая алгоритмы протокола кольцевой подписи на решетках с отзывом со связыванием. В приложении приведен исходный код программы с комментариями. В качестве хеш-функции, используемой при генерации и проверки подписи, а также при зашифровании и расшифровании сертификата, была использована хеш-функция SHA с длиной хеш-значения 512 бит, определенная в модуле hashlib.

32 Для получения случайной матрицы при генерации ключей схемы подписи на решетках была использована функция Sage random_matrix(), которая позволяет задавать размерность матрицы и множество значений ее элементов. Для задания множества была использована функция Zmod(q), с помощью которой можно задать множество классов вычетов по модулю q. При генерации подписи для выборки векторов y в соответствии с дискретным нормальным распределением был использован модуль sage.stats.distributions.discrete_gaussian_lattice, в котором определена функция DiscreteGaussianDistributionLatticeSampler, позволяющая задать множество значений выборки (в данной работе –⁡𝐙𝑚 ) и среднеквадратичное отклонение. Для генерации ключей и сертификатов пользователей использовалась функция random.randint, определенная в модуле random и позволяющая задавать диапазон генерируемого целого числа. Для вычисления мультипликативно обратного элемента в алгоритме сравнения двух зашифрованных сообщений была использована функция Sage inverse_mod. В ходе выполнения работы были разработаны две системы. Первая – описанная в разделе 1.3 схема подписи на решетках, которая была дополнена алгоритмом отзыва права подписи, осуществляемого путем повторной генерации (перевыпуска) открытых и закрытых ключей участников группы за исключением удаленного. Вторая система является реализацией описанной в разделе 2.3 схема подписи на решетках с отзывом со связыванием, в качестве списка отзыва в которой используется белый список участников группы. Структура разработанной программы соответствует описанной структуре схемы подписи. Алгоритмы генерации ключей, формирования и проверки подписи и отзыва права подписи реализованы в функциях setup(), sign(), verify(), revoke(). Каждая из этих функций вызывает функции, реализующие соответствующие алгоритмы схемы подписи и шифрования. В функции setup() генерируются открытые (RS_vk_T, RS_vk_A) и закрытые (RS_sk) ключи подписи для каждого участника с помощью функции

33 RS_key_gen(). С помощью функции PKEET_key_gen происходит генерация открытых (PKEET_p) и закрытых (PKEET_sk) ключей шифрования пользователей. Затем генерируются сертификаты пользователей (CERT) и с помощью функции PKEET_enc происходит их зашифрование. Зашифрованные сертификаты пользователей составляют белый список группы (WL), в котором также указывается, является ли пользователь активным участником. Функция sign() для сообщения msg вызывает функцию формирования кольцевой подписи RS_sign, передавая ей открытые ключи всех участников группы (RS_vk_A) и закрытый ключ автора подписи (RS_sk[j]). Затем вызывается функция PKEET_enc, зашифровывающая сертификат автора подписи (CERT[j]) на его открытом ключе шифрования (PKEET_pk[j]). Полученная подпись (z, c) и зашифрованный сертификат (c2, c4) объединяются в кортеж и возвращаются в качестве результата функции. В функция verify() происходит проверка корректности подписи (z, c) сообщения msg с помощью функции RS_verify, принимающей на вход также открытые ключи участников группы. Затем проверяется, не исключен ли автор подписи из белого списка участников. Для этого зашифрованный сертификат (c2, c4) передается функции PKEET_com, которая сравнивает его с каждым сертификатом из списка. Если сертификат окажется связан с одним из сертификатов в списке, автор подписи признается активным. Функция возвращает 1 в случае, если оба этапа проверки дают положительный результат. Функция revoke() осуществляет поиск зашифрованного сертификата пользователя, которого необходимо исключить, в белом списке с помощью функции PKEET_com, проверяющей, связаны ли два сертификата, после чего удаляет его из списка. Для измерения времени исполнения программы была использована функция time.time из модуля time, возвращающая время в секундах, прошедшее с начала эпохи Unix.

34 3.2 Тестирование и оценка разработанной системы Для проведения тестирования разработанной системы были использованы параметры в соответствии с рекомендациями в работе Любашевского [3], на которой основана реализуемая в системе схема кольцевой подписи: − модуль 𝑞 ≥ 3 – простое число; − размерность матрицы: 𝑛 ∈ 𝐙 ≥ 64, 𝑚 ≈ 64 + 𝑛 log 𝑞 / log 3; − параметры нормального распределения: среднеквадратичное отклонение 𝜎 ≈ 36⁡𝑘⁡√𝑚. Тестирование разработанной программы проводилось для 𝑛 = 64, 𝑞 = 61, 𝑚 = 239, 𝑘 = 80. Параметры p (порядок мультипликативной группы G) и g (образующая группы G) были сгенерированы в функции PKEET_param_gen(). Для поиска образующей группы был использован следующий критерий: Элемент 𝑎 является образующей группы тогда и только тогда, когда 𝑎(𝑝−1)/𝑞 ≢ 1(𝑚𝑜𝑑⁡𝑝) для всех простых 𝑞 – делителей 𝑝 − 1. Таким образом были сгенерированы параметры: p = 1341900549555124873064130204963147708769253581301, g = 149225785016883513407046604525768831537615089201297848785381 91291561205808667455064901451426550236353695837369547299448900196564 13604867081875127370443086. Количество участников кольца изменялось от 2 до 2000. Для тестирования производился последовательный запуск скриптов реализующих генерацию ключей, подписывание сообщения, проверки подписи и отзыва права подписи для базовой схемы с перевыпуском ключей, и для разработанной схемы с отзывом со связыванием. В табл. 3.1–3.4 представлены результаты замеров времени работы перечисленных алгоритмов в зависимости от числа участников. Для каждого значения числа участников было произведено по пять тестовых запусков, в таблицы были внесены средние значения.

35 Таблица 3.1 – Сравнение времени генерации ключей Число участников группы 2 10 50 100 500 1000 1500 2000 Время генерации ключей в Время генерации ключей в схеме с перевыпуском, с разработанной схеме 0,129 0,129 0,663 0,692 3,265 3,461 6,676 6,970 37,085 39,705 74,302 77,008 108,410 111,089 168,285 173,511 Таблица 3.2 – Сравнение времени формирования подписи Число участников группы 2 10 50 100 500 1000 1500 2000 Время формирования подписи Время формирования подписи в схеме с перевыпуском, с в разработанной схеме, с 1,038 1,909 3,554 5,428 22,265 37,704 59,769 77,252 1,009 1,886 3,613 5,684 23,736 38,737 61,540 79,894 Таблица 3.3 – Сравнение времени проверки подписи Число участ- Время проверки подписи Время проверки подписи в разников группы в схеме с перевыпуском, с работанной схеме, с cо стороны cо стороны ценпроверяющего тра отзыва 2 0,007 0,007 0,001 10 0,024 0,022 0,004 50 0,089 0,093 0,019 100 0,187 0,179 0,035 500 0,971 0,986 0,173 1000 2,041 2,182 0,443 1500 2,763 2,833 0,537 2000 3,860 3,893 0,742

36 Таблица 3.4 – Сравнение времени отзыва права подписи Число участников группы 2 10 50 100 500 1000 1500 2000 Время отзыва права подписи в схеме с перевыпуском, с 0,129 0,680 3,208 7,811 36,419 75,296 129,579 161,415 Время отзыва права подписи в разработанной схеме, с 0,001 0,004 0,019 0,037 0,188 0,380 0,542 0,883 На рис. 3.1–3.4 представлены графики зависимости времени работы алгоритмов от числа участников группы, построенные по соответствующим значениям из таблиц. Рисунок 3.1 – Графики зависимости времени генерации ключей от числа участников Рисунок 3.2 – Графики зависимости времени формирования подписи от числа участников

37 Рисунок 3.3 – Графики зависимости времени проверки подписи от числа участников Рисунок 3.4 – Графики зависимости времени отзыва права подписи от числа участников Полученные экспериментальные данные подтверждают теоретические оценки влияния механизма отзыва со связыванием на эффективность схемы кольцевой подписи. Наибольшее влияние проявляется на этапе генерации ключей (рис 3.1), так как время выполнения этого алгоритма зависит от размера группы: для каждого из них выпускаются ключи шифрования и сертификаты. Влияние, оказываемое на формирование подписи, является незначительным, так как на этом этапе к базовому алгоритму добавляется только зашифрование сертификата, размер которого (а соответственно и время зашифрования) не зависит от размера группы. При проверке подписи со стороны проверяющего не требуется никаких дополнительных вычислений, следовательно, время проверки не изменилось в

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

39 ЗАКЛЮЧЕНИЕ В ходе выполнения выпускной квалификационной работы решена задача организации отзыва права подписи в схеме кольцевой подписи на решетках. В рамках работы проведен анализ свойств кольцевых подписей, выбрана базовая схема кольцевой подписи на решетках, не имеющая механизма отзыва права подписи у участников. Осуществлен обзор существующих методов организации отзыва в групповых подписях, их сравнение по критериям влияния на эффективность схемы кольцевой подписи, определяемую объемом вычислений, требуемых от каждого субъекта схемы, и размером подписи. В результате сравнения выбран механизм отзыва, основанный на свойстве контролируемой связываемости, позволяющий производить отзыв права подписи без дополнительных вычислений для участников группы за счет добавления в схему центра отзыва, который является онлайн-сервером для проверяющих. Влияние выбранного механизма на размер подписи и на объем вычислений, производимых при формировании и проверке подписи, не зависит от числа участников группы. Для применения данного механизма выбранная схема кольцевой подписи была дополнена алгоритмом сравнения подписей с помощью протокола AoNPKEET, реализующего схему шифрования с открытым ключом с тестами на равенство. Предложены два варианта применения механизма в зависимости от характеристик системы – с черным и белым списками. Список отзыва хранится центром отзыва и содержит сертификаты пользователей, зашифрованные с помощью протокола AoN-PKEET. При проверке подписи зашифрованный сертификат, являющийся одним из элементов подписи, сравнивается со всеми подписями в списке отзыва с помощью тестов на равенство. Для отзыва права подписи у участника группы его зашифрованный сертификат исключается из списка отзыва (в случае белого списка) или добавляется в него (в случае черного списка). Описаны способы повышения безопасности и эффективности схемы за счет разделения ключа связывания, которым владеет центр отзыва, между не-

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

41 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Rivest R. L. How to leak a secret // International Conference on the Theory and Application of Cryptology and Information Security. – Springer, Berlin, Heidelberg, 2001. – P. 552-565. 2. Gentry C. Trapdoors for hard lattices and new cryptographic constructions // Proceedings of the fortieth annual ACM symposium on Theory of computing. – ACM, 2008. – P. 197-206. 3. Lyubashevsky V. Lattice signatures without trapdoors // Annual International Conference on the Theory and Applications of Cryptographic Techniques. – Springer, Berlin, Heidelberg, 2012. – P. 738-755. 4. Brakerski Z., Kalai Y. T. A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model // IACR Cryptology ePrint Archive. – 2010. – Vol. 2010. – P. 86. 5. Cayrel P. L. et al. A lattice-based threshold ring signature scheme // International Conference on Cryptology and Information Security in Latin America. – Springer, Berlin, Heidelberg, 2010. – P. 255-272. 6. Wang C., Wang H. A new ring signature scheme from NTRU lattice // 2012 Fourth International Conference on Computational and Information Sciences. – IEEE, 2012. – P. 353-356. 7. Wang S. Lattice-based ring signature scheme under the random oracle model // International Journal of High Performance Computing and Networking. – 2018. – Vol. 11. – №. 4. – P. 332-341. 8. Ateniese G. Quasi-efficient revocation of group signatures // International Conference on Financial Cryptography. – Springer, Berlin, Heidelberg, 2002. – P. 183-197. 9. Bresson E., Stern J. Efficient revocation in group signatures // International Workshop on Public Key Cryptography. – Springer, Berlin, Heidelberg, 2001. – P. 190-206.

42 10. Boneh D., Shacham H. Group signatures with verifier-local revocation // Proceedings of the 11th ACM conference on Computer and communications security. – ACM, 2004. – P. 168-177. 11. Camenisch J., Lysyanskaya A. Dynamic accumulators and application to efficient revocation of anonymous credentials // Annual International Cryptology Conference. – Springer, Berlin, Heidelberg, 2002. – P. 61-76. 12. Slamanig D. Linking-based revocation for group signatures: a pragmatic approach for efficient revocation checks // International Conference on Cryptology in Malaysia. – Springer, Cham, 2016. – P. 364-388. 13. Александрова Е. Б., Рехвиашвили И. Ш. Организация отзыва для схемы кольцевой подписи // Проблемы информационной безопасности. Компьютерные системы. – 2019. – №. 2. – P. 80-85. 14. Ростовцев А. Г., Маховенко Е. Б. Теоретическая криптография – СПб.: АНО НПО «Профессионал, 2005. – 479 с. 15. Micciancio D. Lattice-based cryptography // Encyclopedia of Cryptography and Security. – 2011. – P. 713-715. 16. Nguyen P. Q., Stern J. The two faces of lattices in cryptology // International Cryptography and Lattices Conference. – Springer, Berlin, Heidelberg, 2001. – P. 146-180. 17. Boneh D., Boyen X., Shacham H. Short group signatures // Annual international cryptology conference. – Springer, Berlin, Heidelberg, 2004. – P. 41-55. 18. Brickell E., Li J. Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities // Proceedings of the 2007 ACM workshop on Privacy in electronic society. – 2007. – P. 21-30. 19. Au M. H. Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems // Cryptographers Track at the RSA Conference. – Springer, Berlin, Heidelberg, 2009. – P. 295-308. 20. Nakanishi T., Funabiki N. A short verifier-local revocation group signature scheme with backward unlinkability // IEICE transactions on fundamentals of elec-

43 tronics, communications and computer sciences. – 2007. – Vol. 90. – №. 9. – P. 1793-1802. 21. Zhou S., Lin D. Shorter verifier-local revocation group signatures from bilinear maps // International Conference on Cryptology and Network Security. – Springer, Berlin, Heidelberg, 2006. – P. 126-143. 22. Blazy O. Non-interactive plaintext (in-) equality proofs and group signatures with verifiable controllable linkability // Cryptographers’ Track at the RSA Conference. – Springer, Cham, 2016. – P. 127-143. 23. Tang Q. Public key encryption supporting plaintext equality test and user‐specified authorization // Security and Communication Networks. – 2012. – Vol. 5. – №. 12. – P. 1351-1362. 24. Fiat A., Shamir A. How to prove yourself: Practical solutions to identification and signature problems // Conference on the Theory and Application of Cryptographic Techniques. – Springer, Berlin, Heidelberg, 1986. – P. 186-194. 25. Shamir A. How to share a secret // Communications of the ACM. – 1979. – Vol. 22. – №. 11. – P. 612-613. 26. Sage Reference Manual v9.0 [Электронный https://doc.sagemath.org/html/en/reference/index.html. – ресурс]. (дата URL: обращения: 15.11.2019). 27. Python 2.7.17 Documentation [Электронный ресурс]. https://docs.python.org/2/index.html. – (дата обращения: 15.11.2019). URL:

44 Приложение. Исходный код разработанной программы from sage.all import * from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler import random import hashlib import time # число участников кольца l = 500 # параметры кольцевой подписи n = 64 m = 239 q = 61 k = 80 M = 2.7 # параметры нормального распределения sd = 300 # среднеквадратичное отклонение eta = 1.1 D = DiscreteGaussianDistributionLatticeSampler(ZZ**m, sd) # параметры шифрования p = 1341900549555124873064130204963147708769253581301 # порядок мультипликативной группы G g = 1492257850168835134070466045257688315376150892012978487853819129156120580 8667455064901451426550236353695837369547299448900196564136048670818751273 70443086# образующая группы G # хеш-функция, используемая при шифровании def H2(x): h = int(hashlib.sha512(str(x)).hexdigest(), 16) % p return h # генерация параметров шифрования def PKEET_param_gen(): q1 = 3*p+1 h = random.randint(1, p) g = pow(h, (q1-1/p), q1) return 1 # генерация ключей шифрования # Y[] – закрытые ключи участников кольца # G_Y[] – открытые ключи участников кольца def PKEET_key_gen(): Y = [] G_Y = [] i = 0 while i < l: y = random.randint(1, p) g_y = pow(g, y, p) Y.append(y) G_Y.append(g_y) i = i + 1

45 return (Y, G_Y) # зашифрование сообщения msg на открытом ключе g_y # шифртекст – (C2, C4) def PKEET_enc(msg, g_y): v = random.randint(1, p) C2 = pow(g, v, p) C4 = pow(g, H2(pow(g_y, v, p)) + msg, p) return (C2, C4) # тестирование на равенство шифртекстов (Ci2, Ci4) и (Cj2, Cj4) # Ti, Tj – ключ связывания def PKEET_com(Ci2, Ci4, Cj2, Cj4, Ti, Tj): equal = 0 gi = pow(g, H2(pow(Ci2, Ti, p)), p) gi_inv = inverse_mod(gi,p) gj = pow(g, H2(pow(Cj2, Tj, p)), p) gj_inv = inverse_mod(gj,p) if ((Ci4 * gi_inv) % p == (Cj4 * gj_inv) % p) : equal = 1 return equal # белый список # каждая запись состоит из следующих элементов: # (c2, c4) – зашифрованный сертификат # T – ключ связывания # 0/1 – участник активен или неактивен Wight_List = [] RS_sk = [] # закрытые ключи схемы подписи # открытые ключи схемы подписи (RS_vk_T, RS_vk_A) RS_vk_T = 0 RS_vk_A = [] PKEET_sk = [] # закрытые ключи схемы шифрования PKEET_pk = [] # открытые ключи схемы шифрования CERT = [] # сертификаты пользователей # генерация сертификатов def CERT_gen(): cert = [] i = 0 while i < l: cert.append(random.randint(1, p)) i = i + 1 return cert # создание белого списка, состоящего из зашифрованных сертификатов def WL_gen(): WL = [] i = 0 while i < l: c2, c4 = PKEET_enc(CERT[i], PKEET_pk[i]) el = [c2, c4, PKEET_sk[i], 1] WL.append(el) i = i + 1 return WL # хеш-функция, используемая при формировании подписи def H(x):

46 h = int(hashlib.sha512(str(x)).hexdigest(), 16) out = vector([0]*k, Zmod(q)) for i in range(0, k) : out[i] = h%3 h /= 3 i += 1 return out # генерация ключей подписи # A[] – открытые ключи участников кольца # S[] – закрытые ключи участников кольца def RS_key_gen(): T = random_matrix(Zmod(q), n, k) S = [] A = [] i = 0 while i < l: S.append(matrix(Zmod(q), m, k, lambda i, j: choice(range(0, 3)))) A.append(S[i].solve_left(T)) i = i + 1 sk = S vk = (A, T) return (sk, vk) # генерация подписи # A[] - открытые ключи участников кольца # Sj - секретный ключ автора подписи # (z,c) - подпись def RS_sign(msg, A, Sj, j): count = 0 while True: count+=1 if count == 1e3: # ограничение на количество запусков return (0, 0) y = [] z = [] Ay = 0 i = 0 while i < l: y.append(vector(D())) Ay = Ay + A[i] * y[i].change_ring(Zmod(q)) i = i + 1 c = H((Ay, A, msg)) i = 0 while i < l: if i != j: z.append(y[i]) else: Sc = Sj.change_ring(ZZ)*c.change_ring(ZZ) z.append(Sc + y[i]) i = i + 1 pxe = float(-2*z[j]*Sc + (Sc.norm())**2) if random.random() < exp(pxe/(2*(sd**2)))/M: return (z,c) # проверка подписи # (z,c) – подпись, A[] - открытые ключи участников кольца

47 def RS_verify(msg, z, c, A, T): i = 0 ok_norm = 1 Az = 0 while i < l: if z[i].norm() > eta*sd*sqrt(m): ok_norm = 0 Az = Az + A[i] * z[i] i = i + 1 if ok_norm == 1 and c == H((Az-T*c, A, msg)): return 1 return 0 # генерация ключей подписи и шифрования, сертификатов # формирование белого списка def setup(): global RS_sk global RS_vk_T global RS_vk_A global PKEET_sk global PKEET_pk global CERT global Wight_List start = time.time() RS_sk, RS_vk = RS_key_gen() # ключи подписи пользователей RS_vk_A = RS_vk[0] RS_vk_T = RS_vk[1] PKEET_sk, PKEET_pk = PKEET_key_gen() # ключи шифрования пользователей CERT = CERT_gen() Wight_List = WL_gen() end = time.time() print "Время генерации: ", (end-start) return 0 # формирование подписи сообщения msg, состоящей из подписи (z, c) # и зашифрованного сертификата (c2, c4) def sign(msg, j): global RS_sk global RS_vk_A global CERT global PKEET_pk start = time.time() z, c = RS_sign(msg, RS_vk_A, RS_sk[j], j) c2, c4 = PKEET_enc(CERT[j], PKEET_pk[j]) cc = (z, c, c2, c4) end = time.time() print "Время подписывания: ", (end-start) return cc # проверка корректности подписи (z, c) сообщения msg # и проверка наличия сертификата в списке отзыва def verify(msg, z, c, c2, c4, j): global RS_vk_A global RS_vk_T global PKEET_sk start = time.time() ver_sign = 1 if (RS_verify(msg, z, c, RS_vk_A, RS_vk_T) != 1):

48 ver_sign = 0 end = time.time() print "Время проверки проверяющим: ", (end-start) #print "ver_sign", ver_sign start = time.time() ver_cert = 0 for i in Wight_List: if ((PKEET_com(c2, c4, i[0], i[1], PKEET_sk[j], i[2]) == 1) and (i[3] == 1)) : ver_cert = 1 end = time.time() print "Время проверки центром отзыва: ", (end-start) #print "ver_cert", ver_cert return ver_sign*ver_cert # исключение сертификата (c2, c4) из списка отзыва def revoke(c2, c4, j): start = time.time() global Wight_List global PKEET_sk for i in Wight_List: if (PKEET_com(c2, c4, i[0], i[1], PKEET_sk[j], i[2]) == 1) : i[3] = 0 end = time.time() print "Время отзыва: ", (end-start) return 0 # реализация базовой схемы с перевыпуском ключей при отзыве права подписи def basic(): start = time.time() sk, vk = RS_key_gen() end = time.time() print "Время генерации: ", (end-start) start = time.time() z, c = RS_sign("new world", vk[0], sk[0], 0) end = time.time() print "Время подписывания: ", (end-start) start = time.time() RS_verify("new world", z, c, vk[0], vk[1]) end = time.time() print "Время проверки: ", (end-start) start = time.time() sk, vk = RS_key_gen() end = time.time() print "Время отзыва: ", (end-start) return 0 setup() # генерация ключей z, c, c2, c4 = sign("new world", 1) # формирование подписи verify ("new world", z, c, c2, c4, 1) # проверка подписи revoke(c2, c4, 1) # отзыв права подписи print verify ("new world", z, c, c2, c4, 4) # повторная проверка подписи basic() # схема с перевыпуском ключей

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

Рецензия от Ирина Рехвиашвили

Рецензия ведущего научного сотрудника НИО АО "НИИ "Рубин", д. т. н., доцента А. Н. Буренина на выпускную квалификационную работу.

больше 3 лет назад

Отзывы:

Авторизуйтесь, чтобы оставить отзыв