Для розв'язання будемо використовувати Алгоритм RSA.
Також важливо розуміти такі речі:
- Взаємно прості числа - не мають жодного спільного дільника, окрім 1;
- Розуміти, що результатом
буде остача від цілочисленного ділення числа
на число
.
- Оберемо два простих числа: p = 5, q = 11.
- Тоді n = p * q = 5 * 11 = 55.
- Згідно з властивістю функції Ейлера
![{\displaystyle \varphi (n)=(p-1)(q-1)=(5-1)(11-1)=40.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/838b9999e1badb963f03953ac5f970f98869b197)
- Оберемо число, взаємно просте з
— частину ключа для шифрування. Візьмемо e=3. Воно задовольняє умові НСД![{\displaystyle (3,\varphi (n))=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca1e2121b571cb63b7b6d2e5fbceee070ea0b5ca)
- Обчислимо
![{\displaystyle d={\frac {1}{e}}{\pmod {\varphi (55)}}={\frac {1}{3}}={\frac {1-40}{3}}={\frac {-39}{3}}=-13=27{\pmod {40}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a9d6e21f10a08c7ef1c290cb8f9221eb8fddd33)
Таким чином, ми отримали публічний ключ (3,55) для шифрування, та приватний ключ (27,55) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.
Нехай S=15. Отримання значення кодованого слова C, яке відповідає слову S відбувається за правилом
![{\displaystyle C=S^{e}{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/007a027f3f960690a1a52be9c1feead3bfe0ce93)
Отже
Розшифруємо C. Для цього скористаємось правилом
![{\displaystyle S=C^{d}{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab49e941a9a81ddaa59a4b026fe923fe895a404b)
![{\displaystyle S=20^{27}{\pmod {55}}=(4*5)^{27}=(2^{2})^{27}*5^{27}=2^{54}*5^{27}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5185fe8f935eff24f786809f681628332c1fe88d)
Зауважимо, що
та
Підставимо у вираз:
![{\displaystyle 2^{54}*5^{27}=(2^{6})^{9}*(5^{3})^{9}=(3^{2})^{9}*(15)^{9}=(3)^{18}*(15)^{9}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b45c0116bbe5521913508c6f990ba73be161f092)
Зауважимо, що ми вже обчислювали
та обчислимо степені числа 3.
![{\displaystyle 3^{4}{\pmod {55}}=81=26.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa8cf5451d9ad4c5950846469a93310a79dbc9ce)
![{\displaystyle 3^{5}{\pmod {55}}=3^{4}*3=26*3=78=23.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1512ae86151f4c5bdf2e449880b09ddc859669c)
![{\displaystyle 3^{6}{\pmod {55}}=3^{5}*3=23*3=69=14.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/323bd20ed7ed1dc02b957ee29f00786d6453975e)
Підставимо у вираз:
![{\displaystyle (3)^{18}*(15)^{9}=(3^{6})^{3}*(15^{3})^{3}=14^{3}*20^{3}=(14*4)^{3}*5^{3}=56^{3}*15=1^{3}*15=15.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50211775aaa002610b9fcbb4db0280d28d96abf4)
Тим самим розшифроване значення співпадає з початковим значенням.
- Оберемо два простих числа: p = 7, q = 13.
- Тоді n = p * q = 7 * 13 = 91.
- Згідно з властивістю функції Ейлера
![{\displaystyle \varphi (n)=(p-1)(q-1)=(7-1)(13-1)=6*12=72.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9893febacdc6b0e87a61dfe9a8d76f4c34dcf2e1)
- Оберемо число, взаємно просте з
— частину ключа для шифрування. Візьмемо е = 5. Воно задовольняє умові НСД![{\displaystyle (5,\varphi (n))=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21563cac35ce35a1f6405bf15c2aca0e51b32fa5)
- Обчислимо
![{\displaystyle d={\frac {1}{e}}{\pmod {\varphi (91)}}={\frac {1}{5}}={\frac {1+2*72}{5}}={\frac {145}{5}}=29{\pmod {72}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf63e9ee6ce006da747ce7318c47a7d990ab4f4)
Таким чином, ми отримали публічний ключ (5,91) для шифрування, та приватний ключ (29,91) для розшифрування. Візьмемо якесь значення слова S та зашифруємо і розшифруємо цим ключем.
Нехай
. Отримання значення кодованого слова
, яке відповідає слову
відбувається за правилом
![{\displaystyle C=S^{e}{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/007a027f3f960690a1a52be9c1feead3bfe0ce93)
Отже
Зауважимо, що
Тоді
Зауважимо, що
Тоді
, отримуємо
Розшифруємо C. Для цього скористаємось правилом
![{\displaystyle S=C^{d}{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab49e941a9a81ddaa59a4b026fe923fe895a404b)
![{\displaystyle S=72^{29}{\pmod {91}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e48366befe3d9f30cd4c5ba0743f84c7965f89f5)
Зауважимо, що
Тоді
Зауважимо також те, що
Отримаемо
Та врахувавши, що
Матимемо
Тим самим розшифроване значення співпадає з початковим значенням.