Кездейсоқ сандар генераторы деген не?
Кездейсоқ сандар генераторы (RNG) — бұл кездейсоқ немесе псевдокездейсоқ сандарды қалыптастыратын жүйе. Келесі санның алдын ала болжануы генератордың түріне байланысты. Кейбір генераторлар физикалық процеске сүйенеді, кейбіреулері сандарды алгоритм көмегімен есептейді, ал кейбір алгоритмдер олардың нәтижелерін көрген адамның өзі келесі мәнді болжай алмайтындай етіп құрастырылған. Кездейсоқ болып көріну мен алдын ала болжанбайтындық — әртүрлі қасиеттер, және бұл мақаланың негізгі бөлігі осы айырмашылыққа арналған.
Аппараттық кездейсоқ сандар генераторлары
Аппараттық кездейсоқ сандар генераторы (HRNG), оны сондай-ақ шынайы кездейсоқ сандар генераторы (TRNG) деп те атайды, сандарды физикалық процестерден алады. Ең көне үлгілері көз алдымызда жұмыс істейді: лақтырылған тиын, домалатылған ойын сүйегі, рулетка дөңгелегі. Механика заңдары олардың әрқайсысын толық сипаттайды, дегенмен жақсы жасалған дөңгелек іс жүзінде бәрібір болжап білгісіз болып қалады, өйткені әрбір айналдырудың бастапқы қозғалысындағы болмашы айырмашылықтар мүлдем басқа нәтижелерге алып келеді.
Заманауи аппараттық генераторлар оның орнына микроскопиялық құбылыстарды өлшейді: электрондық тізбектердегі бөлшектердің шуылы (shot noise) мен жылулық шу, атмосфералық шу, кванттық эффектілер. Бұл энтропияның — өлшеуге болатын болжанбайтындықтың жақсы көздері — бірақ физикалық көз табиғатынан мінсіз емес: ол ауытқуы, өзгеріске ұшырауы және істен шығуы мүмкін, сондықтан оның сапасын бағалап, бақылап отыру керек және қажет болған жағдайда алынған мәндерді қосымша өңдеу қажет, бұл NIST SP 800-90B сияқты стандарттарда сипатталған. Аппараттық көздер сенімділік аса маңызды жерлерде қолданылады — әсіресе криптографияда, мұнда олар Transport Layer Security (TLS) сияқты хаттамалардың кілттері үшін болжанбайтын бастапқы материалды қамтамасыз етеді.
Псевдокездейсоқ сандар генераторлары
Физикалық құрылғының баламасы — алгоритм. Псевдокездейсоқ сандар генераторы (PRNG) кездейсоқ болып көрінетін, бірақ бастапқы мән (seed) деп аталатын бастапқы шамамен толық анықталатын сандар тізбегін жасайды. Бірдей бастапқы мәнді бірдей алгоритмге берсеңіз, сіз әрқашан бірдей тізбекті аласыз. Бұл нәтиже болжанбауы тиіс болған және бастапқы мәнді немесе ішкі күйді болжауға немесе қалпына келтіруге болатын жерлерде әлсіздік болып саналады, ал нәтижені дәл қайталау қажет болған кезде — симуляцияны немесе сынақты дәл қайта жүргізуде — күшті жағы болып табылады. PRNG-лер сонымен қатар жылдам, арзан әрі оңай енгізіледі, сондықтан бағдарламалық жасақтаманың басым бөлігі соларға сүйенеді. Белгілі алгоритмдер қатарына сызықтық конгруэнтті генератор (LCG), xorshift генераторлары және Mersenne Twister жатады.
Mersenne Twister
1997 жылы Макото Мацумото мен Такуджи Нишимура жариялаған Mersenne Twister — ең кең таралған псевдокездейсоқ сандар генераторларының бірі және көптеген бағдарламалау тілдеріндегі әдепкі таңдау. Оның атауы период ұзындығынан — тізбек қайталанғанға дейінгі қадамдар санынан шыққан, ол стандартты MT19937 нұсқасында Мерсенн жай саны 219937 − 1 құрайды. Ол кездейсоқтықтың көптеген статистикалық сынақтарынан өтеді және модельдеу процестеріне жақсы үйлеседі. Алайда, ол құпияларды сақтау үшін жасалмаған: кез келген адам 624 дәйекті 32-биттік нәтижеден оның ішкі күйін қалпына келтіріп, одан кейінгі барлық мәндерді болжай алады, сондықтан оны кілттер, құпия сөздер немесе болжанбайтын болып қалуы тиіс кез келген басқа деректер үшін пайдалануға болмайды.
Криптографиялық тұрғыдан қауіпсіз генераторлар және энтропия
Көптеген қолданбалар бір уақытта екі нәрсені қажет етеді: алгоритмнің жылдамдығын және физикалық көздің болжанбайтындығын. Бұған жауап — криптографиялық тұрғыдан қауіпсіз псевдокездейсоқ сандар генераторы (CSPRNG). Ол әлі де PRNG болып табылады, бірақ оның нәтижесінің бір бөлігін көру арқылы қалғанын іс жүзінде болжау мүмкін болмайтындай етіп жасалған, және ол нақты энтропия көзінен бастапқы мәнмен қамтамасыз етіледі әрі жүйелі түрде қайта жаңартылып отырады. Физикалық көзден алынған бастапқы мән қарапайым PRNG-ні қауіпсіз етпейді; алгоритмнің өзі соған арналып жасалуы керек. Жылулық шу немесе аппараттық оқиғалардың уақыты сияқты физикалық көз шынайы кездейсоқтықтың шағын көлемін береді, ал CSPRNG одан әлдеқайда жылдам мәндердің ұзын тізбегін алады. Бұл үйлесім операциондық жүйенің онда жұмыс істейтін бағдарламаларға ұсынатыны және бүгінгі таңда іс жүзінде «кездейсоқ сандар генераторы» дегеннің нақты мағынасы болып табылады. Ол шифрлау кілттерін, сессия токендерін және құпия сөздерді жасайды.
Браузердегі кездейсоқ сандар
JavaScript веб-бетке кездейсоқ мәндерді алудың екі кірістірілген әдісін ұсынады және олар әртүрлі сыныптарға жатады. Math.random() — қарапайым PRNG: тіл стандарты алгоритм таңдауын әр браузердің еркіне қалдырады және қауіпсіздік туралы ешқандай кепілдік бермейді — бұл анимация үшін жақсы, бірақ біреу дауласуы мүмкін ұтыс ойыны үшін жарамсыз. Екіншісі — Web Crypto API. Оның crypto.getRandomValues() әдісі операциондық жүйенің энтропиясымен қамтамасыз етілген CSPRNG арқылы жасалған криптографиялық күшті кездейсоқ мәндерді қайтарады.
Біздің кездейсоқ сандар онлайн генераторы әрбір таңдау үшін Web Crypto API пайдаланады және сандар серверде емес, сіздің браузеріңізде жасалады. Дәл осы көз сайттағы басқа генераторларды да іске қосады, сіз сүйек лақтырсаңыз да, тиын лақтырсаңыз да немесе құпия сөз жасасаңыз да бірдей жұмыс істейді.
Кездейсоқ биттерден қажетті аралықтағы санға дейін
Криптографиялық тұрғыдан қауіпсіз генератор — әділ ұтыстың тек жартысы ғана. Ол бастапқы биттерді береді, ал бағдарлама оларды сіздің аралығыңыздағы санға айналдыруы керек — дәл осы жерде ауытқу пайда болуы мүмкін. Айталық, бастапқы көз 0-ден 9-ға дейінгі мәндерді бірдей ықтималдықпен береді, ал сізге 0-ден 5-ке дейінгі сан қажет. 6-ға бөлгеннен кейінгі қалдықты алу табиғи көрінеді, бірақ бұл жағдайда 0, 1, 2 және 3 сандары екі жолмен, ал 4 және 5 тек бір ғана жолмен шығуы мүмкін, сондықтан 0-ден 3-ке дейінгі әр санның түсу ықтималдығы 20%, ал 4 пен 5 сандарының әрқайсысында небәрі 10% құрайды. Бұл ауытқуды (modulo bias) жоюдың бір жолы — сәйкес келмейтін мәндерді алып тастап, қайта таңдау; кездейсоқ сандар генераторы материалдары бұл мәселені егжей-тегжейлі түсіндіреді.
Адамдарды тағы екі нәрсе таңғалдырады. Қайталанулар — бұл қалыпты жағдай: 1-ден 10-ға дейінгі бүтін сан тәуелсіз түрде таңдалғанда және әрбір санның шығу мүмкіндігі бірдей болғанда, жаңа ғана шыққан санның қайта түсу мүмкіндігі кез келген басқа сан сияқты 10-нан 1 болады. Қайталанбайтын таңдау — бұл кездейсоғырақ таңдау емес, таңдаудың басқа түрі. Сондай-ақ, тек әділ генератордың болуы бүкіл процедураны әділ ете алмайды: қатысушылар тізімі мен таңдау әрекеттерінің саны да дәл сондай маңызды, бұл біздің конкурс жеңімпазын кездейсоқ қалай таңдауға болады туралы мақаламызда баяндалған.