ფსევდო შემთხვევითი რიცხვი არის სპეციალური რიცხვი, რომელიც გენერირებულია სპეციალური გენერატორის მიერ. Deterministic Random Bit Generator (PRNG), ასევე ცნობილი როგორც Deterministic Random Bit Generator (DRBG), არის ალგორითმი რიცხვების თანმიმდევრობის გენერირებისთვის, რომელთა თვისებები უხდება შემთხვევითი რიცხვების მიმდევრობის მახასიათებლებს. გენერირებული PRNG თანმიმდევრობა ნამდვილად არ არის შემთხვევითი, რადგან ის მთლიანად განისაზღვრება თესლის მნიშვნელობით, რომელსაც ეწოდება PRNG თესლი, რომელიც შეიძლება შეიცავდეს ჭეშმარიტად შემთხვევით მნიშვნელობებს. მიუხედავად იმისა, რომ მიმდევრობები, რომლებიც უფრო ახლოს არიან შემთხვევითობასთან, შეიძლება წარმოიქმნას ტექნიკის შემთხვევითი რიცხვების გენერატორების გამოყენებით, ფსევდო შემთხვევითი რიცხვების გენერატორები პრაქტიკაში მნიშვნელოვანია რიცხვების წარმოქმნის სიჩქარისა და მათი განმეორებადობისთვის.
აპლიკაცია
PRNG ცენტრალურია ისეთი აპლიკაციებისთვის, როგორიცაა სიმულაცია (მაგ. მონტე კარლოსთვის), ელექტრონული თამაშები (მაგ. პროცედურული გენერირებისთვის) და კრიპტოგრაფია. კრიპტოგრაფიული აპლიკაციები მოითხოვს, რომ გამომავალიმონაცემები არ იყო პროგნოზირებადი ადრინდელი ინფორმაციით. საჭიროა უფრო რთული ალგორითმები, რომლებიც არ დაიმკვიდრებენ მარტივი PRNG-ების წრფივობას.
წესები და პირობები
კარგი სტატისტიკური თვისებები ცენტრალური მოთხოვნაა PRNG-ის მისაღებად. ზოგადად, საჭიროა ფრთხილი მათემატიკური ანალიზი, რათა დარწმუნდეთ, რომ RNG წარმოქმნის რიცხვებს, რომლებიც საკმარისად ახლოსაა შემთხვევითობასთან, რათა იყოს შესაბამისი დანიშნულებისამებრ.
ჯონ ფონ ნოიმანმა გააფრთხილა PRNG, როგორც ჭეშმარიტად შემთხვევითი გენერატორის არასწორი ინტერპრეტაცია და ხუმრობდა, რომ "ვინც განიხილავს შემთხვევითი რიცხვების წარმოქმნის არითმეტიკულ მეთოდებს, რა თქმა უნდა, ცოდვის მდგომარეობაშია."
გამოიყენე
PRNG შეიძლება გაშვებული იყოს თვითნებური საწყისი მდგომარეობიდან. ის ყოველთვის გამოიმუშავებს იმავე თანმიმდევრობას ამ მდგომარეობით ინიციალიზაციისას. PRNG პერიოდი განისაზღვრება შემდეგნაირად: არაგანმეორებადი მიმდევრობის პრეფიქსის სიგრძის ყველა საწყის მდგომარეობაზე მაქსიმუმი. პერიოდი შემოიფარგლება მდგომარეობების რაოდენობით, რომელიც ჩვეულებრივ იზომება ბიტებში. იმის გამო, რომ პერიოდის სიგრძე პოტენციურად გაორმაგდება ყოველი "მდგომარეობის" ბიტის დამატებით, ადვილია PRNG-ების შექმნა მრავალი პრაქტიკული აპლიკაციისთვის საკმარისად დიდი პერიოდებით.
თუ PRNG-ის შიდა მდგომარეობა შეიცავს n ბიტს, მისი პერიოდი შეიძლება იყოს არაუმეტეს 2n შედეგი, ის გაცილებით მოკლეა. ზოგიერთი PRNG-ისთვის, ხანგრძლივობა შეიძლება გამოითვალოს მთელი პერიოდის გვერდის ავლით. ხაზოვანი უკუკავშირის Shift რეგისტრები (LFSRs) ჩვეულებრივ არისარჩეულია ისე, რომ ჰქონდეს პერიოდები ტოლი 2n − 1.
წრფივი კონგრუენციული გენერატორებს აქვთ პერიოდები, რომლებიც შეიძლება გამოითვალოს ფაქტორინგის გამოყენებით. მიუხედავად იმისა, რომ PPP გაიმეორებს თავის შედეგებს მას შემდეგ, რაც ისინი მიაღწევენ პერიოდის ბოლოს, განმეორებითი შედეგი არ ნიშნავს, რომ პერიოდის დასასრულია მიღწეული, რადგან მისი შიდა მდგომარეობა შეიძლება იყოს გამომუშავებაზე მეტი; ეს განსაკუთრებით აშკარაა PRNG-ებისთვის, რომლებსაც აქვთ ერთი ბიტიანი გამომავალი.
შესაძლო შეცდომები
დეფექტური PRNG-ების მიერ აღმოჩენილი შეცდომები მერყეობს დახვეწილიდან (და უცნობიდან) ცხადამდე. ამის მაგალითია RANDU შემთხვევითი რიცხვების ალგორითმი, რომელიც ათწლეულების განმავლობაში გამოიყენება მთავარ სისტემაზე. ეს იყო სერიოზული ხარვეზი, მაგრამ მისი არაადეკვატურობა შეუმჩნეველი დარჩა დიდი ხნის განმავლობაში.
ბევრ სფეროში, კვლევითი კვლევები, რომლებიც გამოიყენეს შემთხვევითი შერჩევა, მონტე კარლოს სიმულაციები ან სხვა მეთოდები, რომლებიც დაფუძნებულია RNG-ზე, გაცილებით ნაკლებად სანდოა, ვიდრე შეიძლება იყოს ცუდი ხარისხის GNPG-ის შედეგი. დღესაც კი ზოგჯერ საჭიროა სიფრთხილე, რასაც მოწმობს სტატისტიკური მეცნიერების საერთაშორისო ენციკლოპედიის გაფრთხილება (2010).
წარმატებული შემთხვევის შესწავლა
როგორც ილუსტრაცია, განიხილეთ ფართოდ გამოყენებული Java პროგრამირების ენა. 2017 წლის მდგომარეობით, ჯავა კვლავ ეყრდნობა ხაზოვან კონგრუენციალურ გენერატორს (LCG) თავისი PRNG-ისთვის.
ისტორია
პირველი 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-ის კრიპტოგრაფიული ვარგისიანობისთვის, მაგრამ არა ერთადერთი.
1946 წელს ჯონ ფონ ნეუმანის მიერ შემოთავაზებული ადრეული კომპიუტერული PRNG ცნობილია, როგორც საშუალო კვადრატების მეთოდი. ალგორითმი ასეთია: აიღეთ ნებისმიერი რიცხვი, კვადრატში, ამოიღეთ მიღებული რიცხვის შუა რიცხვები, როგორც "შემთხვევითი რიცხვი", შემდეგ გამოიყენეთ ეს რიცხვი, როგორც საწყისი რიცხვი შემდეგი გამეორებისთვის. მაგალითად, რიცხვი 1111 კვადრატში იძლევა1234321, რომელიც შეიძლება დაიწეროს როგორც 01234321, 8-ნიშნა რიცხვი არის 4-ნიშნა რიცხვის კვადრატი. ეს იძლევა 2343-ს, როგორც "შემთხვევით" რიცხვს. ამ პროცედურის გამეორების შედეგია 4896 და ა.შ. ფონ ნეუმანმა გამოიყენა 10 ციფრიანი რიცხვები, მაგრამ პროცესი იგივე იყო.
"შუა მოედნის" უარყოფითი მხარეები
პრობლემა "საშუალო კვადრატის" მეთოდთან არის ის, რომ ყველა თანმიმდევრობა საბოლოოდ მეორდება, ზოგიერთი ძალიან სწრაფად, მაგალითად: 0000. ფონ ნეუმანმა იცოდა ამის შესახებ, მაგრამ მან აღმოაჩინა მიდგომა საკმარისი მისი მიზნებისთვის და წუხდა, რომ მათემატიკური „შესწორებები“უბრალოდ მალავს შეცდომებს მათი წაშლის ნაცვლად.
ფონ ნეუმანმა აღმოაჩინა, რომ აპარატურის შემთხვევითი და ფსევდო შემთხვევითი რიცხვების გენერატორები შეუფერებელია: თუ ისინი არ ჩაიწერენ გენერირებულ გამომავალს, ისინი მოგვიანებით ვერ შემოწმდება შეცდომებზე. თუ ისინი ჩაწერდნენ თავიანთ შედეგებს, ისინი ამოწურავდნენ კომპიუტერის შეზღუდული ხელმისაწვდომ მეხსიერებას და, შესაბამისად, კომპიუტერის უნარს წაიკითხოს და ჩაწეროს რიცხვები. თუ ნომრები ეწერა ბარათებზე, მათ დაწერას და წაკითხვას გაცილებით მეტი დრო დასჭირდებოდა. ENIAC-ის კომპიუტერზე მან გამოიყენა „შუა კვადრატის“მეთოდი და ფსევდო შემთხვევითი რიცხვების მოპოვების პროცესი რამდენიმე ასეულჯერ უფრო სწრაფად განახორციელა, ვიდრე დარტყმული ბარათებიდან რიცხვების კითხვა.
საშუალო კვადრატი მას შემდეგ შეიცვალა უფრო რთული გენერატორებით.
ინოვაციური მეთოდი
უახლესი ინოვაცია არის საშუალო კვადრატის გაერთიანება ვეილის თანმიმდევრობასთან. ეს მეთოდი უზრუნველყოფს მაღალი ხარისხის პროდუქციას შიგნითხანგრძლივი პერიოდი. ის გვეხმარება საუკეთესო ფსევდო შემთხვევითი რიცხვების ფორმულების მიღებაში.
