-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmethodical.html
227 lines (219 loc) · 24.6 KB
/
methodical.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
<!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"/>
<script data-main="js/main" src="js/3rdparty/require.js"></script>
</head>
<body>
<nav id = "header">
<div id = "title">Методическое пособие по Алгоритму Эль Гамаля</div>
<ul id = "menu">
<li>
<a href = "./index.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">
Схема Эль-Гамаля — это криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема была предложена Тахером Эль-Гамалем в 1985 году. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой.
<br/>
<br/>
Что такое криптосистема с открытым и закрытым ключом (или как её ещё называют – ассиметричное шифрование)?
<br/>
<br/>
Это такая система, где чтобы зашифровать сообщение используется один ключ, а чтобы расшифровать – второй, в отличие от симметричного шифрования, где используется один и тот же ключ для шифрования и расшифровки. Здесь эти ключи называют так: первый – это открытый (или публичный), а второй – закрытый (или секретный). Открытый ключ рассказывается кому угодно, с помощью него сообщение шифруется и передаётся обладателю этого ключа. Далее он (обладатель) расшифровывает сообщение с помощью секретного ключа.
<br/>
<br/>
Теперь сам алгоритм:
Первым делом нужно сгенерировать числа %%P%% и %%A%% %%(1 < A < P - 1)%% такие, что %%P%% простое, а %%A%% является генератором мультипликативной группы кольца вычетов по модулю %%P%% (или как ещё это называют: %%A%% – это первообразный корень по модулю %%P%%).
<br/>
<br/>
Что такое генератор мультипликативной группы кольца вычетов по модулю %%P%%? В данном случае это число %%A%% такое, что все числа из интервала %%[1, P-1]%% могут быть представлены как различные степень %%A \pmod{P}%%. <br>
Добавим ещё одно обозначение: операцию деления по модулю %%mod{}%%. Другими словами, она находит просто остаток от деления. Например, %%24\mod{10} = 4%% или %%13\mod{11} = 2%%, или %%5\mod{2} = 1%% и т. д.<br>
Рассмотрим пример:
<br/>
<br/>
Возьмём группу %%Z_7: \{0, 1, 2, 3, 4, 5, 6\}%%. Недолго думая, выберем число %%3%%. Проверим:
$$3^1 = 3 \pmod{7}$$
$$3^2 = 2 \pmod{7}$$
$$3^3 = 6 \pmod{7}$$
$$3^4 = 4 \pmod{7}$$
$$3^5 = 5 \pmod{7}$$
$$3^6 = 1 \pmod{7}$$
Видно, что все числа %%\{1, 2, 3, 4, 5, 6\}%% представляются в виде %%(3^i)\pmod{7}%%, где %%i%% от %%1%% до %%6%% %%\{1= 36, 2=32, 3=31, 4=34, 5= 35, 6=33\}%%. Значит %%3%% – это генератор мультипликативной группы кольца вычетов по модулю %%7%%. Но это только пример, здесь %%3%% и %%7%% – очень маленькие числа. На самом деле на практике берутся числа, у которых хотя бы %%250-300%% цифр в записи.
<br/>
<br/>
Чтобы было просто генерировать такие числа можно использовать следующий подход: простое число %%P%% берётся такое, что %%P = 2 \cdot q+1%%, где число %%q%% тоже простое. Тогда в качестве %%A%% можно взять число, для которого выполняется: %%A^q \pmod{P} \neq 1%% и %%1 < A < P – 1%%. Такой выбор числа %%P%% также и усиливает криптостойкость.
<br/>
<br/>
Вторым шагом каждый пользователь выбирает себе секретный ключ %%X%% и публичный ключ %%Y%% следующий образом:
<br/>%%X%% такое, что: %%1 < X < P-1%%<br/>
%%Y%% такое, что: %%Y = A^X \pmod{P}%%<br/>
<br/>
Будем обозначать %%X_1%% и %%Y_1%% секретный и публичный ключи для пользователя %%1%% и %%X_2%% и %%Y_2%% для пользователя %%2%% соответственно, и так далее.
<br/>
<br/>
По сути, теперь уже можно начинать шифровать и дешифровать сообщения. А также их подписывать.
<br/>
<br/>
Введём ещё одно обозначение. Будем обозначать числом %%m%% само сообщение. Это число может быть получено разными способами, главное, чтобы оно не было бы больше, чем %%P%%. Хотя бы можно поступать так: какое-то сообщение представляется в двоичном виде (каждую букву представить как байт, а потом просто записать все эти байты один за другим), этот же двоичный вид может представлять число %%m%%. Ну а если это число %%m%% получается больше, чем %%P%%, то сообщение можно “разбить” на более мелкие.
<br/>
<br/>
</p>
<h2 class="subtitle">Шифрование, передача и расшифровка</h2>
<p class = "text">
Пользователь %%1%% хочет отправить сообщение %%m%% в зашифрованном виде.<br/>
Шаг %%1%%: пользователь %%2%% передаёт пользователю %%1%% числа %%P, A%% и %%Y_2%%.<br/>
Шаг %%2%%: пользователь %%1%% находит числа %%k, r%% и %%e%%:
$$\forall k : НОД(k, p-1) = 1$$
$$r = A^k \pmod{P}$$
$$e = (m*Y_2^k)\pmod{P}$$
Теперь зашифрованное сообщение представляется в таком виде %%(r, e)%%. То есть зашифрованное сообщение %%(r, e)%% передаётся пользователю %%2%%.
<br/>
<br/>
Шаг %%3%%: пользователь %%2%% расшифровывает:
$$m = (e*r^{P-1-X_2})\pmod{P}$$
<br/>
<br/>
Почему это вообще работает?!<br/>
Начнём с теоремы Эйлера. Она гласит:</br>
Если %%a%% и %%P%% взаимно просты (то есть их наибольший общий делитель равен %%1%%), то %%a^{φ(P)}\pmod{P} = 1%%, где %%φ(P)%% – это функция Эйлера. Теперь про функцию Эйлера – это функция, которая равна количеству натуральных чисел, меньших %%P%% и взаимно с простых с %%P%%. Например, %%φ(24) = 8%%, так как всего %%8%% чисел, меньших %%24%%, взаимно просты с %%24%% (т. е. имеют наибольший общий делитель %%1%%): %%1, 5, 7, 11, 13, 17, 19, 23%%. Нетрудно догадаться, что если %%P%% – простое, то все числа, меньшие %%P%%, будут взаимно просты с %%P%%. Т.е. получается, что если %%a%% не делится на простое число %%P%%, то %%a^{P-1}\pmod{P} = 1%% (это называется малой теоремой Ферма).
<br/>
<br/>
Так вот, говорилось что: <br/>
%%m = (e*r^{P-1-X2}) \pmod{P}%%, где %%e = (m*Y_2^k)\pmod{P}, r = A^k \pmod{P}%% и %%Y_2 = A^X_2\pmod{P}%%. Подставим %%e, r%% и %%Y_2%% в %%(e*r^{P-1-X_2})\pmod{P}%%:
$$ m = ((m*Y_2^k) * A^{k*(P-1-X_2)}) \pmod{P} = $$
$$ = ((m*A^{k*X_2}) * A^{k*(P-1-X_2)} )\pmod{P} = $$
$$ = ((m*A^{k*X_2 + k*(P-1-X_2)})\pmod{P} = $$
$$ = ((m*A^{k*(P-1)})\pmod{P} = [t = A^k] = $$
$$ = ((m*t^{P-1})\pmod{P} = [t^{P-1}\pmod{P} = 1] = $$
$$ = ((m*1)\pmod{P} = m$$
Действительно, %%m = m%%.
<br/>
<br/>
Ладно, звучит всё хорошо, но что, если мы будем полностью слушать канал, в котором передаются все эти сообщения? Тогда мы узнаем: %%P, A, e, r%% и %%Y_2%%. Но как ни крути раскрыть %%m%% не получится, у нас не хватает %%X_2%% и %%k%%. Подбирать их будем до конца вселенной, если, конечно, речь идёт о больших числах.
<br/>
<br/>
Теперь подпись сообщений. Или как её в данном случае лучше назвать – электронная подпись. Она позволяет подписать сообщение так, что если его чуть-чуть изменить, то сразу станет понятно, что это (чуть-чуть изменённое сообщение) вы не подписывали.
<br/>
<br/>
Но сначала нужно понять, что такое хеш-функция. Это такая функция %%f(x) = y%%, что y вычислить очень легко, а вот %%x%% найти, зная %%y%%, очень сложно. Скажем вместо %%x%% подставляется набор байт (сколь угодно длинный), который на выходе даёт (ровно %%N%% байт) = %%y%%. Причём если в %%x%% поменять где-нибудь хотя бы %%1%% бит, то y изменится настолько, что его даже %%x%% не узнает. В общем смысл понятен. Например, такой функцией может быть SHA-512 или SHA-256, MD5 и т.д. Ну или вообще такое: %%f(a, b) = y%%, где, для наглядности, %%a%% и %%b%% простые, а %%y = a*b%%. Здесь %%y%% вычислить легко, а вот восстановить %%a%% и %%b%% сложно.
</p>
<h2 class="subtitle">Шифрование, передача и расшифровка</h2>
<p class = "text">
Пользователь хочет подписать сообщение %%M%% (это вполне может быть документ или просто строка символов).
<br/>
<br/>
Шаг %%1%%: Пользователь пользуется хэш-функцией %%f(M) = m%%. На выходе получается в данном случае число.
<br/>
Шаг %%2%%: Пользователь вычисляет числа %%k, r%% и %%e%%:
$$\forall k: 1 < k < P-1, НОД(k, P-1) = 1$$
$$r = A^k \pmod{P}$$
$$e = ((m – X*r)*k^{-1})\pmod{P-1}$$
Теперь кому-то (кому надо) передаётся само сообщение %%M, P, A%% и %%(r, e)%%, где %%(r, e)%% и есть подпись сообщения
<br/>
<br/>
Шаг %%3%%: Проверка подписи. Снова вычисляется %%m = f(M)%%. Далее если выполняется условие: %%(Y^r*r^e)\pmod{P} = A^m\pmod{P}%% - то подпись верна.
<br/>
<br/>
Замечание: здесь очень важно, чтобы было действительно сложно вычислить %%x%%, зная %%y=f(x)%%. Ведь можно меняя биты в %%x%% рано или поздно найти такое %%x`%%, что %%f(x`) = f(x)%%, так как %%y=f(x)%% фиксированной длины, а %%x%% – нет
<br/>
<br/>
Замечание: важно, чтобы %%k%% было одноразовым для каждого %%M%%, так как можно (если всё-таки подобрать %%k%%) узнать %%X = ((m – k*e)*r^{-1})\pmod{P-1}%%, а зная %%X%%, можно подделать подпись, да и вообще расшифровывать сообщения.
<br/>
<br/>
Почему это всё верно? Было сказано, что %%e = ((m – X*r)*k^{-1})\pmod{P-1}%%. Выразим отсюда %%m = (e*k + X*r)\pmod{P-1}%% (да, так тоже можно делать). Замечу (для примера), что если %%a\pmod{P} = b%%, то %%a = P*c + b%%, где %%с%% – какое-то целое число. Действительно, выражение %%a = P*c + b%% показывает, что %%b%% – это остаток от деления %%a%% на %%P%% (изначально говорилось, что %%\mod{}%% – это остаток). Частное c сейчас нас не сильно волнует. Тогда получается, что %%m = (P-1)*c + (e*k + X*r)%%.
<br/>
<br/>
Теперь
$$A^m \pmod{P} = A^{(P-1)*c + (e*k + X*r)}\pmod{P} = $$
$$= (A^{c*(P-1)}*A^{e*k + X*r})\pmod{P} = [t = A^c] = $$
$$ = (t^{P-1}*A^{e*k + X*r})\pmod{P} = [t^{P-1}\mod{P} = 1]$$
$$ = (A^{e*k + X*r})\pmod{P} = (A^{e*k} * A^{X*r})\pmod{P} =$$
$$ = [A^k \pmod{P} = r, A^X \pmod{P} = Y] = (Y^r * r^e)\pmod{P}.$$
В общем, что и требовалось доказать.
<br/>
<br/>
Замечу, что вместо %%M%% можно использовать какой-нибудь ключ, тем самым подписать его. Но об этом позже.
<br/>
<br/>
Теперь вернёмся к вопросу: “Что такое мультипликативное обратное и как его искать?”. Если совсем прямо, то %%k^{-1}\pmod{P} = (\frac{1}{k})\mod{P}%%. Лучше это рассмотреть на примере: %%(\frac{1}{9})\pmod{7} = x\pmod{7}%%. Нужно найти %%x%%. Умножим правую и левую часть на %%9%%: %%1\pmod{7} = 1 = (9*x)\pmod{7}%%.
Другими словами, %% 1= 7*c + 9*x %%, где %%c%% – какое-то целое число. Вот это вот: %%1= 7*c + 9*x%% - называется диофантово уравнение. Решив его, мы получим ответ, а сделать это достаточно просто. Итого %%(\frac{1}{9})\pmod{7} = 4%%.
<br/>
<br/>
Всё звучит хорошо. Но как мы узнаем, что к нам пришёл публичный ключ именно того пользователя, от которого мы хотим (его вообще-то могут поменять, пока он к вам “идёт”, и тогда вы будете общаться с кем-то вообще другим)? И вообще, как узнать публичный ключ нужного нам пользователя?
<br/>
<br/>
Вот постановка задачи: Майк хочет получить публичный ключ Антона так, чтобы гарантировать, что это именно его публичный ключ. Скажем, что Майк и Антон никак не могут встретиться лично. Здесь в игру вступает Пётр (или центр сертификации).
</p>
<h2 class="subtitle">Цифровые сертификаты</h2>
<p class = "text">
Цифровым сертификатом будем называть подписанную кем-то документ, в котором содержится публичный ключ, его описание и данные владельца этого публичного ключа.
<br/>
<br/>
Шаг %%0%%: Пётр всем как-нибудь рассказывает свой публичный ключ. По радио, по телевизору, на заборе, в рекламе или ещё как-то.
<br/>
Шаг %%1%%: Пётр каким-то образом удостоверяет личность Антона (например, Пётр зарабатывает на жизнь тем, что он ездит к людям и лично с ними встречается, тем самым он удостоверяется в личности этих пользователей, или пользователи сами приезжает к Петру) и получает публичный ключ Антона.
<br/>
Шаг %%2%%: Пётр подписывает публичный ключ Антона + добавляет к нему какой-нибудь описание. Например, имя и почту Антона. Или ещё пример: добавляет описание, что Пётр полностью доверяет Антону, и Антон может подписывать другие ключи также, как Пётр.
<br/>
Шаг %%3%%: Пётр отсылает Антону его теперь уже подписанный ключ.
<br/>
Шаг %%4%%: теперь Антон может отослать Майку свой подписанный публичный ключ или Майк сам может запросить подписанный ключ у Петра (всё же ведь Пётр подписывает публичную информацию, поэтому он предоставит Майку ключ).
<br/>
Шаг %%5%%: Майк смотрит, что этот подписанный ключ был подписан именно Петром (для этого Майк использует публичный ключ Петра, который был всем рассказан в шаге 0).
<br/>
<br/>
Замечание: публичный ключ Петра может быть подписан другим пользователем, доверие к которому больше и так далее.
<br/>
<br/>
Теперь давайте проанализируем всю эту ситуацию. Если в подписанном ключе изменить хоть %%1%% бит, то подпись сразу станет не верна. Так что можно вполне быть уверенным, что никто не изменил подписанный ключ, пока он шёл от Петра к Антону или Майку или от Антона к Майку.
<br/>
<br/>
Вообще, чтобы зашифровать сообщение с помощью алгоритма Эль-Гамаля, нужны большие вычислительные мощности. А если сообщений много? Намного разумнее будет использовать алгоритм Эль-Гамаля, чтобы обменяться каким-нибудь ключом для симметричного шифрования. Например, для AES-256 или тому подобных.
</p>
</div>
<div id = "links" class="block">
<h1 class = "title">Материалы</h1>
<p class = "text">
Вы можете скачать данный материал в .docx файле на странице проекта на github.
</p>
<p class = "text">
Источники, которые мы использовали:
</p>
<ul class = "list">
<li>
<a href = "" target="_blank">
<b>Басалова Г.В</b> - Основы криптографии. 2016. - С. 156-233.
</a>
</li>
<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>
</body>
</html>