Ի՞նչ է պատահական թվերի գեներատորը:
Պատահական թվերի գեներատորը (RNG) համակարգ է, որն արտադրում է պատահական կամ պսևդոպատահական թվեր: Արդյոք հաջորդ թիվը հնարավոր է կանխատեսել, կախված է գեներատորի տեսակից: Որոշ գեներատորներ հիմնվում են ֆիզիկական գործընթացի վրա, մյուսները թվերը հաշվարկում են ալգորիթմով, իսկ որոշ ալգորիթմներ ստեղծված են այնպես, որ նույնիսկ նախորդ արդյունքները տեսած մարդը չի կարող գուշակել հաջորդը: Պատահական տեսք ունենալը և անկանխատեսելի լինելը տարբեր հատկանիշներ են, և այս հոդվածի մեծ մասը նվիրված է հենց այդ տարբերությանը:
Սարքավորումային պատահական թվերի գեներատորներ
Սարքավորումային պատահական թվերի գեներատորը (HRNG), որը կոչվում է նաև ճշմարիտ պատահական թվերի գեներատոր (TRNG), իր թվերը ստանում է ֆիզիկական գործընթացից: Ամենահին տարբերակներն աշխատում են հենց մեր աչքի առաջ՝ նետված մետաղադրամ, գլորված զառ, ռուլետկայի անիվ: Մեխանիկայի օրենքներն ամբողջությամբ նկարագրում են դրանցից յուրաքանչյուրը, սակայն որակյալ պատրաստված անիվը գործնականում մնում է անկանխատեսելի, քանի որ յուրաքանչյուր պտույտի մեկնարկի չնչին տարբերությունները վերածվում են միանգամայն տարբեր ելքերի:
Ժամանակակից սարքավորումային գեներատորները դրա փոխարեն չափում են միկրոսկոպիկ երևույթներ՝ կոտորակային և ջերմային աղմուկը էլեկտրոնային շղթաներում, մթնոլորտային աղմուկը, քվանտային էֆեկտները: Սրանք էնտրոպիայի՝ չափելի անկանխատեսելիության լավ աղբյուրներ են, բայց ֆիզիկական աղբյուրն ինքնին կատարյալ չէ. այն կարող է ունենալ շեղումներ, ժամանակի ընթացքում փոխվել կամ խափանվել: Այդ պատճառով դրա որակը պետք է գնահատվի և վերահսկվի, իսկ արդյունքներն անհրաժեշտության դեպքում ենթարկվեն հետագա մշակման, ինչպես նկարագրված է NIST SP 800-90B և համանման ստանդարտներում: Սարքավորումային աղբյուրներն օգտագործվում են այնտեղ, որտեղ հուսալիության երաշխիքն ամենակարևորն է, հատկապես կրիպտոգրաֆիայում, որտեղ դրանք ապահովում են անկանխատեսելի ելակետային նյութ Transport Layer Security (TLS) և նմանատիպ արձանագրությունների բանալիների համար:
Պսևդոպատահական թվերի գեներատորներ
Ֆիզիկական սարքի այլընտրանքն ալգորիթմն է: Պսևդոպատահական թվերի գեներատորը (PRNG) ստեղծում է հաջորդականություն, որը պատահական տեսք ունի, բայց ամբողջությամբ որոշվում է սկզբնական արժեքով, որը կոչվում է սկզբնարժեք կամ սերմ (seed): Տվեք նույն սերմը նույն ալգորիթմին և ամեն անգամ կստանաք ճիշտ նույն հաջորդականությունը: Դա թուլություն է այնտեղ, որտեղ արդյունքը պետք է լինի անկանխատեսելի, իսկ սերմը կամ ներքին վիճակը հնարավոր է գուշակել կամ վերականգնել, և առավելություն է այնտեղ, որտեղ արդյունքը պետք է լինի վերարտադրելի, օրինակ՝ սիմուլյացիան կամ թեստը ճշգրտորեն կրկնելու համար: PRNG-ները նաև արագ են, էժան և հեշտ ներդրվող, ինչի պատճառով ծրագրային ապահովման մեծ մասը հենվում է հենց դրանց վրա: Հայտնի ալգորիթմներից են գծային կոնգրուենտային գեներատորը (LCG), xorshift գեներատորները և Mersenne Twister-ը:
Mersenne Twister
Mersenne Twister-ը, որը 1997 թվականին հրապարակել են Մակոտո Մացումոտոն և Տակուջի Նիշիմուրան, ամենաշատ օգտագործվող պսևդոպատահական գեներատորներից մեկն է և լռելյայն ընտրությունը բազմաթիվ ծրագրավորման լեզուներում: Նրա անունը գալիս է իր պարբերությունից՝ հաջորդականության երկարությունից մինչև կրկնվելը, որը ստանդարտ 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-ական տոկոս: Շեղումը վերացնելու եղանակներից մեկը չհամապատասխանող արժեքները դեն նետելն ու նորից ընտրելն է. պատահական թվերի գեներատորի նյութերը սա մանրամասն բացատրում են:
Եվս երկու բան հաճախ զարմացնում է մարդկանց: Կրկնությունները լիովին բնականոն են. երբ 1-ից 10 ամբողջ թիվը խաղարկվում է անկախ կերպով և յուրաքանչյուր թիվ ունի հավասար հավանականություն, նոր ընտրված թիվն ունի նույն 1-ը 10-ից հավանականությունը նորից դուրս գալու, ինչպես ցանկացած այլ թիվ: Առանց կրկնությունների խաղարկությունը պարզապես այլ տեսակի ընտրություն է, ոչ թե ավելի պատահական: Իսկ արդար գեներատորը միայնակ չի ապահովում ամբողջ ընթացակարգի արդարությունը. մասնակիցների ցուցակը և փորձերի քանակը նույնքան կարևոր են, ինչպես բացատրվում է մեր հոդվածում այն մասին, թե ինչպես պատահականորեն ընտրել մրցույթի հաղթողին: