-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
644 lines (602 loc) · 46 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
<!DOCTYPE HTML>
<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="content-type">
<title>Алгоритм Эль Гамаля</title>
<link type="text/css" rel="stylesheet" href="css/normalize.css"/>
<link type="text/css" rel="stylesheet" href="css/style.css"/>
<link type="text/css" rel="stylesheet" href="css/TangleKit.css"/>
<script data-main="js/main" src="js/3rdparty/require.js"></script>
<script type="text/javascript" src="js/3rdparty/TangleKit/sprintf.js"></script>
<script src="js/elgamal.js"></script>
<script src="js/machines.js"></script>
</head>
<body>
<nav id = "header">
<div id = "title">Алгоритм Эль Гамаля</div>
<ul id = "menu">
<li>
<a href = "./methodical.html" class = "nav-link">Пособие</a>
</li>
<li>
<a href = "https://github.com/The220th/DM2020_AltExam_ElGamalEncryption" class = "nav-link">Github проект</a>
</li>
</ul>
</nav>
<div id="wrapper">
<div id = "introduction" class="block">
<h1 class = "title">Введение</h1>
<p class = "text">
Цель алгоритмов шифрования - помочь людям обмениваться секретной или конфиденциальной информацией друг с другом, используя информационный эквивалент физических ключей. Чтобы облегчить обсуждение, мы скажем, что Боб хочет послать Алисе сообщение, чтобы Ева не смогла его увидеть. С симметричным алгоритмом шифрования ключ, используемый для шифрования сообщения, совпадает с ключом, используемым для его расшифровки. Это аналогично тому, как Боб помещает свое сообщение в ящик, закрывает его и отправляет Алисе для открытия. Большая проблема с таким подходом состоит в том, что Алиса нуждается в копии ключа, который использовал Боб. Это проблема курицы и яйца: для безопасного обмена информацией друг с другом Алиса и Боб уже должны были обмениваться секретной информацией. Если Боб когда-нибудь отправит ключ Алисе, Ева может легко перехватить его и использовать для чтения своих сообщений. Теоретически, Боб может дать Алисе ключ лично, но на практике это не очень хорошо работает. Представьте, что вам нужно ехать в офис какой-либо компании, чтобы дать им номер вашей кредитной карты, прежде чем вы сможете что-то купить онлайн. Это ужасно неудобно!
<br/>
<br/>
Решением проблемы являются алгоритмы асимметричного шифрования,
которые не используют один и тот же ключ для шифрования и дешифрования.
Продолжая нашу аналогию с ящиками и физическими ключами, Алиса отправляет
разблокированный замок всем, кто хочет отправлять ей сообщения.
Боб кладет свое сообщение в ящик, запирает его замком Алисы и отправляет обратно Алисе.
Поскольку Алиса - единственная, у кого есть ключ от замка,
только она может прочитать сообщение, как только оно окажется в запертом ящике.
Алгоритм Эль Гамаля является примером информационного алгоритма,
который работает по этому принципу.
В основу криптографической системы Эль Гамаля
положена сложность задачи вычисления дискретных логарифмов в конечном поле.
Существуют эффективные алгоритмы возведения числа в степень в конечном поле,
однако восстановление показателя (дискретного логарифма) по известному
основанию и его степени является сложной математической задачей.
На сегодняшний день не известно ни одного эффективного алгоритма
вычисления дискретных логарифмов больших чисел
</p>
</div>
<div id="theory" class = "block">
<h1 class = "title">Немного вводной теории</h1>
<p class = "text">
Перед тем, как мы познакомимся с алгоритмом Эль Гамаля, мы должны понять несколько базовых вещей.
</p>
<div class = "example js-modulo-example">
<h3 class = "border_title">Сравнения</h3>
<p class = "text">
<strong>Сравнение двух целых чисел по модулю натурального числа m</strong> — математическая операция,
позволяющая ответить на вопрос о том, дают ли два выбранных целых числа
при делении на m один и тот же остаток.<br/>
Величина остатка может быть получена бинарной операцией «взятия остатка»
от деления, обозначаемой %%mod%%. Попробуйте:
</p>
<p class="center-example">
<span class="TKAdjustableNumber" data-var="moduloA" data-min="-100" data-max="100"></span>
%%
\bmod{} %%
<span class="TKAdjustableNumber" data-var="moduloB" data-min="-100"
data-max="100"></span>
%% = %%
<span data-var="moduloRes"></span>
</p>
<p class="text js-modulo-example-possibly-broken">Результат
<span data-var="moduloRes"> </span>
может быть также получен как
<span
data-var="moduloALookalike"> <span> </span></span>%% \bmod{} %% <span data-var="moduloB"></span>
,
<span
data-var="moduloA"> <span> </span></span>%% \bmod{} %% <span data-var="moduloB"></span>. Мы говорим, что
<span
data-var="moduloA"> <span> </span></span>и <span data-var="moduloALookalike"></span> сравнимы по модулю <span data-var="moduloB"></span>:</p>
<p class="js-modulo-example-possibly-broken center-example">
<span data-var="moduloA"></span> %% \equiv %% <span data-var="moduloALookalike"></span> (%%
\bmod{} %% <span data-var="moduloB"></span>)</p>
<p class = "text">
Операция сравнения по модулю является неотъемлемой частью многих систем шифрования.
Главное свойство, которое делает сравнение по модулю настолько полезным для алгоритмов шифрования,
заключается в том, что результат операции не раскрывает никакой информации о числе.
</p>
<p class = "text">
Узнайте больше про модульную арифетику на
<a href = "https://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E" target="_blank"><strong>Wikipedia</strong></a>.
</p>
</div>
<div class = "example">
<h3 class = "border_title">Конечные циклические группы и подгруппы</h3>
<p class = "text">
<strong>Циклическая группа</strong> — это математическая группа, порожденная одним из элементов в группе %%G%%.
Так как мы будем говорить об алгоритме Эль Гамаля, то нас интересуют только два типа групп:
</p>
<ul class = "list">
<li>
Группа целых чисел от %%1%% до %%p-1%% по операции умножения %%(mod p)%%
для некоторого простого числа %%p%%, которое известно как %%\mathbb{Z}_p^*%%
</li>
<li>
Подгруппы %%\mathbb{Z}_p^*%% простого порядка
</li>
</ul>
<p class = "text">
Узнайте больше о циклических группах на
<a href = "https://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0" target="_blank"><strong>Wikipedia</strong></a>.
</p>
</div>
</div>
<div id = "theory-chipher" class="block">
<h1 class = "title">Работа в режиме шифрования</h1>
<p class = "text">
Алиса хочет, чтобы люди могли отправлять ей секретные сообщения, поэтому она создает открытый ключ %%(p,g,y)%%,
которым она делится с миром и личный ключом %%x%%, который она никогда никому не рассказывает.
Боб хочет отправить Алисе секретное сообщение, поэтому он использует открытый ключ Алисы и одноразовый сессионный ключ %%k%%, создает зашифрованный текст %%(u, v)%%.<br/>
Вот как это работает:
</p>
<div class="example">
<p class="alice-column-start">
<img src="images/Alice.svg" alt="Alice" />
</p>
<p class="bob-column-start">
<img src="images/Bob.svg" alt="Bob" />
</p>
<p class="alice-column">1.Алиса выбирает простое число %%p%%</p>
<p class="alice-column">2.Выбирает целое число %%g%%, такое, что %%g%% - первообразный корень %%p%%,
который генерирует циклическую подгруппу %%\mathbb{Z}_p^*%% порядка %%n%%</p>
<p class="alice-column">3.Выбирает случайный секретный ключ, такой что %%1 \leq x \leq n-1%%.</p>
<p class="alice-column">3.Вычисляет %%y = g^x \pmod{p}%%</p>
<p class="alice-column send-right">5.Публикует открытый ключ %%(p,g,y)%%.</p>
<p class="bob-column">1.Смотрит на ключ Алисы %%(p,g,y)%%.</p>
<p class="bob-column">2.Боб выбирает случайное %%k%%, такое что %%1 \leq k \leq n-1%%</p>
<p class="bob-column">3.Создает сообщение %%m%%, такое что %%1 \leq m \leq p-1%%. Если сообщение слишком большое, то
Боб делит сообщение на части и шифрует их отдельно.</p>
<p class="bob-column">4.Вычисляет числа %%u = g^k \pmod{p}%%, %%v = m y^k \pmod{p}%%.</p>
<p class="bob-column send-left">5.Боб публикует шифр текст %%(u,v)%%.</p>
<p class="alice-column">6.Алиса видит шифртекст %%(u,v)%%.</p>
<p class="alice-column">7.Расшифровывает сообщение %%m = u^{-x} v \pmod{p}%%.</p>
</div>
</div>
<div id = "interactive" class="block">
<h1 class = "title">Интерактивная схема шифрования</h1>
<p class = "text">
Это небольшое приложение, которое вы можете использовать,
чтобы попробовать шифрование Эль Гамаля.<br>
Это игрушечная реализация, поэтому, пожалуйста, даже не пытайтесь
использовать большие числа))
</p>
<div class="row">
<div class="col">
<div class = "machine" id="aliceMachine">
<div class="machine-title-panel">
<h3 class="machine-title">Алиса</h3>
</div>
<div class = "machine-main">
<ul class="errors"></ul>
<form>
<div class="form-group" id="prime">
<label for="txtPrime">
Введите простое число %%p%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtPrime"/>
<button id="getGenerators" class="btn" type="button">Ввести</button>
</div>
<span class="errorInfo">Данное число не является простым</span>
</div>
<div class="form-group" id="generator">
<label for="txtG">
Выберете примитивный корень %%g%%
</label>
<div id="generatorInfo">Нажмите на кнопку выше, чтоб увидеть спиcок примитивных корней</div>
<div id="selectG"></div>
<span class="errorInfo">Ошибка</span>
</div>
<div class="form-group" id="privateKey">
<label for="txtPrivateKey">
Введите приватный ключ %%x%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtPrivateKey"/>
<button id="getRandomPrivateKey" class="btn" type="button">Рандом</button>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p-1%%</span>
</div>
<div class="form-group">
<button id="getPublicKey" class = "btn" type="button">
Сгенерировать и Опубликовать Открытый ключ
</button>
</div>
</form>
</div>
<div class="message">
<div id="messageDisplay">
<div class="inbox-empty" style="display: block">
У вас нет сообщений.
</div>
<div class="inbox-has-message" style="display: none">
<div>Вы получили сообщение от Боба. <button id="decrypt" class="btn btn-primary btn-sm" type="button">Расшифровать</button></div>
<div class="data" style="font-weight: bold;margin-top:10px;"></div>
</div>
</div>
</div>
<div class="extrainfo"></div>
</div>
</div>
<!-- ТАБЛИЦА ДАННЫХ -->
<div class="col">
<div id="wire">
<div class="wire-data">
<div id="keyDisplay" class="display">
Публичный ключ<br/>
<span class="data">-</span>
</div>
<div id="encryptedMsg" class="display">
Зашифрованное сообщение<br/>
<span class="data">-</span>
</div>
</div>
</div>
</div>
<!-- ВТОРОЙ АБОНЕНТ -->
<div class="col">
<div class="machine" id="bobMachine">
<div class="machine-title-panel">
<h3 class="machine-title">Боб</h3>
</div>
<div class="machine-main">
<form>
<div class="form-group" id="encryptPrivate">
<label for="txtEncryptPrivate">
Введите закрытый ключ для шифрования %%k%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtEncryptPrivate"/>
<div class="input-group-btn">
<button id="getRandomEncyptKey" class="btn" type="button">Рандом</button>
</div>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p-1%%</span>
</div>
<div class="form-group" id="message">
<label for="txtMessage">
Сообщение %%m%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtMessage"/>
<button id="encrypt" class="btn" type="button">
Отправить
</button>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p%%.</span>
</div>
</form>
<div class="extrainfo"></div>
</div>
</div>
</div>
</div>
</div>
<div id = "attacks" class="block">
<h1 class = "title">Атаки на алгоритм шифрования</h1>
<p class = "text">
<img src = "images/Eve.svg"/>
Пока Алиса и Боб обменивались секретиками, Ева чувствовала себя брошенной.
Она решила научиться читать сообщения друзей. Давайте поможем ей в этом интересном занятии!
</p>
<h2 class = "subtitle">Атака одинаковых сессионных ключей</h2>
<p class = "text">
Пока Боб ненадолго отлучился, хитрая Ева смогла подсмотреть в переписку. Она увидела то, что все сообщения шифруются при помощи одного и того же сессионного ключа. Кроме того, она смогла запомнить одно из сообщений.
<br/>
<br/>
Такого набора данных хватит, чтоб Ева спокойно могла прочитать любое сообщение, которое будет отправлено с данными параметрами.
<br/>
<br/>
Предположим, что при отправке двух разных сообщений %%m%% и %%m'%% был использован один и тот же секретный ключ %%k%%. (Параметры %%p,g,y,x%% тоже одинаковые). Тогда рассмотрим шифртекст, который получается в таком случае:<br/>
$$m: u = g^k \pmod{p}, v = m \cdot (y^k) \pmod{p} $$
$$m': u' = g^k \pmod{p}, v' = m'\cdot(y^k) \pmod{p} $$
$$ \frac{v'}{v}= \frac{m'}{m} \Rightarrow m' = \frac{v' \cdot m}{v} $$
Ура! При помощи такой формулы мы спокойно можем получить информацию о другом сообщении, которое было передано с таким же %%k%%.
<br/>
<br/>
Когда мы рассказали Еве о данной атаке, она была на седьмом небе от счастья. Но недолго она оставалась такой: Алиса и Боб догадались о том, что их сообщения были прочитаны, поэтому они устранили уязвимость: решили каждый раз генерировать случайный сессионный ключ. Но при этом они продолжили использовать относительно маленькие числа для ключей. Этим мы и воспользуемся!
</p>
<h2 class = "subtitle">Атака малого модуля</h2>
<p class = "text">
Атака состоит в том, что мы будем искать решение %%y = g^x \pmod{p}%%, зная %%y%%, %%g%% и %%p%% (помним, что параметры имеют относительно малое значение), алгоритмом <em>baby step giant step</em>.
<br/>
<br/>
Пусть есть уравнение %%y = g^x%% в цикличекой группе. Положим, что %%x = i \cdot m - j%%, где %%m%% - заранее выбранная константа (обычно используют округленное вверх значение квадратного корня из %%p%%).
Очевидно, что любое %%x%% из промежутка %%[0,p)%% можно представить в такой форме. Тогда уравение принимает вид: %%y = g^{m \cdot i - j} \Rightarrow y \cdot (g^{-m})^{i} = g^j%%
Алгоритм предварительно вычисляет %%g^i%% для некоторых %%i%%. Потом корректируется значение %%m%% и пробуются различные значения %%i%%.
<br/>
<br/>
Давайте рассмотрим пример:<br/>
$$20 = 5^x \pmod{53}$$<br/>
В данном случае %%g = 5%%, %%y = 20%% и %%p = 53%%, и мы хотим узнать %%x%%. Для начала определим квадратный корень из %%p-1%%, и округлим до ближайшего целого:<br/>
$$m = \lfloor\sqrt{p-1}\rfloor = \lfloor\sqrt{52}\rfloor = 7$$<br/>
Затем мы вычислим %%g^i \pmod{p} %% от %%1%% до %%m%% и занесем информацию в виде словаря %%\{g^i \pmod{p}, i\}%%<br/>
$$\{1: 0, 5: 1, 25: 2, 11: 3, 42: 4, 51: 5, 43: 6, 3: 7\}$$<br/>
Например: Если %%i = 6%%, мы получаем %%5^6 \pmod{53} \equiv 43 \Rightarrow \{43:6\}%%<br/>
Теперь у нас есть список пар от %%0%% до квадратного корня из %%p-1%%. Вычислим %%g^{-m}%%. Согласно одному из следствий малой теоремы Ферма %%g^{-m} = g^{m(p-2)} = 18%%
Затем мы проходимся по значениям %%y \cdot (g^{-m})^j \pmod{p} = 20 \cdot 18^j \pmod{53}%% пока мы не найдем совпадения в таблице. Тогда мы умножаем число на %%m%% и добавляем число, которое сопоставлено в таблице.<br/>
$$j = 0: 20 \pmod{53} = 20$$
$$j = 1: 20 \cdot 18 \pmod{53} = 42$$
Число %%42%% есть в нашем словаре, значит %%x = 1*7 + 4 = 11%% <br/>
Действительно, если выполнить проверку, то получится верное равенство! Таким образом, мы знаем более эффективный алгоритм нахождения решения уравнения %%y = g^x \pmod{p}%%, чем полный перебор.
</p>
<h2 class = "subtitle">Атака Meet in the Middle</h2>
<p class = "text">
Очередная атака, которую мы попробуем называется Meet in the Middle (встреча в середине).
Не стоит путать эту атаку с Man in the Middle (человек по середине), о которой [спойлер]
мы поговорим чуть позже.
<br/>
Если соблюдается ряд условий и сообщение m, которое Боб посылает Алисе, достаточно короткое,
то Ева может восстановить %%m%%, если она сможет узнать %%v%% (а она сможет, т.к это открытая информация),
когда Боб посылает свой шифротекст Алисе.
В частности, Meet in the Middle работает только в том случае, если:
</p>
<ul class = "list">
<li>
%%m%% состоит из %%B%% бит, причем Ева знает %%B%%, и %%B%% является небольшим числом.
</li>
<li>
%%m%% можно разделить на две части таким образом, что %%m=(m1)(m2)%%.
Пусть %%m1%% состоит из битов %%b1%%, а %%m2%% - из битов %%b2%%.
</li>
<li>
Ева знает %%n%%. Поскольку сессионный ключ Боба %%k%% обладает свойством %%1 \leq k \leq n-1%%,
ему также необходимо каким-то образом определить %%n%%. Если он может, то Ева может тоже.
</li>
<li>
%%m%% не является элементом подгруппы, порожденной %%g%%.
Это кажется совершенно маловероятным. Однако, порядок %%n%% подгруппы, генерируемой %%g%%,
часто выбирается небольшим по соображениям эффективности.
</li>
<li>
Порядок %%n%% подгруппы, порожденной %%g%%, имеет свойство, что %%n ≤ (p-1) \cdot 2^{−b}%%.
Опять же, возможно, что %%n%% мало по соображениям эффективности.
</li>
</ul>
<p class = "text">
Если все магическим образом будут выполнены все условия,то Ева может действовать следующем образом: <br/>
Она знает, что $$y = g^x (mod p)$$ <br/>
и что $$v = m \cdot (y^k) (mod p)$$ <br/>
Возведем обе части в степень n: $$v^n = (m^n) \cdot (y^{nr}) (mod p)$$ <br/>
Это бесполезно как часть атаки, если %%m%% является элементом подгруппы, порожденной %%g%%,
потому что тогда %%m^n=1%%
(поскольку все элементы подгруппы генерируют эту подгруппу, хотя и в другом порядке) <br/>
Однако если это не так, вспомним, что %%g_n=g_0=1%%, поскольку подгруппа, порожденная %%g%%, циклична, так что<br/>
$$y^{kn}=g^{xkn}=(g^n)^{xk}=1^{xk}=1$$<br/>
Получаем, что $$v^n = m^n (modp)$$<br/>
Используя предположение, что %%m = (m1)(m2)%%: $$v^n=(m^n_1)(m^n_2) (modp)$$ $$(v^n)(m^{−n}_2)=m^n_1(modp)$$
</p>
<p class = "text">С теорией закончили, перейдем к реализации атаки:</p>
</div>
<div class = "example js-attack-example">
<p>Простое число %%p%% имеет <span class="TKAdjustableNumber" data-var="pBits"
data-min="8" data-max="128"></span> бит,</p>
<p>
<button class="btn js-attack-example-pick-p">Выбери случайное p</button>
</p>
<p>Открытый ключ:</p>
<p>( %%p = %% <span data-var="primeP"></span>,</p>
<p>%%g = %% <span data-var="generatorG"></span>,</p>
<p>%%y = g^x \pmod{p} = %% <span data-var="valueY"></span> )</p>
<p>где порядок подгруппы сгенерированной %%g%% это %%n=%% <span data-var="orderN"></span>,</p>
<p>и секретный ключ: %%x = %% <span data-var="keyX"></span>
</p>
<p>Предполагая, %%b = %% <span class="TKAdjustableNumber" data-var="bBits"
data-min="8" data-max="64"></span> бит, положим, что %%b_1 = %% <span class="TKAdjustableNumber"
data-var="b1Bits" data-min="2" data-max="64"></span> бит, значит %%b_2=%%
<span
data-var="b2Bits"><span> </span> </span>бит,</p>
<p>
<button class="btn js-attack-example-pick-m">Выбери случайное m</button>
</p>
<p>%%m = %% <span data-var="messageM"></span>
</p>
<p>Если публичный ключ %%k%%, то<span data-var="keyK"></span>, шифртекст:</p>
<p>( %%u = %% <span data-var="ciphertextU"></span>,</p>
<p>%%v = %% <span data-var="ciphertextV"></span> )</p>
<ol>
<li>Для всех %%m_1=1,...,2^{b_1}%%, создаем структуру словаря %%m_1^n
\pmod{p} \to m_1%%</li>
<li>Для всех %%m_2=1,...,2^{b_2}%%, вычисляем %%v^n m_2^{-n} \pmod{p}%% и ищем
данное значение в словаре.</li>
<li>Если мы найдем совпадение в словаре, мы нашли решение %%(m_1,m_2)%%
для %%(v^n)(m_2^{-n}) = m_1^n \pmod{p}%% и %%m%% возможно равно
%%(m_1)(m_2)%%.</li>
</ol>
<p>Поскольку словарь зависит только от открытого ключа %%(p,g,y)%% и
длины сообщения %%b%%, мы можем использовать его снова.
Примечательно, что от сеансового ключа %%k%% словарь никак не зависит.</p>
<p>Используя атаку<em> Meet in the Middle</em>, мы помогли вычислить Еве сообщение %%m = %%
<span
data-var="eveGuessM"></span>.</p>
</div>
<div id = "theory-signature" class="block">
<h1 class = "title">Работа в режиме подписи</h1>
<p class = "text">Теперь рассмотрим работу алгоритма в режиме подписи.</p>
<h2 class = "subtitle">Подпись сообщений</h2>
<p class = "text">
Для подписи сообщения %%m%% выполняются следующие операции: <br/>
1) Выбирается случайное число %%1 < k < p-1%% взаимнопростое с %%p-1%% - разовый ключ<br/>
2) Вычисляется %%r = g^k \pmod{p}%%<br/>
3) Вычисляется %%s = (m - xr)k^{-1} \pmod{p-1}%%<br/>
4) Подписью сообщения %%m%% является пара %%(r,s)%% <br/>
</p>
<h2 class = "subtitle">Проверка подписи</h2>
<p class = "text">
Зная открытый ключ %%(p,g,y)%%, подпись %%(r,s)%% сообщения %%m%% проверяется следующим образом: <br>
1) Проверяется выполнимость условий: %%0 < r < p%% и %%0 < s < p-1%% <br>
2) Подпись считается верной, если выполняется сравнение: %%y^r \cdot r^s \equiv g^m (mod p)%%<br>
<br>
</p>
</div>
<div id = "interactive-2" class="block">
<h1 class = "title">Интерактивная схема подписи</h1>
<p class = "text">
Это небольшое приложение, которое вы можете использовать,
чтобы попробовать алгоритм Эль Гамаля в режиме подписи.<br>
Это игрушечная реализация, поэтому, пожалуйста, даже не пытайтесь
использовать большие числа))
</p>
<div class="row">
<div class="col">
<div class = "machine" id="bobMachine2">
<div class="machine-title-panel">
<h3 class="machine-title">Боб</h3>
</div>
<div class = "machine-main">
<ul class="errors"></ul>
<form>
<div class="form-group" id="prime2">
<label for="txtPrime">
Введите простое число %%p%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtPrime2"/>
<button id="getGenerators2" class="btn" type="button">Ввести</button>
</div>
<span class="errorInfo">Данное число не является простым</span>
</div>
<div class="form-group" id="generator2">
<label for="txtG">
Выберете примитивный корень %%g%%
</label>
<div id="generatorInfo2">Нажмите на кнопку выше, чтоб увидеть спиcок примитивных корней</div>
<div id="selectG2"></div>
<span class="errorInfo">Ошибка</span>
</div>
<div class="form-group" id="privateKey2">
<label for="txtPrivateKey">
Введите приватный ключ %%x%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtPrivateKey2"/>
<button id="getRandomPrivateKey2" class="btn" type="button">Рандом</button>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p-1%%</span>
</div>
<div class="form-group">
<button id="getPublicKey2" class = "btn" type="button">
Сгенерировать и Опубликовать Открытый ключ
</button>
</div>
<div class="form-group" id="encryptPrivate2">
<label for="txtEncryptPrivate">
Введите разовый ключ подписи %%k%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtEncryptPrivate2"/>
<div class="input-group-btn">
<button id="getRandomEncyptKey2" class="btn" type="button">Рандом</button>
</div>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p-1%%</span>
</div>
<div class="form-group" id="message2">
<label for="txtMessage">
Сообщение %%m%%
</label>
<div class="input-group">
<input type="text" class="form-control" id="txtMessage2"/>
<button id="encrypt2" class="btn" type="button">
Подписать
</button>
</div>
<span class="errorInfo">Число должно быть больше %%0%% и меньше %%p%%.</span>
</div>
</form>
</div>
<div class="extrainfo"></div>
</div>
</div>
<!-- ТАБЛИЦА ДАННЫХ -->
<div class="col">
<div id="wire2">
<div class="wire-data">
<div id="keyDisplay2" class="display">
Публичный ключ<br/>
<span class="data">-</span>
</div>
<div id="encryptedMsg2" class="display">
Подпись сообщения<br/>
<span class="data">-</span>
</div>
</div>
</div>
</div>
<!-- ВТОРОЙ АБОНЕНТ -->
<div class="col">
<div class="machine" id="aliceMachine2">
<div class="machine-title-panel">
<h3 class="machine-title">Алиса</h3>
</div>
<div class="message">
<div id="messageDisplay2">
<div class="inbox-empty" style="display: block">
У вас нет сообщений.
</div>
<div class="inbox-has-message" style="display: none">
<div>Вы получили сообщение от Боба. <button id="decrypt2" class="btn btn-primary btn-sm" type="button">Проверить подпись</button></div>
<div class="data" style="font-weight: bold;margin-top:10px;"></div>
</div>
</div>
</div>
<div class="extrainfo"></div>
</div>
</div>
</div>
</div>
<div id = "attacks-2" class = "block">
<h1 class = "title">Атаки на алгоритм цифровой подписи</h1>
<h2 class = "subtitle">Атака на плохо выбранные разовые ключи</h2>
<p class = "text">
При рассмотрении стойкости необходимо соотношение %%m \equiv xr + ks \pmod{p-1}%%. Тот, кто наблюдает за подписывающим, видит серию подписанных документов: <br/>
$$ [m_1, r_1, s_1] \longrightarrow m_1 \equiv xr_1 + k_1s_1 \pmod{p-1}$$
$$ [m_2, r_2, s_2] \longrightarrow m_2 \equiv xr_2 + k_2s_2 \pmod{p-1}$$
$$ \dots $$
$$ [m_n, r_n, s_n] \longrightarrow m_n \equiv xr_n + k_1s_n \pmod{p-1}$$
Неизвестные тут: %%x, k_1 \dots k_n%%. Получили систему уравнений от %%n+1%% неизвестных,
т.е. неопределенная система уравнений.
Если знаем хоть один разовый ключ, то система становится определенной
и решается - значит, все ключи должны быть случайными, секретными и разными.
</p>
<h2 class = "subtitle">Атака "по корректной тройке"</h2>
<p class = "text">
Атака связана с построением цифровой подписи по известной корректной тройке %%[m, r, s]%%
Если взять параметры %%A,B,C%% такие, что %%\exists (Ar - Cs)^{-1} \pmod{p-1} %% то можно построить целую серию документов, удовлетворяющих соотношению проверки.
$$r' = r^Ag^By^c \pmod{p}$$
$$s' = s \cdot r'/(Ar - Cs)^{-1} \pmod{p-1}$$
$$m' = r'(Am-Bs)/(Ar-Cs) \pmod{p-1}$$
Покажем это:
$$y^{r'}r'^{s'} \equiv y^{r'}(r^{A}g^{B}y^{C})^{{sr'}/(Ar-Cs)} \equiv (y^{r'(Ar-Cs)} \cdot r^{Asr'} \cdot g^{Bsr'} \cdot y^{Csy'})^{(Ar-Cs)^{-1}} = (y^{r'Ar-r'Cs+r'Cs} \cdot r^{Asr'} \cdot g^{Bsr'})^{1 \over Ar-Cs} = ((y^{r} \cdot r^{s})^{Ar'} \cdot g^{Bsr'})^{1 \over Ar-Cs} \equiv g^{(mAr'+Bsr')/(Ar-Cs)}\equiv g^{m'} $$
Создав таким образом множество документов, можно организовать DDOS-атаку на проверяющего. Защита: %%m'%% - случайное число, %%m = Hash(m')%% - значит, цифровая подпись для Эль Гамаля должна применяться вместе с Хеш-функцией.
</p>
</div>
<div id = "links" class="block">
<h1 class = "title">Материалы</h1>
<p class = "text">
Если вам понравился алгоритм Эль Гамаля и вы хотите более подробно изучить его работу,
то исследуйте проект на github. Там вы найдете много полезной информации, а также
реализацию данного алгоритма в приложении обмена сообщениями.
</p>
<p class = "text">
Источники, которые мы использовали:
</p>
<ul class = "list">
<li>
<a href = "http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf" target="_blank">
<b>El Gamal T.</b> - A public key cryptosystem and a signature scheme based on discrete logarithms
</a>
</li>
<li>
<a href = "http://cyber.sibsutis.ru/%D0%A1%D0%9F%D0%98/%D0%9F%D0%B5%D1%80%D0%B2%D0%B0%D1%8F%20%D1%87%D0%B0%D1%81%D1%82%D1%8C/%D0%9A%D0%9C%D0%97%D0%98.pdf" target="_blank">
<b>Рябко, Фионов</b> - Криптографические методы защиты информации
</a>
</li>
<li>
<a href = "http://www.cacr.math.uwaterloo.ca/hac/about/chap11.pdf" target="_blank">
<b>Menezes A. J., Oorschot P. v., Vanstone S. A</b> - Handbook of Applied Cryptography
</a>
</li>
</ul>
</div>
</div>
<footer>
</footer>
<script src="js/elgamal.js"></script>
<script src="js/machines.js"></script>
</body>
</html>