Ўзбекистон республикаси олий ва ўрта махсус таълим вазирлиги мирзо улуғбек номидаги ўзбекистон миллий университети математика факультети «Математик моделлаштириш ва криптоанализ»

§6.2. FiatShamir protokoli.
Ushbu protokolda isbot qiluvchi P abonent tekshiruvchi V abonentga _{ } sirni bilishini 3 ta qadamga asoslangan t iterasiya yordamida isbotlaydi. Protokol katta son n ning moduli bo’yicha kvadrat ildiz chiqarishning murakkabligiga asoslangan. Shu sababli bu masala n sonini tub ko’paytuvchilarga yoyish masalasi bilan ekvivalent.
Qandaydir T ishonchli markaz 2 ta katta p va q tub sonlarini tanlaydi. N=pq modulni hisoblaydi va uni barcha isbotlovchilarga tarqatadi (yoki e’lon qiladi). Ammo, bunda p va q sonlarini sirligi saqlanib qolinadi.
Har bir isbot qiluvchi P abonent n soniga o’zaro tub bo’lgan sonni quyidagi shart asosida tasodifiy tanlaydi va miqdorni hisoblaydi:
,
.
ni o’zining ochiq kaliti sifatida e’lon qiladi. esa abonentning maxfiy kaliti hisoblanadi.
Protokolda quyida keltirigan 3 ta qadam bir-biriga bog’liq bo’lmagan holda marta amalga oshiriladi. Agar barcha iterasiyalar ijobiy natijaga olib kelsa, u holda V abonent haqiqatdan ham P abonent sirni bilishini isbotini qabul qiladi.
Protokolda amalga oshiriladigan qadamlar:

1. 
   P abonent oraliqdan tasodifiy sonini tanlaydi va V tekshiruvchiga sonini jo’natadi.
   
2. 
   V tekshiruvchi tasodifiy bitni tanlaydi va uni P abonentga jo’natadi.
   
3. 
   P abonent sonini hisoblab, uni V tekshiruvchiga jo’natadi. Bu erda sonini qiymati bitning qiymatiga bog’liq bo’ladi: agar bo’lsa, bo’ladi; agar bo’lsa, bo’ladi.
   

V tekshiruvchi sonini qiymatiga bog’liq holda qaror qabul qiladi: agar yoki o’rinli bo’lsa, V tekshiruvchi ijobiy qaror qabul qiladi.
bitning qiymatiga bog’liq holda yoki shartlardan biri bajarilishini payqash mumkin.
Ushbu protokolni korrektligini quyida keltirilgan mulohazalar bilan asoslash mumkin.
bitdan foydalanish P abonentga nisbatan quyida keltirilgan 2 ta talabni amalga oshirish uchun ishlatilgan:

1. 
   sirni bilishini namoyish qilish;
   
2. 
   yolg’on javob berishini oldini olish maqsadida.
   

O’zini P abonent sifatida tutuvchi raqib ixtiyoriy sonini tanlab, V tekshiruvchiga sonini jo’natish orqali V tekshiruvchini aldashga harakat qilishi mumkin. U holda u bo’lganda to’g’ri javobni tekshiruvchiga jo’natishi mumkin. Ammo, bo’lganda u javob berolmaydi. Bunga javob berish sonidan modul bo’yocha kvadrat ildiz chiqarishni talab qiladi. Buni esa hozirgi kunda amalga oshirishning imkoni yo’q.
sirni biluvchi P abonent 2 ta savolga ham javob berish imkoniyatiga ega. Agar sirni bilmasa eng yaxshi holda u ikkita savoldan bittasiga javob berish mumkin. Shunday qilib, aldash dan katta bo’lmagan ehtimollik bilan bajariladi. ga karrali iterasiyali protokolda aldovni sodir bo’lish ehtimoli miqdordan oshmaydi. Shu sababli ushbu protokolda iterrasiyalar soni ni oraliqdan tanlash tavsiya etiladi.
javob isbot qiluvchi P abonentning siriga bog’liq emas. javobda sir haqida ma’lumot yo’q. Chunki tasodifiy sonini V tekshiruvchi bilmaydi va bilish imkoniyatiga ham ega emas.
1-misol. T ishonchli markaz p va q tub sonlarini va tarzda tanlab, ni e’lon qiladi.
Isbot qiluvchi P abonent n soniga o’zaro tub bo’lgan sirni (ya’ni, maxfiy kalitni) oraliqdan sifatida tanlaydi hamda ochiq kaliti ni hisoblaydi:
.
Protokol quyidagicha amalga oshiriladi:

1. 
   P abonent oraliqdan tasodifiy sonini tanlaydi va V tekshiruvchiga sonini jo’natadi.
   
2. 
   V tekshiruvchi tasodifiy bitni tanlaydi va uni P abonentga jo’natadi.
   
3. 
   P abonent bo’lsa, sonini, bo’lsa,
   

sonini hisoblab, V tekshiruvchiga jo’natadi.
tengsizlik o’rinli ekanligi ko’rinib turibdi. Shu sababli, V tekshiruvchi taqqoslamani tekshirib ko’radi:
.
Bu taqqoslamani o’rinli ekanligi protokolning 1-chi qadamidan ham ko’rinib turibdi. Shu bois, V tekshiruvchi bu iterasiyada ijobiy qaror qabul qiladi. Shu tarzda bir necha iterasiya bajariladi va barcha iterasiyalarning natijalari ijobiy bo’lsa, V tekshiruvchi haqiqatdan ham P abonent sirni bilishini isbotini qabul qiladi.