Модуль 2. Математичні основи криптографії 1

Лекция 6 Криптография с использованием эллиптических кривых 1. Основные понятия 2. Способы использования эллиптических кривых 2

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

4 В общем случае уравнение эллиптической кривой Е имеет вид: y 2 + axy + by = x 3 + cx 2 + dx + e 1. Основные понятия

5 Пример y 2 + y = x 3 - x 2 На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки А (0, 0), В (1, -1), С (1, 0) и D (0, -1) 1. Основные понятия

6

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

8

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

10 Поскольку P + Q + S = О Следовательно, P + Q = -S или P + Q = T 1. Основные понятия

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

12 Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р 1. Основные понятия

13 Элементами эллиптических кривых в криптографии являются пары неотрицательных целых чисел, которые меньше р (простое число) и удовлетворяют частному виду эллиптической кривой: y 2 x 3 + ax + b (mod p) 1. Основные понятия

Эллиптическая кривая: y 2 x 3 + ax + b (mod p) обозначается E p (a,b) Числа а и b должны быть меньше р и должны удовлетворять условию 4a b 2 (mod p) Основные понятия

15 Алгоритм вычисления точек на эллиптической кривой: 1. Основные понятия Для каждого х ( 0 х р) вычисляется x 3 + ax + b (mod p) Выясняется: имеет ли это значение квадратный корень Если корень – есть, то эти два значения (х,у) являются точками E p (a,b)

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

Если Р = (x 1,y 1 ) и Q = (x 2,y 2 ), где P Q, то P + Q = (x 3,y 3 ) Где: x 3 λ 2 - x 1 - x 2 (mod p) y 3 λ (x 1 - x 3 ) - y 1 (mod p) Основные понятия Свойства множества точек E p (a,b)

(y 2 - y 1 )/(x 2 - x 1 ), если P Q λ = { (3x a)/2y 1, если P = Q Число λ есть угловой коэффициент секущей, проведенной через точки P = (x 1, y 1 ) и Q = (x 2, y 2 ). При P = Q секущая превращается в касательную Основные понятия Свойства множества точек E p (a,b)

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

20 Выбирается простое число р и параметры a и b для уравнения эллиптической кривой. Это задает множество точек E p (a,b). В E p (a,b) выбирается генерирующая точка G = (x 1,y 1 ). При выборе G важно, чтобы наименьшее значение n, при котором n × G = 0, оказалось очень большим простым числом. Параметры E p (a,b) и G криптосистемы являются параметрами, известными всем участникам. 2. Способы использования эллиптических кривых Задача обмена ключами Подготовительный этап

21 Участник А выбирает целое число n A, меньшее n. Это число является закрытым ключом участника А. Участник А вычисляет открытый ключ P A = n A × G (это - точка на E p (a,b). Участник В выбирает закрытый ключ n B и вычисляет открытый ключ P B. Участники обмениваются открытыми ключами, и вычисляют общий секретный ключ K 2. Способы использования эллиптических кривых Задача обмена ключами Расчет открытого ключа

22 Участник А: K = n A × P B Участник В: K = n В × P А Общий секретный ключ – это пара чисел. Если ключ предполагается использовать в качестве сеансового ключа для алгоритма симметричного шифрования, то из этой пары необходимо создать одно значение. 2. Способы использования эллиптических кривых Задача обмена ключами Расчет общего секретного ключа

23 Создание ключей: Выбирается эллиптическая кривая E p (a,b). Число точек на ней должно делиться на большое целое n. Выбирается точка Р E p (a,b). Выбирается случайное число d [1, n-1] Вычисляется Q = d × P. Закрытым ключом является d, открытым ключом - (E, P, n, Q). 2. Способы использования эллиптических кривых Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

24 Создание подписи: Выбирается случайное число k [1, n-1]. Вычисляется k × P = (x 1, y 1 ) и r = x 1 (mod n) Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k. 2. Способы использования эллиптических кривых Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

25 Вычисляется k -1 mod n s = k -1 (Н(M) + dr) (mod n) Проверяется, чтобы s не было равно нулю, так как в этом случае необходимого для проверки подписи числа s -1 mod n не существует. Если s = 0, то выбирается другое случайное число k. Подписью для сообщения М является пара чисел (r,s). 2. Способы использования эллиптических кривых Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

26 Проверка подписи: Числа r и s должны принадлежать [0, n-1]. Иначе подпись отвергается. Вычислить w = s -1 (mod n) и H(M) u 1 = H(M) w (mod n) u 2 = rw (mod n) u 1 P + u 2 Q = (x 0, y 0 ) v = x 0 (mod n) Подпись верна, когда v = r 2. Способы использования эллиптических кривых Алгоритм цифровой подписи на основе эллиптических кривых ECDSA

27 Параметры - эллиптическая кривая E p (a,b) и точка G на ней. Участник B выбирает закрытый ключ n B и вычисляет открытый ключ P B = n B × G. Чтобы зашифровать сообщение P m используется открытый ключ получателя B P B. Участник А выбирает случайное целое положительное число k и вычисляет зашифрованное сообщение C m, являющееся точкой на эллиптической кривой. C m = {k × G, P m + k × P B } 2. Способы использования эллиптических кривых Шифрование/дешифрование с использованием эллиптических кривых

28 Чтобы дешифровать сообщение, участник В умножает первую координату точки на свой закрытый ключ и вычитает результат из второй координаты: P m + k × P B - n B × (k × G) = P m + k × (n B × G) - n B × (k × G) = P m 2. Способы использования эллиптических кривых Шифрование/дешифрование с использованием эллиптических кривых

29 Участник А зашифровал сообщение P m добавлением к нему kxP B. Никто не знает значения k, поэтому, хотя P B и является открытым ключом, никто не знает k × P B. Противнику для восстановления сообщения придется вычислить k, зная G и k × G. Сделать это будет нелегко. 2. Способы использования эллиптических кривых Шифрование/дешифрование с использованием эллиптических кривых

30 Получатель также не знает k, но ему в качестве подсказки посылается k × G. Умножив k × G на свой закрытый ключ, получатель получит значение, которое было добавлено отправителем к незашифрованному сообщению. Тем самым получатель, не зная k, но имея свой закрытый ключ, может восстановить незашифрованное сообщение. 2. Способы использования эллиптических кривых Шифрование/дешифрование с использованием эллиптических кривых