Лабораторные и практики / 01_ПЗ / 1_ПЗ
.pdf
МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА» (СПбГУТ)
_____________________________________________________________________________
Кафедра информационной безопасности телекоммуникационных систем Дисциплина «Основы криптографии с открытыми ключами»
Практическое задание 1
« Исследование криптосистем с открытым ключом на основе эллиптических кривых»
Выполнила: |
студ. гр. |
|
. |
. .
Проверил: |
проф. Яковлев В.А.. |
Санкт-Петербург
2021
Цель работы:
Приобретение навыков вычислений с использованием матаппарата эллиптических кривых. Моделирование алгоритмов криптосистем с открытыми ключами на основе эллиптических кривых и их анализ.
Ход работы:
Вариант 6.
|
|
|
Задано |
|
|
|
Найти |
||
Nвар |
A |
|
B |
k |
|
C |
-C |
|
kC |
6 |
8,1 |
|
0,12 |
5 |
|
|
|
|
|
Задание 1. |
|
|
|
|
|
|
|
|
|
Задана эллиптическая кривая Е13(1,1) |
|
в поле GF(13) |
по уравнению |
||||||
y2 x3 x 1. (Уравнение вида 2 = 3 |
+ + , где a=1, b=1.) |
||||||||
Проверка принадлежности точек заданной кривой: |
|||||||||
A(8,1) |
: |
12 13 = 1 |
|
|
|
|
|
||
|
: |
83 + 8 + 1 13 = 521 13 = 1 |
|
|
|||||
Так как x=y, то точка A принадлежит заданной кривой. |
|||||||||
B(0,12) |
: |
122 13 = 144 13 = 1 |
|
|
|
||||
|
x: |
03 + 0 + 1 13 = 1 |
|
|
|
|
|
||
Так как x=y, то точка B принадлежит заданной кривой.
Взаимообратные точки:
A(8;1) → A’(8;12)
B(0;12) → B’(0;1)
Вычисления:
1. Найдем точку C по формуле ( 3, 3) = ( 1, 1) + ( 2, 2) Так как A≠B, то
= (y2 − y1)(x2 − x1)−1 13 = (12 − 1) ∙ (0 − 8)−1 13 =
= 11 13 ∙ (−8)−1 13 = 11 13 ∙ 5−1 13 =
−1 (mod p) = 5−1 (mod 13) =?
Ищем обратный элемент
13 = 5 ∙ 2 + 3 3 = 13 − 5 ∙ 2
5 = 3 ∙ 1 + 2 |
|
2 = 5 − 3 ∙ 1 2 = 5 − 2 ∙ 1 − 1 = |
3 = 2 ∙ 1 + 1 |
|
1 = 3 − 2 ∙ 1 |
1 = 3 − 2 ∙ 1 = 3 − (5 − 3 ∙ 1) ∙ 1 =
=(13 − 5 ∙ 2) − (5 − (13 − 5 ∙ 2) ∙ 1) ∙ 1 =
=13 − 5 ∙ 2 − 5 + 13 − 5 ∙ 2 = −5 ∙ 5 + 13 ∙ 2
−5 13 = 8 5−1 (mod 13) = 8
= 8 ∙ 11 13 = (78 + 10) 13 = 10
x3 = ( 2 − x1 − x2) 13 = (102 − 8 − 0) 13 = (91 + 1) 13 = 1
y3 = ( (x1 − x3) − 1) 13 = (10 ∙ (8 − 1) − 1) 13 = (65 + 4) 13 = 4
|
|
= , |
|
= |
|
|
|
|
(1,4)
2. Поиск противоположной точки C
( 3, 3) => − (1, −4) → − (1,9)
3. Умножение на константу k=5
= = 5 = + + + + = 2(2 ) +
1) ( 3, 3) = (1,4)
Так как С=С, то
= (3x32 + )(2y3)−1 13 = (3 ∙ 12 + 1)(2 ∙ 4)−1 13 =
= 4 ∙ 8−1 13
−1 (mod p) = 8−1 (mod 13) =?
Ищем обратный элемент
13 = 8 + 5 5 = 13 − 8
8 = 5 + 3 |
3 = 8 − 5 |
5 = 3 + 2 |
2 = 5 − 3 |
3 = 2 + 1 |
1 = 3 − 2 |
1 = 3 − 2 = 8 − 5 − 5 + 8 − 5 = = 8 − 13 + 8 − 13 + 8 + 8 − 13 + 8 = 8 ∙ 5 − 13 ∙ 3 8−1 (mod 13) = 5
= 4 ∙ 5 13 = (13 + 7) 13 = 7
x4 = ( 2 − 2x3) 13 = (72 − 2 ∙ 1) 13 = (39 + 8) 13 = 8 y4 = ( (x3 − x4) − 3) 13 = (7 ∙ (1 − 8) − 4) 13 =
= (−52 − 1) 13 = (−1) 13 = 12
|
|
= , = |
|
|
|
2 = (8,12) |
||
2) |
(x4, y4) = (8,12) |
|
Так как R=R, то
= (3x42 + )(2y4)−1 13 = (3 ∙ 82 + 1)(2 ∙ 12)−1 13 = = (182 + 11) ∙ (13 + 11)−1 13 = 11 ∙ 11−1 13
−1 (mod p) = 11−1 (mod 13) =?
Ищем обратный элемент
13 |
= 11 + 2 2 = 13 − 11 |
11 = 2 ∙ 5 + 1 1 = 11 − 2 ∙ 5 |
|
1 = 11 − 2 ∙ 5 = 11 − 13 ∙ 5 + 11 ∙ 5 = 11 ∙ 6 − 13 ∙ 5 11−1 (mod 13) = 6
= 11 ∙ 6 13 = (65 + 1) 13 = 1
x5 = ( 2 − 2x4) 13 = (12 − 2 ∙ 8) 13 = (−13 − 2) 13 = 11
y5 = ( (x4 |
− x5) − 4) 13 = ((8 − 11) − 12) 13 = |
|||||||
= (−15) 13 = 11 |
|
|||||||
|
|
= , |
|
|
= |
|
||
|
|
|
|
|
|
|
||
2 = (11,11) |
|
|
|
|||||
3) |
( 3, 3) = (1,4) |
и (x5, 5) = (11,11) |
||||||
Так как С≠Q, то |
|
|
||||||
= (y − y |
)(x |
5 |
− x |
)−1 13 = (11 − 4) ∙ (11 − 1)−1 13 = |
||||
|
|
5 |
3 |
|
|
3 |
|
|
= 7 ∙ 10−1 13 =
−1 (mod p) = 10−1 (mod 13) =?
Ищем обратный элемент
13 = 10 + 3 3 = 13 − 10 10 = 3 ∙ 3 + 1 1 = 10 − 3 ∙ 3
1 = 10 − 3 ∙ 3 = 10 − 3 ∙ (13 − 10) = 10 ∙ 4 − 13 ∙ 3 10−1 (mod 13) = 4
= 7 ∙ 4 13 = (26 + 2) 13 = 2
x6 |
= ( 2 − x3 − x5) 13 = (22 − 1 − 11) 13 = (−8) 13 = 5 |
||
y6 |
= ( (x3 − x6) − 3) 13 = (2 ∙ (1 − 5) − 4) 13 |
||
|
|
|
= (−12) 13 = 1 |
|
|
= , |
= |
|
|
|
|
= = 5 , |
(5,1) |
||
Задание 2.
Моделирование криптосистемы Эль-Гамаля на эллиптической кривой
|
|
( , ) – кривая, |
|
|
|
|
|
|
|
|
||
|
|
= + + – уравнение кривой |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Вариант 6. |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Задано |
|
|
|
|
Вычислить |
|
|||
Nвар |
d |
r |
|
|
|
E1 |
E2 |
|
C1 |
C2 |
||
6 |
|
|
2 |
5 |
|
|
|
|
|
|
|
|
1. |
|
Генерирование ключей |
|
|
|
|
||||||
|
( , ) = (0,4) |
= 42 67 = 16 |
|
|
|
|||||||
1 |
|
|
1 |
= 02 + 2 ∙ 0 + 6 = 6 |
|
|
|
|||||
|
|
|
|
|
|
|
||||||
Так как x≠y, то точка 1 |
не принадлежит заданной кривой. |
|
||||||||||
2 = 1 = 2 1
1(x1, y1) = 1(0,4), Так как 1 = 1, то
= (3x12 + )(2y1)−1 67 = (3 ∙ 02 + 2)(2 ∙ 4)−1 67 =
= 2 ∙ 8−1 67 = 2 ∙ 8−1 67
−1 (mod p) = 8−1 (mod 67) =?
Ищем обратный элемент
67 = 8 ∙ 8 + 3 3 = 67 − 8 ∙ 8 8 = 3 ∙ 2 + 2 2 = 8 − 3 ∙ 2 3 = 2 + 1 1 = 3 − 2
1 = 3 − 2 = 3 − 8 + 3 ∙ 2 = 67 − 8 ∙ 8 − 8 + 67 ∙ 2 − 8 ∙ 8 ∙ 2 = = 67 ∙ 3 − 8 ∙ 25
8−1 (mod 67) = (−25)mod 67 = 42
= 2 ∙ 42 67 = 84 |
67 = 17 |
|
|||
x2 |
= ( 2 − 2x1) 67 = (172 − 2 ∙ 0) 67 = (268 + 21) 67 = 21 |
||||
y2 |
= ( (x1 − x2) − 1) |
67 = (17 ∙ (0 − 21) − 4) 67 = |
|||
= (−361) 67 = (−361 − 26) 67 = 41 |
|
||||
x2 |
= 21, y2 = 41 |
|
|
|
|
Открытый ключ: |
( , ); |
( , ); |
( , ) |
||
|
|
|
|
|
|
Закрытый ключ: |
= |
|
|
|
|
2. Шифрование сообщения( , ) - сообщение (произвольная точка),
1 = 1 = 5 1 = 2(2 1) + 1
1)2 1 = 2(21, 41)
2)2( 2, 2) = 2(21, 41)
Так как 2 = 2, то
= (3x22 + )(2y2)−1 67 = (3 ∙ 212 + 2)(2 ∙ 41)−1 67 = = 1325 ∙ 82−1 67 = 52 ∙ 15−1 67
−1 (mod p) = 15−1 (mod 67) =?
Ищем обратный элемент
67 = 15 ∙ 4 + 7 7 = 67 − 15 ∙ 4 15 = 7 ∙ 2 + 1 1 = 15 − 7 ∙ 2
1 = 15 − 7 ∙ 2 = 15 − 67 ∙ 2 + 15 ∙ 8 = 15 ∙ 9 − 67 ∙ 2 15−1 (mod 67) = 9
= 51 ∙ 9 67 = (402 + 57) 67 = 57
x3 = ( 2 − 2x2) 67 = (572 − 2 ∙ 21) 67 = (3149 + 58) 67 = = 58
y3 = ( (x2 − x3) − 2) 67 = (57 ∙ (21 − 58) − 41) 67 = = (−2144 − 6) 67 = (−6) 67 = 61
x3 = 58, y3 = 61
2 2 = (58, 61)
3) 1(x1, 1) = 1(0,4) и ( 3, 3) = (58, 61)
Так как O≠M, то
= (y1 − y3)(x1 − x3)−1 67 = (4 − 61) ∙ (0 − 58)−1 67 = = (−57) ∙ (−58)−1 67 = 10 ∙ 9−1 67
−1 (mod p) = 9−1 (mod 67) =?
Ищем обратный элемент
67 = 9 ∙ 7 + 4 4 = 67 − 9 ∙ 7 9 = 4 ∙ 2 + 1 1 = 9 − 4 ∙ 2
|
1 = 9 − 4 ∙ 2 = 9 − 67 ∙ 2 + 9 ∙ 14 = 9 ∙ 15 − 67 ∙ 2 |
|
|
9−1 (mod 67) = 15 |
|
|
= 10 ∙ 15 67 = (134 + 16) 67 = 16 |
|
|
x4 = ( 2 − x3 − x1) 67 = (162 − 58 − 0) 67 |
|
|
|
= (134 + 64) 67 = 64 |
|
y4 = ( (x3 − x4) − 3) 67 = (16 ∙ (58 − 64) − 61) 67 = |
|
|
= (−134 − 23) 67 = 44 |
|
|
x4 = 64, |
y4 = 44 |
1 |
= 1 = 5 1 |
= 2(2 1) + 1, 1(64, 44) |
2 |
= + 2 = + 5 2 = + 5(2 1) = + 10 1 = + 2(5 1) = + 2 1 |
|
2 |
= + 2 1, |
где (5, 1) |
|
1) 1(64, 44) = 1(x4, 4) |
|
Так как 1 = 1, то
= (3x42 + )(2y4)−1 67 = (3 ∙ 642 + 2)(2 ∙ 44)−1 67 = = (183 ∙ 67 + 29) ∙ 21−1 67 = 29 ∙ 21−1 67
−1 (mod p) = 21−1 (mod 67) =?
Ищем обратный элемент
67 = 21 ∙ 3 + 4 4 = 67 − 21 ∙ 3 21 = 4 ∙ 5 + 1 1 = 21 − 4 ∙ 5
1 = 21 − 4 ∙ 5 = 21 − 67 ∙ 5 + 21 ∙ 15 = 21 ∙ 16 − 67 ∙ 5 21−1 (mod 67) = 16
= 29 ∙ 16 67 = (402 + 62) 67 = 62
x5 = ( 2 − 2x4) 67 = (622 − 2 ∙ 64) 67 = (2685 + 31) 67 =
= 31
y5 |
= ( (x4 |
− x5) − 4) 67 = (62 ∙ (64 − 31) − 44) 67 = |
|
= (1943 |
+ 59) 67 = 59 |
||
x5 |
= 31, |
|
y5 = 59 |
2 1 = (31, 59)
2) (x5, y5) = (31, 59) и (x6, 6) = (5, 1)
Так как N≠P, то
= (y5 − y6)(x5 − x6)−1 67 = (59 − 1) ∙ (31 − 5)−1 67 = = 58 ∙ 26−1 67
−1 (mod p) = 26−1 (mod 67) =?
Ищем обратный элемент
67 |
= 26 |
∙ 2 + 15 |
15 = 67 − 26 ∙ 2 |
|
26 |
= 15 |
+ 11 |
|
11 = 26 − 15 |
15 |
= 11 |
+ 4 |
|
4 = 15 − 11 |
11 = 4 ∙ 2 + 3 3 = 11 − 4 ∙ 2
4 = 3 + 1 1 = 4 − 3
1 = 4 − 3 = 4 − 11 + 4 ∙ 2 = 15 ∙ 3 − 11 ∙ 3 − 11 =
=15 ∙ 3 − 11 ∙ 4 = 15 ∙ 3 − 26 ∙ 4 + 15 ∙ 4 = 15 ∙ 7 − 26 ∙ 4 =
=67 ∙ 7 − 26 ∙ 14 − 26 ∙ 4 = 67 ∙ 7 − 26 ∙ 18
|
26−1 (mod 67) = (−18)mod67 = 49 |
|
|
= 58 ∙ 49 67 = (2814 + 28) 67 = 28 |
|
|
x7 = ( 2 − x5 − x6) 67 = (282 − 31 − 5) 67 |
|
|
|
= (737 + 11) 67 = 11 |
|
y7 = ( (x5 − x7) − 5) 67 = (28 ∙ (31 − 11) − 59) 67 = |
|
|
= (469 + 32) 67 = 32 |
|
|
x7 = 11, |
y7 = 32 |
2 = + 2 1, |
2(x7, y7) |
|
|
( , ), ( , ) - криптограмма |
|
|
|
|
3. Расшифрование криптограммы′ = 2 − ( 1), где −( 1) противоположный элемент к точке 1
1) = 2, 2 1 рассчитали ранее, 2 1 = (31, 59)
Противоположный элемент к точке 1:
(31, 59) => − (31, −59) → − (31, 8)( 8, 8) = (31, 8), 2(x7, y7) = 2(11, 32)
2) ′ = 2 +
Так как 2 ≠ , то
= (y8 − y7)(x8 − x7)−1 67 = (8 − 32) ∙ (31 − 11)−1 67 =
= 43 ∙ 20−1 67
−1 (mod p) = 20−1 (mod 67) =?
Ищем обратный элемент
67 = 20 ∙ 3 + 7 7 = 67 − 20 ∙ 3
20 = 7 ∙ 2 + 6 6 = 20 − 7 ∙ 2 7 = 6 + 1 1 = 7 − 6
1 = 7 − 6 = 7 ∙ 3 − 20 = 67 ∙ 3 − 20 ∙ 10 20−1 (mod 67) = (−10)mod67 = 57
= 43 ∙ 57 67 = (2412 + 39) 67 = 39
x9 = ( 2 − x8 − x7) 67 = (392 − 31 − 11) 67 = (1474 + 5) 67 = 5
y9 = ( (x8 − x9) − 8) 67 = (39 ∙ (31 − 5) − 8) 67 =
= (1005 + 1) 67 = 1
x9 = 5, y9 = 1
′(5, 1) – расшифрованное сообщение
= ′, сообщение успешно зашифровано и расшифровано.
Вывод:
В ходе выполнения практического задания мы приобрели навыки вычислений с использованием матаппарата эллиптических кривых. Провели моделирование криптосистемы Эль-Гамаля на основе эллиптической кривой.