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

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

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

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

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

Приклад №1

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

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

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

$C=S^{e}{\pmod {n}}.$

Отже $C=15^{3}{\pmod {55}}=15^{2}*15=225*15=5*15=75=20.$

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

$S=C^{d}{\pmod {n}}.$

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

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

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

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

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

$3^{4}{\pmod {55}}=81=26.$

$3^{5}{\pmod {55}}=3^{4}*3=26*3=78=23.$

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

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

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

$C=S^{e}{\pmod {n}}.$

Отже $C=11^{5}{\pmod {91}}.$

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

Тоді $11^{5}{\pmod {91}}=(11^{2})^{2}*11=30^{2}*11.$

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

Тоді $30^{2}*11=81*11=891-9*91=72$, отримуємо $C=72{\pmod {91}}$

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

$S=C^{d}{\pmod {n}}.$

$S=72^{29}{\pmod {91}}.$

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

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

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

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

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

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

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