Կեղծ պատահական թիվը հատուկ գեներատորի կողմից ստեղծված հատուկ թիվ է: Որոշիչ պատահական բիթերի գեներատորը (PRNG), որը նաև հայտնի է որպես որոշիչ պատահական բիթերի գեներատոր (DRBG), թվերի հաջորդականություն ստեղծելու ալգորիթմ է, որոնց հատկությունները մոտավոր են պատահական թվերի հաջորդականությունների բնութագրերին։ Ստեղծված PRNG հաջորդականությունը իսկապես պատահական չէ, քանի որ այն ամբողջությամբ որոշվում է սերմի արժեքով, որը կոչվում է PRNG սերմ, որը կարող է ներառել իսկապես պատահական արժեքներ: Չնայած այն հաջորդականությունները, որոնք ավելի մոտ են պատահականությանը, կարող են ստեղծվել՝ օգտագործելով ապարատային պատահական թվերի գեներատորներ, կեղծ պատահական թվերի գեներատորները գործնականում կարևոր են թվերի առաջացման արագության և դրանց վերարտադրելիության համար:
Դիմում
PRNG-ները առանցքային են այնպիսի ծրագրերի համար, ինչպիսիք են սիմուլյացիան (օրինակ՝ Մոնտե Կառլոյի համար), էլեկտրոնային խաղերը (օրինակ՝ ընթացակարգային ստեղծման համար) և ծածկագրությունը: Կրիպտոգրաֆիկ հավելվածները պահանջում են, որ ելքըտվյալները կանխատեսելի չէին ավելի վաղ տեղեկություններից։ Պահանջվում են ավելի բարդ ալգորիթմներ, որոնք չեն ժառանգում պարզ PRNG-ների գծայինությունը:
Պայմաններ և դրույթներ
Լավ վիճակագրական հատկությունները PRNG ստանալու կենտրոնական պահանջն են: Ընդհանուր առմամբ, զգույշ մաթեմատիկական վերլուծություն է անհրաժեշտ՝ համոզվելու համար, որ RNG-ն առաջացնում է թվեր, որոնք բավական մոտ են պատահականությանը, որպեսզի համապատասխանեն նախատեսված օգտագործմանը:
Ջոն ֆոն Նոյմանը նախազգուշացրեց PRNG-ը որպես իսկապես պատահական գեներատոր սխալ մեկնաբանելուց և կատակեց, որ «Ամեն ոք, ով հաշվի է առնում պատահական թվերի ստեղծման թվաբանական մեթոդները, անշուշտ մեղքի վիճակում է»:
:
Օգտագործել
PRNG-ը կարող է գործարկվել կամայական սկզբնական վիճակից: Այն միշտ կստեղծի նույն հաջորդականությունը, երբ սկզբնավորվում է այս վիճակով: PRNG ժամանակահատվածը սահմանվում է հետևյալ կերպ. չկրկնվող հաջորդականության նախածանցի երկարության բոլոր սկզբնական վիճակների առավելագույնը: Ժամանակահատվածը սահմանափակվում է վիճակների քանակով, որոնք սովորաբար չափվում են բիթերով: Քանի որ ժամանակաշրջանի երկարությունը պոտենցիալ կրկնապատկվում է յուրաքանչյուր «վիճակի» բիթով, հեշտ է ստեղծել PRNG-ներ՝ բավականաչափ մեծ ժամանակահատվածներով բազմաթիվ գործնական կիրառությունների համար:
Եթե PRNG-ի ներքին վիճակը պարունակում է n բիթ, ապա դրա ժամանակաշրջանը կարող է լինել ոչ ավելի, քան 2n արդյունք, այն շատ ավելի կարճ է: Որոշ PRNG-ների համար տեւողությունը կարելի է հաշվարկել՝ առանց ամբողջ ժամանակաշրջանը շրջանցելու: Գծային Հետադարձ կապի հերթափոխի գրանցամատյանները (LFSRs) սովորաբար լինում ենընտրված են այնպես, որ ունենան 2n − 1 պարբերակներ։
Գծային կոնգրուենցիալ գեներատորներն ունեն ժամանակաշրջաններ, որոնք կարող են հաշվարկվել ֆակտորինգի միջոցով: Թեև ՊՄԳ-ն կկրկնի իր արդյունքները ժամանակաշրջանի ավարտից հետո, սակայն կրկնվող արդյունքը չի նշանակում, որ ժամանակաշրջանի ավարտը հասել է, քանի որ դրա ներքին վիճակը կարող է ավելի մեծ լինել, քան արդյունքը. սա հատկապես ակնհայտ է մեկ բիթ ելքով PRNG-ների համար:
Հնարավոր սխալներ
Թերի PRNG-ների կողմից հայտնաբերված սխալները տատանվում են նուրբ (և անհայտ)ից մինչև ակնհայտ: Օրինակ է RANDU պատահական թվերի ալգորիթմը, որը տասնամյակներ շարունակ օգտագործվում է հիմնական սարքերում: Դա լուրջ թերություն էր, բայց դրա անբավարարությունը երկար ժամանակ աննկատ մնաց։
Շատ ոլորտներում հետազոտական ուսումնասիրությունները, որոնք օգտագործել են պատահական ընտրություն, Մոնտե Կառլոյի սիմուլյացիա կամ այլ մեթոդներ, որոնք հիմնված են RNG-ի վրա, շատ ավելի քիչ հուսալի են, քան կարող է լինել անորակ GNPG-ի արդյունք: Նույնիսկ այսօր երբեմն զգուշություն է պահանջվում, ինչի մասին վկայում է Վիճակագրական գիտության միջազգային հանրագիտարանի (2010) նախազգուշացումը.
Հաջողակ դեպքի ուսումնասիրություն
Որպես օրինակ, դիտարկենք լայնորեն օգտագործվող Java ծրագրավորման լեզուն: 2017 թվականի դրությամբ Java-ն իր PRNG-ի համար դեռևս ապավինում է Linear Congruential Generator-ին (LCG):
Պատմություն
Առաջին PRNG-ը, որը խուսափում է լուրջ խնդիրներից և դեռ բավականին արագ է աշխատում,Mersenne Twister-ն էր (քննարկվում է ստորև), որը լույս է տեսել 1998 թ. Այդ ժամանակից ի վեր մշակվել են բարձրորակ այլ PRNG-ներ:
Բայց կեղծ պատահական թվերի պատմությունն այսքանով չի ավարտվում։ 20-րդ դարի երկրորդ կեսին PRNG-ների համար օգտագործվող ալգորիթմների ստանդարտ դասը ներառում էր գծային կոնգրուենցիալ գեներատորներ։ Հայտնի էր, որ LCG-ի որակը անբավարար է, բայց ավելի լավ մեթոդներ հասանելի չեն եղել: Press et al (2007) նկարագրել է արդյունքը հետևյալ կերպ. «Եթե բոլոր գիտական աշխատությունները, որոնց արդյունքները կասկածի տակ են [LCG-ների և դրանց հետ կապված] պատճառով, անհետանան գրադարանի դարակներից, ապա յուրաքանչյուր դարակում ձեր բռունցքի չափի բացվածք կլինի»:
Պսևդոպատահական գեներատորների ստեղծման հիմնական ձեռքբերումը գծային ռեկուրենտի վրա հիմնված մեթոդների ներդրումն էր երկու տարրից բաղկացած դաշտում; այդպիսի օսլիլատորները միացված են գծային հետադարձ կապի հերթափոխի ռեգիստրներին: Դրանք հիմք են ծառայել կեղծ պատահական թվերի տվիչների հայտնագործման համար։
Մասնավորապես, 1997 թվականին Մերսեն Թվիսթերի գյուտը խուսափեց ավելի վաղ գեներատորների հետ կապված շատ խնդիրներից: Mersenne Twister-ն ունի 219937−1 կրկնությունների ժամանակաշրջան (≈4,3 × 106001): Ապացուցված է, որ այն հավասարաչափ բաշխված է (մինչև) 623 չափսերով (32-բիթանոց արժեքների համար), և իր ներդրման պահին ավելի արագ էր, քան այլ վիճակագրական ձայնային գեներատորներ, որոնք արտադրում են կեղծ պատահական թվերի հաջորդականություն:
:
2003 թվականին Ջորջ Մարսալիան ներկայացրեց xorshift գեներատորների ընտանիքը, որը նույնպես հիմնված էր գծային կրկնության վրա: Այս գեներատորները չափազանցարագ են և, զուգակցված ոչ գծային գործողության հետ, նրանք անցնում են խիստ վիճակագրական թեստեր:
2006 թվականին ստեղծվեց WELL գեներատորների ընտանիքը: WELL գեներատորներն ինչ-որ իմաստով բարելավում են Twister Mersenne-ի որակը, որն ունի չափազանց մեծ վիճակի տարածություն և դրանցից շատ դանդաղ վերականգնում, առաջացնելով կեղծ պատահական թվեր՝ բազմաթիվ զրոներով:
Գաղտնագրություն
PRNG-ը, որը հարմար է ծածկագրային հավելվածների համար, կոչվում է կրիպտոգրաֆիկորեն ապահով PRNG (CSPRNG): CSPRNG-ի պահանջն այն է, որ հարձակվողը, ով չգիտի սերմը, ունի միայն սահմանային առավելություն՝ գեներատորի ելքային հաջորդականությունը պատահական հաջորդականությունից տարբերելու հարցում: Այլ կերպ ասած, մինչդեռ PRNG-ը պահանջվում է միայն որոշակի վիճակագրական թեստեր անցնելու համար, CSPRNG-ը պետք է անցնի բոլոր վիճակագրական թեստերը, որոնք սահմանափակված են բազմանդամ ժամանակով սերմի չափով:
Չնայած այս հատկության ապացույցը դուրս է հաշվողական բարդության տեսության ներկա մակարդակից, կարելի է ամուր ապացույցներ տրամադրել՝ նվազեցնելով CSPRNG-ը մի խնդրի, որը համարվում է դժվար, օրինակ՝ ամբողջ թվերի ֆակտորիզացիան: Ընդհանուր առմամբ, կարող է պահանջվել տարիների վերանայում, նախքան ալգորիթմը որպես CSPRNG հավաստագրվելը:
Ցույց է տրվել, որ հավանական է, որ NSA-ն ասիմետրիկ հետևի դուռ է մտցրել NIST հավաստագրված Dual_EC_DRBG կեղծ պատահական թվերի գեներատորի մեջ:
Կեղծ-պատահական ալգորիթմներթվեր
PRNG ալգորիթմների մեծ մասը արտադրում են հաջորդականություններ, որոնք հավասարաչափ բաշխված են մի քանի թեստերից որևէ մեկի միջոցով: Սա բաց հարց է։ Այն կրիպտոգրաֆիայի տեսության և պրակտիկայում կենտրոնականներից մեկն է. կա՞ տարբերակ բարձրորակ PRNG-ի ելքը իսկապես պատահական հաջորդականությունից: Այս պարամետրում լուծիչը գիտի, որ կամ օգտագործվել է հայտնի PRNG ալգորիթմ (բայց ոչ այն վիճակը, որով սկզբնավորվել է), կամ օգտագործվել է իսկապես պատահական ալգորիթմ: Նա պետք է տարբերի դրանք:
Գրիպտոգրաֆիկ ալգորիթմների և արձանագրությունների մեծ մասի անվտանգությունը, որոնք օգտագործում են PRNG-ներ, հիմնված է այն ենթադրության վրա, որ անհնար է տարբերակել հարմար PRNG-ի օգտագործումը և իսկապես պատահական հաջորդականության օգտագործումը: Այս կախվածության ամենապարզ օրինակներն են հոսքային ծածկագրերը, որոնք առավել հաճախ աշխատում են՝ բաց թողնելով կամ ուղարկելով պարզ տեքստային հաղորդագրություն PRNG ելքով՝ արտադրելով գաղտնագրված տեքստ: Կրիպտոգրաֆիկորեն համարժեք PRNG-ների նախագծումը չափազանց դժվար է, քանի որ դրանք պետք է համապատասխանեն լրացուցիչ չափանիշներին: Դրա ժամանակաշրջանի չափը կարևոր գործոն է PRNG-ի գաղտնագրային համապատասխանության համար, բայց ոչ միակը:
Վաղ համակարգչային PRNG-ն, որն առաջարկվել է Ջոն ֆոն Նեյմանի կողմից 1946 թվականին, հայտնի է որպես միջին քառակուսիների մեթոդ: Ալգորիթմը հետևյալն է՝ վերցրեք ցանկացած թիվ, քառակուսիացրեք այն, ստացված թվի միջին թվերը հանեք որպես «պատահական թիվ», այնուհետև օգտագործեք այս թիվը որպես մեկնարկային թիվ հաջորդ կրկնության համար։ Օրինակ՝ 1111 թիվը քառակուսելով տալիս է1234321, որը կարելի է գրել 01234321, 8 նիշանոց թիվը քառանիշ թվի քառակուսին է։ Սա տալիս է 2343 որպես «պատահական» թիվ։ Այս պրոցեդուրան կրկնելու արդյունքը 4896 է և այլն։ Ֆոն Նոյմանը օգտագործեց 10 նիշ թվեր, բայց գործընթացը նույնն էր։
«միջին քառակուսու» թերությունները
«միջին քառակուսի» մեթոդի խնդիրն այն է, որ բոլոր հաջորդականությունները, ի վերջո, կրկնվում են, որոշները շատ արագ, օրինակ՝ 0000: Ֆոն Նեյմանը գիտեր այս մասին, բայց նա գտավ իր նպատակների համար բավարար մոտեցում և անհանգստացավ, որ մաթեմատիկական «ուղղումները» պարզապես կթաքցնեն սխալները՝ դրանք հեռացնելու փոխարեն:
Von Neumann-ը գտել է, որ ապարատային պատահական և կեղծ պատահական թվերի գեներատորներն անհամապատասխան են. Եթե նրանք գրեին իրենց արդյունքները, նրանք կսպառեին համակարգչի սահմանափակ հասանելի հիշողությունը և, հետևաբար, համակարգչի՝ թվեր կարդալու և գրելու կարողությունը: Եթե թվերը գրված լինեին քարտերի վրա, ապա դրանք գրելու և կարդալու համար շատ ավելի երկար ժամանակ կպահանջվեր: ENIAC համակարգչի վրա նա օգտագործել է «միջին քառակուսի» մեթոդը և իրականացրել կեղծ պատահական թվեր ստանալու գործընթացը մի քանի հարյուր անգամ ավելի արագ, քան դակված քարտերից թվեր կարդալը։
Միջին քառակուսին այդ ժամանակվանից փոխարինվել է ավելի բարդ գեներատորներով:
Նորարար մեթոդ
Վերջին նորամուծությունը միջին քառակուսի միավորելն է Վեյլի հաջորդականության հետ: Այս մեթոդը ապահովում է բարձրորակ արտադրանքի ներսումերկար ժամանակաշրջան. Այն օգնում է ստանալ կեղծ պատահական թվերի լավագույն բանաձևերը:
