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

2. 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.