Алгоритм распределения ключей на эллиптических кривых

Стр 1 из 3Следующая ⇒

Одесская национальная академия связи им А. С. Попова

Криптосистемы на эллиптических кривых

Басов В. Е.

Одесса 2009 г.

Содержание

1. Элементарные операции на эллиптических кривых. 4

1.1. Цель работы.. 4

1.2. Ключевые положения. 4

1.3. Домашнее задание. 6

1.4. Содержание протокола. 7

1.5. Ключевые вопросы.. 7

1.6. Лабораторное задание. 7

2. Алгоритм распределения ключей на эллиптических кривых. 8

2.1. Цель работы.. 8

2.2. Ключевые положения. 8

2.3. Домашнее задание. 9

2.4. Содержание протокола. 9

2.5. Ключевые вопросы.. 9

2.6. Лабораторное задание. 9

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

3.1. Цель работы.. 10

3.2. Ключевые положения. 10

3.3. Домашнее задание. 11

3.4. Содержание протокола. 12

3.5. Ключевые вопросы.. 12

3.6. Лабораторное задание. 12

4. Двухключевой алгоритм шифрования на эллиптических кривых. 12

4.1. Цель работы.. 12

4.2. Ключевые положения. 13

4.3. Домашнее задание. 13

4.4. Содержание протокола. 14

4.5. Ключевые вопросы.. 14

4.6. Лабораторное задание. 14

Элементарные операции на эллиптических кривых

Цель работы

Изучить основные свойства эллиптических кривых в конечном поле. Освоить выполнение операций сложения и умножения на эллиптической кривой.

Ключевые положения

Математические понятия

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

В общем случае уравнение эллиптической кривой Е имеет вид:

y² + axy + by = x³ + cx² + dx + e

В качестве примера рассмотрим эллиптическую кривую Е, уравнение которой имеет вид:

y² + y = x³ - x²

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки

А (0, 0), В (1, -1), С (1, 0) и D (0, -1)

Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:

На плоскости существует бесконечно удаленная точка 0 Е, в которой сходятся все вертикальные прямые.
Будем считать, что касательная к кривой пересекает точку касания два раза.
Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть 0.

Введем следующие правила сложения точек на эллиптической кривой:

Точка 0 выступает в роли нулевого элемента. Так, 0 = -0 и для любой точки Р на эллиптической кривой Р + 0 = Р.
Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х - скажем, S = (x, y) и T = (x, -y). Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р₁ + Р₂ + 0 = 0 и Р₁ = -Р₂.
Чтобы сложить две точки P и Q (см. рисунок 11.2) с разными координатами х, следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой. Если прямая не является касательной к кривой в точках P или Q, то существует только одна такая точка, обозначим ее S. Согласно нашему предположению

P + Q + S = О

Следовательно,

P + Q = -SилиP + Q = T

Если прямая является касательной к кривой в какой-либо из точек P или Q, то в этом случае следует положить S = P или S = Q соответственно.

Чтобы удвоить точку Q, следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой. Тогда Q + Q = 2 × Q = -S.

Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р.

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

y² = x³ + ax + b (mod p)

Такую кривую будем обозначать E_p (a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию 4a³ + 27b² (mod p) ¹ 0. Множество точек на эллиптической кривой вычисляется следующим образом.

1. Для каждого такого значения х, что 0 х р, вычисляется x³ + ax + b (mod p).

2. Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в E_p (a,b) нет точек с этим значением х. Если корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0). Эти значения (x,y) и будут точками E_p (a,b).

Множество точек E_p (a,b) обладает следующими свойствами:

1. Р + 0 = Р

2. Если Р = (x,y), то Р + (x,-y) = 0. Точка (x,-y) является отрицательным значением точки Р и обозначается -Р. Заметим, что (x,-y) лежит на эллиптической кривой и принадлежит E_p (a,b).

3. Если Р = (x₁,y₁) и Q = (x₂,y₂), где P Q, то P + Q = (x₃,y₃) определяется по следующим формулам:

4. x₃

λ2 - x₁ - x₂ (mod p)5. y₃

λ (x₁ - x₃) - y₁ (mod p)

где

(y₂ - y₁)/(x₂ - x₁) , если P ¹ Q λ = { (3x₁² + a)/2y₁ , если P = Q

Число λ есть угловой коэффициент секущей, проведенной через точки P = (x₁, y₁) и Q = (x₂, y₂). При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления λ.

Задача, которую должен решить в этом случае атакующий, есть своего рода задача "дискретного логарифмирования на эллиптической кривой", и формулируется она следующим образом. Даны точки P и Q на эллиптической кривой E_p (a,b). Необходимо найти коэффициент k < p такой, что

P = k × Q

Относительно легко вычислить P по данным k и Q, но довольно трудно вычислить k, зная P и Q.

Домашнее задание

Вариант соответствует последней цифре номера студенческого билета.

Пусть эллиптическая кривая задана уравнением y²=(x³+3x+5) mod 17, а образующая точка (элемент) G(x,y) = (1,3).

Вычислить согласно номеру варианта следующие выражения (исходные данные находятся в Таблица 1):

S=P(x₁,y₁) + P(x₁,y₁)

T=P(x₁,y₁) + Q(x₂,y₂)

M=P(x₁,y₁) ´ k

Таблица 1 Исходные данные для домашнего задания.

Вариант	Точка P(x₁,y₁)	Точка Q(x₂,y₂)	Множитель k
1	(16,16)	(4,8)	3
2	(11,3)	(5,14)	5
3	(9,9)	(15,12)	7
4	(15,12)	(2,6)	3
5	(2,6)	(12,16)	5
6	(12,16)	(12,1)	7
7	(6,1)	(2,11)	3
8	(10,10)	(15,5)	5
9	(9,8)	(5,3)	7
0	(11,14)	(4,9)	3

Содержание протокола

1.4.1. Название работы.

1.4.2. Цель работы.

1.4.3. Выполненное домашнее задание

1.4.4. Выполненное лабораторное задание

1.4.5. Выводы.

Ключевые вопросы

1.5.1. Запишите уравнение эллиптической кривой в общем виде.

1.5.2. Расскажите три предположения описывающих сложение на эллиптической кривой.

1.5.3. Расскажите три геометрических правила сложения точек на эллиптической кривой.

1.5.4. Расскажите правило удвоения точки на эллиптической кривой.

1.5.5. В каком случае при сложении точек вычисляется угловой коэффициент секущей, а в каком угловой коэффициент касательной. Запишите как его вычислить в каждом случае.

1.5.6. Опишите процесс умножения точки на число на эллиптической кривой.

Лабораторное задание

1.6.1. Показать преподавателю выполненное домашнее задание

1.6.2. Зепустить программу EllipticCrypt.exe

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

1.6.4. Записать выводы.

Алгоритм распределения ключей на эллиптических кривых

Цель работы

Исследовать алгоритм распределения сеансовых ключей на основе эллиптических кривых

Ключевые положения

Дата добавления: 2022-11-11; просмотров: 25; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!