Электронная подпись (цифровая подпись).

Если  планирует подписывать документ Ц.П., то он должен выбрать параметры RSA.  выбирает два простых числа  и , вычисляет  затем выбирает число ,взаимно простое с , и вычисляет , далее публикует числа  и  и хранит в секрете . Числа – более не понадобятся.

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

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

Далее  вычисляет число , т.е. она возводит число  в свою секретную степень. Число – цифровая подпись.

 – вид сообщения с подписью.

Теперь каждый, кто знает открытые параметры , т.е.  и , может проверить подлинность его подписи.

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

 

/*Пример*/ Электронная подпись RSA.

 

Пусть

 (алгоритм Евклида).

 

 (допущение)

 вычисляет

 – сообщение с подписью

 

Вычисляем значение хеш-функции, получим  

 

 

Подпись верна.

Определение Хеш-функции.

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

 

Криптографические алгоритмы

Шифр Эль-Гамаля

 

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

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

Затем каждый абонент выбирает своё секретное число , , и вычисляет соответствующе ему открытое число ,

 

                                                   ( )

 

В результате получаем следующую таблицу ().

 

Абонент	Открытый ключ	Секретный ключ

Табл(). Ключи пользователей в системе Эль=Гамаля.

 

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

Шаг 1. Алиса формирует случайное число , , вычисляет числа:

 

                        (9.1.2)

                    (9.1.3)

и передаёт пару чисел абоненту Бобу.

Шаг 2. Боб, получив , вычисляет

 

               (9.1.4)

 

/*Пример*/

Алиса хочет передать Бобу сообщение . Допустим  Пусть Боб выбрал для себя секретное число  и вычислил по формуле (9.1.1)

 

 

Алиса выбирает случайное число , например , и вычисляет по (9.1.2) и (9.1.3):

 

.

 

Теперь Алиса посылает Бобу шифрограмму (17,12). Боб вычисляет по формуле (9.1.4):

 

 

Боб расшифровал сообщение

Электронная подпись на базе Эль-Гамаля.

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

Затем она вычисляет число

 

                        (9.1.5)

 

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

Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение . Опишем последовательность действий для построения подписи.

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

 

                        (9.1.6)

 

Далее Алиса вычисляет числа:

 

                     (9.1.7)

                          (9.1.8).

 

Под  в (9.1.8) подразумевается число, удовлетворяющее уравнению

 

                          (9.1.9)

Такое  существует, так как  и  взаимно просты, и может быть найдено по алгоритму Евклида. Наконец Алиса формирует подписанное сообщение

 

                                      (9.1.10).

 

Получив сообщение Боб заново вычисляет значение хеш-функции  и проверяет подпись, используя равенство

 

                           (9.1.11)

 

/*Пример*/

Пусть общие параметры для некоторого сообщества пользователей . Алиса выбирает свой секретный ключ  и вычисляет открытый ключ  по формуле (9.1.5):

 

 

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