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 algoritmidan
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.
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:
