Texnologiyalari universiteti kriptografiyaning matematik asoslari

5.7.2. Taqsimotni tasodifiylikka tekshirishning
“Xi-kvadrat” mezoni
Biror o‘tkazilayotgan tajriba natijalarining barcha mumkin bo‘lgan
holatlari y₁, y₂ ,..., y_k , dan iborat va ularning soni k ga teng bo‘lib, bu tajriba birbiriga bog‘liqsiz holda n marta o‘tkazilsin. Shunda, y₁, y₂ ,..., y_k -holatlarni, ularning n marta o‘tkazilgan tajribada, bir xil sonda takrorlanishidan (tekis taqsimotdan yoki bir xil chastotaga ega bo‘lishdan) qanchalik chetlanganligini baholash masalasining yechilishi ko‘rib chiqiladi. Buning uchun quyidagicha belgilashlar kiritiladi: p_s - tajriba natijasi y_s bo‘lishining ehtimollik qiymati;
Y_s - tajriba natijalarining y_s holatga tegishlilari (tenglari) soni.

21. 
    holda, bu belgilashlarga nisbatan “Xi-kvadarat” deb ataluvchi taqsimot mezoni ushbu
    
22. 
     s^k1 Y_s npnps _s ² ,
    

formula orqali aniqlanadi.
Agar tajriba n martadan bir necha marta o‘tkazilganda, har doim y₁, y₂ ,..., y_k - holatlar teng Y_i martadan takrorlansa (tekis taqsimlangan yoki bir xil
chastotali bo‘lsa), ya’ni Y₁  Y₂ ...  Y_k bo‘lsa, u holda p₁  p₂  ...  p_k  ¹ , deb k
xulosa qilinadi va
2 2
 n n n
V _sk1 Ys  k =k k nk = 0
n s 1
k k
tenglik o‘rinli bo‘ladi. Bunday jarayonning ilmiy-tadqiqot uchun qizig‘i yo‘q. Ammo amaldagi aksariyat jarayonlarda bunday holat kuzatilmaydi, ya’ni biror
tajriba bir-biriga bog‘liqsiz ravishda n marta o‘tkaziliganda: Y₁  Y₂ ... _ Y_k  ⁿ holat k
kuzatilmaydi. Shuning uchun y₁, y₂ ,..., y_k - holatlarni ro‘y berish ehtimolliklari bir
xil p₁  p₂  ... _ p_k  ¹ bo‘lib, tajriba bir-biriga bog‘liq bo‘lmagan ravishda n k
marta o‘tkazilganda, bu holatlarning ro‘y berishi soni mos ravishda Y₁, Y₂ ,...,Y_k bo‘lsa, u holda ushbu
2
 n
Y
V k  s nk = kn sk1 Ys  kn 2
s 1 k
formula Y₁  Y₂ ...  Y_k  ⁿ bo‘lgan teng taqsimotdan Y₁, Y₂ ,...,Y_k -teng bo‘lmagan k
t aqsimotni o‘rtacha kvadratik chetlanishini ifodalaydi. Bu oxirgi formuladagi ^Y  ^{n } - ifoda biror o‘zgarmas son bilan chegaralangan, ya’ni Y_s  ⁿ  C  const .
_s
 k  k
Shuning uchun
2
 n
Y
k s  
V   nk = kn sk1 Ys  kn 2  kn sk1C2 = kCn2  0, agar nbo‘lsa.
s 1 k
Bu oxirgi formuladan, biror generator orqali hosil qilingan psevdotasodifiy ketma-ketlikning davri yetarli uzun bo‘lib, barcha mumkin bo‘lgan bitlar, baytlar va qism bloklarining taqsimoti deyarli tekis (teng taqsimlangan) bo‘lsa, u holda
“Xi-kvadarat” taqsimot mezonining bu ketma-ketlikka nisbatan qiymati nolga yaqin bo‘lib, uning tasodifiylik darajasi yuqori hisoblanadi.
Quyida standart DES, GOST 28147-89, AES-FIPS-197,
O‘z DSt 1106:2009 va boshqa simmetrik shifrlash algoritmlari uchun maxfiy kalitni tasodifiy qilib generasiya qilishning Xi-kvadrat taqsimoti orqali qanday amalga oshirilishini ko‘rib o‘tamiz.
Berilgan kalit bloki bo‘yicha quyidagi jadvalni tuzib olamiz:
Qiymat (s) : 0 1 ;
Ehtimollik ( p_s ) : ;
Kuzatilayotgan son (Y_s ) : N ₀ N₁ , bu yerda N ₀ va N₁ mos ravishda kalit blokida ishtirok etuvchi nollar va birlar,
N₀  N₁  n , orqali kalit uzunligini belgilaydi, masalan n  256;
Kutilayotgan son (np_s ) : ^{n n} ;
2 2
Xi-kvadrat taqsimoti formulasi bo‘yicha [74]:
k1 Y^s  np^s 2 hisoblanadi.
V ^{ }s0 _nps
Ushbu qaralayotgan holatda:
1 k  2; s  0,1; p₀  p₁  ;Y₀  N₀;Y₁  N₁; n  256 ; u holda quyidagicha kattalikka ega 2
bo‘lamiz:
N0 128²  N1 128² .
V 
128
Bu kattalikni hisoblash uchun bizga Xi-kvadrat taqsimotining kritik nuqtalari jadvali deb ataluvchi jadval kerak bo‘ladi (5.2- jadval).
5.2- jadval