Referat topshirdi: Atajonov Muzaffar Qabul qildi: prof G'. Jo'rayev Toshkent 2022-yil

O'ZBEKISTON RESPUBLIKASI OLIY VA O'RTA MAXSUS TA'LIM VAZIRLIGI

MIRZO ULUG'BEK NOMIDAGI O'ZBEKISTON MILLIY UNIVERSITETI

Amaliy matematika va intellektual texnologiya fakulteti “Kriptografiya va kriptoanaliz” yo'nalishi
“Amaliy kriptografiya” fanidan tayyorlagan


REFERAT

Topshirdi: Atajonov Muzaffar
Qabul qildi: prof G'.Jo'rayev


Toshkent 2022-yil.
Mavzu: Psevdotasodifiy sonlar va tasodifiy sonlar generatorlari.
Reja:

1. 
   Psevdor tasodifiy raqamlar generatori.
   
2. 
   Chiziqli takrorlanishlarga asoslangan generatorlar.
   
3. 
   BSI baholash mezonlari.
   

4. 
   

Psevdor tasodifiy raqamlar generatori
Soxta tasodifiy sonlar generatori (PRNG), shuningdek, deterministik tasodifiy bit generatori (DRBG) sifatida ham tanilgan bo’lin tasodifiy sonlar ketma-ketliklarining xususiyatlariga yaqin bo'lgan raqamlar ketma-ketligini yaratish uchun algoritmdir. PRNG tomonidan yaratilgan ketma-ketlik haqiqatdan ham tasodifiy emas, chunki u PRNG urug'i deb ataladigan boshlang'ich qiymat bilan to'liq aniqlanadi (bu haqiqatan ham tasodifiy qiymatlarni o'z ichiga olishi mumkin). Haqiqiy tasodifiyga yaqinroq bo'lgan ketma-ketliklar apparat tasodifiy sonlar generatorlari yordamida yaratilishi mumkin bo'lsa-da, psevdor tasodifiy sonlar generatorlari raqamlarni yaratish tezligi va takrorlanishi uchun amalda muhim ahamiyatga ega. PRNG'lar simulyatsiyalar (masalan, Monte-Karlo usuli uchun), elektron o'yinlar (masalan, protsessual ishlab chiqarish uchun) va kriptografiya kabi ilovalarda markaziy hisoblanadi. Kriptografik ilovalar chiqishni oldingi natijalardan oldindan aytib bo'lmasligini talab qiladi va oddiyroq PRNGlarning chiziqliligini meros qilib olmaydigan yanada murakkab algoritmlarga ehtiyoj bor . Yaxshi statistik xususiyatlar PRNG chiqishi uchun markaziy talabdir. Umuman olganda, PRNG mo'ljallangan foydalanishga mos keladigan tasodifiyga yaqin raqamlarni hosil qilishiga ishonch hosil qilish uchun ehtiyotkorlik bilan matematik tahlil talab qilinadi. Jon fon Neyman PRNG ning haqiqiy tasodifiy generator sifatida noto'g'ri talqin qilinishi haqida ogohlantirdi va "Tasodifiy raqamlarni ishlab chiqarishning arifmetik usullarini hisobga olgan har bir kishi, albatta, gunoh holatidadir" deb hazil qildi .
Potentsial muammolar
Amalda, ko'plab keng tarqalgan PRNG-larning chiqishi statistik naqshlarni aniqlash testlarida muvaffaqiyatsizlikka olib keladigan artefaktlarni namoyish etadi. Bularga quyidagilar kiradi:

• 
  Ba'zi urug'lik holatlari uchun kutilganidan qisqaroq muddatlar (bunday urug'lik holatlari bu nuqtai nazardan "zaif" deb nomlanishi mumkin);
  
• 
  Ko'p miqdorda ishlab chiqarilgan raqamlar uchun taqsimotning bir xilligi yo'qligi;
  
• 
  Ketma-ket qiymatlarning korrelyatsiyasi;
  
• 
  Chiqish ketma-ketligining yomon o'lchovli taqsimlanishi;
  
• 
  Muayyan qiymatlar paydo bo'ladigan joy orasidagi masofalar tasodifiy ketma-ketlik taqsimotidagidan farqli ravishda taqsimlanadi.
  

Noto'g'ri PRNGlar tomonidan namoyon bo'ladigan nuqsonlar sezilmaydigan (va noma'lum) dan juda aniqgacha . Masalan, asosiy kompyuterlarda o'nlab yillar davomida qo'llanilgan RANDU tasodifiy sonlar algoritmi. Bu jiddiy kamchiliklarga ega edi, lekin uning nomutanosibligi juda uzoq vaqt davomida aniqlanmadi.
Ko'pgina sohalarda 21-asrgacha tasodifiy tanlovga yoki Monte-Karlo simulyatsiyalariga yoki boshqa yo'llar bilan PRNGlarga tayangan tadqiqot ishlari sifatsiz PRNG'lardan foydalanish natijasida idealdan ancha kam ishonchli edi. Hatto bugungi kunda ham baʼzan ehtiyotkorlik talab etiladi, buni Xalqaro Statistik fanlar ensiklopediyasida (2010) quyidagi ogohlantirish tasvirlangan.
Yo'q qilinishi kerak bo'lgan keng tarqalgan ishlatiladigan generatorlar ro'yxati [yaxshi generatorlar ro'yxatidan] ancha uzun. Dasturiy ta'minot ishlab chiqaruvchilariga ko'r-ko'rona ishonmang. Sevimli dasturingizning standart RNG-ni tekshiring va agar kerak bo'lsa, uni almashtirishga tayyor bo'ling. Bu oxirgi tavsiya oxirgi 40 yil ichida qayta -qayta qilingan. Ehtimol, ajablanarlisi shundaki, u 40 yil oldin bo'lgani kabi bugungi kunda ham dolzarb bo'lib qolmoqda.
Misol tariqasida keng tarqalgan Java dasturlash tilini ko'rib chiqamiz. 2017 yil holatiga ko'ra, Java hali ham PRNG uchun past sifatli chiziqli kongruensial generatorga (LCG) tayanadi - quyida ko'rib chiqing.
1998 yilda nashr etilgan Mersenne Twister (quyida muhokama qilinadi) katta muammolarning oldini olish va hali ham tez ishlaydigan taniqli PRNG edi. Hisoblash va statistik ko'rsatkichlar nuqtai nazaridan boshqa yuqori sifatli PRNG'lar bundan oldin va keyin ishlab chiqilgan . sana; Bularni psevdor tasodifiy sonlar generatorlari ro'yxatida aniqlash mumkin.
Chiziqli takrorlanishlarga asoslangan generatorlar
Pseudortasodifiy generatorlarni qurishda katta muvaffaqiyat ikki elementli maydonda chiziqli takrorlanishlarga asoslangan texnikani joriy etish edi; bunday generatorlar chiziqli-teskari aloqa siljish registrlari bilan bog'liq . 1997 yilda Mersenne Twister ixtirosi, xususan, oldingi generatorlar bilan bog'liq ko'plab muammolardan qochadi. Mersenne Twister 2 19 937−1 iteratsiya davriga ega (≈4,3 × 106001) , 623 o'lchamda (32 bitli qiymatlar uchun) teng taqsimlanganligi isbotlangan va u joriy qilingan paytda tezroq ishlagan. boshqa statistik jihatdan oqilona generatorlarga qaraganda. 2003 yilda Jorj Marsaglia yana chiziqli takrorlanishga asoslangan xorshift generatorlari oilasini [10] taqdim etdi. Bunday generatorlar juda tez va chiziqli bo'lmagan operatsiya bilan birgalikda kuchli statistik sinovlardan o'tadi. [2006-yilda WELL generatorlari oilasi ishlab chiqildi . WELL generatorlari qaysidir maʼnoda Mersenne Twister sifatini yaxshilaydi – bu juda katta holat maydoniga ega va koʻp sonli shtat boʻshliqlaridan juda sekin tiklanadi. nollar.
Kriptografik PRNGlar
Kriptografik ilovalar uchun mos keladigan PRNG kriptografik jihatdan xavfsiz PRNG (CSPRNG) deb ataladi. CSPRNG uchun talab shundan iboratki, urug'ni bilmagan raqib generatorning chiqish ketma-ketligini tasodifiy ketma-ketlikdan farqlashda juda kam ustunlikka ega. Boshqacha qilib aytadigan bo'lsak, PRNG faqat ma'lum statistik testlardan o'tish uchun kerak bo'lsa-da, CSPRNG urug'ning o'lchamidagi polinom vaqti bilan cheklangan barcha statistik testlardan o'tishi kerak. Ushbu xususiyatning isboti hisoblash murakkabligi nazariyasi san'atining hozirgi holatidan tashqarida bo'lsa-da, CSPRNG ni butun son faktorizatsiyasi kabi qiyin deb hisoblangan muammoga qisqartirish orqali kuchli dalillar keltirilishi mumkin. [15] Umuman olganda, algoritmni CSPRNG sifatida sertifikatlashdan oldin ko'p yillar talab qilinishi mumkin.
CSPRNG ning ba'zi sinflari quyidagilarni o'z ichiga oladi:

• 
  oqim shifrlari
  
• 
  hisoblagich [16] yoki chiqish teskari aloqa rejimida ishlaydigan blokli shifrlar
  
• 
  Kriptografik jihatdan xavfsiz bo'lish uchun maxsus ishlab chiqilgan PRNG'lar, masalan, Microsoft-ning CryptGenRandom kriptografik amaliy dasturlash interfeysi, Yarrow algoritmi (Mac OS X va FreeBSD-ga kiritilgan) va Fortuna
  
• 
  Bir nechta PRNG ibtidoiy algoritmlarini har qanday aniqlanmaydigan tasodifiylikni yo'q qilish maqsadida birlashtirishga harakat qiladigan PRNG kombinatsiyasi
  
• 
  Matematik qattiqlik taxminlariga asoslangan maxsus dizaynlar: misollar Micali-Schnorr generatorini, [17] Naor-Reingold psevdor tasodifiy funktsiyasini va Blum Blum Shub algoritmini o'z ichiga oladi, ular kuchli xavfsizlikni isbotlaydi (bunday algoritmlar an'anaviy konstruktsiyalarga nisbatan ancha sekin va amaliy emas) ko'p ilovalar uchun)
  
• 
  umumiy PRNG'lar: (kriptografik jihatdan) xavfsiz PRNGni har qanday bir tomonlama funktsiyadan umumiy tarzda qurish mumkinligi ko'rsatilgan bo'lsa-da, [18] bu umumiy qurilish amaliyotda juda sekin, shuning uchun asosan nazariy qiziqish uyg'otadi.
  

Aksariyat PRNG algoritmlari bir nechta testlardan birortasi tomonidan bir xil taqsimlangan ketma-ketliklarni ishlab chiqaradi. Bu ochiq savol bo'lib, kriptografiya nazariyasi va amaliyotida markaziy o'rinni egallaydi, yuqori sifatli PRNG chiqishini chinakam tasodifiy ketma-ketlikdan ajratishning biron bir usuli bormi? Bu sozlamada ajratuvchi maʼlum boʻlgan PRNG algoritmi (lekin u ishga tushirilgan holat emas) yoki haqiqiy tasodifiy algoritm ishlatilganligini biladi va ikkalasini farqlashi kerak. PRNG-lardan foydalanadigan ko'pgina kriptografik algoritmlar va protokollarning xavfsizligi tegishli PRNG-dan foydalanishni haqiqiy tasodifiy ketma-ketlikdan ajratish mumkin emas degan taxminga asoslanadi. Ushbu qaramlikning eng oddiy misollari oqim shifrlari bo'lib, ular (ko'pincha) PRNG chiqishi bilan xabarning ochiq matnini eksklyuziv yoki shifrlangan matn ishlab chiqarish orqali ishlaydi. Kriptografik jihatdan adekvat PRNG-larni loyihalash juda qiyin, chunki ular qo'shimcha mezonlarga javob berishi kerak. Uning davrining o'lchami PRNG ning kriptografik muvofiqligida muhim omil hisoblanadi, lekin yagona emas.

BSI baholash mezonlari.

Axborot xavfsizligi bo'yicha Germaniya federal idorasi (nemis: Bundesamt für Sicherheit in der Informationstechnik, BSI) deterministik tasodifiy sonlar generatorlari sifati uchun to'rtta mezonni o'rnatdi. [21] Ular bu yerda jamlangan :

• 
  K1 - tasodifiy sonlarning yaratilgan ketma-ketliklari bir-biridan farq qilish ehtimoli yuqori bo'lishi kerak.
  
• 
  K2 - Belgilangan statistik testlarga ko'ra raqamlar ketma-ketligini "haqiqiy tasodifiy" raqamlardan ajratib bo'lmaydi. Sinovlar - monobit testi (ketma-ketlikdagi birliklar va nollarning teng soni), poker testi (chi-kvadrat testining maxsus namunasi), yugurish testi (turli uzunlikdagi yugurishlar chastotasini hisoblaydi), longruns testi (ketma-ketlikda birliklar va nollarning tengligini tekshiradi). ketma-ketlikning 20 000 bitida 34 yoki undan katta uzunlikdagi har qanday yugurish mavjud) - BSI [21] va NIST, [22] va avtokorrelyatsiya testidan. Aslini olganda, bu talablar bit ketma-ketligi qanchalik to'g'ri ekanligini tekshirishdir: nolga va birlarga teng darajada tez-tez ega; n ta nol (yoki birlik) ketma-ketligidan so'ng, keyingi bit bir yarim (yoki nol) ehtimoli bilan; va har qanday tanlangan quyi ketma-ketlikda ketma-ketlikdagi keyingi element(lar) haqida hech qanday ma'lumot mavjud emas.
  
• 
  K3 - tajovuzkor (barcha amaliy maqsadlar uchun) ketma-ketlikdagi oldingi yoki kelajakdagi qiymatlarni yoki generatorning ichki holatini har qanday berilgan keyingi ketma-ketlikdan hisoblashi yoki boshqacha tarzda taxmin qilishi mumkin bo'lmasligi kerak.
  
• 
  K4 - Barcha amaliy maqsadlarda tajovuzkor generatorning ichki holatini, ketma-ketlikdagi oldingi raqamlarni yoki oldingi ichki generator holatini hisoblashi yoki taxmin qilishi mumkin emas.
  

Matematik ta'rifi:

Berilgan p- ehtimollik taqsimoti ( haqiqiy chiziqda standart Borel o'rnatilgan). T-Borel to'plamlarining bo'sh bo'lmagan to'plami . Agar belgilanmagan bo'lsa, u kontekstga bog'liq bo'lishi mumkin
– bo‘sh bo‘lmagan to‘plam (borel to‘plami bo‘lishi shart emas). Ko'pincha qo'llab-quvvatlash va uning ichki qismi o'rtasida o'rnatiladi ; masalan, agar P oraliqda bir xil taqsimot bo'lsa (0 ;1 ). Agar A ko'rsatilmagan bo'lsa, u kontekstga qarab P tayanchida va uning ichki qismini o'z ichiga olgan ba'zi bir to'plam sifatida qabul qilinadi.
Biz funktsiyani chaqiramiz T berilgan P uchun psevdo tasodifiy sonlar generatori, agar A dagi qiymatlarni oladi, agar quyidagicha bo’lsa:

"O'rta kvadrat" usuli bilan bog'liq muammo shundaki, barcha ketma-ketliklar oxir-oqibat o'zlarini takrorlaydi, ba'zilari juda tez, masalan, "0000". Von Neumann buni bilar edi, lekin u o'z maqsadlari uchun yondashuvni etarli deb topdi va matematik "tuzatishlar" xatolarni yo'q qilish o'rniga ularni yashirishidan xavotirda edi. Von Neyman apparat tasodifiy sonlar generatorlarini yaroqsiz deb topdi, chunki ular hosil bo'lgan natijani qayd qilmasa, ular bajara olmaydi. keyinchalik xatolar uchun sinovdan o'tkaziladi. Agar ular o'z chiqishlarini yozib olsalar, ular o'sha paytda mavjud bo'lgan cheklangan kompyuter xotiralarini va shuning uchun kompyuterning raqamlarni o'qish va yozish qobiliyatini tugatgan bo'lar edi. Agar raqamlar kartalarga yozilgan bo'lsa , ularni yozish va o'qish uchun ko'proq vaqt ketadi. U ishlatayotgan ENIAC kompyuterida "o'rta kvadrat" usuli raqamlarni perfokartalardagi raqamlarni o'qishdan yuz baravar tezroq tezlikda hosil qildi. O'rta kvadrat usuli o'sha paytdan beri ishlab chiqilgan generatorlar bilan almashtirildi . Yaqinda yangilik o'rta kvadratni Veyl ketma-ketligi bilan birlashtirishdir. Bu usul uzoq vaqt davomida yuqori sifatli mahsulot ishlab chiqaradi (o'rta kvadrat usuliga qarang).

Foydalanilgan adabiyotlar ro'yxati:

1. 
   Akbarov D.ye. Axborotni ta'minlash kriptografik usullar va komissiya qo'llab-quvvatlash. – T., O‘zbekiston markasi. 2009 yil.
   
2. 
   www.Ziyonet.uz
   
3. 
   "Pseudorandom number generators" (https://www.khanacademy.org/computing/computer-sc ience/cryptography/crypt/v/random-vs-pseudorandom-number-generators). Khan Academy. Retrieved 2016-01-11.