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

§7.6. Taqsimlangan sirni tekshirish sxemasi.
Oldingi o’tilgan mavzularda sirni taqsimlash sxemalarida sirni tarqatish bosqichida diler ishonchli, sirni tiklash bosqichida esa ishtirokchilar (sirni bilishga haqli odamlar) bir biriga raqib bo’lmagan, bir-biriga nisbatan o’zaro ishonchga ega bo’lgan ishtirokchilar sifatida qaralgan edi.
Endi protokolda ishtirok etuvchilarning ayrimlari bir biriga nisbatan raqib bo’lishi mumkin holatda sirni bo’olishish masalasini ko’rib chiqamiz.
Agar diler firibgar bo’lsa ushbu holda protokolda ishtirok etuvchi halol ishtirokchilar sirni taqsimlashni boshqa bir halol dilerga topshirib vaziyatdan chiqishlari mumkin.
Sirni taqsimlashni tekshirish mumkin bo’lgan sxemasi g’oyasi protokolda ishtirok etuvchi g’araz niyatli ishtirokchilarning ayyorona harakatidan halol ishtirokchilarni himoyalashdir. Ushbu g’oya quyidagilardan iborat.
Sirni taqsimlash bosqichida diler sirni shifrlab, e’lon qiladi. Bunda hech kim sirni o’zicha tiklolmaydi. Ammo, taqsimlangan sirni tekshirish sxemasi asosida har bir abonent yoki ishtirikchi sirning o’zidagi ulushidan foydalanib, haqiqatdan ham ushbu ulush sirdan olinganligini tekshirib ko’rishlari mumkin.
Agar ishtirokchilardan ayrimlari buzg’unchi bo’lsalar, u holda bu g’irrom ishtirokchilar o’zlaridagi sirni ulushlarini o’rniga boshqa qiymatlarni jo’natib, sirni tiklashga halaqit qilishlari mumkin. Protokoldan esa umumiy soni t dan kam bo’lmagan halol ishtorokchilar hamma vaqt m sirning qiymatini to’g’ri tiklashlari talab etiladi.
Diskret logarifmlashga asoslangan Shamir sxemasini ko’rib chiqamiz. Bu sxemada sir ulushlarini tarqatuvchi diler koeffisientlari tasodifiy bo’lgan
S(x)=s₀+s₁x+…+s_t-1x^t-1
ko’hadni quradi. Bu yerda s₀ –sir. Bu ko’hadga tegishli bo’lgan S(j) nuqtalarni sirni ulushi sifatida diler ishtirokchilarga tarqatadi.
Diler tomonidan firibgarlkni yo’qotish maqsadida, sir ulushlarini tarqatish bosqichidan oldin diler
, ,
hisoblashlarni amalga oshirishi talab etiladi. Bu yerda g – Z_p^* multiplikativ gruppa elementi. Bu hisoblashlardan so’ng diler ( ) parametrlarni e’lon qiladi va P_j ishtirokchiga unga tegishli S(j) sir ulushini jo’natadi. Bu sir ulushini qabul qilgan P_j ishtirokchi
*
taqqoslamani tekshirib, unga tegishli S(j) miqdor sir ulushi ekanligiga ishonch hosil qiladi. Haqiqatan ham

taqqoslama o’rinli.
Boshqa tomondan e’lon qilingan r_i ( ) prametrlardan g’irrom ishtirokchilar s_i ( ) koeffisientlar qiymatlarini hisoblashlarini imkoni yo’q. Bu hisoblashlar diskret logarifmlashga asoslanganligi sababli yetarlicha katta p tub sonlari uchun ular murakkab hisoblanadi. Hozirgi kunda ularni hisoblashni samarali yo’llari mavjud emas.
G’irrom ishtirokchilarning firibgarligidan qutilish uchun quyidagi tarzda ishlash lozim bo’ladi.
P_i (abonent) - sirni tiklashni xohlovchi halol abonent bo’lsin u boshqa abonentlarga sirni tiklash uchun so’rovnoma jo’natadi. Ushbu abonentlarning har biri P_i abonentga o’zlaridagi S(j) (j≠i) ulushlarini jo’natadi. Bu ulushlarni olganidan so’ng, P_i abonent (*) taqqoslama bajarilishini tekshirib ko’radi. Bu tekshiruvdan o’tmagan sir ulushlari usbu protokoldan chiqarib tashlanadi. Agar halol abonentlar soni t dan kam bo’lmasa, P_i (abonent) ushbu bobning oldingi mavzularida keltilgan sirni tiklash bosqichlaridan foydalanib, sirni tiklashi mumkin.
1-misol. Diler ko’hadni koeffisientlarini tasodifiy ravishda quyidagicha tanlaydi:
s₀=10, s₁=13, s₂=20.
U holda ko’had
S(x)=10+13x+20x²
ko’rinishda bo’ladi. Bu yerda s₀=10 – sir. Z_p^* multiplikativ gruppa elementini g=19 va modulni p=23 tarzda tanlash mumkin. Endi diler , parametrlar qiymatlarini hisoblaydi:
,
,
.
Bu hisoblashlardan so’ng diler ( ) parametrlarni e’lon qiladi.
Sir ulushlarini taqsimlash bosqichi. Diler sir ulushlarini oldingi bosqichda qurilgan ko’phaddan foydalanib, hisoblaydi:
,
,
.
Diler P_j ishtirokchilarga tegishli ushbu S(j) sir ulushini jo’natadi.
Taqsimlangan sir ulushlarini teksirish bosqichi.
Masalan, P₁ ishtirokchi sirni ulushlarini tekshirish uchun qolgan P₂ va P₃ ishtirokchilarga o’zlaridagi sir ulushlarini jo’natishlarini so’rab, so’rovnoma jo’natadi. Sir ulushlarini qabul qilgan P₁ ishtirokchi (*) taqqoslamadan foydalanib,

hisoblashlarni bajaradi. Unga tegishli S(1) miqdor haqiqatan ham sir ulushi ekanligini tekshirib ko’radi:
,
.
P₁ ishtirokchi natijaga ega bo’ladi. Demak, g’irromlik yo’q.