რა არის შემთხვევითი რიცხვების გენერატორი?
შემთხვევითი რიცხვების გენერატორი (RNG) არის სისტემა, რომელიც წარმოქმნის შემთხვევით ან ფსევდოშემთხვევით რიცხვებს. შესაძლებელია თუ არა შემდეგი რიცხვის წინასწარ განჭვრეტა, დამოკიდებულია გენერატორის ტიპზე. ზოგიერთი გენერატორი ეყრდნობა ფიზიკურ პროცესს, ზოგი ითვლის რიცხვებს ალგორითმით, ხოლო ზოგიერთი ალგორითმი ისეა შექმნილი, რომ იმ ადამიანსაც კი, ვინც ნახა მათი შედეგები, არ შეუძლია გამოიცნოს შემდეგი მნიშვნელობა. შემთხვევითი შესახედაობა და წინასწარ განუჭვრეტლობა განსხვავებული თვისებებია, და ამ სტატიის უდიდესი ნაწილი სწორედ ამ განსხვავებას ეხება.
აპარატურული შემთხვევითი რიცხვების გენერატორები
აპარატურული შემთხვევითი რიცხვების გენერატორი (HRNG), რომელსაც ასევე უწოდებენ ჭეშმარიტად შემთხვევითი რიცხვების გენერატორს (TRNG), რიცხვებს ფიზიკური პროცესიდან იღებს. უძველესი მათგანი ჩვენ თვალწინ მუშაობს: აგდებული მონეტა, გაგორებული კამათელი, რულეტის ბორბალი. მექანიკა სრულად აღწერს თითოეულ მათგანს, თუმცა კარგად დამზადებული ბორბალი პრაქტიკაში მაინც განუჭვრეტელია, რადგან თითოეული დატრიალების საწყის ეტაპზე არსებული უმნიშვნელო განსხვავებები სრულიად განსხვავებულ შედეგებად გარდაიქმნება.
თანამედროვე აპარატურული გენერატორები სამაგიეროდ ზომავენ მიკროსკოპულ მოვლენებს: საფანტის ხმაურსა (shot noise) და თერმულ ხმაურს ელექტრონულ წრედებში, ატმოსფერულ ხმაურს, კვანტურ ეფექტებს. ეს ენტროპიის — გაზომვადი განუჭვრეტლობის — კარგი წყაროებია, მაგრამ ფიზიკური წყარო ბუნებით არ არის სრულყოფილი: ის შეიძლება იყოს გადახრილი, შეიძლება განიცადოს დრეიფი და შეიძლება გამოვიდეს მწყობრიდან, ამიტომ მისი ხარისხი უნდა შეფასდეს და კონტროლდებოდეს, ხოლო მისი გამომავალი მონაცემები საჭიროებისამებრ შემდგომ დამუშავდეს, როგორც ამას აღწერს ისეთი სტანდარტები, როგორიცაა 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% თითოეულს. ამ გადახრის (modulo bias) აღმოფხვრის ერთ-ერთი გზაა შეუსაბამო მნიშვნელობების უარყოფა და ხელახალი შერჩევა; შემთხვევითი რიცხვების გენერატორის მასალები ამას დეტალურად განიხილავს.
კიდევ ორი რამ აკვირვებს ხალხს. განმეორება ნორმალურია: როდესაც მთელი რიცხვი 1-დან 10-მდე შეირჩევა დამოუკიდებლად და თითოეული რიცხვი თანაბრად სავარაუდოა, ახლახან შერჩეულ რიცხვს აქვს ზუსტად იგივე 1 შანსი 10-დან ხელახლა ამოსვლისთვის, როგორც ნებისმიერ სხვას. გათამაშება გამეორების გარეშე არის განსხვავებული ტიპის გათამაშება და არა უფრო შემთხვევითი. და სამართლიანი გენერატორი თავისთავად არ ხდის მთელ პროცედურას სამართლიანს: მონაწილეთა სია და მცდელობების რაოდენობა ისეთივე მნიშვნელოვანია, როგორც ამას განმარტავს ჩვენი სტატია იმაზე, თუ როგორ ავირჩიოთ კონკურსის გამარჯვებული შემთხვევით.