Дискретная математика. Ерош И.Л - 134 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

134
Криптосистема RSA
Наиболее широко распространенной системой с открытым ключом
является криптосистема RSA (Rivest, Shamir, Adleman). Идея систе
мы состоит в том, что сложно разложить произведение двух очень бо
ших простых чисел на сомножители, т. е. найти эти сомножители.
Сама же идея системы RSA исключительно проста.
Пусть p и q – два случайно выбранных простых числа (каждое при
мерно по 100 десятичных разрядов). Обозначим: n = pq и j(n) = (p–1)(q–1),
где j(n) – функция Эйлера от n. Случайно выбирается большое число d > 1,
такое, что (d, j(n)) = 1, и вычисляется e, 1 < e < j(n), удовлетворяю
щее сравнению: ed º 1 mod j(n).
Числа n, e и d называются соответственно модулем, экспонентой за
шифрования и экспонентой расшифрования.
Числа n и e образуют открытый ключ, а p, q, j(n) и d – секретную
лазейку. При этом секретная лазейка включает в себя взаимозависи
мые величины. Так, если известно p (и, конечно, n и e), то остальные
числа лазейки вычисляются просто: q = n/p; j(n) = (p–1)(q–1); d нахо
дится из условия ed º 1 mod j(n).
Зашифрование обеспечивается возведением числового фрагмента
текста S в степень e по модулю n. Расшифрование достигается возве
дением результата предыдущего шага в степень d.
При зашифровании получаем S
e
º C mod n. Здесь C – зашифрован
ный фрагмент текста. При расшифровании
C
d
= S
ed
= S
1+j(n)k
= S
j(n)k
S º S mod n. (6.2)
Справедливость (6.2) легко видна, так как из сравнения ed º 1 mod j(n)
следует, что ed = 1 + j(n)k, где k – некоторое целое.
Пример. Пусть p = 11, q = 13. Тогда n = 143, j(n) = 120. Выберем d
из условия: (d, j(n)) = 1, например, d = 37, тогда из сравнения: ed º
1 mod j(n) находим e = 13. Действительно, 13·37 = 481 º 1 mod 120.
Для зашифрования возьмем фрагмент текста, который закодирован,
например, числом S = 42: 42
13
º 3 mod 143, т. е. шифр фрагмента C = 3.
Для расшифрования возведем число 3 в степень 37: 3
37
º 42 mod 143.
Таким образом, легальный получатель вычисляет значение исходного
кода фрагмента. Нелегальный перехватчик не может вычислить пере
даваемое сообщение.
Передача с открытым ключом ЭльГамаля
Идея ЭльГамаля является аналогом идеи RSA и состоит в следую
щем. Алиса выбирает очень большое простое число P и число g – пер
вообразный корень по модулю P. Вычисляет значение y º g
x
mod P. От
крытыми ключами являются P, g и y. Число x является секретным

Страницы