Feige–Fiat–Shamir identifikatsiya sxemasi
1986 yilda U. Feyge, A. Fiat va A. Shamir taklif qilgan protokol. A tomon B ga o'zining sirini bilishini isbotlaydi, ammo B sir haqida hech qanday ma'lumot olmaydi. Bu — «nol bilimli isbot» (zero-knowledge proof) ning klassik namunasi.
Halqasimon g'or ichida sehrli eshik bor, uni faqat sehrli so'z ochadi. Ali g'orga kirib, chap yoki o'ng yo'lga ketadi. Vali kirishda turib baqiradi: «Chapdan chiq!» Agar Ali so'zni bilsa, qaysi tarafda bo'lmasin, kerakli yo'ldan chiqadi. Bilmasa — 50% ehtimol bilan omadi kelmaydi. 20 marta takrorlansa, firibgarning har safar omadi kelish ehtimoli milliondan bir! Vali Alining so'zni bilishiga ishonch hosil qiladi, lekin so'zning o'zini eshitmaydi.
Tayyorgarlik
n = p·q, p va q — katta tub sonlar, ularni faqat ishonchli markaz biladi. A uchun yopiq kalit s tanlanadi va ochiq kalit v = (s²)⁻¹ mod n e'lon qilinadi (kitobdagi yozuvda: s = √(v⁻¹) mod n). v dan s ni topish — n ni faktorlashga teng kuchli.
Bitta sikl (akkreditatsiya)
b=1 → z = r·s mod nz
b=1: z²·v ≡ y?
Tekshiruv: b = 1 da z²·v = r²·s²·(s²)⁻¹ = r² = y. Har bir siklda aldanish ehtimoli 50%; sikl 10 marta takrorlansa — (1/2)10 ≈ 0,1%.
Umumlashgan sxema
A da k ta sir s₁…sk va ochiq kalitlar v₁…vk bo'ladi. B k ta bit b₁…bk yuboradi, A z = r·∏ sᵢbᵢ mod n javob beradi, B z²·∏ vᵢbᵢ ≡ y ni tekshiradi. Bir siklda aldanish ehtimoli (1/2)k.
Sirni bilmagan firibgar b ni oldindan taxmin qiladi. b = 0 kutsa — oddiy y = r² yuboradi. b = 1 kutsa — z ni tanlab, y = z²·v deb yuboradi. Taxmini to'g'ri bo'lsa o'tadi, noto'g'ri bo'lsa — fosh bo'ladi. Simulyatorda «Firibgar»ni tanlab ko'ring.