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

§7.3. Lagranj interpolyasion ko’phadiga asoslangan
Shamir sxemasi.
Shamir sxemasi k-1 tartibli interpolyasion ko’phad qurish uchun k nuqtadan foydalanishga asoslangan. Bu yerda ham Blekli sxemasi parametrlaridan 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:
Diler Z_p to’plamdan s₁, s₂, … , s_k-1 sonlarni tasodifiy tanlaydi, ulardan foydalanib
S(x) = m+s₁x+s₂x²+ … +s_k-1x^k-1 mod p
maxfiy polinomni quradi.
Taqsimlash bosqichi:
Diler guruhdagi har bir abonentga tegishli sir ulushlari ni jo’natadi.
Sirni tiklash bosqichi:
Sirni bilishga haqli bo’lgan i₁, i₂, … , i_k nomerli k ta ishtirokchi o’zlarining sir ulushlarini birlashtiradilar: (i₁,S(i₁)), (i₂,S(i₂)), …, (i_k,S(i_k)). Ular asosida k—1 tartibli Lagranj interpolyasion ko’phadi quyidagicha quriladi:
S(x)= .
Sir m=S(0) sifatida aniqlanadi.
Misol. - sir, - modul bo’lsin.
Tayyorgarlik bosqichi:
Diler s₁=13, s₂=6 koeffisientlarni tanlaydi. U holda maxfiy polinom
S(x)=18+13x+6x²
ko’rinishda bo’ladi.
Sirni taqsimlash bosqichi.
Abonentlarni ulushlarini tashkil etuvchilari quyidagicha bo’ladi:
P₁: S(1)=18+13·1+6·1 mod 31=37 mod 31 = 6;
P₂: S(2)=18+13·2+6·4 mod 31=68 mod 31 = 6;
P₃: S(3)=18+13·3+6·9 mod 31=111 mod 31 =18.
Sirni tiklash bosqichi:
Abonentlarning sir ulushlarini birlashtirib, Lagranj interpolyasion ko’phadini quyidagicha qurish mumkin:
S(x)= mod 31 =
=3(x²-5x+6)-6(x²-4x+3)+9(x²-3x+2)mod31=18-18x+6x²mod31=
=18+13x+6x² mod 31.
Bundan ko’rinadiki, m=S(0)=18. Demak, sir tiklandi.