Розв'язник вправ по дискретній математиці/Кодування/Алгоритм 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*15=225*15=5*15=75=20.$

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

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

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

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

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

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

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

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

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

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

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

$(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.$

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

Приклад №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*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*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*11=30^2*11.$

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

Тоді $30^2*11=81*11=891-9*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*9{)}^2=64*81=(64-91)*(81-91)=27*10=270-2*91=88-91=-3(\mathrm{mod}91).$

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

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

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

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

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

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