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

§7.4. Qoldiq haqidagi Xitoy teoremasiga asoslangan
sirni taqsimlash sxemasi.
Sirni taqsimlashining bo’sag’ali sxemasini qurishga zamin bo’ladigan teoremani keltiramiz.
Qoldiq haqidagi Xitoy teoremasi.
m₁,…, m_k – jo’fti-jo’fti bilan tub sonlar bo’lsa, u holda

taqqoslamalar sistemasi quyidagi yagona yechimga ega
x₀ ≡ ,
bu yerda M= , M_i= , .
Qoldiq haqidagi Xitoy teoremasiga asoslangan sirni taqsimlash sxemasi quyidagi tarzda quriladi.
N-umumiy sir bo’lsin.
Sirni taqsimlash bosqichi.
p₁, p₂,…, p_n – turli tub sonlari tanlanadi. U holda i abonentga mos keluvchi sirning qiymati x_i≡N(mod p_i). Bunda p₁, p₂,…, p_n tub sonlari Shunday tanlanishi kerakki, ularning ixtiyoriy k tasini ko’paytmasi _{ } dan katta bo’lishi kerak. Bu shart faqat p_i> da bajariladi.
k–1 ta abonent birgalikda k-chi abonent ishtirokisiz sirni tiklash imkoni mavjud bo’lmasligi uchun p_i << bo’lishi kerak. Demak, < p_i << shart bajarilishi kerak.
Sirni tiklash bosqichi.
Bu bosqichda k ta abonent birgalikda yig’ilib, o’zlaridagi taqqoslamalardan quyidagi taqqoslamalar sistemasini hosil qilishlari mumkin:
.
Taqqoslamalar sistemasi yechilib, N sir aniqlanadi.
1-misol. Sir N=549 bo’lsin. Tub sonlar tanlanadigan oraliqlar aniqlanadi:
, . Demak, 8,2< p_i <<23,4.
U holda, p₁=11, p₂=13, p₃=17 deb tanlash mumkin.
Sirni taqsimlash bosqichi:
x₁= N mod p₁ = 549 mod 11 = 10;
x₂=N mod p₂ = 549 mod 13 = 3;
x₃=N mod p₃ = 549 mod 17 = 5.
P₁ ni ulushi: (x₁=10, p₁=11);
P₂ ni ulushi: (x₂=3, p₂=13);
P₃ ni ulushi: (x₃=5, p₃=17).
Sirni tiklash bosqichi:
P₁, P₂ va P₃ abonentlar quyidagi taqqoslamalar sistemasini tuzishadi va qoldiq haqidagi Xitoy teoremasi asosan bu sistemani yechishadi:
N=10·221·1+3·187·8+5·143·5mod11·13·17= 2210+4488+3575 mod
2431 = 2210+2057+1144 mod 2431 = 549.
Sir tiklandi.
Faraz qilaylik, va abonentlar, abonent ishtirokisiz sirni tiklashmoqchi bo’lsalar, unda ular sirni tiklay oladilarmi? Bu holda ular o’zlaridagi taqqoslamalardan quyidagi taqqoslamalar sistemasini hosil qiladilar:

Bundan
N = 10·13·6+3·11·6 mod11·13 = 780+198 mod 143 = 978 mod 143 = 120 ni hosil qiladilar. Ko’rinib turibdiki, ular sirni tiklay olmadilar.