Одним из способов протеста является подача и коллективное подписание разного рода петиций. Но поскольку список подписавших петицию открыт, нередко возникают ситуации, когда несогласные с «курсом партии» подвергаются угрозам и репрессиям со стороны администрации.
А можно ли сделать систему, позволяющую осуществить анонимный сбор подписей, но в то же время дающую возможность верифицировать каждый голос? Предлагаю вашему вниманию свое решение данной задачи.
Постановка задачи
Имеется ограниченный круг лиц, например, студенты института, сотрудники организации или граждане страны. Часть из них подписывают некоторое сообщение (петицию, коллективное обращение и т.п.). Предлагаемый алгоритм подписания обладает следующими свойствами:
- Есть возможность удостовериться, что каждый подписант принадлежит к указанному кругу лиц.
- Есть возможность проверить, что большинство подписей принадлежат разным лицам.
- Нет возможности определить, кому именно принадлежит та или иная подпись.
- Нет возможности определить, оставляло ли данное конкретное лицо свою подпись или нет.
- Любой подписант может по своему желанию поставить вместо анонимной подписи персонализованную.
- Любой анонимный подписант может впоследствии по своему желанию предоставить доказательства того, что именно он поставил подпись.
Система основана на асимметричной криптографии, алгоритмах цифровой подписи и сертификации ключей.
Подготовительный этап
Каждый участник (на рис.1 — А, B,...Z) генерирует пару ключей, открытый и закрытый. Назовем эти ключи персонализованными. Открытый ключ публикуется и подтверждается центром сертификации, в роли которого может выступать деканат института, отдел кадров предприятия или административный аппарат государства. Задача сертификата — подтвердить, что данный ключ действительно принадлежит указанному лицу, и что это лицо имеет право участвовать в коллективном подписании.
Рис. 1. Схема сертификации открытых ключей
Данный этап проводится один раз, независимо от числа сообщений, подписываемых в дальнейшем. База сертифицированных ключей может храниться централизованно или распределенно.
Формирование голосов
Каждый подписант генерирует еще одну пару ключей — т.н. анонимные ключи. При помощи закрытого ключа он подписывает сообщение, а открытый публикует анонимно. Электронная подпись (ЭЦП) и соответствующий открытый ключ составляют один голос.
Рис. 2. Схема формирования голосов
Если подписант хочет отказаться от анонимности, то он может использовать для подписания свой персонализованный ключ и не генерировать анонимные ключи вообще.
Проверка голоса
Первичная проверка голосов заключается в том, что наблюдатель (в роли которого может выступать любой) проверяет подпись каждого голоса при помощи соответствующего открытого анонимного ключа. Таким образом наблюдатель удостоверяется, что данный голос сформирован именно для этого конкретного сообщения. Но пока ничего нельзя сказать ни об уникальности подписантов, ни о принадлежности их к указанному кругу лиц.
Рис. 3. Схема первичной проверки голоса
Верификация подписанта
В дальнейшем производится проверка подписантов. Эта проверка может быть как выборочной, так и полной, в зависимости от числа подписантов и технических возможностей.
Наблюдатель публикует запрос на проверку какого-либо конкретного голоса, используя в качестве идентификатора анонимный открытый ключ. Подписант, ключ которого опубликован в запросе (на рис.4 — А), генерирует случайное контрольное сообщение и публикует его анонимно. В принципе, это сообщение может сгенерировать и наблюдатель, присоединив его к запросу.
Затем А подписывает контрольное сообщение своим анонимным закрытым ключом. Далее А выбирает некоторую группу лиц, включая себя (на рис.4 — А, B, C). Не имеет значения, является ли подписантом кто-то из группы, кроме А, к тому же, это невозможно установить. А разбивает ЭЦП контрольного сообщения на фрагменты, в соответствии с числом участников группы и распределяет эти фрагменты среди них.
Разбиение на фрагменты на рисунке показано условно. Простое разрезание текста, даже с перестановкой символов — плохое решение. Лучше воспользоваться одним из алгоритмов разделения секрета.
Каждый из членов группы (включая самого А) подписывает свой фрагмент своим персонализованным закрытым ключом и затем публикует.
Рис. 4. Схема верификации подписанта
Таким образом, наблюдатель получает доказательство того, что голос сформировал кто-то из группы {A,B,C}, но кто именно — сказать нельзя. Это сильно затрудняет применение репрессий к подписантам со стороны администрации. Размер группы можно выбирать произвольно, чем он выше, тем выше надежность, но тем сложнее (технически) организовать распределение фрагментов. Необходимо запретить повторную верификацию голоса, иначе появляется возможность вычислить подписанта, ища пересечения групп, участвовавших в каждой верификации. Либо требовать, чтобы при повторной верификации состав группы не менялся.
Если подписант желает деанонимизироваться, он производит все те же действия, только не собирает группу, а просто подписывает контрольное сообщение своими закрытыми ключами: анонимным и персонализованным.
Распределение и подписание фрагментов
Остановимся подробнее на алгоритме распределения фрагментов. К нему предъявляются следующие требования:
- Никто из членов группы и сторонних наблюдателей не должен иметь возможности узнать, кто инициировал процедуру.
- Даже если все члены группы, кроме А, в сговоре, у них не должно быть возможности доказать, что именно А — инициатор.
- У лица, не входящего в группу, не должно быть возможности инициировать процедуру.
Последнее требование делает непригодной простую анонимную рассылку фрагментов. Ведь тогда появляется возможность лицу «со стороны» сгенерировать голос и пройти верификацию, разослав фрагменты остальным и не подписываясь своим персонализованным ключом.
Схема распределения фрагментов показана на рис.6. Допустим, А — инициатор. Он подписывает своим закрытым персонализованным ключом случайный фрагмент, а затем пересылает все фрагменты B. Первым делом B проверяет подпись А по сертифицированному открытомуС ключу, и, удостоверившись, что А — тот, за кого себя выдает, публикует подписанный фрагмент.
Затем B удаляет из сообщения подпись А, подписывает своим закрытым персонализованным ключом следующий фрагмент и посылает все фрагменты С. Аналогично, С проверяет подпись B, публикует этот фрагмент и подписывает следующий.
В конце цепочки сообщение опять пересылается А, который проверяет подпись последнего участника (C) и публикует последний фрагмент.
Рис. 5. Схема распределения и подписания фрагментов
Для каждого участника, кроме инициатора, процедура выглядит совершенно одинаково и нет возможности определить, где начало цепочки и где ее конец. Даже если B и C сговорятся и определят последовательность пересылок, А сможет утверждать, что он находится в цепочке после C (соответственно, B — инициатор), и у B с C не будет способа доказать обратное.
Для предотвращения тайминг-атак публикацию подписанных фрагментов необходимо производить после полного завершения процедуры, либо ввести случайные задержки перед публикацией. Также все члены группы должны заранее закэшировать открытые ключи и сертификаты, чтобы очередность нельзя было установить по времени обращений к сертификационному серверу.
Завершение верификации
Наблюдатель, получив подписанные фрагменты, проверяет каждую подпись по открытым ключам А, B и C. Затем от собирает из фрагментов подпись контрольного сообщения и проверяет ее, используя оригинал контрольного сообщения и анонимный открытый ключ из проверяемого голоса. Если проверка всех ЭЦП прошла успешно, верификация считается пройденной.
Рис. 6. Схема завершающего этапа верификации
Все операции, выполненные наблюдателем, может повторить любая другая сторона, так как исходные данные (голос, контрольное сообщение и подписанные фрагменты) публикуются в открытом доступе.
Заключение
Несмотря на то, что двухдневный поиск уже существующих аналогов предложенного алгоритма результатов не дал, я нисколько не удивлюсь, если окажется, что изобрел очередной велосипед. Если это действительно так, буду благодарен за ссылки. В конце концов, велосипедостроение служит отличным упражнением для . Также буду крайне признателен сообществу за поиск неточностей, уязвимостей и тех мест, где алгоритм можно улучшить.
Благодарю за внимание!
Автор: Ocelot
