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

2.3.1. Modul arifmetikasi 
Ochiq kalitli kriptotizimlarni chuqur o’rganishdan oldin ularning asosi 
hisoblangan sonlar nazariyasi bilan yaqindan tanishib chiqish muhim hisoblanadi. 
Ochiq kalitli kriptotizimlar asosan modul arifmetikasiga asoslangani bois, dastlab 
ularga to’xtalib o’tiladi. 
Har  qanday  butun sonni    
𝑆𝑆
∈
 
𝑧𝑧
   ga  bo’lsak, bu songa  tayin  bir  qoldiq 
to’g’ri keladi. Masalan, 
5
2
= 2
∗
2 + 1
 bo’lib, unda qoldiq 1 ga va butun qism 2 ga 
teng bo’ladi. Kriptografiyada 
𝑎𝑎
 sonni 
𝑎𝑎
 songa bo’lgandagi qoldiq 
𝑆𝑆
 ga teng bo’lsa, 
u quyidagicha belgilanadi: 
𝑎𝑎𝑆𝑆𝑒𝑒𝑑𝑑𝑎𝑎 ≡ 𝑆𝑆
.  Dasturlash tillarida esa 
𝑎𝑎
%
𝑎𝑎
 kabi 
belgilanadi.  
Quyida qoldiq arifmetikasiga oid bir qancha misollar keltirilgan: 
−
 
7
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(3
∗
2)
𝑆𝑆𝑒𝑒𝑑𝑑
3 + 1
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
0 + 1
≡
1
 
−
 
14
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(3
∗
4)
𝑆𝑆𝑒𝑒𝑑𝑑
3 + 2
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
0 + 2
≡
2
 
−
 
2
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(0
∗
3)
𝑆𝑆𝑒𝑒𝑑𝑑
3 + 2
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
2
 
−
 
5
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
5
 
−
 
−
2
𝑆𝑆𝑒𝑒𝑑𝑑
5
≡
(
−
2 + 5)
𝑆𝑆𝑒𝑒𝑑𝑑
5
≡
3
𝑆𝑆𝑒𝑒𝑑𝑑
5
≡
3
 
−
 
−
7
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(
−
7 + 3)
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡ −
4
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(
−
4 + 3)
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
−
1
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
(
−
1 + 3)
𝑆𝑆𝑒𝑒𝑑𝑑
3
≡
2
 
Bundan tashqari ochiq kalitli kriptografiyada sonning modul bo’yicha 
teskarisini hisoblash muhim hisoblanadi. Masalan, odatiy matematikada 
𝑎𝑎
 sonining 
teskarisi 
1
𝑎𝑎
 ga teng bo’ladi. Modul arifmetikasida esa 
𝑎𝑎
 sonining 
𝑛𝑛
 modul bo’yicha 
teskarisi  
𝑎𝑎
−1
𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛
 ko’rinishida belgilanadi. Odatiy matematikada sonni uning 
teskarisiga ko’paytmasi birga teng bo’lgani kabi, modul arifmetikasida ham soning 
uning teskarisiga moduldagi ko’paytmasi birga teng bo’ladi. Ya’ni, 
𝑎𝑎
−1
𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛 ≡ 𝑎𝑎
 
bo’lsa, u holda 
(
𝑎𝑎 ∗ 𝑎𝑎
)
𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛 ≡
1
 tenglik o’rinli bo’ladi.  

---

47 
 
Izoh. 
Kriptografiyada modul sifatida (ya’ni, bo’luvchi) faqat tub sonlardan 
foydalanish talab etiladi. Ya’ni, 
amodn
 tenglikdagi 
n
 har doim tub bo’lishi talab 
etiladi.
 
Misol tariqasida, 3 sonining 7 maydondagi teskarisini topish talab etilsin. 
Ya’ni, 
𝑥𝑥
 ni topish talab etilsin: 
3
−1
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡ 𝑥𝑥
. Yuqoridagi tenglik 
(3
∗ 𝑥𝑥
)
𝑆𝑆𝑒𝑒𝑑𝑑
7
≡
1
 dan foydalanib, 
𝑥𝑥
 ning o’rniga son qo’yib natijani hisoblash mumkin. Lekin ushbu 
jarayon ko’p vaqt talab etadi (ayniqsa katta sonlarda juda ham ko’p vaqt talab etiladi).  
Ushbu muammoni yechishning ko’plab usullari mavjud bo’lib, quyida 
ulardan biri bo’lgan qoldiqlar to’g’risidagi 
Yevklidning kengaytirilgan algoritmi
dan 
foydalanib yechish usuli keltirilgan.  
Kengaytirlgan Yevklid algoritmi. 
Kengaytirlgan Yevklid algoritmi RSA 
kriptotizimi ochiq kaliti «
ye
» - ni topishda 
𝑑𝑑 ∗ 𝑒𝑒
 
≡
1(
𝑆𝑆𝑒𝑒𝑑𝑑
ϕ
(
𝑛𝑛
)) 
 
tenglamaga duch 
kelinib, uni yechish bevosita 
𝑎𝑎𝑥𝑥
+
𝑎𝑎𝑦𝑦
=
𝑑𝑑
,    
𝑑𝑑
= EKUB(
𝑎𝑎
,
𝑎𝑎
)
 tenglamaning butun 
yechimlarini topish masalasiga ekvivalent hamda  bu algoritmga ko’ra berilgan 
a
 – 
soniga m
𝑒𝑒𝑑𝑑𝑛𝑛
 bo’yicha teskari elementni topish imkonini beradi. Shuning uchun 
ham bu algoritm ishlash prinsiplarini keltirish muhim.