Розв'язник вправ по дискретній математиці. Кодування. Алгоритм RSA Для розв'язання будемо використовувати Алгоритм RSA.
Також важливо розуміти такі речі: Взаємно прості числа - не мають жодного спільного дільника, окрім 1; Розуміти, що результатом буде остача від цілочисленного ділення числа на число .
Приклад №1 Оберемо два простих числа: p = 5, q = 11. Тоді n = p * q = 5 * 11 = 55. Згідно з властивістю функції Ейлера Оберемо число, взаємно просте з — частину ключа для шифрування. Візьмемо e=3. Воно задовольняє умові НСД Обчислимо
Таким чином, ми отримали публічний ключ (3,55) для шифрування, та приватний ключ (27,55) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.
Нехай S=15. Отримання значення кодованого слова C, яке відповідає слову S відбувається за правилом
Отже
Розшифруємо C. Для цього скористаємось правилом
Зауважимо, що та
Підставимо у вираз:
Зауважимо, що ми вже обчислювали та обчислимо степені числа 3.
Підставимо у вираз:
Тим самим розшифроване значення співпадає з початковим значенням.
Приклад №2
Оберемо два простих числа: p = 7, q = 13. Тоді n = p * q = 7 * 13 = 91. Згідно з властивістю функції Ейлера Оберемо число, взаємно просте з — частину ключа для шифрування. Візьмемо е = 5. Воно задовольняє умові НСД Обчислимо
Таким чином, ми отримали публічний ключ (5,91) для шифрування, та приватний ключ (29,91) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.
Нехай . Отримання значення кодованого слова , яке відповідає слову відбувається за правилом
Отже
Зауважимо, що
Тоді
Зауважимо, що
Тоді , отримуємо
Розшифруємо C. Для цього скористаємось правилом
Зауважимо, що
Тоді
Зауважимо також те, що
Отримаемо
Та врахувавши, що
Матимемо
Тим самим розшифроване значення співпадає з початковим значенням.