НАУКА и ОБРАЗОВАНИЕ

Система тайного электронного голосования на базе локальной сети.

Алехова Елена Юрьевна

Центр образования № 1420, 11 класс

Цель проекта состояла в разработке программного обеспечения для локальной сети электронных вычислительных  машин, позволяющего проводить сеансы тайного электронного голосования в коллективе, членам которого  предоставляется право голоса. В проекте реализованы алгоритмы, придающие системе голосования уникальные свойства, гарантирующие безусловную «честность» подачи и подсчета голосов при сохранении полной анонимности каждого голоса. Ниже приводится описание выполненного проекта.

1.Основные понятия

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

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

2.Требования к системе тайного голосования

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

2)  Частичная отслеживаемость. Для любых двух голосов, поданных на протяжении одного голосования, можно определить, были ли они поданы одним избирателем или нет. Таким образом, пресекаются попытки пользователя подать два голоса в одном и том же голосовании.

3) Частичная неотслеживаемость. Для голосов, поступивших в двух разных голосованиях невозможно определить, были они поданы одним и тем же пользователем или нет.

4) Защита от мошенничества со стороны администраторов. Администратор не должен иметь возможности изменить или подделать результаты голосования.

5) Проверяемость. Пользователь должен иметь возможность проверить правильно ли был учтён его голос.

3.Алгоритмы

    Конечно, существуют программные продукты, отвечающие требованиям, предъявляемым к системе тайного голосования. К сожалению, алгоритмы, использованные в той или иной конкретной программе, не разглашаются. Но в основном современные системы тайного голосования основаны на следующих больших группах алгоритмов: - смешанные сети(mix-nets); - гомоморфические криптосистемы;- слепая подпись;

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

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

4. Описание разработанной программы

          В результате выполнения проекта были разработаны программные модули:

- Сервер, предназначенный для использования администраторами сети;

- Клиент, предназначенный для пользователей системы;

4.1.Сервер

Серверная часть приложения устанавливается на одном из компьютеров сети и используется администраторами сети. Эта часть приложения предоставляет администратору следующие возможности:

- Создание бюллетени и объявление голосования; Для создания бюллетени администратор указывает название голосования, вопрос, выносящийся на голосование, варианты ответов, а так же даты начала и окончания голосования (рис.1).                       

Рисунок 1 Создание и редактирование бюллетеней

- Генерация сертификата пользователя, необходимого для   регистрации;  Для генерации сертификата администратор должен указать ФИО нового пользователя. Впоследствии эти данные будут отображаться в списке пользователей. При голосовании эти данные не используются.

- Просмотр списка действительных пользователей;

- Просмотр результатов голосований;

- Удаление пользователя из списка;

4.2.Клиент

Клиентская часть приложения предназначена для пользователей системы (избирателей). Эта часть приложения предоставляет пользователю следующие возможности:

- Регистрация;   При регистрации пользователь указывает свои ФИО, а также идентификатор, полученный от администратора. По этим данным генерируется цифровая подпись, которая проверяется программой-сервером. Если результат проверки положителен, то пользователь получает право зарегистрироваться в системе, задав логин и пароль (рис.2), которые впоследствии будет указывать каждый раз при входе в программу.

Рисунок 2 Создание логина и пароля

- Просмотр списка действительных бюллетеней;

- Голосование;

- Просмотр результатов голосования;

- Просмотр списка действительных пользователей;

- Проверка учёта собственного голоса;

5.Описание алгоритмов

5.1.Криптосистема  RSA

Криптосистема RSA, изобретенная в 1978 году Р.Ривестом (R.Rivest), А.Шамиром (A.Shamir) и Л.Адлеманом (L.Adleman) и названная по первым буквам фамилий авторов, отличается высокой стойкостью к возможным атакам противника вместе с алгоритмической простотой операций шифрования и расшифрования. Криптосистема RSA построена на использовании двух математических утверждений (теорем ).     

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

, если  и НОД.

НОД – наибольший общий делитель, - функция Эйлера.

      2. Утверждение, которое было известно еще Евклиду, состоит в том, что для двух взаимно простых целых чисел, существует единственное целое число, не превосходящее большего, произведение которого с простым меньшим при делении на простое большее дает в остатке единицу. Математическая запись:

,     НОД,    ,      -  единственно.

     Построение криптосистемы сводится к следующему:

Выбирается два больших простых числа  и . Их произведение обозначается числом . Легко найти, что если , то . Находится некоторое  , взаимно простое с , и для него находится единственное , такое что .

Тогда для любого , не превосходящего и взаимно простого с ним, выполняется соотношение

Действительно, раз , значит  и , а поскольку , то и , значит , а , поскольку .

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

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

       Стойкость такой криптосистемы обеспечивается практической невозможностью найти простые множители  и даже при известном , что было продемонстрировано авторами системы. Они опубликовали числа и , шифротекст  небольшой (закрытой) фразы и даже сообщили, что множитель  имеет 64 десятичных знака, а - 65. Математики убедились в чрезвычайной сложности предложенной им задачи.

5.2.Протоколы системы голосования

5.2.1.Функциональные элементы системы.

Администратор (в дальнейшем TA(thrusted authority)). Избиратели (члены)   U_i    (i = 1 – N)

Информационные элементы системы.

Общедоступные: n₁ , a ,a₀ , b , g , h;  n₂ , u;  , , .

В распоряжении TA:

1)  Криптосистема  RSA  с основанием n₁.

2)  Список пользователей.  

          U_i -  открытый идентификатор члена.

          e_i  -  списочный идентификатор члена.

3)   Список завершенных голосований. По каждому из них:

           m   -      идентификатор голосования.

           M_k  -      варианты ответов (по бюллетеню).

           Список результатов.

             (Т₄)_i   -    анонимный идентификатор голосовавшего.

        (М_k)_i  -    выбранный им вариант ответа.

      Протокол голосования (список полученных сообщений):

        (Т₄)_i   T₁ -  T₇ ,  s₁ – s₉ ,  - информация о выборе.

         C = - сопровождающая хэш-функция.

          (C = H(m b g h u a₀ a T₁ … T₇ d₁ … d₉ M)  )

Список результатов доступен пользователям для контроля. Каждый пользователь и только он знает свой анонимный идентификатор (Т₄)_i .

Протокол голосования хранится ограниченное время для разрешения возможных конфликтов.       

4)  Список объявленных, но не завершенных голосований.

         m   -      идентификатор голосования.

         M_k  -      варианты ответов (по бюллетеню).    

    Протокол голосования (список полученных сообщений):

        (Т₄)_i   T₁ -  T₇ ,  s₁ – s₉ ,  - информация о выборе.

         C = - сопровождающая хэш-функция.

Протокол голосования доступен пользователям для его пополнения.

5)  Криптосистема  RSA  с основанием n₂.

6)  Список зарегистрированных пользователей.  

          e_i -  списочный идентификатор пользователя.

7)  Список пользователей, лишенных голоса.  

          e_j -  списочный  идентификатор удалённого пользователя.

В распоряжении пользователя:

1)  Сертификат  e_i , A_i , u_i ;

2)  Секретный идентификатор  х_i (пароль).

Соотношения, обеспеченные алгоритмом генерации сертификата:

   a);   б)   

5.2.2.Алгоритмы.

5.2.2.1.Изменение списка членов.

Пополнение.

1. По открытому идентификатору  U_i  ТА выдает новому члену списочный идентификатор e_i , как элемент системы RSA, вычисляя для своего списка p_i , такое, что .

2. Кандидат в члены придумывает себе секретный идентификатор х_i и вычисляет . Шифрует :

Посылает к ТА. Сообщение:  U_i  , .

3. ТА по открытому U_i  находит в своем списке секретный код p_i и расшифровывает :

.

Вычисляет элемент сертификата

(Так, что ).

4  Mодифицирует  формуле  .

В список зарегистрированных членов добавляет члена e_i .

5.  посылает новому члену U_i его сертификат:

(А_i , e_i , u_i ), где u_i  - это предыдущее u администратора, зашифровав его:

 .

Всем ранее зарегистрированным членам ТА шлет e_i  нового члена с уведомлением о его приеме.

6.  Избиратель (новый член),

расшифровывая :

_,

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

7. Все члены,

получившие уведомление о приеме нового и элемент его  сертификата (списочный идентификатор) e_i ,

модернизируют свои u_k : 

.

5.2.2.2.Голосование.

1. ТА уведомляет членов о начале нового голосования с идентификатором  и с вариантами ответов .

2. Избиратель ,получив идентификатор  с вариантами ответов ,

2.1  придумывает четыре целых , , ,  (с количеством разрядов в пределах ). Вычисляет семь величин:

,         ,

,       ,

,      ,

.

2.2   Придумывает еще девять целых   -   и вычисляет еще девять              чисел:        

2.3   Вычисляет хэш-функцию:

  Последним элементом в аргументе хэш-функции стоит  выбранный вариант ответа в голосовании - .

 Вычисляет еще девять чисел:

Посылает к ТА свой голос в виде сообщения:

5.2.2.3.Проверка и учет поданного голоса

ТА получив от избирателя сообщение

,

вычисляет:

После этого вычисляет хэш-функцию:

.

Голос подан за , если    .                      

Заключение.

В результате выполнения проекта была разработана система электронного тайного голосования на базе локальной сети, удовлетворяющая следующим требованиям:

- анонимность;

- частичная отслеживаемость;

- частичная неотслеживаемость;

- проверяемость;

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

***

Литература

1. Баричев С.Г., Гончаров В.В., Серов Р.Е.  Основы современной криптографии. – М.:Горячаялиния — Телеком, 2001. – 120 с.

2. Иванов М. А. Криптографические методы защиты информации в компьютерных системах и сетях. — М.:КУДИЦ-ОБРАЗ, 2001 – 368 с.

3. Молдовян А. А., Молдовян Н. А., Советов Б. Я.  Криптография. – СПБ.: Издательство «Лань», 2001. – 224 с. 

4. Чмора А.Л. Современная прикладная криптография. 2-е изд., стер. – М.: Гелиос АРВ, 2002. – 256 с.

5. Введение в криптографию/под общ. ред. В. В. Ященко. – 3-е изд., доп. – М.: МЦНМО:  «ЧеРо», 2000. – 288 с.

6. Сanard S., Traore J. List Signature Sсhemes and Application to Electonic Voting. . WCC 2003.