|
RSA algoritmi
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan
olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining
darajaga ko’tarish amalidan foydalanishga asoslangan.
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
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.
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.
Simmetrik kalitli kriptotizimlarda bo’lgani kabi ochiq kalitli kriptotizimlarda ham
real hayotda foydalanish uchun kalit uzunligiga talablar qo’yiladi. Yuqorida
simmetrik kriptotizimlar uchun ushbu masala bilan tanishib o’tilgan edi. Simmetrik
va ochiq kalitli kriptotizimlarning matematik asosi turlicha bo’lgani bois, ular bir xil
bardoshlik darajasida bo’lganida turli kalit uzunliklariga ega bo’ladilar
immetrik va ochiq kalitli kriptotizimlar bir xil bardoshlikka ega bo’lganida
ulardagi kalitlarning uzunliklari
Simmetrik shifrlash algoritmi RSA algoritmi (
𝑆𝑆
va
𝑞𝑞
sonlari)
56 bit 512 bit
80 bit 1024 bit
112 bit 2048 bit
128 bit 3072 bit
192 bit 7680 bit
256 bit 15360 bit
Simmetrik kriptotizimlarda bo’lgani kabi ochiq kalitli kriptotizimlarda ham
kalitlarni barcha variantlarini hisoblash qurilmalar imkoniyatiga bog’liq. Ya’ni,
hozirgi kunda yetarli deb qaralgan kalit uzunligi, 10 yildan keyin tavsiya etilmasligi
mumkin. Chunki, 10 yil davomida hisoblash qurilmalarining imkoniyatlari hozirgi
kundagi kabi bo’lmaydi.
RSA algoritmidagi
𝑁𝑁
modulning turli uzunligida faktorlash uchun talab etilgan
vaqt qiymatlari ko’rsatilgan. Bunda natijalar bir sekundda million amal
bajaruvchi (one-million-instruction-per-second, mips) kompyuter yoki yiliga 10 -13
amal bajarilishi hisobida olingan. Faktorlash algoritmi sifatida GNFS (general
number field sieve) dan foydalanilgan.
RSA algoritmidagi
𝑁𝑁
modulning turli uzunligida faktorlash uchun talab
etilgan vaqt qiymatlari
𝑁𝑁
ning bitdagi uzunligi Talab etiluvchi yillar
512 30 000
768 2*
10
8
1024 3*
10
11
1280
10
14
1536 3*
10
16
2048 3*
10
20
Yuqoridagi keltirilgan ma’lumotlardan ko’rish mumkinki, hisoblash qurilmalari
imkoniyatining ortishi kriptografik algoritmlarning bardoshligini kamayishiga olib
keladi. Bu ta’sir har ikkala simmetrik va ochiq kalitli kriptotizimlarga tegishli.
Do'stlaringiz bilan baham: |
