Моноалфавитли алмаштириш алгоритми ёрдамида шифрлашга мисол

p,q,e –sonlaridan iborat{p,q,e}=z parametrlar to‘plami tenglik bilan aniqlangan bir tomonli funksiyaning kriptografik mahfiylik uslubi xossasining asosini tashkil etadi. Mahfiy deshifrlash algoritmining asosini tashkil etuvchi teskari funksiyaning qiymatlarini hisoblash ham kvadratga ko‘tarish va ko‘paytirish amallari orqali amalga oshiriladi va bunda daraja ko‘rsatkichi bo‘lgan d soni EKUB(e, n)) ni hisoblashning Yevklid algoritmi bo‘yicha aniqlanadi. Yuqorida ifoda bilan aniqlangan funksiyaning ifoda bilan funksiyaga haqiqatan ham teskari funksiya ekanligi quyidagicha ko‘rsatiladi. Butun sonlar arifmetikasidan ma’lumki, biror butun Q sonida

tenglik o‘rinli bo‘ladi. Yuqoridagi va tengliklarga va Eyler teoremasidagi ifodaga ko‘ra
tenglikka ega bo‘lamiz. Demak, tenglikni qanoatlantiruvchi d va e sonlari uchun: biror x sonlarning n modul bo‘yicha d darajaga ko‘tarish amali, shu x sonlarni xuddi shu n modul bo‘yicha e darajaga ko‘tarish amaliga teskari ekan. Endi nima uchun Rivest, Shamir va Adlman yuqorida ifoda bilan aniqlangan funksiyani n va e sonlarini bilgan holda, unga teskari funksiyani hisoblash mumkin emasligini ta’kidlaganliklarini ko‘rib chiqamiz. Bundan tashqari p va q tub sonlarini qanday qilib tanlanganda, raqib tomonning bu sonlarni bila olmasligini ham ko‘rib chiqamiz.
Raqib tomonga n va e sonlari ma’lum bo‘lsin. Agarda raqib tomon n sonini tub bo‘lgan p va q sonlarining ko‘paytmasidan iborat, ya’ni n=pq ko‘rinishida ifodalay olsa, u holda mahfiylik parametri z={p,q,e} ni to‘la aniqlagan holda, ma’lumotlar kriptogrammasini, ma’lumotni haqiqatan ham olishi kerak bo‘lgan foydalanuvchi kabi, qiyinchiliksiz deshifrlash imkoniyatiga ega bo‘ladi. Shuning uchun RSA kriptosistemasining bardoshlilik darajasi n sonini tub bo‘lgan p va q sonlarining ko‘paytmasiga yoyishning qiyinlik darajasiga ekvivalentdir, ya’ni teng kuchlidir. Agarda p va q sonlarining uzunligi 100 dan ortiq o‘nli raqamdan iborat bo‘lsa, hozirgi zamonaviy hisoblash tehnikalaridan foydalanilganda, n sonini tub ko‘paytuvchilarga ajratish uchun sarflanadigan vaqt yetarli darajada ko‘p bo‘lib, bunday tub ko‘paytuvchilarga ajratish bilan shug‘ullanishining amaliy jihatdan maqsadga muofiq emasligi kelib chiqadi.
Yuqoridagi mulohazalardan tabiiy ravishda, «yetarli darajada katta bo‘lgan p va q tub sonlarini qanday aniqlash mumkin?”, degan savol tug‘iladi. Bunday savolga javob topish uchun Chebeshev teoremasiga murojaat qilamiz: biror butun m sonidan kichik bo‘lgan barcha butun sonlar to‘plamidan tanlab olingan biror sonni, tub son bo‘lish ehtimolligi qiymatga yaqin.
Misol uchun 10¹⁰⁰ dan kichik bo‘lgan barcha musbat butun sonlar to‘plamidan tanlab olingan biror sonni tub son bo‘lish ehtimolligi qiymatga ega. Bu ehtimollik qiymati ikki barobar ko‘payadi, agarda bu tanlab olish faqat 10¹⁰⁰ dan kichik bo‘lgan barcha butun musbat toq sonlar to‘plamida amalga oshirilayotgan bo‘lsa. Toq sonlardan tub sonlarni farqlash Ferma teoremasiga asoslanadi: biror p tub sonidan katta bo‘lmagan butun musbat son uchun tenglik o‘rinlidir.
Misol uchun, 2⁴=1(mod5) yoki 3⁴=1(mod5). Bu keltirilgan munosabat EKUB(5,6)=1 va munosabatning xususiy holidir. Agarda r sonining tub yoki tub emasligini tekshirmoqchi bo‘lsak, shu r sonidan kichik bo‘lgan butun musbat b sonini olib tenglikni bajarilishini tekshirish kifoya:
- tenglik bajarilsa r tub son bo‘lishi mumkin, chunki yoki munosabat p ning yoki r sonining tub bo‘lishini zaruriy sharti;
- tenglik bajarilmasa r tub son emas.
Shunday qilib, agarda munosabat o‘rinli bo‘lmasa qat’iy holda r soni tub emas, deb ayta olamiz. Ammo, munosabat o‘rinli bo‘lsa, faqat, r soni tub bo‘lishi mumkin, lekin qat’iy holda r tub son, deb tasdiqlay olmaymiz.
Shuning uchun, r soni yetarli darajada katta bo‘lib, tasodifiy olingan mumkin qadar ko‘p butun musbat sonlari uchun munosabat bajarilsa r sonining tub ekanligiga shunchalik ko‘p darajada ishonch hosil qilish mumkin. Agarda b ning yuzta qiymatida munosabat o‘rinli bo‘lsa, u holda r sonining tub bo‘lmasligi xodisasining ehtimoli qiymati ga teng bo‘ladi.
Yuqorida keltirilgan algoritmdan bugungi kunda ham biror r sonining tubligini aniqlashda foydalanib kelinmokda har qanday ochiq kalitli kriptosistemaning bardoshliligi ochiq matnga yoki uning biror qismiga mos keluvchi kriptogramma ma’lum bo‘lganda, ya’ni shifrlash algoritmi Ye_z ma’lum bo‘lganda, to‘la shifr matnni (kriptogrammani) deshifrlash imkoniyati qanchalik murakkabligi bilan baholanadi.
Yuqorida ko‘rib o‘tilgan Diozfi va Xellmanning bir tomonli funksiyasi hamda RSA bir tomonli funksiyasi yetarli darajada ochiq kalitli kriptosistemalarninig xossalarini ochib beradi. Bu bir tomonli funksiyalardan tashqari ham ko‘plab bir tomonli funksiyalar kriptologiya sohasidagi ilmiy nashryotlarda e’lon qilingan. Ularning ba’zilari yetarli darajada kriptosistemalar talablariga javob bermagan. Shuni ta’kidlaymizki, hozirgacha ochiq nashryotda hech kim tomonidan haqiqatan ham bir tomonli bo‘lgan yoki mahfiy uslubli bir tomonli bo‘lgan funksiya e’lon qilingan emas.