Розв'язник вправ по дискретній математиці/Кодування/Алгоритм RSA

Матеріал з Вікіпідручника
Перейти до навігації Перейти до пошуку

Для розв'язання будемо використовувати Алгоритм RSA.

Також важливо розуміти такі речі:

  1. Взаємно прості числа - не мають жодного спільного дільника, окрім 1;
  2. Розуміти, що результатом буде остача від цілочисленного ділення числа на число .

Приклад №1[ред.]

  1. Оберемо два простих числа: p = 5, q = 11.
  2. Тоді n = p * q = 5 * 11 = 55.
  3. Згідно з властивістю функції Ейлера
  4. Оберемо число, взаємно просте з  — частину ключа для шифрування. Візьмемо e=3. Воно задовольняє умові НСД
  5. Обчислимо

Таким чином, ми отримали публічний ключ (3,55) для шифрування, та приватний ключ (27,55) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.

Нехай S=15. Отримання значення кодованого слова C, яке відповідає слову S відбувається за правилом

Отже

Розшифруємо C. Для цього скористаємось правилом

Зауважимо, що та

Підставимо у вираз:

Зауважимо, що ми вже обчислювали та обчислимо степені числа 3.

Підставимо у вираз:

Тим самим розшифроване значення співпадає з початковим значенням.

Приклад №2[ред.]

  1. Оберемо два простих числа: p = 7, q = 13.
  2. Тоді n = p * q = 7 * 13 = 91.
  3. Згідно з властивістю функції Ейлера
  4. Оберемо число, взаємно просте з  — частину ключа для шифрування. Візьмемо е = 5. Воно задовольняє умові НСД
  5. Обчислимо

Таким чином, ми отримали публічний ключ (5,91) для шифрування, та приватний ключ (29,91) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.

Нехай . Отримання значення кодованого слова , яке відповідає слову відбувається за правилом

Отже

Зауважимо, що

Тоді

Зауважимо, що

Тоді , отримуємо

Розшифруємо C. Для цього скористаємось правилом

Зауважимо, що

Тоді

Зауважимо також те, що

Отримаемо

Та врахувавши, що

Матимемо

Тим самим розшифроване значення співпадає з початковим значенням.