Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot

48 
Faraz qilaylik,
a 
va
b
sonlarning EKUBni topishda quyidagi ketma-ketlik 
qaralayotgan bo’lsin: 
a= b*q
1
 + r
1
r
1
= ax
1
 + by
1;
 
 
 
b = r
1
* q
2
 + r
2
r
2
= ax
2
+ by
2
; 
 
 
r
1
= r
2
 *q
3
 + r
3
r 
3
= ax
3
+ by
3
; 

 
………………. ……………….. 
 
 
r 
n-3
= r
n-2
* q 
n-1 
+ r 
n-1
r 
n-1 
=ax 
n-1
+ by 
n-1
 
 
 
r 
n-2 
= r 
n-1
* q
n
r 
n
 =0; 
Bu yerda,
 x
1
, x
2
,….x 
n-1 
 
va
u
1
, u
2
……y
n -1
sonlarini topish kerak bo’lsin. Bu sonlar quyidagi formula yordamida topiladi: 
x
j
= x 
j-2
 – q 
j 
x 
j-1 
va u
j 
 = y 
j - 2
 
 
- q
j
 y
j-1

bu yerda, 
x 
-1
=1 , u
-1
 =0 , x
0
 =0 , u
0
 =1.
Kerakli ma’lumotlarni quyidagi jadval orqali aniqlash mumkin: 
qoldiqlar 
bo’luvchi 
x 
U 
a
* 
x 
-1
 
u
-1 
b 
* 
x 
0
 
y
-1
 
r 
1
 
r
2 
r 
3
 
. 
. 
. 
. 
r 
n-2

r 
n-1
 
q
1
 
q
2
 
q
3
 
. 
. 
. 
. 
q
n-2
 
q 
n-1
 
x
1
 
x
2
 
x
3
 
. 
. 
. 
. 
x 
n-2

x 
n-1
 
y
1 
y
2
 
y
3
 
. 
. 
. 
. 
y
n-2
 
y
n-1 
 
Jadvalning oxirgi ustunida keltirilgan ikki qiymat izlanayotgan alfa va beta 
koeffisentlar, yani
α
 = x 
n-1 
, 
β
 = u
n-1
bo’ladi. 

49 
Misol
. Yevklid algoritmini qo’llab EKUB (6188,4709) va
α
,
β
- qiymatlar 
topilsin. 
Yevklid algoritmi qadamlariga muvofiq: 
6188=4709*1+1479, ya’ni r
1
=1479 
4709=1479*3+272, ya’ni r
2
=272 
1479=272*5+119, ya’ni r
3
=119 
272=119*2+34, ya’ni r
4
=34 
119=34*3+17, ya’ni r
5
=17 
34=17*2+0, ya’ni r
6
=0 
demak,
r
5
=17
soni 6188 va 4709 sonlarining EKUBi deb e’lon kilinadi, ya’ni
EKUB (6188, 4709)=17 .
Kengaytirilgan Yevklid algoritmiga ko’ra: 
6188*
α
+ 4709 *
β
=17 
α
=?,
β
=? topilsin: 
yuqorida keltirilgan ifodani quyidagicha yozish mumkin: 
17=119 – 34*3 
34=272 – 119*2 
119=1479 – 272*5 
272=4709 – 1479*3 
1479=6188 – 4709*1 
yoki: 
17= 119 – 3* (272 – 119*2)=7*119 – 3*272=7* (1479 – 272*5) – 3*272= 
=7*1479 - 38*272=7*1479 – 38* (4709 – 1479*3)=121*1479 – 38*4709= 
=121* (6188 - 4709) – 38*4709=121*6188 – 159*4709 ,
Ya’ni, 
6188*121+4709* (- 159)=17; demak,
α
=121; 
β
= - 159 
Javob
:
α
=121, 
β
= - 159. 

50 
Misol. 
3
−1
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡ 𝑥𝑥
 
ni topish talab etilgan bo’lsin. Yuqorida keltirilgan 
algoritmga ko’ra 
7 = 3
∗
2 + 1
 
3 = 1
∗
3 + 0
 
Qoldig’i nolga teng bo’lgan tenglikdan oldingi tenglikdan boshlab 
quyidagicha teskari yozish amalga oshiriladi: 
1 = 7
−
(3
∗
2) = 7 + (
−
2
∗
3) = 7
∗
1 + (
−
2
∗
3)
 
Yuqoridagi tenglikni ikki tomonini modulga (
𝑆𝑆𝑒𝑒𝑑𝑑
7)
olinsa quyidagi 
tenglikga ega bo’linadi: 
�
(7
∗
1)
𝑆𝑆𝑒𝑒𝑑𝑑
7 + (
−
2
∗
3)
𝑆𝑆𝑒𝑒𝑑𝑑
7
�𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
𝑆𝑆𝑒𝑒𝑑𝑑
7
 
yoki 
(
−
2
∗
3)
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
. Ushbu tenglikni 
(3
∗ 𝑥𝑥
)
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
taqqoslash 
orqali 
𝑥𝑥
=
−
2
ga tengligini yoki 
−
2
𝑆𝑆𝑒𝑒𝑑𝑑
7 = 5
ligini topish mumkin. Ya’ni, 
(3
∗
5)
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
tenglikni qanoatlantiradi.
 
Javob
3
−1
( 
𝑆𝑆𝑒𝑒𝑑𝑑
7) = 5.
 
2.3.2. RSA algoritmi 
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan 
olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining 
darajaga ko’tarish amalidan foydalanishga asoslangan [20].
RSA algoritmida ochiq va shaxsiy kalitlar juftini generasiya qilish uchun 
ikkita katta uzunlikdagi 
𝑆𝑆
va 
𝑞𝑞
sonlari tanlanadi va ularning ko’paytmasi 
hisoblanadi: 
𝑁𝑁
=
𝑆𝑆 ∗ 𝑞𝑞
. Shundan so’ng 
𝜑𝜑
(
𝑁𝑁
) = (
𝑆𝑆 −
1)
∗
(
𝑞𝑞 −
1)
bilan o’zaro tub 
bo’lgan, 
𝑒𝑒
soni tanlanadi (
𝜑𝜑
(
𝑁𝑁
)
funksiya ma’nosi quyida keltirilgan). Shundan 
so’ng 
𝜑𝜑
(
𝑁𝑁
)
modulda 
𝑒𝑒
sonining teskarisi hisoblanadi va u 
𝑑𝑑
ga teng bo’ladi. 
Shundan so’ng, ikkita tub sonlarning (
𝑆𝑆
va 
𝑞𝑞
) ko’paytmasi 
𝑁𝑁
va 
𝑒𝑒𝑑𝑑
= 1 
𝑆𝑆𝑒𝑒𝑑𝑑
𝜑𝜑
(
𝑁𝑁
)
shartni qanoatlantiruvchi 
𝑒𝑒
va 
𝑑𝑑
sonlari mavjud. Shundan so’ng, 
𝑆𝑆
va 
𝑞𝑞
lar esdan 
chiqariladi (o’chirib tashlanadi). 
Bu yerda, 
𝑁𝑁
modul hisoblanib, (
𝑁𝑁
,
𝑒𝑒
) ochiq kalit juftini va 
𝑑𝑑
maxfiy kalitni 
tashkil etadi. RSA algoritmida shifrlash va deshifrlash modul bo’yicha darajaga 

51 
oshirish asosida bajariladi. RSA algoritmida shifrlash uchun 
𝑀𝑀
xabarni son 
ko’rinishida ifodalash talab etiladi va 
𝑁𝑁
modul bo’yicha 
𝑒𝑒
darajaga ko’tariladi, ya’ni 
𝐶𝐶
=
𝑀𝑀
𝑒𝑒
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
. 
S 
ni deshifrlash uchun uni 
𝑁𝑁
modul bo’yicha shaxsiy kalit 
𝑑𝑑
darajaga 
ko’tarish talab etiladi: 
𝑀𝑀
=
𝐶𝐶
𝑑𝑑
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
. 
Boshqacha aytganda RSA algoritmida xabar ochiq kalit bilan shifrlansa va 
shaxsiy kalit bilan deshifrlansa, 
𝑀𝑀
=
𝐶𝐶
𝑑𝑑
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
= 
𝑀𝑀
𝑒𝑒𝑑𝑑
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
tenglik 
to’g’riligini isbotlash zarur. 
Eyler teoremasi. 
Agar 
𝑥𝑥
haqiqiqatdan 
𝑛𝑛
bilan o’zaro tub bo’lsa, 
𝑥𝑥
𝜑𝜑
(
𝑛𝑛
)
=
1 
𝑆𝑆𝑒𝑒𝑑𝑑
𝑛𝑛
bo’ladi. Bu yerda, 
𝜑𝜑
(
𝑛𝑛
)
– funksiya, 
𝑛𝑛
dan kichik va u bilan o’zaro tub 
bo’lgan sonlar miqdorini ko’rsatadi. Agar 
𝑛𝑛
soni tub bo’lsa, 
𝜑𝜑
(
𝑛𝑛
) =
𝑛𝑛 −
1
bo’ladi.
Shuning uchun 
𝑒𝑒𝑑𝑑
= 1 
𝑆𝑆𝑒𝑒𝑑𝑑
𝜑𝜑
(
𝑁𝑁
) = 1 
𝑆𝑆𝑒𝑒𝑑𝑑
(
𝑆𝑆 −
1)(
𝑞𝑞 −
1)
tenglik kabi 
yozish mumkin. Mazkur tenglikning to’liq shakli aslida 
𝑒𝑒𝑑𝑑
= 1 
𝑆𝑆𝑒𝑒𝑑𝑑
𝜑𝜑
(
𝑁𝑁
) +
𝑘𝑘
𝜑𝜑
(
𝑁𝑁
)
ga teng. Ya’ni, 
𝑒𝑒𝑑𝑑
ko’paytmani 
𝜑𝜑
(
𝑁𝑁
)
ga bo’lganda 
𝑘𝑘
tadan tegib, bir 
qoldiq qolgan. Shuning uchun ushbu tenglikni quyidagicha yozish mumkin: 
𝑒𝑒𝑑𝑑 −
1 =
𝑘𝑘
𝜑𝜑
(
𝑁𝑁
)
. 
Ushbu tengliklardan, RSA algoritmining to’g’ri ishlashini tasdiqlash mumkin: 
𝐶𝐶
𝑑𝑑
=
𝑀𝑀
𝑒𝑒𝑑𝑑
=
𝑀𝑀
(
𝑒𝑒𝑑𝑑−1
)
+1
=
𝑀𝑀 ∗ 𝑀𝑀
𝑒𝑒𝑑𝑑−1
=
𝑀𝑀 ∗ 𝑀𝑀
𝑘𝑘
𝜑𝜑
(
𝑁𝑁
)
=
𝑀𝑀 ∗
1
𝑘𝑘
=
𝑀𝑀
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
.
Aytaylik, RSA algoritmida ma’lumotni shifrlash va deshifrlash amallarini 
tanlab olingan (
𝑆𝑆
= 11 va 
𝑞𝑞
= 3
) “katta” sonlar ustida amalga oshirish talab qilinsin. 
Mazkur holda modul 
𝑁𝑁
=
𝑆𝑆 ∗ 𝑞𝑞
= 33
ga teng bo’ladi va 
𝜑𝜑
(
𝑁𝑁
) = (
𝑆𝑆 −
1)(
𝑞𝑞 −
1) = 20
ga teng bo’ladi. U holda shifrlash uchun zarur bo’lgan daraja 
e 
ni (
𝑒𝑒
= 3
) 
ga teng deb olish mumkin. Sababi, 3 soni 
𝜑𝜑
(
𝑁𝑁
) = 20
bilan o’zaro tubdir. Shundan 
so’ng, Evklidning kengaytirilgan algoritmi asosida deshifrlash kaliti (
𝑑𝑑
= 7
) 
aniqlanadi. Ya’ni, 
𝑒𝑒𝑑𝑑
= 3
∗
7 = 1 
𝑆𝑆𝑒𝑒𝑑𝑑
20
. U holda A tomonning ochiq kalit jufti 
(
𝑁𝑁
,
𝑒𝑒
) = (33,3)
va shaxsiy kaliti esa 
𝑑𝑑
= 7
ga teng.

52 
Shundan so’ng, A tomon o’zining ochiq kalitini barchaga uzatadi. Biroq, 
shaxsiy kalitini maxfiy saqlaydi.
Faraz qilaylik, B tomon A tomonga 
𝑀𝑀
= 15
ma’lumotni shifrlab 
yubormoqchi. Buning uchun B tomon A tomonning ochiq kaliti juftini 
(
𝑁𝑁
,
𝑒𝑒
) =
(33,3)
oladi va shifrmatnni quyidagicha hisoblaydi: 
𝐶𝐶
=
𝑀𝑀
𝑒𝑒
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
= 15
3
= 3375 = 9 
𝑆𝑆𝑒𝑒𝑑𝑑
33
 
va uni A tomonga yuboradi.
A tomon 
𝐶𝐶
= 9
shifrmatnni deshifrlash uchun shaxsiy kalit 
𝑑𝑑
= 7
dan 
foydalanadi: 
𝑀𝑀
=
𝐶𝐶
𝑑𝑑
𝑆𝑆𝑒𝑒𝑑𝑑
𝑁𝑁
= 9
7
= 4782969 = 144938
∗
33 + 15 = 15 
𝑆𝑆𝑒𝑒𝑑𝑑
33
 
Agar RSA algoritmida kichik tub sonlardan (
𝑆𝑆
va 
𝑞𝑞
uchun
) foydalanilgan 
taqdirda, hujumchi ochik bo’lgan 
𝑁𝑁
ni osonlik bilan ikkita tub sonning ko’paytmasi 
ko’rinishida yozishi mumkin. Shundan so’ng, ochiq kalitning ikkinchi qism 
𝑒𝑒
dan 
foydalangan holda, shaxsiy kalit 
𝑑𝑑
ni hisoblay oladi. Shuning uchun RSA 
algoritmidan amalda foydalanish uchun tanlanuvchi tub sonlar uzunligi kamida 2048 
bit bo’lishi talab etiladi. Bundan tashqari, RSA algoritmini buzish faqat faktorlash 
muammosiga bog’liqligi isbotlanmagan. Boshqacha aytganda, RSA algoritmini 
buzishning faktorlash muammosini yechishdan tashqari biror usuli aniqlanmagan.

Download 4,35 Mb.