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

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

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

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

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

Приклад №1

1. Оберемо два простих числа: p = 5, q = 11.
2. Тоді n = p * q = 5 * 11 = 55.
3. Згідно з властивістю функції Ейлера $\phi (n)=(p-1)(q-1)=(5-1)(11-1)=40.$
4. Оберемо число, взаємно просте з $\phi (n)$ — частину ключа для шифрування. Візьмемо e=3. Воно задовольняє умові НСД$(3,\phi (n))=1.$
5. Обчислимо $d=\frac{1}{e}(\mathrm{mod}\phi (55))=\frac{1}{3}=\frac{1-40}{3}=\frac{-39}{3}=-13=27(\mathrm{mod}40).$

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

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

$C=S^e(\mathrm{mod}n).$

Отже $C=15^3(\mathrm{mod}55)=15^2\ast 15=225\ast 15=5\ast 15=75=20.$

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

$S=C^d(\mathrm{mod}n).$

$S=20^{27}(\mathrm{mod}55)=(4\ast 5{)}^{27}=(2^2{)}^{27}\ast 5^{27}=2^{54}\ast 5^{27}.$

Зауважимо, що $2^6(\mathrm{mod}55)=64=9=3^2,$ та $5^3(\mathrm{mod}55)=125=15.$

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

$2^{54}\ast 5^{27}=(2^6{)}^9\ast (5^3{)}^9=(3^2{)}^9\ast (15{)}^9=(3{)}^{18}\ast (15{)}^9.$

Зауважимо, що ми вже обчислювали $15^3(\mathrm{mod}5)5=20,$ та обчислимо степені числа 3.

$3^4(\mathrm{mod}55)=81=26.$

$3^5(\mathrm{mod}55)=3^4\ast 3=26\ast 3=78=23.$

$3^6(\mathrm{mod}55)=3^5\ast 3=23\ast 3=69=14.$

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

$(3{)}^{18}\ast (15{)}^9=(3^6{)}^3\ast (15^3{)}^3=14^3\ast 20^3=(14\ast 4{)}^3\ast 5^3=56^3\ast 15=1^3\ast 15=15.$

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

Приклад №2

1. Оберемо два простих числа: p = 7, q = 13.
2. Тоді n = p * q = 7 * 13 = 91.
3. Згідно з властивістю функції Ейлера $\phi (n)=(p-1)(q-1)=(7-1)(13-1)=6\ast 12=72.$
4. Оберемо число, взаємно просте з $\phi (n)$ — частину ключа для шифрування. Візьмемо е = 5. Воно задовольняє умові НСД$(5,\phi (n))=1.$
5. Обчислимо $d=\frac{1}{e}(\mathrm{mod}\phi (91))=\frac{1}{5}=\frac{1+2\ast 72}{5}=\frac{145}{5}=29(\mathrm{mod}72).$

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

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

$C=S^e(\mathrm{mod}n).$

Отже $C=11^5(\mathrm{mod}91).$

Зауважимо, що $11^2(\mathrm{mod}91)=121-91=30(\mathrm{mod}91).$

Тоді $11^5(\mathrm{mod}91)=(11^2{)}^2\ast 11=30^2\ast 11.$

Зауважимо, що $30^2(\mathrm{mod}91)=900-91\ast 9=81(\mathrm{mod}91).$

Тоді $30^2\ast 11=81\ast 11=891-9\ast 91=72$, отримуємо $C=72(\mathrm{mod}91)$

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

$S=C^d(\mathrm{mod}n).$

$S=72^{29}(\mathrm{mod}91).$

Зауважимо, що $72^2(\mathrm{mod}91)=(8\ast 9{)}^2=64\ast 81=(64-91)\ast (81-91)=27\ast 10=270-2\ast 91=88-91=-3(\mathrm{mod}91).$

Тоді $S=72^{29}(\mathrm{mod}91)=72\ast (72^2{)}^{14}=72\ast (-3{)}^{14}=72\ast 3^{14}=8\ast 9\ast 3^{14}=8\ast 3^{16}=8\ast (3^4{)}^4.$

Зауважимо також те, що $3^4(\mathrm{mod}91)=81-91=-10(\mathrm{mod}91).$

Отримаемо $8\ast (3^4{)}^4=8\ast (-10{)}^4=8\ast 10\ast 10^3=80\ast 1000.$

Та врахувавши, що $1000(\mathrm{mod}91)=1000-11\ast 91=-1(\mathrm{mod}91).$

Матимемо $80\ast 1000=-80+91=11.$

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