Vazirligi mirzo ulug„bek nomidagi

Feige-Fiat-Shamir idеntifikatsiya sxеmasi

Bu sxema 1986 yilda U.Feyge, A.Fiat va A.Shamirlar tomonidan taklif etilgan. Bu sxemada ikkita tomon ishtirok etadi. Tomonlarning har biri n=p*q, p va q lar katta tub sonlarni oldindan bilishi shart, boshqa hech kim p va q larni bilmasliklari kerak. Protokol boshlanishidan oldin quyidagilar hisoblanishi kerak: x²modn=v tenglikdan barcha v lar topiladi. Bunda x natural son bo‗lib, 1 dan n/2 gacha o‗zgaradi. Topilgan v larning n bilan o‗zaro tub bo‗lganlari ajratib olinadi va v^-1modn hisoblanadi. s=sqrt(v^-1)modn tenglik orqali ochiq kalit hisoblanadi va e‘lon qilinadi.

1. 
   A tomon: tasodifiy r < n-1 natural son tanlaydi va hisoblaydi: y=r²modn va y qiymatni B tomonga jo‗natadi.
   
2. 
   B tomon: ixtiyoriy b bit tanlaydi va uni A tomonga jo‗natadi.
   
3. 
   A tomon: B tomon jo‗natgan bit 0 ga teng bo‗lsa, r qiymatni B tomonga jo‗natadi. Agar B tomon jo‗natgan bit 1 ga teng bo‗lsa, z=r*s modn qiymatni B tomonga jo‗natadi.
   
4. 
   B tomon: A tomonga 0 ni jo‗natgan bo‗lsa, r²modn=y tenglikni tekshiradi, aks holda (z²*v) modn=y tenglikni tekshiradi. Tenglik bajarilsa B tomon A tomon ekanligiga ishonch hosil qilguncha
   

shu 4 ta bosqichni bir necha marta takrorlaydi.
Bu 4 ta bosqich protokolning bitta sikli bo‗lib, akkreditatsiya deyiladi. Har bir siklda aldanish ehtimolligi 50% ni tashkil etadi. Sikl 10 marta takrorlansa, aldanish ehtimolligi 0,1% ni tashkil etadi.
Bu sxemani yanada umumiyroq qilib yozish mumkin:

1. 
   A tomon: tasodifiy r < n-1 natural son tanlaydi va hisoblaydi: y=r²modn va y qiymatni B tomonga jo‗natadi.
   
2. 
   B tomon: ixtiyoriy b_i (i=1,..,k) bitlarni tanlaydi va ularni A tomonga jo‗natadi.
   

z = r_∏s mod n
k

3. 
   i
   A tomon: bi

qiymatni B tomonga jo‗natadi.

i=1
k