Лабораторные работы № 3 и 4 / LAB_3

Санкт-Петербургский государственный электротехнический университет

Кафедра МОЭВМ

Отчет по лабораторной работе №3,4.

Алгоритм на основе эллиптических уравнений

ЭЦП ГОСТ Р 34.10-2001

Выполнили:

Студенты гр.3351

Сергеев М.В.

Фонарева С.А.

Санкт-Петербург

2007г.

1. Основные теоретические сведения

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

Эллиптической кривой, используемой в данной схеме, является выражение вида у2 = (х2 + а  х + b) mod p, где p – большое простое число. Обе координаты х и у, а также параметры а и b являются натуральными числами из диапазона [0; p-1], т. е. все вычисления производятся по модулю р. Пары чисел (х, у) удовлетворяющие приведенному равенству называются точками эллиптической кривой.

Над точками определена операция сложения следующим образом. Если абсциссы точек Q1 (х1, y1) и Q2 (х2,у2) различимы, то точка S = Q1 + Q2 имеет координаты (хs, ys), определяемые формулами:

k = (( y2 – y1) / (х2 – х1)) mod p

xs = (k2 – x1 – x2) mod p

ys = (k  (x1-x2) – e1) mod p .

Если же точки Q1 и Q2 совпадают, т. е. речь идет о об "удвоении точки" то применяются следующие формулы:

k = ((3  x 12 + a) / (2  y1)) mod p

xs = k2 – 2 x1 ) mod p

ys = (k  (x1 – xs) – y1) mod p.

Подобные формулы позволяют ввести над точками эллиптической кривой операцию умножения на число: R = n  P – n кратное сложение точки P с самой собой. Данная операция по свойствам тождественна операции возведения в степень в конечном поле простого числа. Само умножение (шифрование) характеризуется полиномиальной скоростью вычислений, а вот попытка по известным P и R определить число n уже не укладывается в полиномиальные рамки.

2. Общие положения

Общепризнанная схема (модель) цифровой подписи (см. 6 ИСО/МЭК 14888-1 [3]) охватывает три процесса:

• генерация ключей (подписи и проверки);

• формирование подписи;

• проверка подписи.

В настоящем стандарте процесс генерации ключей (подписи и проверки) не рассмотрен. Характеристики и способы реализации данного процесса определяются вовлеченными в него субъектами, которые устанавливают соответствующие параметры по взаимному согласованию.

Механизм цифровой подписи определяется по средством реализации двух основных процессов:

• процесс формирования подписи;

• процесса проверки подписи.

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

• осуществляет контроль целостности передаваемого подписанного сообщения,

• предоставляет возможность доказательно подтвердить авторство лица, подписавшего сообщение,

• о беспечивает защиту от возможностей подделки сообщения.

Схематическое представление подписанного сообщения показано на рисунке 1.

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

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

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

3. Основные процессы

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

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

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

Формирование цифровой подписи

Для получения цифровой подписи под сообщением необходимо выполнить следующие действия (шаги) по Алгоритму I:

Шаг 1 – вычислить хэш-код сообщения .

Шаг 2 – вычислить целое число , двоичным представлением которого является вектор , и определить

.

Если е = 0, то определить е = 1.

Шаг 3 – вычислить случайное (псевдослучайное) целое число k, удовлетворяющее неравенствам

.

Шаг 4 – вычислить точку эллиптической кривой C=kP и положить

где xc – x-координата точки С. Если , то вернуться на шаг 3.

Шаг 5 – вычислить значение

Если , то вернуться на шаг 3.

Шаг 6 – вычислить двоичные векторы и , соответствующие числам r и s и определить цифровую подпись как конкатенацию двух двоичных векторов.

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

С хематическое представление процесса формирования цифровой подписи приведено на рисунке 2.

Проверка цифровой подписи

Для проверки цифровой подписи под полученным сообщением М необходимо выполнить следующие действия (шаги) по Алгоритму II:

Шаг 1 – по полученной подписи вычислить целые числа r и s. Если выполнены неравенства , то перейти к следующему шагу. В противном случае подпись не верна.

Шаг 2 – вычислить хэш-код полученного сообщения М

.

Шаг 3 – вычислить целое число , двоичным представлением которого является вектор и определить . Если e = 0, то определить e = 1.

Шаг 4 – вычислить значение .

Шаг 5 – вычислить значения

Шаг 6 – вычислить точку эллиптической кривой и определить

,

где xc – х-координата точки С.

Шаг 7 – если выполнено равенство , то подпись принимается, в противном случае, подпись не верна.

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

С хематическое представление процесса проверки цифровой подписи приведено на рисунке 3.

4. Работа с программой шифрования

Создание подписи:

Вставьте подписываемое сообщение в поле (2) и секретный ключ в поле (1), нажмите кнопку «Создать ЭЦП» (3). Цифровая подпись и публичный ключ появятся в полях (4) и (5).

Проверка подписи:

Вставьте подписанное сообщение в поле (8), цифровую подпись в поле (6), публичный ключ в поле (7), нажмите кнопку «Проверить ЭЦП» (9). Результат проверки появится в поле (10).

5