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