§ 4. Применение эллиптических кривых в криптографии
Перед шифрованием необходимо выбрать способ кодирования текста. Для этого найдены точки на кривой и некоторым из них поставлены в соответствие символы.
Пример кодирования и декодирования текста. Алфавит представляет собой множество символов языка открытых текстов и соответствующих им точек эллиптической кривой над конечным полем.
Выбрана
кривая
т. е.
(mod
751). Предлагается следующий (один из
возможных) алфавит (табл. 9).
Таблица 9
Алфавит точек эллиптической кривой для выполнения индивидуальных заданий
№ |
Символ |
Точка |
№ |
Символ |
Точка |
№ |
Символ |
Точка |
№ |
Символ |
Точка |
1 |
пробел |
(33, 355) |
41 |
H |
(72, 254) |
81 |
p |
(109, 200) |
121 |
Щ |
(218, 601) |
2 |
! |
(33, 396) |
42 |
I |
(72, 497) |
82 |
q |
(109, 551) |
122 |
Ъ |
(221, 138) |
3 |
" |
(34, 74) |
43 |
J |
(73,72) |
83 |
r |
(110, 129) |
123 |
Ы |
(221, 613) |
4 |
# |
(34, 677) |
44 |
K |
(73, 679) |
84 |
s |
(110, 622) |
124 |
Ь |
(226, 9) |
5 |
$ |
(36, 87) |
45 |
L |
(74, 170) |
85 |
t |
(114, 144) |
125 |
Э |
(226, 742) |
6 |
% |
(36, 664) |
46 |
M |
(74, 581) |
86 |
u |
(114, 607) |
126 |
Ю |
(227, 299) |
7 |
& |
(39, 171) |
47 |
N |
(75, 318) |
87 |
v |
(115, 242) |
127 |
Я |
(227, 452) |
8 |
' |
(39, 580) |
48 |
O |
(75, 433) |
88 |
w |
(115, 509) |
128 |
а |
(228, 271) |
9 |
( |
(43, 224) |
49 |
P |
(78, 271) |
89 |
x |
(116, 92) |
129 |
б |
(228, 480) |
10 |
) |
(43, 527) |
50 |
Q |
(78, 480) |
90 |
y |
(116, 659) |
130 |
в |
(229, 151) |
11 |
* |
(44, 366) |
51 |
R |
(79, 111) |
91 |
z |
(120, 147) |
131 |
г |
(229, 600) |
12 |
+ |
(44, 385) |
52 |
S |
(79, 640) |
92 |
{ |
(120, 604) |
132 |
д |
(234, 164) |
13 |
, |
(45, 31) |
53 |
T |
(80, 318) |
93 |
| |
(125, 292) |
133 |
е |
(234, 587) |
14 |
- |
(45, 720) |
54 |
U |
(80, 433) |
94 |
} |
(125, 459) |
134 |
ж |
(235, 19) |
15 |
. |
(47, 349) |
55 |
V |
(82, 270) |
95 |
~ |
(126, 33) |
135 |
з |
(235, 732) |
16 |
/ |
(47, 402) |
56 |
W |
(82, 481) |
96 |
А |
(189, 297) |
136 |
и |
(236, 39) |
17 |
0 |
(48,49) |
57 |
X |
(83, 373) |
97 |
Б |
(189, 454) |
137 |
й |
(236, 712) |
18 |
1 |
(48, 702) |
58 |
Y |
(83, 378) |
98 |
В |
(192, 32) |
138 |
к |
(237, 297) |
19 |
2 |
(49, 183) |
59 |
Z |
(85, 35) |
99 |
Г |
(192, 719) |
139 |
л |
(237, 454) |
20 |
3 |
(49, 568) |
60 |
[ |
(85, 716) |
100 |
Д |
(194, 205) |
140 |
м |
(238, 175) |
21 |
4 |
(53, 277) |
61 |
\ |
(86,25) |
101 |
Е |
(194, 546) |
141 |
н |
(238, 576) |
22 |
5 |
(53, 474) |
62 |
] |
(86, 726) |
102 |
Ж |
(197, 145) |
142 |
о |
(240, 309) |
23 |
6 |
(56, 332) |
63 |
^ |
(90,21) |
103 |
З |
(197, 606) |
143 |
п |
(240, 442) |
24 |
7 |
(56, 419) |
64 |
_ |
(90, 730) |
104 |
И |
(198, 224) |
144 |
р |
(243, 87) |
25 |
8 |
(58, 139) |
65 |
` |
(93, 267) |
105 |
Й |
(198, 527) |
145 |
с |
(243, 664) |
26 |
9 |
(58, 612) |
66 |
a |
(93, 484) |
106 |
К |
(200, 30) |
146 |
т |
(247, 266) |
27 |
: |
(59, 365) |
67 |
b |
(98, 338) |
107 |
Л |
(200, 721) |
147 |
у |
(247, 485) |
28 |
; |
(59, 386) |
68 |
c |
(98, 413) |
108 |
М |
(203, 324) |
148 |
ф |
(249, 183) |
29 |
< |
(61, 129) |
69 |
d |
(99, 295) |
109 |
Н |
(203, 427) |
149 |
х |
(249, 568) |
30 |
= |
(61, 622) |
70 |
e |
(99, 456) |
110 |
О |
(205, 372) |
150 |
ц |
(250, 14) |
31 |
> |
(62, 372) |
71 |
f |
(100, 364) |
111 |
П |
(205, 379) |
151 |
ч |
(250, 737) |
32 |
? |
(62, 379) |
72 |
g |
(100, 387) |
112 |
Р |
(206, 106) |
152 |
ш |
(251, 245) |
33 |
@ |
(66, 199) |
73 |
h |
(102, 267) |
113 |
С |
(206, 645) |
153 |
щ |
(251, 506) |
34 |
A |
(66, 552) |
74 |
i |
(102, 484) |
114 |
Т |
(209, 82) |
154 |
ъ |
(253, 211) |
35 |
B |
(67,84) |
75 |
j |
(105, 369) |
115 |
У |
(209, 669) |
155 |
ы |
(253, 540) |
36 |
C |
(67, 667) |
76 |
k |
(105,382) |
116 |
Ф |
(210, 31) |
156 |
ь |
(256, 121) |
37 |
D |
(69, 241) |
77 |
l |
(106, 24) |
117 |
Х |
(210, 720) |
157 |
э |
(256, 630) |
38 |
E |
(69, 510) |
78 |
m |
(106, 727) |
118 |
Ц |
(215, 247) |
158 |
ю |
(257, 293) |
39 |
F |
(70, 195) |
79 |
n |
(108, 247) |
119 |
Ч |
(215, 504) |
159 |
я |
(257, 458) |
40 |
G |
(70, 556) |
80 |
o |
(108, 504) |
120 |
Ш |
(218,150) |
|
|
|
Заметим, что мощность множества точек на этой кривой N = 727, поэтому при необходимости можно точками закодировать и некоторые специальные знаки (например, знак интеграла и т. п.), а также целые слова.
Приведем примеры решения контрольных заданий, представленных ниже.
Пример
шифрования. Пусть
выбрана генерирующая точка G
=
(0, 1). Предположим,
пользователь А
решил отправить пользователю
B
сообщение:
строчную латинскую букву «A».
В нашем алфавите эта буква кодируется
точкой
= (66, 522). Пусть пользователь А
выбрал случайное значение k
= 3, а открытым
ключом B
является точка
= (406, 397), при
этом секретным ключом B
является число
.
Шифрованный
текст имеет вид
= {kG,
+ k
}.
Находим
kG
=
.
Для нахождения 3G используем правила сложения точек эллиптической кривой. Напомним их:
Вычисляем 2G:
Итак, мы нашли 2G = (188,93). Теперь находим 3G:
Таким образом, мы нашли точку kG = = (56, 419).
Вычисляем
+ k
= (66, 552)
+
(406,
397) = (301, 734).
В результате: = {(56, 419), (301, 734)}.
Пользователь
B
для расшифрования сообщения должен
провести следующие вычисления:
+ k
–
(kG)
=
+
k
(
G)
–
(kG)
= = (301, 734) – 45·(56, 419) = (301, 734) + (175, 559)
= (66, 552).
После этого пользователь B по алфавиту определяет открытый буквенный текст: точке (66, 552) соответствует строчная латинская буква A.
Приведем еще один пример зашифрования.
Входные данные
Кривая:
Генерирующая
точка:
Открытый текст: «терновник»
Открытый ключ: (188,93)
Значения случайных чисел 𝑘 для букв открытого текста:
8, 14, 17, 17, 2, 10, 8, 2, 2
Таблица 10.
Соответствие точек эллиптической кривой буквам открытого текста.
т |
(247, 266) |
в |
(229, 151) |
е |
(234, 587) |
н |
(238, 576) |
р |
(243, 87) |
и |
(236, 39) |
н |
(238, 576) |
к |
(237, 297) |
о |
(240, 309) |
|
|
Расчёт
=
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
;
=
=
=
=
.
Таблица 11.
Соответствие букв открытого текста точкам шифрованного текста.
Т |
(346, 242), (594, 414) |
в |
(377, 456), (517, 573) |
е |
(596, 433), (34, 677) |
н |
(346, 242), (288, 639) |
р |
(440, 539), (546, 670) |
и |
(188, 93), (209, 82) |
н |
(440, 539), (694, 581) |
к |
(188, 93), (205, 379) |
о |
(188, 93), (515, 684) |
|
|
Шифртекст:
;
;
;
;
;
;
;
;
.
Пример расшифрования.
Входные данные
Кривая:
Генерирующая
точка: 𝐺 =
Шифртекст:
,
;
,
;
,
;
,
;
,
;
.
Секретный
ключ:
= 44.
Расчёт
=
+
-
⋅ (𝑘𝐺) = ( 367, 360) – 44 ⋅ (377, 456) = (235, 732) →
«з»
=
(715, 938) – 44 ⋅ (425, 663) = (228, 271) → «а»
= (279, 353) – 44 ⋅ (188, 93) = (240, 309) → «о»
=
(128, 79) – 44 ⋅ (179, 275) = (243, 664) → «с»
=
(515, 67) – 44 ⋅ (568, 355) = (247, 266) → «т»
=
(482, 230) – 44 ⋅ (568, 355) = (235, 732) → «р»
=
(206, 645) – 44 ⋅ (377, 456) = (243, 87) → «е»
=
(300, 455) – 44 ⋅ (188, 93) = (238, 576) → «н»
=
(362, 446) - 44 ⋅ (489, 468) = (238, 576) → «н»
=
(69, 510) – 44 ⋅ (16, 416) = (253, 540) → «ы»
=
(218, 601) – 44 ⋅ (425, 663) = (236, 712) → «й»
Открытый текст – «заостренный».
Пример выполнения контрольного задания 3. Сложение точек.
Найти точку 2𝑃 + 3𝑄 – 𝑅
Кривая:
𝑃 = (72, 497)
𝑄 = (61, 622)
𝑅 = (70, 556)
Расчет
2𝑃 + 3𝑄 – 𝑅 = 2 ⋅ (72, 497) + 3 ⋅ (61, 622) - (70, 556) =
= (5, 11) + (198, 224) + (70, - 556) = (320, 744)