Pull to refresh

Слепая подпись на основе ГОСТ 34.10-2001

Reading time 5 min
Views 22K
Прошедшим и будущим выборам посвящается.

После вбросов, скандалов, интриг, расследований, которые были на думских выборах, невольно задаешься вопросом: а как сделать так, чтобы было все честно? Ну а применительно к ИТ, как сделать так, чтобы все было честно, да еще и с помощью высоких технологий? Я читал и про пробивание дырочек, и про QR-коды, поэтому решил внести скромную математическую лепту.
В этом топике мы поговорим с вами о том, как решить две взаимно противоположные проблемы с помощью криптографии: проблему верификации избирателя и проблему тайны голосования. Я немного расскажу о так называемой «слепой подписи» и даже представлю демонстрационное приложение, которое показывает, каким образом могут быть решены задачи верификации и анонимности одновременно, причем на основе криптоалгоритмов ГОСТ 34.10 и 34.11, которые официально одобрены ФСБ.

Ни для кого не секрет, что в цивилизованных странах уже давно можно голосовать на выборах через Интернет. В этом смысле показателен эстонский опыт, с его карточками и электронными подписями. Смысл эстонской системы в том, что в день выборов человек подписывает условно свой голос своей электронной подписью (7 шаг). Между тем, в нашей стране, где нет доверия никому и ничему, поневоле приходится признавать, что схема с простой верификацией пользователя никуда не годится, ведь в этом случае теоретически может быть нарушена тайна волеизъявления. С другой стороны, если заботиться только о тайне голосования, то может возникнуть ситуация, когда в избирательной урне, или, в нашем случае, на счетчике бюллетеней окажутся лишние с голосами, поданными в пользу определенной партии или определенного кандидата, поэтому голосование должно быть персонифицированным.

Слепая подпись


Механизм, который мы рассмотрим, одновременно и защищает приватность поданного голоса, и однозначно верифицирует избирателя. Достигается это с помощью так называемой «слепой» электронной подписи. Задачу, решаемую с помощью слепой подписи, можно в двух предложениях сформулировать примерно так:
  1. Алиса желает анонимно отправить некую достоверную информацию Цезарю;
  2. Боб может удостоверить источник информации (Алису), но не должен знать ее суть.
Для этого используется следующее решение:
  1. Алиса запечатывает листок с информации в конверт;
  2. Алиса приносит запечатанный конверт Бобу;
  3. Боб видит, что Алиса это Алиса и ставит штамп на конверт с информацией, не видя ее сути;
  4. Алиса идет на почту и отправляет конверт со штампом Цезарю без обратного адреса;
  5. Цезарь получает конверт, видит штамп Боба и доверяет источнику информации, не зная этот источник.
Один в один наше голосование, не так ли? Нам тоже нужно, чтобы тот, кто выдает нам бюллетень, знал, что мы – это мы. И тоже нужно, чтобы тот, кто считал бюллетень, видел только, за кого подан голос, а не то, у кого бюллетень побывал в руках.

Механизм


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

Конечно так, да не так. Поясню на примере. Допустим, валидатор подписывает сообщение, умножив его на 2, т.е. мы отправляем валидатору число, он возвращает нам удвоенное число в качестве подписи и счетчик такую подпись признает истинной. Мы отправляем валидатору 1, он нам возвращает 2, мы пересылаем счетчику пару 1 и 2, счетчик смотрит, что да, действительно, 2 ровно в 2 раза больше 1 и признает подпись истинной. А теперь мы делаем иначе, мы берем наше сообщение (1), отправляем валидатору удвоенное сообщение (2), он его подписывает, возвращает подпись (4), мы производим обратное преобразование, делим четверку на два, получаем истинную подпись (2) для нашего сообщения. Таким образом, валидатор не знал нашего сообщения (откуда он знает, на сколько изначально сообщение умножили? На два? А может на минус два?), но из его подписи нашего замаскированного сообщения мы восстановили истинную подпись для нашего секретного сообщения.

Стандарт


Теперь поговорим чуть-чуть об алгоритме ГОСТ Р 34.10-2001. Этот алгоритм был принят взамен алгоритма ГОСТ 34.10-94, а здесь даже кратко описаны отличия. От всем известного RSA алгоритм отличается сложной проблемой, если RSA использует сложную проблему разложения числа на множители, то ГОСТ Р 34.10-2001 основан на эллиптических кривых и использует проблему вычисления дискретного логарифма в группе точек. Между нами, девочками, говоря, эллиптические кривые очень интересные штуки и до конца не изученные. Это достаточно новое направление математики, которое открывает широкие перспективы. Стоит ли упоминать, что доказательство Великой теоремы Ферма было основано именно на эллиптических кривых?

Как работает ГОСТ (давайте я буду просто писать ГОСТ вместо ГОСТ Р 34.10-2001), можно узнать, долистав до шестой страницы стандарта, а ниже презенташка с видоизмененным алгоритмом:


Голосование


Таким образом, мы получаем общую схему:
  1. Избиратель устанавливает защищенное соединение с валидатором. Защищенное в том смысле, что во-первых, избиратель точно знает, что валидатор это валидатор (SSL еще никто не отменял), а валидатор точно знает, что избиратель это избиратель (просто весь исходящий поток данных избиратель подписывает своим закрытым ключом);
  2. Избиратель генерирует избирательный бюллетень, голосует за любую другую партию, добавляет к бюллетеню уникальную последовательность символов и хеширует бюллетень;
  3. Избиратель добавляет к хешу бюллетеня маскирующий множитель и направляет на подпись валидатору;
  4. Валидатор проверяет, голосовал ли уже этот избиратель. В случае отрицательной проверки, подписывает замаскированный хеш;
  5. Избиратель извлекает из подписи маскирующий множитель и получает корректную подпись для своего оригинального хеша бюллетеня;
  6. Избиратель устанавливает незащищенное открытое соединение с счетчиком из любого места, которое считает анонимным (хоть, например, регистрирует адрес на mail.ru и отправляет заказным письмом) и пересылает подписанный бюллетень.
  7. Счетчик проверяет корректность подписи бюллетеня, уникальность идентификатора, если проверка положительна, дописывает +1 голос любой другой партии.

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

Приложение


И в заключении моя демка — приложение на C#, которое вслепую подписывает ГОСТ 34.11-хеш слова «Бюллетень». Кнопки нажимать последовательно, после каждого нажатия они забирают данные из контролов, в памяти ничего не хранится кроме параметров кривой. Сама кривая взята в оригинальном ГОСТе, но, конечно, при желании можно ее заменить на какую-нибудь из КриптоПрошных. Красным помечено то, что остается в секрете, синим — то, что пересылается. Я использовал криптографические библиотеки BouncyCastle для генерации ключевой пары и проверки подписи, само же формирование подписи «вслепую» происходит прямо внутри программы.


Приложение с исходниками можно забрать здесь.

В заключение отмечу, что уже сейчас законом разрешено пользоваться электронной подписью наравне с рукописной, поэтому валидация избирателя возможна уже хоть сейчас. А также отдельное спасибо профессору Н.А. Молдавяну за статью в журнале International Journal of Network Security в мае прошлого года.
Tags:
Hubs:
+53
Comments 46
Comments Comments 46

Articles