Покажем, что отображение D является левым обратным к E, т.е. для всякого ссобщения s выполняется равенство D(E(s)) = s. Имеем
D(E(s)) == D(s^e) == (s^e)^d == s^(e*d) (mod m)
Так как e*d == 1 (mod phi(m)), имеем
e*d = 1 + h * phi(m)
По следствию 4,
s^(e*d) = s^(1 + h*phi(m)) == s (mod m)
Итак, DE = 1. Аналогично доказывается, что ED = 1. Суммируем все вышесказанное.
Рассматривается множество сообщений Zm, где m -- произведение двух больших простых чисел: m = p*q. Число m является открытым, но его разложение на множители -- секретным.
Знание разложения позволяет вычислить функцию Эйлера phi(m) = (p-1)*(q-1). Случайным образом выбирается обратимый элемент e в кольце вычетов по модулю phi(m). Для него вычисляется (с помощью расширенного алгоритма Евклида) обратный элемент d в кольце вычетов по модулю phi(m). Отображение E задается парой (m, e) и состоит в возведении в степень e по модулю m:
E(s) = s^e (mod m).
Отображение D задается парой (m, d) и состоит в возведении в степень d по модулю m:
D(t) = t^d (mod m).
Эти два отображения взаимно обратны. Пара (m, e) является открытым ключом (public key), пара (m, d) является секретным ключом (private key).
Пример. Рассмотрим пример с небольшими числами, чтобы только проиллюстрировать схему RSA. В реальных приложениях используют большие целые числа, порядка 200-400 десятичных цифр.
Пусть m = 11*13 = 143. Вычислим функцию Эйлера phi(m) = 10*12 = 120. Выберем e = 113, тогда d = 17 -- обратный к e
элемент в кольце Z120. Действительно,
113 * 17 = 1921 = 120 * 16 + 1.
50
Пара (143, 113) составляет открытый ключ, пара (143, 17) -- секретный ключ. Отображение E состоит в возведении в степень 113 по модулю 143, отображение D -- в степень 17 по модулю 143. Рассмотрим произвольное сообщение s = 123. Тогда
E(123) == 123^113 (mod 143) == 41.
Таким образом, 41 -- это закодированное сообщение. Применим к нему декодирующую процедуру:
D(41) == 41^17 (mod 143) == 123.
Мы получили исходное сообщение.
6.4. Алгоритмические задачи, связанные со схемой RSA
В связи со схемой RSA возникает ряд алгоритмических задач.
1.Для генерации ключей нам надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа.
2.Для взламывания ключа в RSA нужно уметь раскладывать целое число на множители (или, что практически то же самое, уметь вычислять функцию Эйлера). Взлом ключа может интересовать только преступников, но, с другой стороны, те, кто пытаются защитить информацию, должны быть уверены, что задача разложения на множители достаточно сложна.
7.ШИФР ЭЛЬ-ГАМАЛЯ
7.1. Общая идея метода
Основная идея ElGamal состоит в том, что не существует эффективных методов решения сравнения ax == b (mod p) Обозначения. Через Z(n) обозначим вычеты по модулю n, через Z*(n) - мультипликативную группу обратимых элементов в Z(n). Через ab (mod n) будем обозначать возведение a в степень b в кольце Z(n). Hапоминаем, что если p - простое число, то группа Z*(p) изоморфна Z(p-1).
51
Пусть числа p и 2p+1 - простые, p>2,v и w - образующие мультипликативных групп Z*(p) и Z*(2p+1) соответственно. Лемма. Если v - образующая Z*(p), то v0 = (p + (p+1)v)(mod 2p) - образующая мультипликативной группы Z*(2p). (Эта группа, очевидно, изоморфна Z*(p) ).
Числа p, 2p+1, v, v0, w фиксируются при выборе алгоритма.
7.2. Пароли
СЕКРЕТHЫЙ пароль - число x из Z*(p). ОТКРЫТЫЙ пароль (y) вычисляем в два шага.
1.Сначала находим z=v0x (mod 2p), z принадлежит группе
Z*(2p).
2.Hаконец вычисляем сам открытый пароль y = wz (mod 2p+1), y принадлежит группе Z*(2p+1).
Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение ya = b (mod 2p+1) разрешимо относительно a при любом b. Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v0x (mod 2p), где v0 - образующая группы Z*(2p).
7.3. Электронная подпись
Пусть s - число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где
a = a(r,s) = z-1*r*s = v0(-x)*r*s (mod 2p); b = b(r,s) = wr (mod 2p+1).
Так как
Z*(2p) = Z*(p)+Z*(2) = Z*(p) = Z(p-1),
то
1/z = z-1 = v0 (p-1-x).
52
Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v0x.
Для проверки подлинности подписи можно воспользоваться
равенством
ya = bs (mod 2p+1).
В самом деле,
ya = (wz)^(z-1*r*s) = w^(z*z-1*r*s) = wrs = (wr)^s = bs (mod 2p+1)
Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y).
При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).
7.4. Итог
Обозначения.
p, 2p+1 - простые числа,
v, w - образующие групп Z*(p) и Z*(2p+1) соответсвенно,
v0 = p + (p+1)v - образующая Z*(2p),
x- секретный пароль, число из Z(p-1),
z- промежуточное выражение из Z(2p),
y- открытий пароль, число из Z*(2p+1),
s - информационное число,
r - случайное число из Z(2p),
(a,b) - электронная подпись,
a из Z(2p),
b из Z*(2p+1),
53
(c,d) - зашифрованное сообщение, c из Z*(2p+1),
d из Z*(2p+1),
e - промежуточное выражение из Z*(2p+1). Hахождение открытого ключа по секретному. x =>y
1.v0 = p + (p+1)*v (mod 2p)
2.z = v0x (mod 2p)
3.y = wz (mod 2p+1)
Электронная подпись x, s, r =>a, b (r - случайное)
1.v0 = p + (p+1)*v (mod 2p)
2.a = v0(p-1-x)*r*s (mod 2p)
3.b = ws (mod 2p+1)
Проверка подписи y, s, a, b =>y/n
1. ya == bs (mod 2p+1)
Шифрование y, s, r =>c, d
1.e = yr (mod 2p+1)
2.c = wr (mod 2p+1)
3.d = s*e (mod 2p+1)
Расшифровка x, c, d =>s
1.v0 = p + (p+1)*v (mod 2p)
2.z = v0x (mod 2p)
3.1/e = c2p-z (mod 2p+1)
4.s = d/e (mod 2p+1)
8.КОНТРОЛЬ НЕИЗМЕННОСТИ МАССИВОВ ДАННЫХ
Наш совсем уже близкий к своему завершению век с полным правом может считаться веком тотальной информатизации общества – роль информации в современном мире настолько велика, что информационная индустрия стала одной из ведущих отраслей наших дней, а получившие огромное распространение устройства для обработки цифровых данных
– компьютеры – являются одним из символов нашей цивилизации. Информация, представленная в самых различных формах, подобно другим товарам производится, хранится, транс-
54