Pseudo-tasodifiy raqam - bu maxsus generator tomonidan yaratilgan maxsus raqam. Deterministik Tasodifiy Bit Generator (PRNG), shuningdek, Deterministik Tasodifiy Bit Generator (DRBG) sifatida ham tanilgan, xususiyatlari tasodifiy sonlar ketma-ketligining xarakteristikasiga yaqin bo'lgan raqamlar ketma-ketligini yaratish algoritmidir. Yaratilgan PRNG ketma-ketligi haqiqatdan ham tasodifiy emas, chunki u to'liq PRNG urug'i deb ataladigan urug'lik qiymati bilan belgilanadi, bu haqiqatan ham tasodifiy qiymatlarni o'z ichiga olishi mumkin. Tasodifiyga yaqinroq ketma-ketliklar apparat tasodifiy sonlar generatorlari yordamida yaratilishi mumkin bo'lsa-da, psevdo-tasodifiy sonlar generatorlari raqamlarni yaratish tezligi va ularning takrorlanishi uchun amalda muhim ahamiyatga ega.
Ilova
PRNG'lar simulyatsiya (masalan, Monte-Karlo uchun), elektron o'yinlar (masalan, protsessual ishlab chiqarish uchun) va kriptografiya kabi ilovalar uchun markaziy hisoblanadi. Kriptografik ilovalar chiqishni talab qiladima'lumotlar oldingi ma'lumotlardan oldindan aytib bo'lmaydi. Oddiy PRNGlarning chiziqliligini meros qilib olmaydigan murakkabroq algoritmlar talab qilinadi.
Shartlar va shartlar
Yaxshi statistik xususiyatlar PRNG olish uchun asosiy talabdir. Umuman olganda, RNG mo‘ljallangan foydalanishga mos keladigan tasodifiyga yaqin raqamlarni yaratishiga ishonch hosil qilish uchun sinchkovlik bilan matematik tahlil qilish kerak.
Jon fon Neyman PRNG ni haqiqiy tasodifiy generator sifatida notoʻgʻri talqin qilishdan ogohlantirdi va “Tasodifiy sonlarni yaratishning arifmetik usullarini koʻrib chiqqan har bir kishi, albatta, gunoh holatidadir”, deb hazil qildi.
Foydalanish
PRNG ixtiyoriy boshlang'ich holatdan ishga tushirilishi mumkin. Bu holat bilan ishga tushirilganda har doim bir xil ketma-ketlikni hosil qiladi. PRNG davri quyidagicha aniqlanadi: takrorlanmaydigan ketma-ketlik prefiksi uzunligining barcha boshlang'ich holatlari bo'yicha maksimal. Davr odatda bitlarda o'lchanadigan holatlar soni bilan chegaralanadi. Har bir “holat” biti qo‘shilganda davr uzunligi ikki baravar ko‘payganligi sababli, ko‘plab amaliy ilovalar uchun etarlicha katta davrlarga ega PRNG yaratish oson.
Agar PRNG ning ichki holati n bitdan iborat bo'lsa, uning davri 2n natijadan ko'p bo'lmasligi mumkin, u ancha qisqaroq. Ba'zi PRNG'lar uchun muddat butun davrni chetlab o'tmasdan hisoblanishi mumkin. Lineer Feedback Shift Register (LFSR) odatdanuqtalar 2n − 1 ga teng bo‘ladigan tarzda tanlanadi.
Chiziqli kongriensial generatorlarda faktoring yordamida hisoblab chiqiladigan davrlar mavjud. Garchi PPP o'z natijalarini davr oxiriga etganidan keyin takrorlasa-da, takroriy natija muddat oxiriga yetganligini anglatmaydi, chunki uning ichki holati ishlab chiqarishdan kattaroq bo'lishi mumkin; Bu, ayniqsa, bitta bitli PRNGlar uchun aniq.
Mumkin xatolar
Buzuq PRNGlar tomonidan topilgan xatolar nozik (va noma'lum)dan aniqgacha bo'lgan turlicha. Misol tariqasida o'nlab yillar davomida meynfreymlarda qo'llanilgan RANDU tasodifiy sonlar algoritmini keltirish mumkin. Bu jiddiy kamchilik edi, lekin uning nomutanosibligi uzoq vaqt davomida sezilmay qoldi.
Koʻpgina sohalarda tasodifiy tanlash, Monte-Karlo simulyatsiyasi yoki RNGga asoslangan boshqa usullardan foydalangan tadqiqot ishlari sifatsiz GNPG natijasi boʻlishi mumkin boʻlgan ishonchliligidan ancha past. Hatto bugungi kunda ham ba'zida ehtiyotkorlik talab etiladi, buni Xalqaro Statistik fanlar ensiklopediyasi (2010)dagi ogohlantirish tasdiqlaydi.
Muvaffaqiyatli misollar
Masalan sifatida keng tarqalgan Java dasturlash tilini ko'rib chiqaylik. 2017-yil holatiga ko‘ra, Java hali ham PRNG uchun Lineer Congruential Generator (LCG) ga tayanadi.
Tarix
Jiddiy muammolardan qochish va hali ham juda tez ishlaydigan birinchi PRNG,1998 yilda nashr etilgan Mersenne Twister edi (quyida muhokama qilinadi). Oʻshandan beri boshqa yuqori sifatli PRNGlar ishlab chiqildi.
Ammo psevdotasodifiy raqamlarning tarixi shu bilan tugamaydi. 20-asrning ikkinchi yarmida PRNG uchun ishlatiladigan standart algoritmlar sinfiga chiziqli kongruential generatorlar kiradi. LCG sifati etarli emasligi ma'lum edi, ammo yaxshiroq usullar mavjud emas edi. Press va boshqalar (2007) natijani quyidagicha ta'riflagan: "Agar [LCG va shunga o'xshash] tufayli natijalari shubhali bo'lgan barcha ilmiy maqolalar kutubxona javonlaridan yo'qolib qolsa, har bir javonda sizning mushtingizdek bo'shliq bo'lar edi."
Pseudo-tasodifiy generatorlarni yaratishdagi asosiy yutuq ikki elementli sohada chiziqli takrorlanishga asoslangan usullarni joriy etish edi; bunday osilatorlar chiziqli fikr almashish registrlari bilan birlashtiriladi. Ular psevdo-tasodifiy raqamlar sensorlari ixtirosi uchun asos bo'lib xizmat qildi.
Xususan, 1997-yilda Mersen Twister ixtirosi oldingi generatorlar bilan bogʻliq koʻplab muammolardan qochdi. Mersenne Twister 219937−1 iteratsiya davriga ega (≈4,3 × 106001). U 623 oʻlchamda (32-bit qiymatlar uchun) bir xilda taqsimlangani isbotlangan va u joriy qilingan paytda psevdo-tasodifiy raqamlar ketma-ketligini hosil qiluvchi boshqa statistik ishonchli generatorlarga qaraganda tezroq edi.
2003 yilda Jorj Marsaglia chiziqli takrorlashga asoslangan xorshift generatorlari oilasini taqdim etdi. Bu generatorlar juda kattatez va - chiziqli bo'lmagan operatsiya bilan birgalikda - ular qattiq statistik testlardan o'tadi.
2006 yilda WELL generatorlar oilasi ishlab chiqildi. WELL generatorlari ma'lum ma'noda Twister Mersenne sifatini yaxshilaydi, u haddan tashqari katta holat maydoniga ega va ulardan juda sekin tiklanadi va juda ko'p nolga ega psevdo-tasodifiy raqamlarni hosil qiladi.
Kriptografiya
Kriptografik ilovalar uchun mos
PRNG kriptografik xavfsiz PRNG (CSPRNG) deb ataladi. CSPRNG ga qo'yiladigan talab shundan iboratki, urug'ni bilmagan tajovuzkor generatorning chiqish ketma-ketligini tasodifiy ketma-ketlikdan farqlashda faqat marjinal ustunlikka ega. Boshqacha qilib aytganda, PRNG faqat maʼlum statistik testlardan oʻtish uchun zarur boʻlsa-da, CSPRNG urugʻ oʻlchamidagi polinom vaqti bilan cheklangan barcha statistik testlardan oʻtishi kerak.
Bu xususiyatning isboti hisoblash murakkabligi nazariyasining hozirgi darajasidan tashqarida boʻlsa-da, CSPRNG ni butun son faktorizatsiyasi kabi qiyin hisoblangan muammoga qisqartirish orqali kuchli dalillar keltirilishi mumkin. Umuman olganda, algoritmni CSPRNG sifatida sertifikatlashdan oldin ko‘p yillar talab qilinishi mumkin.
NSA NIST tomonidan sertifikatlangan Dual_EC_DRBG psevdotasodifiy raqamlar generatoriga assimetrik orqa eshikni oʻrnatgan boʻlishi aniqlandi.
Pseudo-tasodifiy algoritmlarraqamlar
Koʻpchilik PRNG algoritmlari bir nechta testlardan birortasi tomonidan teng taqsimlangan ketma-ketliklarni ishlab chiqaradi. Bu ochiq savol. Bu kriptografiya nazariyasi va amaliyotidagi markaziy nuqtalardan biri: yuqori sifatli PRNG chiqishini haqiqiy tasodifiy ketma-ketlikdan ajratishning bir usuli bormi? Ushbu sozlamada hal qiluvchi ma'lum PRNG algoritmi ishlatilganligini (lekin u ishga tushirilgan holat emas) yoki haqiqiy tasodifiy algoritm ishlatilganligini biladi. U ularni farqlashi kerak.
PRNG'lardan foydalanadigan ko'pgina kriptografik algoritmlar va protokollarning xavfsizligi mos PRNGdan foydalanish va haqiqiy tasodifiy ketma-ketlikdan foydalanish o'rtasidagi farqni ajratib bo'lmaydi degan taxminga asoslanadi. Ushbu bog'liqlikning eng oddiy misollari oqim shifrlari bo'lib, ular ko'pincha PRNG chiqishi bilan ochiq matnli xabarni o'tkazib yuborish yoki yuborish orqali ishlaydi va shifrlangan matnni yaratadi. Kriptografik jihatdan mos PRNG-larni loyihalash juda qiyin, chunki ular qo'shimcha mezonlarga javob berishi kerak. Uning davrining kattaligi PRNG ning kriptografik yaroqliligida muhim omil hisoblanadi, lekin yagona emas.
1946 yilda Jon fon Neyman tomonidan taklif qilingan dastlabki kompyuter PRNG o'rtacha kvadratlar usuli sifatida tanilgan. Algoritm quyidagicha: istalgan raqamni oling, kvadratga aylantiring, natijada paydo bo'lgan sonning o'rta raqamlarini "tasodifiy raqam" sifatida olib tashlang, so'ngra bu raqamni keyingi iteratsiya uchun boshlang'ich raqam sifatida ishlating. Misol uchun, 1111 raqamini kvadratga ajratish01234321 deb yozilishi mumkin bo'lgan 1234321, 8 xonali son 4 xonali sonning kvadratidir. Bu "tasodifiy" raqam sifatida 2343 ni beradi. Ushbu protsedurani takrorlash natijasi 4896 va hokazo. Von Neumann 10 xonali raqamlardan foydalangan, lekin jarayon bir xil edi.
"O'rta kvadrat"ning kamchiliklari
"O'rtacha kvadrat" usuli bilan bog'liq muammo shundaki, barcha ketma-ketliklar oxir-oqibat takrorlanadi, ba'zilari juda tez, masalan: 0000. Von Neumann bu haqda bilar edi, lekin u o'z maqsadlari uchun etarli yondashuvni topdi va xavotirda edi. Matematik "tuzatishlar" xatolarni olib tashlash o'rniga ularni yashiradi.
Von Neuman apparat tasodifiy va psevdo-tasodifiy sonlar generatorlarini yaroqsiz deb topdi: agar ular ishlab chiqarilgan natijani qayd qilmasa, ularni keyinroq xatolik uchun tekshirib boʻlmaydi. Agar ular o'z natijalarini yozsalar, ular kompyuterning cheklangan xotirasini va shuning uchun kompyuterning raqamlarni o'qish va yozish qobiliyatini tugatadi. Agar raqamlar kartalarga yozilgan bo'lsa, ularni yozish va o'qish uchun ko'proq vaqt ketadi. U ENIAC kompyuterida "o'rta kvadrat" usulidan foydalangan va psevdotasodifiy raqamlarni olish jarayonini perfokartalardagi raqamlarni o'qishga qaraganda bir necha yuz marta tezroq amalga oshirgan.
Oʻrta kvadrat oʻrniga murakkabroq generatorlar qoʻyildi.
Innovatsion usul
Yaqinda kiritilgan yangilik oʻrtacha kvadratni Vayl ketma-ketligi bilan birlashtirishdir. Ushbu usul mahsulotning yuqori sifatini ta'minlaydiuzoq muddat. Bu eng yaxshi psevdo-tasodifiy raqamlar formulalarini olishga yordam beradi.
