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

Teorema.
  Aytaylik,   
a
  va 
b
  natural sonlar,  
𝑑𝑑
  =  EKUB( a ,
𝑎𝑎
 )
 bo’lsin. U 
holda   shunday   
α
   va 
β
  butun sonlar topiladiki  
 
 
 
α
 
∗
 a  +  
β
∗
 
𝑎𝑎
  =  
𝑑𝑑
  
tenglik o’rinli bo’ladi. 
Demak, bu algoritm nafaqat ikkita natural sonning EKUBini, balki 
yoyilmadagi  
α
 va 
β
  koeffisentlarni ham topish imkonini berar ekan. Shunisi bilan 
ham aslida Yevklid algoritmidan   farqlanadi. 
Kengaytirilgan Yevklid algoritmiga muvofiq topiladigan 
α
 va 
β
   butun 
sonlar, quyidagi Diafant  tenglamasining   
 
 
 
α
 
∗
 a  +  
β
∗
 
𝑎𝑎
  =  
𝑑𝑑
  
butun yechimlari hisoblanadi. Bundan RSA algoritmining ochiq kalitiga ko’ra 
maxfiy kalitini hisoblashda foydalanish mumkin. Shu sababli bu algoritm  ishlash 
qadamlari bilan yaqindan tanishib chiqiladi. 

---

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.