Mavzu: dastur ketma-ketlikning tasodifiyligini tekshirish uchun nist statistik testlar to'plami

8-amaliy ish
Mavzu: dastur ketma-ketlikning tasodifiyligini tekshirish uchun NIST statistik testlar to'plami
Ishning maqsadi: ketma-ketlikni tasodifiy tekshirishda NIST statistik testlarini yig'ish bo'yicha bilim va ko'nikmalarni egallash.
Nazariy qism
Kriptografik dasturlarda ishlatiladigan tasodifiy va psevdo-tasodifiy sonlar generatorlarini (rng va GPSCH) sinovdan o'tkazish ham amaliy, ham nazariy jihatdan dolzarb vazifadir. Ushbu sohadagi sezilarli yutuqlarga qaramay, ishlab chiquvchilar rng (GPSCH) tomonidan ishlab chiqarilgan ketma-ketliklarning tasodifiylik darajasini etarlicha aniq tekshirishga imkon beradigan va ishlab chiquvchilarga generatorning "sifati" to'g'risida qaror qabul qilish uchun etarli ma'lumot beradigan maqbul metrikani taqdim etadigan qulay vositalarga muhtoj.
Bugungi kunda rng (GPSCH) ning juda ko'p sonli turlari ishlab chiqilgan. Biroq, ularning statistik xususiyatlarini namoyish qilish uchun statistik testlarga turli xil yondashuvlar qo'llanilgan. Ko'pincha, generatorni ishlab chiquvchining o'zi sinov to'plami va texnikasini taklif qildi. Shunday qilib, turli xil generatorlarni yagona pozitsiyalardan xolisona taqqoslash mumkin emasligi bilan tavsiflanadigan vaziyat yuzaga keldi. Ushbu qoidadan chiqish yo'li GPSCH samaradorligining zarur ko'rsatkichlarini hisoblash va hosil bo'lgan ketma-ketliklarning tasodifiyligi to'g'risida qaror qabul qilishning yagona usuli bilan birlashtirilgan statistik testlarning ba'zi standart to'plamidan foydalanishdir.
NIST sts to'plami rng yoki GPSCH tomonidan ishlab chiqarilgan ixtiyoriy uzunlikdagi ikkilik ketma-ketliklarning tasodifiyligi gipotezasini sinab ko'rish uchun mo'ljallangan 16 ta statistik testni o'z ichiga oladi. Barcha testlar turli xil tasodifiy nuqsonlarni aniqlashga qaratilgan. Sinovning asosiy printsipi NR 0r nol gipotezasini sinab ko'rishdir, ya'ni sinovdan o'tgan ketma-ketlik tasodifiy. HR arning muqobil gipotezasi-bu sinovdan o'tgan ketma-ketlik tasodifiy emasligi haqidagi gipoteza. Har bir testni qo'llash natijalariga ko'ra, nol gipoteza qabul qilinadi yoki rad etiladi. Berilgan nollar va birliklarning ketma-ketligi tasodifiy bo'ladimi yoki yo'qmi degan qaror barcha testlarning natijalari yig'indisidan kelib chiqadi. Alohida ikkilik ketma-ketlikni sinash tartibi s quyidagicha.
1. Nol gipoteza ilgari surildi H0-berilgan ikkilik ketma-ketlik degan taxmin s tasodifiy.
2. S ketma-ketligi bo'yicha C(s) test statistikasi hisoblanadi.
3. Maxsus funktsiya va test statistikasi yordamida ehtimollik qiymati hisoblanadi R \ u003d f (c(S) ), R [0, 1].
4. Ehtimollik qiymati R ahamiyatlilik darajasi bilan taqqoslanadi,   [0,001, 0,01]. Agar p bo'lsa, u holda h0 gipotezasi qabul qilinadi. Aks holda, muqobil gipoteza qabul qilinadi.
Yuqorida aytib o'tilganidek, paket 16 ta statistik testni o'z ichiga oladi. Ammo, aslida, kirish parametrlariga qarab, ehtimollikning 189 qiymati hisoblanadi R, bu individual testlarning natijasi sifatida qaralishi mumkin. 8.1-jadvalda p ehtimolligining hisoblangan qiymatlari soni, test statistikasining jismoniy ma'nosi va test aniqlashga qaratilgan nuqson ko'rsatilgan barcha testlarning qisqacha ma'lumotlari keltirilgan (diagrammalarda ishlatiladigan testning seriya raqami qavs ichida berilgan).
Jadval 8.1
№ Statistik test ehtimollik qiymatlari soni R test statistikasi c(S) aniqlangan nuqson
1 chastota (monobit) testi 1 (1) ketma-ketlik elementlari qiymatlarining normallashtirilgan mutlaq yig'indisi ketma-ketlikda juda ko'p nol yoki birlikdir
2 birlik ichidagi chastota testi 1 (2) birlik ichidagi kuzatilgan birliklar sonini nazariy jihatdan kutilgan bilan moslashtirish o'lchovi. Blokdagi birliklarning paydo bo'lish chastotasining ideal qiymatdan lokalizatsiya qilingan og'ishlari½.
3 to'plangan summalarni tekshirish 2 (3-4) ketma-ketlik elementlarining to'plangan yig'indisi qiymatining boshlang'ich mos yozuvlar nuqtasidan maksimal og'ishi (0-nuqta) ikkilik ketma-ketlikning boshida yoki oxirida birliklar yoki nollarning katta qiymati.
4 seriyalarni tekshirish 1 (5) ketma-ketlikning butun uzunligi bo'ylab seriyalarning umumiy soni. Ikkilik ketma-ketlikning boshida yoki oxirida katta birlik yoki nol qiymati.
5 1 (6) blokdagi seriyaning maksimal uzunligini tekshirish birlik seriyasining maksimal uzunligining kuzatilgan qiymatini nazariy jihatdan kutilgan qiymatga moslashtirish o'lchovi. Birliklar seriyasining maksimal uzunliklarini taqsimlashning nazariy qonunidan og'ish.
6 ikkilik matritsaning darajasini tekshirish 1 (7) har xil tartibdagi darajalarning kuzatilgan qiymatini nazariy jihatdan kutilgan darajaga moslashtirish o'lchovi. Matritsa darajalari qiymatlarini taqsimlashning empirik qonunining nazariydan og'ishi, bu ketma-ketlikdagi belgilarning bog'liqligini ko'rsatadi.
7 ikkilik matritsa darajasini tekshirish 1 (8) kuzatilgan va kutilgan chastota komponentlari soni o'rtasidagi normallashtirilgan farq, bu 95% dan oshadi.chegara darajasi. Ikkilik ketma-ketlikda davriy tarkibiy qismlarni (tendentsiyalarni) aniqlash.
8 bir-birining ustiga chiqadigan naqshlarni tekshirish 1 (9) nazariy qiymatga ega ketma-ketlikda bir-birining ustiga chiqadigan naqshlarning kuzatilgan sonini moslashtirish o'lchovi. Ketma-ketlikdagi birliklarning ko'p sonli Mbit seriyalari.
9 Universal Maurer testi 1 (10) l-bitli naqshlar orasidagi masofa logarifmining yig'indisi. Ketma-ketlikning siqilishi.
10 Universal Maurer testi 1 (11) manba entropiyasining kuzatilgan qiymatini tasodifiy manba uchun nazariy jihatdan kutilgan qiymatga moslashtirish o'lchovi. M-bitli so'zlarning ketma-ketlikda notekis taqsimlanishi (manba xususiyatlarining muntazamligi).
11 tasodifiy og'ishlarni tekshirish 8 (12-19) tsikl ichidagi ma'lum bir holatga tasodifiy yurish paytida kuzatilgan tashriflar sonini nazariy jihatdan kutilgan bilan muvofiqlashtirish o'lchovi. Tasodifiy yurish paytida tashriflarni ma'lum bir holatga taqsimlashning nazariy qonunidan chetga chiqish.
12 tasodifiy og'ishlarni tekshirish (variant) 18 (20-37) tasodifiy yurish paytida ma'lum bir holatga tashriflarning umumiy soni belgilangan blok uchun ekvivalent LRR ning belgilangan uzunligi nazariy jihatdan kutilgan holda paydo bo'lishidan iborat kuzatilgan hodisalar sonini muvofiqlashtirish o'lchovi.
13 ketma-ket sinov 2 (38-39) Mbit shablonlarining barcha duch kelgan variantlarining kuzatilgan sonini nazariy jihatdan kutilgan bilan muvofiqlashtirish o'lchovi. M-bitli so'zlarning ketma-ketlikda notekis taqsimlanishi.
14 ketma-ket sinov 1 (40) Mbit shablonlarining barcha duch kelgan variantlarining kuzatilgan sonini nazariy jihatdan kutilgan bilan muvofiqlashtirish o'lchovi. Tasodifiy ketma-ketlik uchun kutilgan siqishni nisbati bilan taqqoslaganda sinovdan o'tgan ketma-ketlikning katta siqilish darajasi.
15 bir-biriga mos kelmaydigan naqshlarni tekshirish 148 (41-188) davriy bo'lmagan naqshlarning kuzatilgan sonini nazariy ahamiyatga ega ketma-ketlikda muvofiqlashtirish o'lchovi. Ketma-ketlikda berilgan davriy bo'lmagan naqshlarning ko'pligi.
16 chiziqli murakkablikni tekshirish 1 (189) nazariy jihatdan kutilgan birlik uchun ekvivalent LRR ning belgilangan uzunligi paydo bo'lishidan iborat kuzatilgan hodisalar sonini moslashtirish o'lchovi. Ruxsat etilgan uzunlikdagi ketma-ketlik uchun ekvivalent LRR uzunliklarining empirik taqsimotining tasodifiy ketma-ketlik uchun nazariy taqsimot qonunidan og'ishi, bu sinovdan o'tgan ketma-ketlikning etarli darajada murakkabligini ko'rsatadi.

Ko'rib chiqilayotgan statistik testlar to'plami quyidagi muammolarni hal qilish uchun ishlatilishi mumkin: – "yomon" ikkilik ketma-ketlikni tashkil etuvchi rng (GPSCH) ni aniqlash; - yangi rng (GPSCH) ni ishlab chiqish; - rng (GPSCH) ni amalga oshirishning to'g'riligini tekshirish; - standartlarda tavsiflangan generatorlarni o'rganish; - haqiqiy ishlatilgan rng (GPSCH) ning tasodifiylik darajasini o'rganish). Ushbu muammolarni hal qilishda generatorlarni sinovdan o'tkazishning quyidagi usuli qo'llaniladi.

1. Ko'pgina apparat yoki dasturiy ta'minot generatorlaridan g generatori tanlanadi, uni baholash va tasodifiy ikkilik ketma-ketliklarni shakllantirish to'g'risida qaror qabul qilish kerak. Jeneratör ikkilik ketma-ketlikni hosil qilishi kerak s ={s1,s2, ..., sn}, si qiymat {0,1}, ixtiyoriy uzunlik n.
2. Ruxsat etilgan qiymat uchun n ning to'plamini hosil qiladi m ikkilik ketma-ketliklar:
S1 ={s1, s2, …, sn};
S2 ={s1, s2, …, sn};
………………….
Sm ={s1, s2, …, sn}.
Shunday qilib, sinov uchun n \ u003d m dan n gacha bo'lgan namunani yaratish kerak.
3. Har bir ketma-ketlik NIST sts to'plami yordamida sinovdan o'tkaziladi. Natijada quyidagi turdagi generatorning statistik portreti hosil bo'ladi
Xavfsizlik masalalari
1. Taqsimotni tasodifiy tekshirish uchun "Xi-kvadrat" mezonining tasnifi.
2. Tasodifiylik darajasini aniqlaydigan test turlari 3. Psevdo tasodifiy ketma-ketlik generatorlarining tasnifi.