Розв'язник вправ по дискретній математиці/Кодування/Алгоритм 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. Для цього скористаємось правилом

 
 

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

Тоді  

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

Отримаемо  

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

Матимемо  

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