Хуурамч санамсаргүй тоо нь тусгай генератороор үүсгэгдсэн тусгай тоо юм. Deterministic Random Bit Generator (PRNG), мөн Deterministic Random Bit Generator (DRBG) гэж нэрлэдэг бөгөөд шинж чанар нь санамсаргүй тооны дарааллын шинж чанаруудтай ойролцоо тоонуудын дарааллыг үүсгэх алгоритм юм. Үүсгэсэн PRNG дараалал нь PRNG үр гэж нэрлэгддэг үрийн утгаар бүхэлдээ тодорхойлогддог тул үнэхээр санамсаргүй биш юм. Техник хангамжийн санамсаргүй тоо үүсгэгчийг ашиглан санамсаргүйд илүү ойр дарааллыг үүсгэж болох ч псевдо санамсаргүй тоо үүсгэгч нь тоо үүсгэх хурд болон тэдгээрийн дахин үржих чадварт чухал ач холбогдолтой.
Програм
PRNG нь симуляци (жишээ нь Монте Карлогийн хувьд), цахим тоглоом (жишээ нь процедурын хувьд), криптограф зэрэг програмуудад гол үүрэг гүйцэтгэдэг. Криптографийн програмууд нь гаралтыг шаарддагӨмнөх мэдээллээс өгөгдлийг урьдчилан таамаглах боломжгүй байсан. Энгийн PRNG-ийн шугаман байдлыг өвлөн авдаггүй илүү нарийн төвөгтэй алгоритмууд шаардлагатай.
Үйлчилгээний нөхцөл
Сайн статистик шинж чанарууд нь PRNG авах гол шаардлага юм. Ерөнхийдөө RNG нь зориулалтын дагуу ашиглахад тохиромжтой санамсаргүй тоонуудын ойролцоо тоонуудыг үүсгэдэг гэдэгт итгэлтэй байхын тулд нарийн математикийн шинжилгээ хийх шаардлагатай.
Жон фон Нейман PRNG-г үнэхээр санамсаргүй үүсгүүр гэж буруу тайлбарлахаас сэрэмжлүүлж, "Санамсаргүй тоо гаргах арифметик аргуудыг авч үздэг хүн нүгэл үйлдсэн байх нь гарцаагүй."
Ашиглах
PRNG-г дурын анхны төлөвөөс эхлүүлэх боломжтой. Энэ төлөвийг эхлүүлэх үед энэ нь үргэлж ижил дарааллыг үүсгэх болно. PRNG үеийг дараах байдлаар тодорхойлно: давтагдахгүй дарааллын угтварын уртын бүх эхний төлөвт хамгийн их байна. Хугацаа нь төлөвийн тоогоор хязгаарлагддаг бөгөөд ихэвчлэн битээр хэмжигддэг. "Төлөв" бит нэмэгдэх тусам хугацааны урт хоёр дахин нэмэгдэж болзошгүй тул олон практик хэрэглээнд хангалттай том хугацаатай PRNG үүсгэхэд хялбар байдаг.
Хэрэв PRNG-ийн дотоод төлөвт n бит байгаа бол түүний хугацаа нь 2n үр дүнгээс илүүгүй байж болно, энэ нь хамаагүй богино байна. Зарим PRNG-ийн хувьд үргэлжлэх хугацааг бүхэлд нь тойрч гарахгүйгээр тооцоолж болно. Linear Feedback Shift Registers (LFSRs) нь ихэвчлэн байдаг2n − 1-тэй тэнцүү үетэй байхаар сонгосон.
Шугаман конгрюциал генераторууд нь факторинг ашиглан тооцоолж болох үетэй байдаг. Хэдийгээр хугацааны төгсгөлд хүрсний дараа ТХХТ үр дүнгээ давтах боловч давтан үр дүн нь хугацааны төгсгөлд хүрсэн гэсэн үг биш, учир нь түүний дотоод төлөв нь гарцаас илүү байж болно; Энэ нь ялангуяа нэг битийн гаралттай PRNG-д тод харагдаж байна.
Боломжтой алдаа
Гэмтэлтэй PRNG-ийн олсон алдаа нь нарийн (болон үл мэдэгдэх)-ээс илт хүртэл хэлбэлздэг. Жишээ нь олон арван жилийн турш үндсэн фрэймүүд дээр ашиглагдаж ирсэн RANDU санамсаргүй тооны алгоритм юм. Энэ нь ноцтой дутагдал байсан ч түүний хангалтгүй байдал удаан хугацаанд анзаарагдахгүй байсан.
Олон салбарт санамсаргүй сонголт, Монте-Карлогийн симуляци эсвэл RNG дээр суурилсан бусад аргуудыг ашигласан судалгааны судалгаа нь чанар муутай GNPG-ийн үр дагавар байж болохоос хамаагүй бага найдвартай байдаг. Өнөөдөр ч гэсэн заримдаа болгоомжтой байх шаардлагатай байдаг нь Олон улсын статистикийн нэвтэрхий толь бичигт (2010) гардаг.
Амжилттай жишээ судалгаа
Жишээ болгон өргөн хэрэглэгддэг Java програмчлалын хэлийг авч үзье. 2017 оны байдлаар Java нь PRNG-дээ Шугаман конгруциональ генератор (LCG) дээр тулгуурласан хэвээр байна.
Түүх
Ноцтой асуудлаас зайлсхийж, маш хурдан ажилладаг анхны PRNG,нь 1998 онд хэвлэгдсэн Mersenne Twister (доор хэлэлцэх) байсан. Түүнээс хойш бусад өндөр чанартай PRNG-г боловсруулсан.
Гэхдээ псевдо санамсаргүй тооны түүх үүгээр дуусахгүй. 20-р зууны хоёрдугаар хагаст PRNG-д хэрэглэгддэг стандарт алгоритмын ангилалд шугаман конгруциал генераторууд багтсан. LCG-ийн чанар хангалтгүй байгаа нь мэдэгдэж байсан ч илүү сайн арга байхгүй байв. Press et al (2007) үр дүнг дараах байдлаар тайлбарлав: "Хэрэв [LCG болон холбогдох]-ын улмаас үр дүн нь эргэлзээтэй байгаа бүх шинжлэх ухааны баримтууд номын сангийн тавиураас алга болсон бол тавиур бүр дээр таны нударганы хэмжээтэй зай гарах болно."
Псевдо санамсаргүй генераторыг бий болгох гол ололт нь хоёр элементийн талбарт шугаман давталт дээр суурилсан аргуудыг нэвтрүүлсэн явдал байв; ийм осцилляторууд нь шугаман эргэх холбоо бүхий шилжилтийн регистрүүдтэй холбогддог. Эдгээр нь псевдо санамсаргүй тооны мэдрэгчийг зохион бүтээх үндэс суурь болсон.
Ялангуяа, 1997 онд Мерсен Твистерийн шинэ бүтээл нь өмнөх генераторуудтай холбоотой олон асуудлаас зайлсхийсэн. Mersenne Twister нь 219937−1 давталтын хугацаатай (≈4.3 × 106001). Энэ нь (32 битийн утгын хувьд) 623 хэмжээст (хүртэл) жигд тархсан болох нь батлагдсан бөгөөд түүнийг нэвтрүүлэх үед псевдо санамсаргүй тооны дараалал үүсгэдэг бусад статистикийн үндэслэлтэй генераторуудаас хурдан байсан.
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-ийн криптографийн тохиромжтой байдлын чухал хүчин зүйл боловч цорын ганц хүчин зүйл биш юм.
1946 онд Жон фон Нейманы санал болгосон анхны компьютерийн PRNG-ийг дундаж квадратын арга гэж нэрлэдэг. Алгоритм нь дараах байдалтай байна: дурын тоог авч, квадрат болгож, үүссэн тооны дундах цифрүүдийг "санамсаргүй тоо" болгон хасч, дараа нь энэ тоог дараагийн давталтын эхний дугаар болгон ашигла. Жишээлбэл, 1111 тоог квадрат болгоход гарч ирнэ01234321 гэж бичиж болох 1234321, 8 оронтой тоо нь 4 оронтой тооны квадрат юм. Энэ нь 2343-ыг "санамсаргүй" тоо болгож өгдөг. Энэ процедурыг давтах үр дүн нь 4896 гэх мэт. Фон Нейман 10 оронтой тоо ашигласан ч үйл явц нь ижил байсан.
"дунд дөрвөлжин"-ийн сул тал
"Дундаж квадрат"-ын аргын асуудал бол бүх дараалал нь эцэстээ давтагддаг, зарим нь маш хурдан давтагддаг, жишээ нь: 0000. Фон Нейман үүнийг мэддэг байсан ч зорилгодоо хүрэх хангалттай арга замыг олж хараад санаа зовж байв. математикийн "засвар" нь алдааг арилгахын оронд зүгээр л нуух болно.
Вон Нейман техник хангамжийн санамсаргүй болон псевдо-санамсаргүй тоо үүсгэгчийг тохиромжгүй гэж үзсэн: хэрэв тэдгээр нь үүсгэсэн гаралтыг бүртгээгүй бол дараа нь алдаа байгаа эсэхийг шалгах боломжгүй. Хэрэв тэд үр дүнгээ бичих юм бол компьютерийн хязгаарлагдмал санах ойг шавхаж, улмаар компьютерийн тоо унших, бичих чадварыг шавхах болно. Хэрэв тоонуудыг карт дээр бичсэн бол бичих, уншихад илүү их хугацаа шаардагдах болно. ENIAC компьютер дээрээ "дунд дөрвөлжин" аргыг ашиглаж, псевдо санамсаргүй тоо авах процессыг цоолбортой картнаас тоо уншихаас хэдэн зуу дахин хурдан хийжээ.
Дундаж квадратыг илүү нарийн төвөгтэй генераторууд орлуулсан.
Шинэлэг арга
Сүүлийн үеийн шинэлэг зүйл бол дундаж квадратыг Вайлийн дараалалтай хослуулах явдал юм. Энэ арга нь дотроо өндөр чанартай бүтээгдэхүүнийг баталгаажуулдагурт хугацаа. Энэ нь хамгийн сайн псевдо санамсаргүй тооны томьёог авахад тусална.
