Мініcтерство освіти та науки України

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Інститут радіоелектроніки та телекомунікацій

Кафедра ІБ



Протокол

до лабораторної роботи №5

“Алгоритмы обмена ключами и цифровой подписи, основанные на эллиптических кривых”



Виконав студент групи РТ-061

______________

(підпис)

___________________2010 р.

Перевірив ств. каф. ІБ

______________ Яковенко О.О.

(підпис)

___________________2010 р.



Одеса

2010

Цель работы: . Понять принцип работы криптографических примитивов, основанных на эллиптических кривых. Выполнить на небольших числах алгоритм Дифи-Хэллмана на эллиптических кривых (ECDH) и алгоритм цифровой подписи на эллиптических кривых (ECDSA);

Работа в лаборатории



Выбор параметров кривой

1. Выберем простой модуль р, по которому производятся вычисления. Выберем простое число р=59.

2. Выберем параметры а и b. Пусть а=17 и b=37. Эти коэффициенты соответствуют неравенству

.

3. Так как данное неравенство выполняется, то выберем параметры кривой. При выборе параметров кривой, следует учитывать количество корней Nk, существующих для этой кривой. Количество корней отображается в программе Вычисления на эллиптических кривых на вкладке Параметры кривой(рис. 5.1);



Рис. 5.1 – Выбор параметров кривой при учёте количества корней

4. Выберем точку-генератор G на кривой, порядок которой должен совпадать количеством корней Nk, существующих для этой кривой. Проведем выбор точки-генератора с помощью программы Нахождение кратной точки на эллиптической кривой (рис. 5.2)



Рис. 5.2 – Выбор точки-генератора G на кривой



5. Параметры р=59, а=17 , b=37 и G=64. Они должны быть опубликованы (например, на доске).



Обмен ключами

1. Выберем случайное секретное число k– целое, от 2 до . Пусть k =2 – это число – секретный ключ.

2. Вычислим координаты точки kG при помощи программы Вычисления на эллиптических кривых (рис. 5.3)



Рис. 5.3 – вычисление координат точки kG



3. Пошлем полученные координаты х=34 и у=34 нашему адресату.

4. Получим координаты адресата, точку N: х=40, у=42.

5. Вычислим координаты точки kN (рис. 5.4). Эти координаты и есть ваш общий ключ.



Рис. 5.4 – Вычисление координаты адресата точки kN

6. Сверимся с нашим адресатом – он получил такие же координаты (рис. 5.5).



\



Рис. 5.5 – Проверка координат с адресатом



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



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



Алгоритм цифровой подписи на эллиптических кривых (ECDSA)

1. Выбор параметров кривой



Выберем параметры эллиптической кривой так же как и для алгоритма Дифи-Хэлмана: р=79, а=19, b=41 и G=83.



2. Генерирование ключей



1. Выберем случайное секретное число d в диапазоне от 1 до – это ваш секретный ключ; тогда d=2.

2. При помощи программы Вычисления на эллиптических кривых вычислим координаты точки Q = dG; тогда Q =(26, 40).

3. Точка Q – ваш открытый ключ.



3. Подписывание сообщения



1. Подготовим сообщение



2. Найдем хэш подготовленной строки – Н. Тогда Н=402.

3. Выберем случайное число k в диапазоне от 1 до . Тогда k=4.

4. Вычислим координаты kG. Допустим, координаты kG – это (x1=76, y1=73).

5. Вычислим r = x1 mod p=76 mod79=76.

6. Вычислим

7. Пара чисел r и s является цифровой подписью сообщения. Необходимо дописать в блокноте с новой строки два числа – r и s (например, через запятую). Эти два числа и являются цифровой подписью. Они передаются вместе с сообщением.



4. Проверка подписи сообщения



1. Получим сообщение и его хэш: Н1=402.

2. Для того чтобы проверить подлинность подписи, необходимо использовать полученные вместе со строчкой числа r и s, а также открытый ключ подписчика Q;

3. Рассчитаем w по формуле: .

4. Рассчитать по формуле:

5. Рассчитать по формуле:

6. Рассчитать координаты точки V по формуле: .

7.