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

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

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

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

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

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

6 6

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

8 8

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

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

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

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

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

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

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

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

17 Если Р = (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)

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

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

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

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

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

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

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