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

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