Составители:
Рубрика:
35
Справедливость (∗) легко видна, так как из сравнения ed ≡ 1 mod ϕ(n)
следует, что ed = 1 + ϕ(n)k, где k – некоторое целое.
Пример.
Пусть p = 11, q = 13. Тогда n = 143, ϕ(n) = 120.
Выберем d из условия: ( d, ϕ(n)) = 1, например, d = 37, тогда из
сравнения: ed ≡ 1 mod ϕ(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.
Таким образом, легальный получатель вычисляет значение исход-
ного кода фрагмента.
3.2. Использование систем
с открытым распределением ключей для абонентских сетей
Рассмотрим несколько близких задач, в которых абоненты обмени-
ваются секретной информацией по открытому каналу.
1. Пусть несколько абонентов A, B, C, договорились об обмене ин-
формацией. Они могут выбрать некоторое общее простое число p, та-
кое, что p –1 раскладывается на простые сомножители в первой степе-
ни. Число вида N = p
1
p
2
p
3
…p
k
называется эвклидовым числом. Каж-
дый из участников выбирает два числа меньших и взаимно простых с
p –1 так, чтобы:
a
1
a
2
≡ b
1
b
2
≡ c
1
c
2
≡ 1 mod (p–1).
Пусть абонент A хочет передать сообщение S абоненту B. Он коди-
рует свое сообщение возведением в степень a
1
: S
a
1
≡ S
1
mod p и переда-
ет его B. Тот, в свою очередь, кодирует полученное сообщение возведе-
нием в степень b
1
: S
1
b
1
≡ S
2
mod p и возвращает его A. A возводит его
в степень a
2
и передает его B: S
2
a
2
≡ S
3
mod p. B возводит его в степень
b
2
и читает сообщение. Справедливость результата следует из сравне-
ния: a
1
b
1
a
2
b
2
≡ 1 mod (p – 1).
Пример. Пусть абоненты A, B и C выбрали число p = 103. Это число
простое, причем 103
–
1 = 102 – эвклидово число, так как представляется
в виде произведения простых чисел в первых степенях: 102 = 2⋅3⋅17.
Каждый из участников выбирает пару секретных ключей, например:
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
