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 quyidagilarni qanoatlantirishi kerak:
p mod4=3, q mod4=3.
Ochiq kalit n=p·q. M ochiq xabar va MShifrlash: C=M 2 modn;
Shifrni ochishda quyidagilar hisoblanadi: 𝑚1 = 𝐶
𝑝+1
4 𝑚𝑜𝑑 𝑝,
𝑚2 = (𝑝 − 𝐶
𝑝+1
4 ) 𝑚𝑜𝑑 𝑝, 𝑚3 = 𝐶
𝚐+1
4 𝑚𝑜𝑑 𝑞, 𝑚4 = (𝑞 − 𝐶
𝚐+1
4 ) 𝑚𝑜𝑑 𝑞,
𝑎 = 𝑝 (𝑝 −1𝑚𝑜𝑑 𝑞 ), 𝑏 = 𝑞 (𝑞 −1𝑚𝑜𝑑 𝑝 ),
𝑀 1 = (𝑎 · 𝑚 3 + 𝑏 · 𝑚 1)𝑚𝑜𝑑 𝑛,
𝑀 2 = (𝑎 · 𝑚 3 + 𝑏 · 𝑚 2)𝑚𝑜𝑑 𝑛,
𝑀 3 = (𝑎 · 𝑚 4 + 𝑏 · 𝑚 1)𝑚𝑜𝑑 𝑛,
𝑀 4 = (𝑎 · 𝑚 4 + 𝑏 · 𝑚 2)𝑚𝑜𝑑 𝑛.
Hosil bo‗lgan M 1 , M 2 , M 3 , M 4 lardan bittasi kerakli M xabarga teng
bo‗ladi. M={ M 1 , M 2 , M 3 , M 4 }.
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.
Dostları ilə paylaş: |