Mirzo ulug’bek nomidagi

Rabin algoritmi

Bu shifrlash usuli 1979 yilda Maykl Rabin tomonidan chop etilgan. Algoritmning xavfsizligi katta tub sonlarga va ko‘paytuvchilarga ajratish muammosiga asoslangan. Bunda ikkita katta tub son tanlanadi va ularning har birini to‘rt soniga bo‘lganda uch qoldiq chiqishi kerak. Bu sonlar yopiq kalit hisoblanadi. Ularning ko‘paytmasi ochiq kalit hisoblanadi. p, q tub sonlar tanlanadi.Yuqoridagi shartga ko‘ra ular quyidagilarniqanoatlantirishi kerak:
p mod4=3, q mod4=3.
Ochiq kalit n=p-q. M ochiq xabar va MShifrlash: C=M² modn;
Shifrni ochishda quyidagilar hisoblanadi:
𝑝+1

𝑚₁ = 𝐶
⁴ 𝑚𝑜𝑑 𝑝,
𝑝+1

𝑚₂ = (𝑝 − 𝐶
⁴ )𝑚𝑜𝑑 𝑝,

𝑚₃ = 𝐶

𝑝+1
⁴ 𝑚𝑜𝑑 𝑞,
𝑝+1

𝑚₄ = (𝑝 − 𝐶
⁴ 𝑚𝑜𝑑 𝑞,

𝑎 = 𝑝⁽𝑝⁻¹𝑚𝑜𝑑 𝑞⁾, 𝑏 = 𝑞(𝑞⁻¹𝑚𝑜𝑑 𝑝)
M₁ = (a · m₃ + b · m₁)mod n,
M₂ = (a · m₃ + b · m₂)mod n,

M₃ = (a · m₄ + b · m₁ )mod n, M₄ = (a · m₄ + b · m₂)mod n.
Hosil bo‘lgan M₁, M₂, M₃, M₄ lardan bittasi kerakli M xabarga teng bo‘ladi. M={ M₁, M₂, M₃, M₄}.
Qolgan uchta xabar yolg‘on bo‘ladi. Mana shu jihat bu algoritmning keng tarqalishiga to‘sqinlik qildi. Shifrlash tezligi jihatidan RSA algoritmidan ustun turadi, lekin shifrni ochishda tezlikdan ancha yutqazadi. Agar shifrlanayotgan xabar tasodifiy bitlardan iborat bo‘lsa, uni ochishda qiyinchiliklar tug‘diradi, chunki qaysi javob to‘g‘riligini aniqlash uchun ichiga ma’lum tekstlarni joylashtirishga to‘g‘ri keladi.
Misol.
Ikkita tub son p=43, q=19 va M=OLTI matn berilgan. Shu matnni Rabin algoritmidan foydalanib shifrlaymiz.
Shifrlash.

1. 
   n ni hisoblab olamiz n=q · p=19·43=817
   
2. 
   Matnni 10 lik sanoq sistemasida ifodalaymiz: 0 → 4F →7 9 , L → 4 C → 76, T → 54 → 84, 1 → 49 → 73 .
   

M=79, 76, 84, 73.
2. С₁=M_i² mod nformula yordamida shifrlash amalga oshiriladi:
С₁ =M_i² mod n=79²mod 817=522 C₂ = M_i² mod n = 76²mod817 = 57, С₃ =M_i² mod n = 84²mod 817 = 520, С₄ =M_i² mod n= 73²mod 817 = 427.
C = { C ₁ , C ₂ , C ₃ , C ₄} = {522, 57, 520, 427} shifrtekst hosil bo‘ldi. Shifrni ochish.
Shifrni ochish jarayoniga ko‘proq vaqt sarflanadi. Shifrtekstdagi har bir son alohida ochiladi. C = C₁ = 5 2 2 ni ko‘rib chiqamiz.

1. 𝑚₁ = 𝐶

𝑝+1
⁴ 𝑚𝑜𝑑 𝑝 = 522 mod 43 = 36

2. 𝑚₂ = 𝐶
3. 𝑚₃ = 𝐶
4. 𝑚₄ = 𝐶
𝑝+1


⁴ 𝑚𝑜𝑑 𝑝 = (43 − 36) mod 43 = 7
𝑞+1
⁴ 𝑚𝑜𝑑 𝑝 = 522 mod 19 = 16
𝑞+1


⁴ 𝑚𝑜𝑑 𝑝 = (19 − 16) mod 19 = 3

5. a va b larni hisoblash uchun p, q larning teskarisini topib olamiz: p ^-1 mod q=43^-1mod 19= 5¹⁷ mod 19=4
q ^-1 mod p=19^-1 mod 43=19⁴¹ mod 43=34
6. a=p(p ^-1 mod q)=43·4=172 b=q(q ^-1 mod p)=19·34=646
7. M₁=(a·m₃ +b·m₁ ) mod n=(172·16+646·36) mod 817=681
8. M₂=(a·m₄ +b· m₁ ) mod n=(172·3+646·36) mod 817=79
9. M₃=(a·m₃+b·m₂) mod n=(172·16+646·7) mod 817=738
10. M₄=(a·m₄+b·m₂) mod n=(172·3+646·7) mod 817=136
Olingan Mi, M₂, M₃, M₄ lardan 127 dan kichiklarini o‘n oltilik sanoq tizimiga o‘tkazamiz: 79₁₀=>4F₁₆=>O harfi paydo bo‘ldi.
1-10 qadamlar C ₂ , C ₃ , C ₄ larning har biri uchun alohida hisoblanadi. Shu orqali bizda M=OLTI ochiq matn hosil bo‘ladi.