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

§7.2. Sirni taqsimlashning bo’sag’ali sxemalari.
Sirni taqsimlashning (n,k) (k≤n) bo’sag’ali sxemalari deb Shunday sxemaga aytiladiki, bunda sir n ta ishtirokchi o’rtasida bo’linadi va sirga ruxsat etilgan guruh sifatida abonentlar soni k dan kam bo’lmagan ixtiyoriy guruh qatnashishi mumkin.
Blekli sxemasi. Ma’lumki k noma’lumli tub son moduli bo’yicha hosil qilingan chiziqli erkli k taqqoslamalar yagona yechimga ega bo’ladi. 1979 yilda yaratilgan Blekli sxemasi Shunga asoslangan. n ta abonentlar o’rtasida m sir Shunday taqsimlanadiki, abonontlar soni k dan kam bo’lmagan ixtiyoriy guruh sirni bilishga ruxsat etilishi mumkin.
Blekli sxemasida quyidagi parametrlardan foydalaniladi:
p - katta tub son. p soni ushbu sxema bo’yicha tarqatiladigan ixtiyoriy sirdan katta bo’lishi kerak (p>m). U holda mZ_p.
n – sir ulushlari soni.
k – sirni bilishga ruxsat etilgan guruhning minimal o’lchovi.
Tayyorgarlik bosqichi.
Tasodifiy ravishda sirni tarqatuvchi x₂^*, x₃^*, … , x_k^*  Z_p sonlarini tanlaydi, ya’ni Q = (m, x₂^*, x₃^*, … , x_k^*) sir nuqtasi hosil qilinadi.
Sirni taqsimlash bosqichi.
Sirni taqsimlovchi i (i=1,…,n) ishtirokchilar uchun _{ } guruhda tasodifiy tekis taqsimlangan sonlarni tanlaydi va b_i=a_1i m + a_2ix₂^*+…+a_kix_k^* modp ni hisoblaydi. Shundan so’ng tarqatuvchi P_i abonentlarga
a_1ix₁+a_2ix₂+…+a_kix_k ≡ b_i (mod p)
taqqoslamalarni x₁, x₂, …, x_k noma’lumlari bilan birgalikda koeffisientlarini jo’natadi. Bunda tarqatuvchi Shunga e’tibor berishi lozimki, ixtiyoriy k taqqoslamalar chiziqli erkli bo’lishlari lozim.
Sirni tiklash bosqichi.
Bu bosqichda k abonentlar birgalikda yig’ilib, o’zlaridagi taqqoslamalardan quyidagi taqqoslamalar sistemasini hosil qilishlari mumkin:
a₁₁x₁+ a₂₁x₂+…+a_k1x_k≡b₁(mod p)
a₁₂x₁+ a₂₂x₂+…+a_k2x_k≡b₂(mod p)
………………………….
a_1kx₁+ a_2kx₂+…+a_kkx_k≡b_k(mod p).
Ushbu taqqoslamalar sistemasini yechib, Q nuqtani topishlari mumkin, ushbu nuqtaning birinchi koordinatasi m sir bo’ladi.
Eslatma:

1. 
   p etarlicha katta tub son bo’lsa, taqqoslamalar koeffisientlarini tasodifiy tanlanishi e’tiborga olinsa, taqqoslamalarni chiziqli erkli bo’lish shartini hisobga olmaslik mumkin, chunki bu shartning buzilish ehtimoli kam.
   
2. 
   Agar abonentlar birlashib sirni tiklamoqchi bo’lsa, bu sirni tiklashning iloji yo’q, chunki ular tomonidan tuzilgan taqqoslamalar sistemasi kerakli yechimni emas, balki k o’lchovli fazodagi t - tartibli gipertekislikda yotuvchi nuqtalar to’plamini beradi. Bu to’plamda qaysi biri sirli nuqta ekanligini topish amalda mumkin emas. Ya’ni, ushbu holda sir sifatida Z_p dan olingan ixtiyoriy qiymat teng ehtimollik bilan sir bo’lishi mumkin.
   

Misol. - sir, - modul, Q=(m=5, x₂^*=2, x₃^*=1) – sir nuqtasi bo’lsin.
Sirni taqsimlash bosqichi.
Abonentlar uchun _{ } guruhda tasodifiy tekis taqsimlangan sonlari tanlanadi. Bu sonlar va sir nuqtasi koordinatalari asosida soni (bu son va sonlari birgalikda i abonentning sur ulushini tashkil qiladi) quyidagicha hisoblanadi:
uchun: a₁₁=1, a₂₁=1, a₃₁=1. U holda b₁=1·5+1·2+1·1 mod 11=8.
uchun: a₁₂=3, a₂₂=2, a₃₂=7. U holda b₂=3·5+2·2+7·1 mod 11=4.
uchun: a₁₃=8, a₂₃=1, a₃₃=10. U holda b₃=8·5+1·2+10·1 mod 11=8.
Sirni tiklash bosqichi.
Bu bosqichda abonentlar taqqoslamalaridan quyidagi taqqoslamalar sistemasini hosil qilish mumkin:
.
Ushbu taqqoslamalar sistemasining matrisasi kengaytirilgan ko’rinishga keltiriladi va bu sistema Gauss usulida to’plamda yechiladi:
.
Taqqoslamalar sistemasini yechib, x₁=5, x₂=2, x₃=1 ni topamiz. Birinchi noma’lumning qiymati aynan m=5 sirni ifodalaydi.
Faraz qilaylik, va abonentlar, abonent ishtirokisiz sirni tiklashmoqchi bo’lsalar, unda ular sirni tiklay oladilarmi? Bu holda ular shtirokidagi taqqoslamalar sistemasining matrisasi quyidagi kengaytirilgan ko’rinishda bo’ladi:

Bu taqqoslamalar sistemasining yechimi
m=x₁=10—x₃ mod 11,
x₂=9—7x₃ mod 11.
Bu holda m - sir 0 va 10 oralig’dagi ixtiyoriy qiymatni qabul qilishi mumkin. Shuday qilib, va abonentlar birgalikda ( abonent ishtirokisiz) sirni tiklay olmadilar.