यादृच्छिक संख्या जनरेटर

कंप्यूटर यादृच्छिकता का संक्षिप्त इतिहास

कंप्यूटर निश्चयात्मक मशीनें हैं, जो "यादृच्छिक" को उनके लिए उत्पन्न करना अजीब बनाती हैं। कंप्यूटरों पर छद्म यादृच्छिक संख्या जनरेटरों (PRNG) का इतिहास 1946 में John von Neumann की मध्य-वर्ग विधि से शुरू होता है: पिछले अंक का वर्ग करें, बीच के अंकों को नया मान लें, दोहराएँ। von Neumann ने स्वयं इसे "पापपूर्ण अवस्था" कहा था, यदि आप उन्हें पूरी तरह न समझें तो किसी भी प्रकार के यादृच्छिक संख्या जनरेटर का उपयोग न करना, क्योंकि मध्य-वर्ग के स्पष्ट विफलता मोड हैं (शून्य पर वापस चक्र, छोटे आवर्तन)। Lehmer का रैखिक सर्वांगसम जनरेटर (LCG, 1951), x_(n+1) = (a × x_n + c) mod m, उचित सांख्यिकीय गुणधर्मों वाला PRNG का पहला परिवार था; C मानक पुस्तकालय का rand() आज भी आमतौर पर LCG संस्करण उपयोग करता है। Mersenne Twister (Matsumoto और Nishimura, 1997-1998) ने हमें 2¹⁹⁹³⁷−1 की अवधि वाला जनरेटर दिया (हाँ, 6,000 अंकों की संख्या) और उत्कृष्ट सांख्यिकीय गुण; यह Python, R, MATLAB, PHP और कई अन्य भाषाओं में डिफ़ॉल्ट बना। Marsaglia का xorshift परिवार (2003) कहीं अधिक तेज़ है और इतना छोटा कि हार्डवेयर रजिस्टर में फ़िट हो जाए; आधुनिक V8 (Chrome का JavaScript इंजन) Math.random() के लिए xorshift128+ संस्करण का उपयोग करता है। PCG (Permuted Congruential Generator) Melissa O'Neill (2014) द्वारा गैर-क्रिप्टोग्राफ़िक PRNG के लिए वर्तमान सांख्यिकीय शीर्ष-कला है, जो LCG-शैली राज्य-प्रगति को आउटपुट क्रमचय के साथ संयोजित करके कम लागत पर उत्कृष्ट सांख्यिकीय गुण देता है।

क्रिप्टोग्राफ़िक रूप से सुरक्षित PRNG (CSPRNG) एक अलग जानवर हैं। परिभाषित विशेषता: यदि कोई हमलावर जनरेटर द्वारा उत्पादित प्रत्येक आउटपुट जानता हो, तब भी वह नगण्य लाभ से अधिक के साथ अगला आउटपुट नहीं भविष्यवाणी कर सकता। Linux का getrandom() syscall (कर्नेल 3.17, अक्टूबर 2014 में जोड़ा गया) और अंतर्निहित /dev/urandom ChaCha20-आधारित जनरेटर का उपयोग करते हैं, जिसे हार्डवेयर एन्ट्रॉपी स्रोतों (RDRAND, इंटरप्ट टाइमिंग, ऑडियो शोर) से सीड किया जाता है। Windows BCryptGenRandom AES-CTR-DRBG रचना (NIST SP 800-90A) का उपयोग करता है, जो कई एन्ट्रॉपी स्रोतों से सीड होती है। macOS / iOS Fortuna-व्युत्पन्न CSPRNG का उपयोग करते हैं। PRNG और CSPRNG के बीच का अंतर बहुत मायने रखता है: एक PRNG खेल यादृच्छिकता, A/B परीक्षण बकेटिंग या सिमुलेशन के लिए ठीक है; ऐसी किसी भी चीज़ के लिए जिसे एक हमलावर भविष्यवाणी करने की कोशिश कर सकता है (सत्र टोकन, पासवर्ड जनरेशन, सुरक्षा ID), केवल CSPRNG सुरक्षित है।

JavaScript के दो यादृच्छिक API

Math.random() पुराना, सरल API है, [0, 1) में लगभग एक समान वितरित एक फ़्लोटिंग-पॉइंट संख्या लौटाता है। ECMAScript विनिर्देश ज़मीनी एल्गोरिथ्म को जानबूझकर अनिर्दिष्ट छोड़ता है ("approximately uniform distribution between 0 and 1, exclusive"), और इंजन वर्षों से जो उपयोग करते हैं उसे बदलते रहे हैं। V8 (Chrome) ने 2015 तक Park-Miller LCG उपयोग किया, फिर बेहतर सांख्यिकीय गुणों के लिए xorshift128+ पर स्विच किया। SpiderMonkey (Firefox) और JavaScriptCore (Safari) समान तेज़ गैर-क्रिप्टोग्राफ़िक जनरेटर का उपयोग करते हैं। Math.random() गेम मैकेनिक्स, सिमुलेशन और किसी भी अनुप्रयोग के लिए तेज़ और पर्याप्त एक समान है जहाँ अप्रत्याशितता कोई सुरक्षा आवश्यकता नहीं है। यह क्रिप्टोग्राफ़िक रूप से सुरक्षित नहीं है, अवधि कार्यान्वयन-परिभाषित है, स्थिति को कुछ आउटपुटों से पुनः प्राप्त किया जा सकता है, और अनुक्रम पासवर्ड जनरेशन या सुरक्षा-संवेदी उपयोग के मामलों के लिए सुरक्षित नहीं है। crypto.getRandomValues() Web Crypto API का CSPRNG है। यह एक टाइप किए गए ऐरे को क्रिप्टोग्राफ़िक रूप से सुरक्षित यादृच्छिक बाइट्स से भरता है, जो ऑपरेटिंग सिस्टम के CSPRNG से लिए जाते हैं (वही स्रोत जिसे TLS सत्र कुंजियों के लिए उपयोग करता है)। लगभग 2014 से सभी आधुनिक ब्राउज़रों में उपलब्ध; एक कॉल में अधिकतम बफ़र आकार 65,536 बाइट्स है। किसी भी यादृच्छिक संख्या के लिए सही विकल्प जो मायने रखती है, टोकन जनरेशन, सुरक्षा ID, पासवर्ड जनरेशन, ऐसी कोई भी चीज़ जिसे एक हमलावर भविष्यवाणी करने की कोशिश कर सकता है।

मॉड्यूलो बायस का जाल

CSPRNG से किसी विशिष्ट सीमा में एक समान पूर्णांक उत्पन्न करना दिखने से कठिन है। भोला तरीका, एक डाई रोल के लिए crypto.getRandomValues(new Uint8Array(1))[0] % 6, एक पक्षपातपूर्ण वितरण उत्पन्न करता है क्योंकि 256 6 से समान रूप से विभाजित नहीं होता। मान 0-3 0-255 सीमा में 43 बार होते हैं; मान 4-5 42 बार होते हैं। पक्षपात छोटी सीमाओं के लिए छोटा है पर वास्तविक है, और लंबे रन में पता लगाने योग्य है। मानक सुधार है अस्वीकृति प्रतिचयन: एक यादृच्छिक बाइट उत्पन्न करें, परीक्षण करें कि यह आपकी सीमा के सबसे बड़े गुणक में आता है या नहीं जो फ़िट हो (यहाँ, 252 = 42 × 6), यदि हाँ तो उपयोग करें, यदि नहीं तो फेंक दें और फिर से प्रयास करें। फेंकने की दर (सीमा / अगली 2 की घात) से सीमित है, इसलिए "1-6" के लिए आप लगभग 1.5 % बाइट्स बर्बाद करते हैं; "1-1000000" के लिए 32-बिट यादृच्छिक int के विरुद्ध आप लगभग 0.02 % बर्बाद करते हैं। हर गंभीर यादृच्छिक पुस्तकालय अस्वीकृति प्रतिचयन लागू करता है; Math.random()-आधारित Math.floor(Math.random() * (max - min + 1)) + min पक्षपात से बचता है क्योंकि Math.random() की सटीकता इतनी अधिक है (53 बिट मंटिसा) कि किसी भी उचित सीमा के लिए पक्षपात मानवीय रूप से पता लगाने योग्य स्तर से नीचे है। यह जनरेटर अस्वीकृति प्रतिचयन के साथ CSPRNG आउटपुट का उपयोग करता है, आपके अनुरोधित किसी भी पूर्णांक श्रेणी पर एक समान आउटपुट।

उपयोग के मामले और प्रत्येक के लिए यादृच्छिकता का स्तर

• लॉटरी और रैफ़ल चयन। गैर-मौद्रिक चयनों के लिए (कार्यालय अदला-बदली, हैकाथॉन टीम असाइनमेंट, कक्षा बैठक), Math.random() ठीक है। मौद्रिक चयनों या किसी भी विनियमित चीज़ के लिए, CSPRNG का उपयोग करें और आदर्श रूप से सत्यापन हेतु बीज प्रकाशित करें।
• खेल मैकेनिक्स। डाइस रोल, कार्ड फेंट, लूट ड्रॉप, प्रक्रियात्मक जनरेशन। Math.random() मानक विकल्प है, तेज़, पर्याप्त एक समान, इतना अप्रत्याशित कि खिलाड़ी पैटर्न नहीं देखेंगे। CSPRNG ऑनलाइन कार्ड खेलों के लिए आरक्षित हैं जहाँ सर्वर पक्ष को धोखाधड़ी रोकनी चाहिए।
• A/B परीक्षण के लिए बकेट असाइनमेंट। प्रत्येक उपयोगकर्ता को निश्चयात्मक रूप से एक बकेट में रखने के लिए स्थिर रहस्य के साथ उपयोगकर्ता ID का हैश करें, Math.random() उपयोग करना मतलब उपयोगकर्ता पृष्ठ लोड के बीच विभिन्न बकेट्स में पहुँचेगा, जो प्रयोग को नष्ट कर देगा। हैश-आधारित असाइनमेंट सही पैटर्न है; यादृच्छिकता का उपयोग केवल प्रयोग बीज चुनने के लिए, एक बार होता है।
• सर्वेक्षणों के लिए यादृच्छिक प्रतिचयन। जनसंख्या से प्रतिनिधि उपसमुच्चय निकालना। Math.random() ठीक है; सांख्यिकीय प्रश्न यह है कि क्या आपका नमूना पर्याप्त बड़ा है, न कि क्या यादृच्छिक स्रोत क्रिप्टोग्राफ़िक है।
• परीक्षण डेटा जनरेशन। Faker, मॉकअप डेटा, सिंथेटिक डेटाबेस फ़िक्सचर। Math.random() एक निश्चित बीज (पुनरुत्पादन के लिए) के साथ सही विकल्प है।
• क्रिप्टोग्राफ़िक कुंजियाँ, सत्र टोकन, पासवर्ड जनरेशन। केवल CSPRNG, ब्राउज़र में crypto.getRandomValues(), Python में secrets मॉड्यूल, Go में crypto/rand, कभी भी भाषा का डिफ़ॉल्ट यादृच्छिक नहीं। इस परत में बग उस पर निर्भर सब कुछ संकटपूर्ण कर देता है; परिणाम "सबकी सत्र हाइजैक हो सकती है" से लेकर "एन्क्रिप्शन कुंजी पुनः प्राप्त की जा सकती है" तक होते हैं।

RANDOM.ORG और सच्ची यादृच्छिकता का अंतर

RANDOM.ORG Mads Haahr ने 1998 में Trinity College Dublin में लॉन्च किया था और ऑनलाइन "सच्ची यादृच्छिकता" का स्वर्ण मानक बना हुआ है। जहाँ हर CSPRNG अंततः अपने बिट हार्डवेयर-सीडेड स्थिति के एल्गोरिदमिक रूपांतरणों से प्राप्त करता है (एक निश्चयात्मक प्रक्रिया, भले ही हमलावर के लिए अप्रत्याशित), RANDOM.ORG रेडियो रिसीवरों से वायुमंडलीय शोर को मापता है और एनालॉग शोर को सीधे बिट्स में परिवर्तित करता है। यह इसे छद्म-यादृच्छिक संख्या जनरेटर के बजाय True Random Number Generator (TRNG) बनाता है: बिट्स एक भौतिक प्रक्रिया से आते हैं जो वास्तव में गैर-निश्चयात्मक है, निश्चयात्मक एल्गोरिथ्म से नहीं। RANDOM.ORG का उपयोग लॉटरी संचालक, डबल-ब्लाइंड अध्ययन चलाने वाले शैक्षणिक शोधकर्ता और ऐसे खेल करते हैं जहाँ सत्यापन योग्य यादृच्छिकता मायने रखती है। समझौता: प्रति अनुरोध एक नेटवर्क राउंड-ट्रिप, मुफ़्त स्तर के लिए दैनिक कोटा, और दार्शनिक प्रश्न कि क्या आप RANDOM.ORG के दावा किए गए एन्ट्रॉपी स्रोत पर अपने स्थानीय CSPRNG से अधिक भरोसा करते हैं। अधिकांश उपयोग के मामलों के लिए स्थानीय CSPRNG पर्याप्त है; उन मामलों के लिए जहाँ तीसरे पक्ष को स्वतंत्र रूप से यादृच्छिकता की पुष्टि करनी होती है, RANDOM.ORG भुगतान सेवा के रूप में यादृच्छिकता के हस्ताक्षरित प्रमाणपत्र प्रदान करता है।

बिना प्रतिस्थापन के प्रतिचयन, Fisher-Yates फेंट

जब आपको किसी सीमा से N अद्वितीय संख्याएँ चाहिए, लॉटरी के लिए 1-49 से 6 संख्याएँ खींचना, 1000 प्रतिभागियों में से 10 विजेता चुनना, भोला "उत्पन्न करें और डुप्लिकेट हो तो अस्वीकार करें" छोटे N के लिए काम करता है पर तेजी से बिगड़ता है जब N सीमा-आकार के निकट पहुँचता है (जैसे-जैसे पूल सिकुड़ता है, ताज़ा संख्या निकलने का अवसर घटता है)। मानक एल्गोरिथ्म Fisher-Yates फेंट है, जो Fisher और Yates की 1938 की सांख्यिकीय तालिकाओं से उत्पन्न हुआ और 1969 में Donald Knuth द्वारा अपने आधुनिक कंप्यूटर-विज्ञान रूप में प्रस्तुत किया गया (कभी-कभी Knuth shuffle कहलाता है)। एल्गोरिथ्म बेहद सरल है: संख्या 1 से N तक एक ऐरे में लिखें; N-1 से 1 तक i के लिए, तत्व i को 0 और i (समावेशी) के बीच एक यादृच्छिक तत्व के साथ अदला-बदल करें; ऐरे अब समान रूप से फेंटा गया है। K अद्वितीय यादृच्छिक संख्याओं के लिए पहले K तत्व लें। महत्वपूर्ण विवरण: यादृच्छिक सूचकांक [0, i] में होना चाहिए, समावेशी, [0, i-1] का उपयोग एक सूक्ष्म पक्षपात लाता है जिसे क्रिप्टोग्राफ़ी समुदाय को दर्शाने में वर्षों लगे (Sattolo संस्करण, कभी-कभी सच्चे Fisher-Yates के बजाय गलती से उपयोग किया जाता है)। बहुत बड़ी सीमाओं के लिए जहाँ सभी N मानों का ऐरे आवंटित करना अव्यावहारिक हो (जैसे 1-10⁹ से 100 अद्वितीय मान चुनना), जलाशय प्रतिचयन (Vitter, 1985) सीमित मेमोरी के साथ एकल-पास में स्ट्रीमिंग या असीम इनपुट को संभालता है।

डाइस रोल परंपराएँ

यादृच्छिक संख्या जनरेटर भेस में डाइस हैं। D6 (छह-तरफ़ा डाई) बोर्डगेम का सार्वभौमिक डिफ़ॉल्ट है, सीमा 1-6। D20 (बीस-तरफ़ा डाई) Dungeons & Dragons की प्रतिष्ठित डाई है जो योग्यता जाँच, हमले के रोल और बचाव रोल के लिए उपयोग होती है, D&D की मॉडिफ़ायर प्रणाली का अर्थ है कि एक एकल D20 रोल और स्टैट बोनस अधिकांश क्रियाओं का परिणाम तय करते हैं। D100 (प्रतिशत, 1-100) Call of Cthulhu, Warhammer Roleplay और कई crit-chance सिस्टम में प्रतिशत रोल के लिए उपयोग होता है। नोटेशन NdM का अर्थ है "प्रत्येक M पक्षों वाली N डाइस फेंकें और जोड़ें"; NdM+B एक बोनस जोड़ता है। 3d6 तीन छह-तरफ़ा डाइस फेंकता है और जोड़ता है (सीमा 3-18, क्लासिक D&D योग्यता-स्कोर सीमा, 10-11 पर केन्द्रित त्रिभुजीय वितरण के साथ)। निष्पक्ष सिमुलेशन के लिए, हर डाई के लिए [1, M] में एक एक समान पूर्णांक उत्पन्न करना और जोड़ना भौतिक डाइस फेंकने के बिल्कुल समकक्ष है, अंतर्निहित CSPRNG वितरण किसी भी भौतिक डाई से अधिक एक समान है जो आप ख़रीद सकते हैं। कैसीनो और विनियमित गेमिंग प्रमाणित RNG का उपयोग करते हैं जिनका सांख्यिकीय बैटरियों (TestU01 की BigCrush, NIST SP 800-22) के विरुद्ध परीक्षण किया जाता है ताकि गेमिंग नियामकों को एकरूपता सिद्ध की जा सके; वही मानक लॉटरी RNG पर लागू होते हैं।

सीडिंग और पुनरुत्पादन

PRNG की एक सूक्ष्म पर महत्वपूर्ण विशेषता: एक सीड दिए जाने पर वे निश्चयात्मक होते हैं। सीड को ज्ञात मान पर सेट करें, और "यादृच्छिक" संख्याओं का अनुक्रम बिल्कुल पुनरुत्पादन योग्य है। यह परीक्षण के लिए अनमोल है (एक यूनिट टेस्ट जो यादृच्छिक डेटा का उपयोग करता है उसे एक निश्चित सीड सेट करना चाहिए ताकि विफलताएँ पुनरुत्पादन योग्य हों) और सत्यापन योग्य रैफ़ल के लिए (ड्राइंग से पहले सीड प्रकाशित करें, फिर कोई भी परिणाम सत्यापित कर सकता है)। Python के random मॉड्यूल में इसके लिए random.seed(value) है; Java का Random कन्स्ट्रक्टर में सीड लेता है। JavaScript का Math.random() जानबूझकर सीडिंग API उजागर नहीं करता, इंजन सीड को आंतरिक स्थिति मानते हैं, पर कई शुद्ध-JS पुस्तकालय (seedrandom, pcg-random) सीडेड PRNG प्रदान करते हैं। CSPRNG डिज़ाइन से अलग हैं: वे सीडिंग उजागर नहीं करते क्योंकि पूरी बात अप्रत्याशितता है। यदि आपको पुनरुत्पादन चाहिए, स्पष्ट सीडिंग वाले PRNG का उपयोग करें; यदि आपको सुरक्षा चाहिए, CSPRNG का उपयोग करें और स्वीकार करें कि आप बाद में अनुक्रम पुनरुत्पादित नहीं कर सकते।

गोपनीयता: यादृच्छिक संख्याओं के लिए भी केवल-ब्राउज़र क्यों

यादृच्छिक संख्याएँ स्वयं ही शायद ही कभी संवेदनशील जानकारी रखती हैं, तो केवल-ब्राउज़र वास्तुकला क्यों मायने रखती है? दो कारण। पहला, जब एक यादृच्छिक संख्या सत्र टोकन, idempotency कुंजी, प्रमाणीकरण चुनौती, या किसी अन्य गुप्त-समान मान के रूप में उपयोग होती है, तो उसे तृतीय-पक्ष सर्वर पर उत्पन्न करने का अर्थ है कि उस सर्वर ने मान को आपके उपयोग करने से पहले देखा, एक छोटा पर वास्तविक एक्सपोज़र। दूसरा, सर्वर-साइड जनरेटर जो "क्रिप्टोग्राफ़िक यादृच्छिकता" का वादा करते हैं, उनको उपयोगकर्ता द्वारा सत्यापित नहीं किया जा सकता; एक बग्गी या दुर्भावनापूर्ण सर्वर गैर-यादृच्छिक या पक्षपातपूर्ण मान लौटा सकता है जो यादृच्छिक दिखें, और आपके पास बिना बहुत बड़े नमूने के पक्षपात पता लगाने का कोई तरीक़ा नहीं होगा। केवल-ब्राउज़र जनरेटर वही crypto.getRandomValues() कॉल चलाता है जो आपका अनुप्रयोग सर्वर-साइड चलाता; एन्ट्रॉपी उसी ऑपरेटिंग सिस्टम स्रोत से आती है (Linux getrandom(), Windows BCryptGenRandom, macOS); कोई तीसरा पक्ष आउटपुट नहीं देखता। आप DevTools की Network टैब खोलकर Generate पर क्लिक करते समय सत्यापित कर सकते हैं, कोई आउटगोइंग अनुरोध नहीं हैं। पेज लोड होने के बाद ऑफ़लाइन (एयरप्लेन मोड) पर जाएँ और जनरेटर अब भी काम करता है।

अक्सर पूछे जाने वाले प्रश्न