Для розв'язання будемо використовувати Алгоритм RSA .
Також важливо розуміти такі речі:
Взаємно прості числа - не мають жодного спільного дільника, окрім 1;
Розуміти, що результатом
a
mod
b
{\displaystyle a\mod b}
a
{\displaystyle a}
b
{\displaystyle b}
Приклад №1
ред.
Оберемо два простих числа: p = 5, q = 11.
Тоді n = p * q = 5 * 11 = 55.
Згідно з властивістю функції Ейлера
φ
(
n
)
=
(
p
−
1
)
(
q
−
1
)
=
(
5
−
1
)
(
11
−
1
)
=
40.
{\displaystyle \varphi (n)=(p-1)(q-1)=(5-1)(11-1)=40.}
Оберемо число, взаємно просте з
φ
(
n
)
{\displaystyle \varphi (n)}
НСД
(
3
,
φ
(
n
)
)
=
1.
{\displaystyle (3,\varphi (n))=1.}
Обчислимо
d
=
1
e
(
mod
φ
(
55
)
)
=
1
3
=
1
−
40
3
=
−
39
3
=
−
13
=
27
(
mod
40
)
.
{\displaystyle 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
(
mod
n
)
.
{\displaystyle C=S^{e}{\pmod {n}}.}
Отже
C
=
15
3
(
mod
55
)
=
15
2
∗
15
=
225
∗
15
=
5
∗
15
=
75
=
20.
{\displaystyle C=15^{3}{\pmod {55}}=15^{2}*15=225*15=5*15=75=20.}
Розшифруємо C. Для цього скористаємось правилом
S
=
C
d
(
mod
n
)
.
{\displaystyle S=C^{d}{\pmod {n}}.}
S
=
20
27
(
mod
55
)
=
(
4
∗
5
)
27
=
(
2
2
)
27
∗
5
27
=
2
54
∗
5
27
.
{\displaystyle S=20^{27}{\pmod {55}}=(4*5)^{27}=(2^{2})^{27}*5^{27}=2^{54}*5^{27}.}
Зауважимо, що
2
6
(
mod
55
)
=
64
=
9
=
3
2
,
{\displaystyle 2^{6}{\pmod {55}}=64=9=3^{2},}
5
3
(
mod
55
)
=
125
=
15.
{\displaystyle 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
.
{\displaystyle 2^{54}*5^{27}=(2^{6})^{9}*(5^{3})^{9}=(3^{2})^{9}*(15)^{9}=(3)^{18}*(15)^{9}.}
Зауважимо, що ми вже обчислювали
15
3
(
mod
5
)
5
=
20
,
{\displaystyle 15^{3}{\pmod {5}}5=20,}
3
4
(
mod
55
)
=
81
=
26.
{\displaystyle 3^{4}{\pmod {55}}=81=26.}
3
5
(
mod
55
)
=
3
4
∗
3
=
26
∗
3
=
78
=
23.
{\displaystyle 3^{5}{\pmod {55}}=3^{4}*3=26*3=78=23.}
3
6
(
mod
55
)
=
3
5
∗
3
=
23
∗
3
=
69
=
14.
{\displaystyle 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.
{\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.}
Тим самим розшифроване значення співпадає з початковим значенням.
Приклад №2
ред.
Оберемо два простих числа: p = 7, q = 13.
Тоді n = p * q = 7 * 13 = 91.
Згідно з властивістю функції Ейлера
φ
(
n
)
=
(
p
−
1
)
(
q
−
1
)
=
(
7
−
1
)
(
13
−
1
)
=
6
∗
12
=
72.
{\displaystyle \varphi (n)=(p-1)(q-1)=(7-1)(13-1)=6*12=72.}
Оберемо число, взаємно просте з
φ
(
n
)
{\displaystyle \varphi (n)}
НСД
(
5
,
φ
(
n
)
)
=
1.
{\displaystyle (5,\varphi (n))=1.}
Обчислимо
d
=
1
e
(
mod
φ
(
91
)
)
=
1
5
=
1
+
2
∗
72
5
=
145
5
=
29
(
mod
72
)
.
{\displaystyle 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
{\displaystyle S=11}
C
{\displaystyle C}
S
{\displaystyle S}
C
=
S
e
(
mod
n
)
.
{\displaystyle C=S^{e}{\pmod {n}}.}
Отже
C
=
11
5
(
mod
91
)
.
{\displaystyle C=11^{5}{\pmod {91}}.}
Зауважимо, що
11
2
(
mod
91
)
=
121
−
91
=
30
(
mod
91
)
.
{\displaystyle 11^{2}{\pmod {91}}=121-91=30{\pmod {91}}.}
Тоді
11
5
(
mod
91
)
=
(
11
2
)
2
∗
11
=
30
2
∗
11.
{\displaystyle 11^{5}{\pmod {91}}=(11^{2})^{2}*11=30^{2}*11.}
Зауважимо, що
30
2
(
mod
91
)
=
900
−
91
∗
9
=
81
(
mod
91
)
.
{\displaystyle 30^{2}{\pmod {91}}=900-91*9=81{\pmod {91}}.}
Тоді
30
2
∗
11
=
81
∗
11
=
891
−
9
∗
91
=
72
{\displaystyle 30^{2}*11=81*11=891-9*91=72}
C
=
72
(
mod
91
)
{\displaystyle C=72{\pmod {91}}}
Розшифруємо C. Для цього скористаємось правилом
S
=
C
d
(
mod
n
)
.
{\displaystyle S=C^{d}{\pmod {n}}.}
S
=
72
29
(
mod
91
)
.
{\displaystyle S=72^{29}{\pmod {91}}.}
Зауважимо, що
72
2
(
mod
91
)
=
(
8
∗
9
)
2
=
64
∗
81
=
(
64
−
91
)
∗
(
81
−
91
)
=
27
∗
10
=
270
−
2
∗
91
=
88
−
91
=
−
3
(
mod
91
)
.
{\displaystyle 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
(
mod
91
)
=
72
∗
(
72
2
)
14
=
72
∗
(
−
3
)
14
=
72
∗
3
14
=
8
∗
9
∗
3
14
=
8
∗
3
16
=
8
∗
(
3
4
)
4
.
{\displaystyle 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
(
mod
91
)
=
81
−
91
=
−
10
(
mod
91
)
.
{\displaystyle 3^{4}{\pmod {91}}=81-91=-10{\pmod {91}}.}
Отримаемо
8
∗
(
3
4
)
4
=
8
∗
(
−
10
)
4
=
8
∗
10
∗
10
3
=
80
∗
1000.
{\displaystyle 8*(3^{4})^{4}=8*(-10)^{4}=8*10*10^{3}=80*1000.}
Та врахувавши, що
1000
(
mod
91
)
=
1000
−
11
∗
91
=
−
1
(
mod
91
)
.
{\displaystyle 1000{\pmod {91}}=1000-11*91=-1{\pmod {91}}.}
Матимемо
80
∗
1000
=
−
80
+
91
=
11.
{\displaystyle 80*1000=-80+91=11.}
Тим самим розшифроване значення співпадає з початковим значенням.
