Псевдокездейсоқ сан – арнайы генератор арқылы жасалған арнайы сан. Детерминистикалық кездейсоқ разряд генераторы (PRNG), сондай-ақ детерминистикалық кездейсоқ разряд генераторы (DRBG) ретінде белгілі, қасиеттері кездейсоқ сандар тізбегі сипаттамаларына жуықтайтын сандар тізбегін құруға арналған алгоритм болып табылады. Жасалған PRNG тізбегі шын мәнінде кездейсоқ емес, өйткені ол толығымен PRNG тұқымы деп аталатын тұқымдық мәнмен анықталады, ол шын мәнінде кездейсоқ мәндерді қамтуы мүмкін. Кездейсоққа жақын тізбектерді аппараттық кездейсоқ сандар генераторлары арқылы жасауға болатынына қарамастан, жалған кездейсоқ сандар генераторлары сандарды генерациялау жылдамдығы мен олардың қайталануы үшін практикада маңызды.
Қолданба
PRNG модельдеу (мысалы, Монте-Карло үшін), электрондық ойындар (мысалы, процедуралық генерация үшін) және криптография сияқты қолданбалардың орталық бөлігі болып табылады. Криптографиялық қолданбалар шығуды талап етедідеректер бұрынғы ақпараттан болжауға келмеді. Қарапайым PRNG сызықтылығын мұра етпейтін күрделірек алгоритмдер қажет.
Шарттар мен шарттар
Жақсы статистикалық сипаттар PRNG алу үшін орталық талап болып табылады. Жалпы, RNG мақсатты пайдалануға сәйкес келетін кездейсоқ сандарға жеткілікті жақын сандарды жасайтынына сенімді болу үшін мұқият математикалық талдау қажет.
Джон фон Нейман PRNG-ді шынымен кездейсоқ генератор ретінде дұрыс түсінбеу туралы ескертті және «Кездейсоқ сандарды шығарудың арифметикалық әдістерін қарастыратын кез келген адам, әрине, күнәға батады» деп қалжыңдаған.
Қолдану
PRNG ерікті бастапқы күйден іске қосылуы мүмкін. Бұл күймен инициализацияланған кезде ол әрқашан бірдей реттілік жасайды. PRNG кезеңі келесідей анықталады: қайталанбайтын реттілік префиксінің ұзындығының барлық бастапқы күйлері бойынша максимум. Период күйлер санымен шектеледі, әдетте битпен өлшенеді. Әрбір "күй" бит қосылған сайын кезең ұзындығы екі еселенетіндіктен, көптеген практикалық қолданбалар үшін жеткілікті үлкен кезеңдері бар PRNG жасау оңай.
Егер PRNG ішкі күйінде n бит болса, оның периоды 2n нәтижеден аспауы мүмкін, ол әлдеқайда қысқа. Кейбір PRNG үшін ұзақтықты бүкіл кезеңді айналып өтпестен есептеуге болады. Сызықтық кері байланысты ауыстыру регистрлері (LFSR) әдетте болып табылады2n − 1 нүктелеріне тең болатындай етіп таңдалады.
Сызықтық конгруциалды генераторларда факторинг арқылы есептелетін кезеңдері болады. МЖӘ өз нәтижелерін кезеңнің соңына жеткеннен кейін қайталайтынына қарамастан, қайталанатын нәтиже кезеңнің соңына жетті дегенді білдірмейді, өйткені оның ішкі күйі шығарылымнан жоғары болуы мүмкін; бұл әсіресе бір биттік шығысы бар PRNG үшін айқын.
Мүмкін қателер
Ақаулы PRNG арқылы табылған қателер нәзіктен (және белгісіз) айқынға дейін болады. Мысал ретінде ондаған жылдар бойы негізгі компьютерлерде қолданылған RANDU кездейсоқ сандар алгоритмін келтіруге болады. Бұл елеулі кемшілік болды, бірақ оның жеткіліксіздігі ұзақ уақыт бойы байқалмады.
Көптеген салаларда кездейсоқ таңдауды, Монте-Карло модельдеулерін немесе RNG негізіндегі басқа әдістерді пайдаланған зерттеу зерттеулері сапасыз GNPG нәтижесі болуы мүмкін қарағанда сенімдірек. Бүгінгі күннің өзінде кейде сақтық қажет, мұны Халықаралық статистикалық ғылым энциклопедиясындағы (2010) ескерту куәландырады.
Сәтті жағдайлық зерттеу
Мысалы ретінде кеңінен қолданылатын Java бағдарламалау тілін қарастырайық. 2017 жылғы жағдай бойынша Java әлі де PRNG үшін сызықтық конгруенциялық генераторға (LCG) сүйенеді.
Тарих
Бірінші PRNG маңызды проблемаларды болдырмайды және әлі де өте жылдам жұмыс істейді,1998 жылы жарияланған Mersenne Twister (төменде талқыланады) болды. Содан бері басқа жоғары сапалы PRNGs әзірленді.
Бірақ псевдокездейсоқ сандардың тарихы мұнымен бітпейді. 20 ғасырдың екінші жартысында PRNG үшін қолданылатын алгоритмдердің стандартты класына сызықтық конгруциалды генераторлар кірді. LCG сапасы жеткіліксіз екені белгілі болды, бірақ жақсырақ әдістер қол жетімді болмады. Пресс және басқалары (2007) нәтижені былай сипаттады: «Егер [LCG және соған қатысты] себебінен нәтижелері күмән тудыратын барлық ғылыми мақалалар кітапхана сөрелерінен жоғалып кетсе, әрбір сөреде жұдырықтай бос орын қалады.»
Псевдокездейсоқ генераторларды құрудағы басты жетістік екі элементті өрісте сызықтық рекуррентке негізделген әдістерді енгізу болды; мұндай осцилляторлар кері байланыстың сызықтық ауысу регистрлерімен біріктірілген. Олар псевдокездейсоқ сандар сенсорларының өнертабысы үшін негіз болды.
Атап айтқанда, 1997 жылы Mersen Twister өнертабысы бұрынғы генераторларға қатысты көптеген мәселелерден аулақ болды. Mersenne Twister 219937−1 итерация кезеңіне ие (≈4,3 × 106001). Оның 623 өлшемге (32-биттік мәндер үшін) біркелкі бөлінгені дәлелденді және оны енгізу кезінде жалған кездейсоқ сандар тізбегін шығаратын басқа статистикалық сенімді генераторларға қарағанда жылдамырақ болды.
2003 жылы Джордж Марсаглия сызықтық қайталауға негізделген xorshift генераторларының отбасын ұсынды. Бұл генераторлар өте жақсыжылдам және - сызықтық емес операциямен біріктірілген - олар қатаң статистикалық сынақтардан өтеді.
2006 жылы WELL генераторлар тобы әзірленді. WELL генераторлары белгілі бір мағынада Twister Mersenne сапасын жақсартады, оның күй кеңістігі тым үлкен және олардан қалпына келтіру өте баяу, нөлдері көп жалған кездейсоқ сандарды жасайды.
Криптография
Криптографиялық қолданбаларға жарамды
PRNG криптографиялық қауіпсіз PRNG (CSPRNG) деп аталады. CSPRNG талабы - тұқымды білмейтін шабуылдаушы генератордың шығу ретін кездейсоқ реттіліктен ажыратуда шекті артықшылыққа ие болуы. Басқаша айтқанда, PRNG белгілі бір статистикалық сынақтардан өту үшін ғана талап етілсе, CSPRNG тұқым өлшеміндегі полиномдық уақытпен шектелген барлық статистикалық сынақтардан өтуі керек.
Бұл сипаттың дәлелі есептеу күрделілігі теориясының қазіргі деңгейінен тыс болса да, CSPRNG-ті бүтін санды көбейткіштерге бөлу сияқты қиын деп есептелетін мәселеге дейін азайту арқылы күшті дәлелдерді беруге болады. Жалпы, алгоритмді CSPRNG ретінде сертификаттау үшін жылдар бойы тексеру қажет болуы мүмкін.
ҰҚА NIST сертификатталған Dual_EC_DRBG псевдокездейсоқ сандар генераторына асимметриялық артқы есікті кіргізген болуы мүмкін.
Псевдокездейсоқ алгоритмдерсандар
PRNG алгоритмдерінің көпшілігі бірнеше сынақтардың кез келгені арқылы біркелкі таратылатын тізбектерді жасайды. Бұл ашық сұрақ. Бұл криптографияның теориясы мен тәжірибесіндегі орталықтардың бірі: жоғары сапалы PRNG шығысын шын кездейсоқ реттіліктен ажыратудың жолы бар ма? Бұл параметрде шешуші белгілі PRNG алгоритмі пайдаланылғанын (бірақ оның инициализацияланған күйі емес) немесе шынымен кездейсоқ алгоритмнің пайдаланылғанын біледі. Ол олардың арасындағы айырмашылықты білуі керек.
PRNG қолданатын криптографиялық алгоритмдер мен хаттамалардың көпшілігінің қауіпсіздігі қолайлы PRNG пайдалану мен шын кездейсоқ ретті пайдалануды ажырату мүмкін емес деген болжамға негізделген. Бұл тәуелділіктің қарапайым мысалдары ағындық шифрлар болып табылады, олар көбінесе PRNG шығысымен ашық мәтіндік хабарламаны өткізіп жіберу немесе шифрлық мәтінді жасау арқылы жұмыс істейді. Криптографиялық барабар PRNG жобалау өте қиын, өйткені олар қосымша критерийлерге сай болуы керек. Оның кезеңінің өлшемі PRNG криптографиялық жарамдылығының маңызды факторы болып табылады, бірақ жалғыз емес.
1946 жылы Джон фон Нейман ұсынған алғашқы компьютерлік PRNG орташа квадраттар әдісі ретінде белгілі. Алгоритм келесідей: кез келген санды алыңыз, оның квадратын алыңыз, алынған санның ортаңғы цифрларын «кездейсоқ сан» ретінде алып тастаңыз, содан кейін бұл санды келесі итерация үшін бастапқы сан ретінде пайдаланыңыз. Мысалы, 1111 санын квадраттау береді1234321, оны 01234321 деп жазуға болады, 8 таңбалы сан 4 таңбалы санның квадраты болып табылады. Бұл «кездейсоқ» сан ретінде 2343 береді. Бұл процедураны қайталаудың нәтижесі 4896 және т.б. Фон Нейман 10 таңбалы сандарды пайдаланды, бірақ процесс бірдей болды.
"ортаңғы шаршының" кемшіліктері
«Орташа квадрат» әдісіне қатысты мәселе мынада: барлық тізбектер ақырында қайталанады, кейбіреулері өте жылдам, мысалы: 0000. Фон Нейман бұл туралы білген, бірақ ол өз мақсаттары үшін жеткілікті тәсіл тапты және математикалық "түзетулер" қателерді жоюдың орнына оларды жасырады.
Вон Нейман аппараттық құралдың кездейсоқ және псевдокездейсоқ сандар генераторларын жарамсыз деп тапты: егер олар жасалған шығысты жазбаса, оларды кейінірек қателерді тексеру мүмкін емес. Егер олар өз нәтижелерін жазатын болса, олар компьютердің шектеулі қол жетімді жадын және осылайша компьютердің сандарды оқу және жазу мүмкіндігін таусатын еді. Егер сандар карталарға жазылса, оларды жазуға және оқуға көп уақыт кетеді. Ол ENIAC компьютерінде «ортаңғы квадрат» әдісін қолданып, перфокарталардан сандарды оқуға қарағанда псевдокездейсоқ сандарды алу процесін бірнеше жүз есе жылдам жүргізді.
Орташа квадрат содан кейін күрделі генераторлармен ауыстырылды.
Инновациялық әдіс
Жақында жасалған жаңалық - орташа квадратты Вайль тізбегімен біріктіру. Бұл әдіс өнімнің жоғары сапасын қамтамасыз етедіұзақ кезең. Бұл ең жақсы псевдокездейсоқ сандар формулаларын алуға көмектеседі.
