Математические основы защиты информации. Ишмухаметов Ш.Т - 21 стр.

UptoLike

Глава 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