Rabin algoritmi

Rabin algoritmi
Bu shifrlash usuli 1979-yilda Maykl Rabin tomonidan chop etilgan. Algortimning xavfsizligi kata tub sonlarga va ko’paytuvchilarga ajiratish muammosiga asoslangan. Bunda ikkita kata tub son tanlanadi va ularning har birini to’rt soniga bo’linganda qoldiq uch chiqishi kerak. Bu sonlar yopiq kalit hisoblanadi. Ularning ko’paytmasi ochiq kalit hisoblanadi. P,q tub sonlar tanlanadi. Yuqordagi shartga ko’ra ular quyidagilarni qanooatlantirishi kerak:
p mod4=3, q mod4=3.
Ochiq kalit n=p*q. M ochiq xabar va M


Qolgan uchta xabar yolg’on bo’ladi. Mana shu jihatdan 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 qiyinchilik 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.

RSA algoritmi

Ochiq kalitli kriptotizmlarni bir tomonli funksiyalar ko’rinishi bo’yicha farqlash mumkin. Bularning ichida RSA, El-Gamal va Mak-Elis tizimlarini alohida tilga olish o’rinli. Hozirda eng samarali va keng tarqalgan ochiq kalitli shifrlash algortimi sifatida RSA agoritmini ko’rsatish mumkin.
1976-yilda Uitfild Diffi va Martin Xellmanlar tomonidan chop etilgan “Kriptografiyada yangi yo’nalish” deb nomlangan maqola kriptografik tizimlar haqidagi tasavvurlarni o’zgartirib yubordi, ochiq kalitli kriptografiya paydo bo’lishiga zamin yaratdi. Bu maqolani o’rganib chiqqan Massachusets texnologiyalar institute olimlari Ronald Rivest, Adi Shamir va Leonard Adleman 1977-yil avgust oyida Scientific American jurnalida RSA kriptotizmini yoritib berishdi va shu algoritm bilan shifrlangan quyidagi iborani ochishni o’quvchilarga taklif etishdi.

n=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, e=9007, M=?
Mukofot sifatida 100 AQSh dollari e’lon qilindi. Algoritm avtorlaridan biri Rivest bu shifrni ochishga 40 kvadrillion yil ketishini aytgan bo’lsa, 1993-yil 3-sentabrdan 1994-yil mart oyigacha 20 ta mamlaktdan 600 ta ko’ngilli shaxslar 1600 ta kompyuterda parallel ishlab bu sshifrni ochishdi – THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.
1982-yilda Ronald Rives, Adi Shamir va Leonard Adleman RSA Data Security kompaniyasini tashhkil etishdi. 1989-yildan boshlab RSA algoritmi Internetda foydalanila boshlandi. 1990-yildan boshlab AQSh mudofa vazirligi foydalana boshladi. 1993-yilda PKCSI standaartining 1.5 versiyasida RSA algoritmini shifrlash va electron imzo yaratishda qo’llash keltirildi. Bu standaartning oxirgi versiyalari RFC standartida keltirilgan (RFC 2313 – 1.5, 1993 yil; RFC 2437 – 2.0, 1998 yil; RFC 3447 – 2.1, 2002 yil).
Algoritmni quyidagi qadamar ketma-ketligi ko’rinishida ifodalash mumkin;