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

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

Инициализация системы. На этапе инициализации голосования выполняются следующие криптографические операции:

• Выработка ключевой пары валидатора для выдачи и проверки слепой подписи, как наиболее стойкий и рекомендуемый академическим сообществом для процедуры анонимизации в системах электронного голосования. В настоящий момент системой поддерживается алгоритмы слепой подписи на эллиптических кривых и на базе алгоритма шифрования RSA. В проводимом голосовании использовался алгоритм выдачи и проверки слепой подписи на базе алгоритма шифрования RSA с длиной ключа 4096 бит.
• Выработка общего открытого ключа шифрования. Для большей безопасности в процессе выработки ключа используется сразу два криптографических алгоритма: протокол DKG Pedersen 91 распределенной выработки ключа и протокол разделения ключа Шамира. Выработка ключа осуществляется как участниками, обладающими техническими средствами, позволяющими контролировать непосредственно ноды сети и сервера подсчета, так и участниками, которые являются хранителями ключей, записанных на внешние носители. Итогом работы двух этих алгоритмов является общий открытый ключ шифрования бюллетеней. Далее мы более подробно рассмотрим процедуру выработки этого ключа.

Предоставление доступа к бюллетеню. На данном этапе работают следующие механизмы:

• Выработка ключевой пары электронной подписи на устройстве избирателя по ГОСТ Р 34.10-2012
• Выработка слепой подписи для маскированного открытого ключа избирателя для удостоверения и последующей проверки его права принять участие в голосовании. В настоящий момент механизм базируется на алгоритме шифрования RSA. Подробно механизм анонимизации рассматривается в отдельной статье.

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

• Шифрование бюллетеня по схеме Эль-Гамаля на эллиптических кривых. Данная схема используется в протоколе, поскольку обладает свойством гомоморфности по сложению, что позволяет получить результаты голосования без расшифрования каждого бюллетеня.
• Доказательство с нулевым разглашением Disjunctive Chaum-Pedersen range proof используется для доказательства корректности содержимого бюллетеня без его расшифрования. Данный механизм мы разберем подробно в следующей статье.
• Электронная подпись зашифрованного бюллетеня по ГОСТ Р 34.10-2012.

Подсчет итогов. На этапе подведения итогов выполняется:

• Гомоморфное сложение зашифрованных бюллетеней.
• Предварительное частичное расшифрование итогового суммированного бюллетеня частями закрытого ключа участниками, контролирующими отдельные ноды и серверы подсчета с получением шифротекстов от каждого участника;
• Сборка закрытого ключа в Избирательной комиссии и частичное расшифрование итогового суммированного бюллетеня собранным ключом.
• Окончательное суммирование шифротекстов и получение итогов подсчета.
• Выработка и проверка доказательства с нулевым разглашением Chaum-Pedersen proof. Используется для доказательства корректности расшифрования итогового суммированного бюллетеня. Данный механизм мы разберем подробно в следующей статье.

Аудит. На данном этапе могут быть выполнены проверки корректности всех этапов протокола, и в этой статье мы подробнее рассмотрим возможные проверки.

Давайте разберем криптографические механизмы подробнее.

Блокчейн-платформа

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

Ниже на рисунке приведена упрощенная целевая схема размещения блокчейн-платформы.



Размещение и резервирование узлов блокчейна происходит в географически распределенных ЦОД ПАО «Ростелеком». При этом ответственность за «атомарный» набор компонентов, участвующий в хранении всех данных голосования, может быть возложена на избирательную комиссию или различные институты общественного наблюдения.

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

Список участников может со временем меняться – от минимального на этапе запуска системы в промышленную эксплуатацию, до достаточно широкого и полностью децентрализованного по мере развития системы. При этом всегда существует возможность размещения набора компонентов вне ЦОД.

В качестве блокчейн-платформы используется отечественное решение Waves Enterprise. Транзакции и блоки подписываются по ГОСТ Р 34.10-2012.

Выработка ключей шифрования

Общий открытый ключ шифрования бюллетеней вырабатывается с применением двух криптографических алгоритмов: протокол DKG Pedersen 91 распределенной выработки ключа и протокол разделения ключа Шамира. На базе каждого из этих алгоритмов вырабатывается “промежуточный” открытый ключ. Затем эти два ключа комбинируются в один общий.

Схема сборки ключа приведена ниже на рисунке.



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

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

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

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

Участниками процедуры распределенной выработки ключей являются n серверов подсчета голосов, о которых мы писали ранее в обзорной статье. Все операции взаимодействия серверов подсчета, как промежуточные, так и конечные фиксируются в блокчейне, а, следовательно, прозрачны и проверяемы. В системе реализована пороговая схема «k из n», то есть при расшифровании данных не требуется участие всех n сторон, формировавших открытый ключ DKG, достаточно меньшего числа участников k. Это позволяет расшифровать результаты голосования, даже если n-k серверов подсчета недоступно, либо их закрытые ключи утрачены.

Для формирования открытого ключа используется алгоритм DKG (Distributed Key Generation), описанный в статье «A threshold cryptosystem without a trusted party» автора Torben Pryds Pedersen, перенесенный на эллиптические кривые. Предполагается, что каждый сервер обладает постоянной (фиксируются регистратором в учетчике) ключевой парой Диффи-Хеллмана, используемой для защищенной передачи данных этому серверу (экспорт/импорт долей ключа).

Параметры протокола

• Эллиптическая кривая E и генератор P подгруппы этой кривой большого простого порядка q. В текущей реализации используется кривая secp256k1.
• Другой генератор Q той же подгруппы, для которого значение $$ неизвестно никому.
• (k,n), где n — общее число участников, сгенерировавших пары ключей, а k — минимальное число участников, которое необходимо для восстановления общего секрета, при этом $$. То есть, если k-1 участников скомпрометированы или у них украли ключи, то это никак не повлияет на безопасность общего секрета.

В общем виде алгоритм получения точки Q выглядит следующим образом: берется любая последовательность байт, например строка “Hello, World!”, и от нее считается хэш h = Hash(“Hello, World!”) после чего преобразуем последовательность байт h в число и считаем $$, где p – модуль кривой, подставляем $$ в уравнение кривой: $$ и пытаемся его решить относительно y. При отсутствии решения мы инкрементируем x0 и снова пытаемся решить уравнение для нового значения x0 и т.д.

Шаг 0.
Каждому из n серверов присваивается уникальный порядковый номер от 1 до n. Это необходимо, поскольку коэффициент Лагранжа зависит от порядкового номера сервера.

Шаг 1 — создание открытого ключа DKG.

Каждый j -й сервер, j=1,…,n:
1. Генерирует пару закрытый ключ ?priv?_j и открытый ключ $$
2. Делает Pedersen commitment для открытого ключа:
Генерируется случайное число r_j
Вычисляется точка $$
$$ публикуется с помощью учетчика
3. После того как все серверы опубликовали свои значения C_i, публикуется скаляр r_j.

Используя скаляры, каждый может восстановить открытые ключи каждого сервера $$ и вычислить открытый ключ DKG $$.
Отрытый ключ DKG записывается в блокчейн.

Шаг 2 — генерация полиномов и раздача теней.

Каждый j -й сервер, j=1,…,n:

1. Генерирует случайным образом полином степени k-1:
$$
где коэффициент $$, а остальные — случайные элементы поля GF(q).

2. Считает значения полинома $$

3. Зашифровывает значение $$ при помощи открытого ключа экспорта/импорта i -го сервер для каждого i и публикует с помощью учетчика результаты шифрования.

Шаг 3 — проверка коэффициентов полиномов.

Каждый j -й сервер, j=1,…,n:

1. Публикует каждый коэффициент своего полинома, умноженный на генератор P.
$$
2. Расшифровывает все значения $$ и проверяет их корректность:
Вычисляет $$
Вычисляет сумму
Если A=B, то результат принимается, иначе публикуется жалоба на сервер i, и протокол запускается с самого начала — переход к шагу 0.
3. Если ни у кого нет жалоб, то вычисляет свой секретный ключ



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

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

MainPubKey = Hash(PubDKG, PubCommission)*PubDKG + Hash(PubCommission,PubDKG)*PubCommission

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

Описание схемы шифрования бюллетеней

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

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

Encrypted (A) + Encrypted (B) = Encrypted (A+B).

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

Длина закрытого ключа при использовании алгоритма Эль-Гамаля на эллиптических кривых выбирается равной 256 бит, открытый ключ при этом представляет из себя точку эллиптической кривой. Это соответствует уровню безопасности в 128 бит (для взлома необходима 2^128 операций с точками кривой). Такой уровень считается оптимальным для большинства современных промышленных и финансовых систем, в том числе для российского стандарта ГОСТ 34.10-2018 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» (вариант 256 бит).

В качестве эллиптической кривой используется secp256k1.

Допустим, мы имеем ключевую пару priv, Pub:
Число priv: 0 < priv < q
Точка Pub = priv*Base

Зашифрование:

• Есть сообщение m, небольшое число, которое мы хотим зашифровать на ключе Pub.
• Вычисляем точку M = m*Base
• Генерируем случайное число r: 0 < r < q
• Вычисляем точку R = r*Base и точку C = M + r*Pub
• Шифротекст: (R, C)

Расшифрование:

• Имеется закрытый ключ priv и шифротекст (R, C)
• Вычисляем точку M = C – priv*Base
• Восстанавливаем m: решаем перебором ECDLP для соотношения M = m*Base

Гомоморфность схемы.

Мы видим, что если зашифровать два сообщения $$ и $$ на ключе Pub:
$$
$$

То их сумма $$ соответствует зашифрованному сообщению $$.

Таким образом, можно шифровать и складывать “покандидатно” все бюллетени. К примеру, пусть открытый бюллетень выглядит так:

Иванов Петров Сидоров

0 1 0

Тогда, преобразовав его в точки, получим:

Иванов Петров Сидоров

ZeroPoint Base ZeroPoint

где ZeroPoint – это точка на бесконечности.

И, наконец, шифруем бюллетень на ключе Pub:

Иванов Петров Сидоров

$$ $$ $$

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

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



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

Описание процедуры расшифрования

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

Для того, чтобы расшифровать шифротекст (R,C) необходимо, чтобы любые k из n серверов вычислили и опубликовали значение $$ и доказательство корректности расшифрования Chaum-Pedersen (доказательство, что посчитанный $$ – это именно точка R, умноженная на $$, не раскрывая значения $$). Также для этого необходимо собрать закрытый ключ комиссии из не менее чем k1 из т1 частей и с его помощью также выполнить вычисление $$ с публикацией в блокчейн.



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

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

Результаты операции публикуется в блокчейн.

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

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

Обратите внимание, что наличие шифротекста, сформированного на закрытом ключе комиссии, является обязательным условием. Без него подсчет итогов не состоится.

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

Доказательства с нулевым разглашением

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

Первый тип ZKP (zero-knowledge proof), применяемых в cистеме – доказательства диапазона. Данные ZKP используются при публикации зашифрованного бюллетеня, чтобы в отсутствие информации о том, как проголосовал участник голосования, можно было убедиться, что участник не испортил бюллетень на своем устройстве одним из следующим способов:

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

Более подробное описание реализации NIZK, а также их проверки, будет рассмотрено в отдельной статье.

Структура записей в блокчейне

Вся информация в блокчейне записывается тремя типами транзакций:

• CreateContract – для создания смарт-контракта под конкретное голосование. Далее в этом смарт-контракте будет агрегироваться вся информация по голосованию. Если одновременно проводится два (и более) голосования, то создается, соответственно, два (и более) экземпляра контракта.
• CallContract – для взаимодействия со смарт-контрактом по различным операциям, перечень которых приведем далее.
• Data transaction – для записи списка избирателей после создания экземпляра смарт-контракта голосования и перед началом непосредственно голосования.

Взаимодействие со смарт-контрактом производится по следующим операциям:

• Запись базовых данных в смарт-контракт. Здесь сохраняются публичные ключи северов подсчета, которые будут участвовать в криптографическом протоколе, threshold схема, ключи проверки слепой подписи и другие данные, необходимые для организации работы протокола и голосования в целом.
• dkgScalar, dkgCommit, dkgShadows – данные, необходимые для сборки публичного ключа шифрования бюллетеней и реализации пороговой k из n схемы. Подробнее об этом поговорим далее в статье.
• addMainKey – запись набора публичных ключей и общего публичного ключа шифрования бюллетеней.
• blindSigIssue – запись факта выдачи слепой подписи.
• vote – запись непосредственно зашифрованного голоса избирателя.
• finishVoting – команда завершения голосования. После нее новые бюллетени не принимаются.
• Decryption – запись частичного расшифрования результатов голосования. Отправляется каждым сервером подсчета.
• ComissionDecryption – запись частичного расшифрования результатов голосования на закрытом ключе комиссии.
• Results – запись расшифрованных итогов голосования. О расшифровании, подведении итогов и записи результатов подробнее далее в статье.

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

Ниже на рисунках представлено отображение транзакции с голосом в блокчейн-клиенте.





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

Ниже на рисунке представлено отображение агрегированной информации в смарт-контракте.


*Данные с тестового сервера.

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

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

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

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

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

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

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

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