ВУЗ:
Составители:
Глава 1. Системы шифрования с открытым ключом 22
Корректность операции восстановления исходных символов текста
обеспечивается следующей теоремой Эйлера, являющейся обобщением малой
теоремы Ферма:
Теорема Эйлера. Для любого элемента a > 0 кольца вычетов Z
n
по
модулю n выполняется следующая формула:
a
φ(n)
mod n = 1
Поскольку из условия e·d mod φ(n) = 1 следует, что e·d = k·φ(n)+1,
где k ∈ Z, то вычисление (2.4) даем нам
h
d
= (c
e
)
d
= c
ed
= c
k·φ(n)+1
= c · (c
φ(n)
)
k
= c · 1
k
= c,
откуда вытекает справедливость формулы (2.4).
Пример. Пусть p = 11, q = 5.
1. Вычислим n = p · q = 55 и функцию Эйлера φ(n) = (p − 1) · (q − 1) =
10 · 4 = 40.
2. Возьмем открытый ключ, равным e = 7. Проверим условие
Н.О.Д.(φ(n), e) = Н.О.Д.(40, 7) = 1
3. Найдем d из условия 7 · d mod 40 = 1. Вычисление d выполнено в
примере 2 следующего параграфа. Получим d = 23.
Параметры RSA определены.
4. Зашифруем число m = 15:
h = enc(15) = m
e
mod n = 15
7
mod 55 = 5
5. Расшифруем шифрокод
c = h
d
mod n = 5
23
mod 55 = 15
Глава 1. Системы шифрования с открытым ключом 22 Корректность операции восстановления исходных символов текста обеспечивается следующей теоремой Эйлера, являющейся обобщением малой теоремы Ферма: Теорема Эйлера. Для любого элемента a > 0 кольца вычетов Zn по модулю n выполняется следующая формула: aφ(n) mod n = 1 Поскольку из условия e·d mod φ(n) = 1 следует, что e·d = k·φ(n)+1, где k ∈ Z, то вычисление (2.4) даем нам hd = (ce )d = ced = ck·φ(n)+1 = c · (cφ(n) )k = c · 1k = c, откуда вытекает справедливость формулы (2.4). Пример. Пусть p = 11, q = 5. 1. Вычислим n = p · q = 55 и функцию Эйлера φ(n) = (p − 1) · (q − 1) = 10 · 4 = 40. 2. Возьмем открытый ключ, равным e = 7. Проверим условие Н.О.Д.(φ(n), e) = Н.О.Д.(40, 7) = 1 3. Найдем d из условия 7 · d mod 40 = 1. Вычисление d выполнено в примере 2 следующего параграфа. Получим d = 23. Параметры RSA определены. 4. Зашифруем число m = 15: h = enc(15) = me mod n = 157 mod 55 = 5 5. Расшифруем шифрокод c = hd mod n = 523 mod 55 = 15
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »