सवाल छद्म यादृच्छिक और वास्तव में यादृच्छिक संख्या कैसे भिन्न हैं और इससे कोई फर्क क्यों पड़ता है?


मुझे यह कभी नहीं मिला है। बस कहें कि आप किसी भी भाषा में एक छोटा सा प्रोग्राम लिखते हैं जो कुछ पासा रोल करता है (केवल उदाहरण के रूप में पासा का उपयोग करके)। 600,000 रोल के बाद, प्रत्येक नंबर लगभग 100,000 बार लुढ़का होता, जो मैं अपेक्षा करता हूं।

'सच्ची यादृच्छिकता' को समर्पित वेबसाइटें क्यों हैं? निश्चित रूप से, ऊपर दिए गए अवलोकन को देखते हुए, किसी भी संख्या को प्राप्त करने की संभावना लगभग 1 है कि यह कितनी संख्या से चुन सकती है।

मैंने कोशिश की अजगर: यहां 60 मिलियन रोल का नतीजा है। उच्चतम भिन्नता 0.15 की तरह है। क्या यह यादृच्छिक नहीं है जैसा कि यह प्राप्त होगा?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

653


मूल


विकिपीडिया लेख पर एक नज़र डालें हार्डवेयर यादृच्छिक संख्या उत्पन्न किया यह भी देखें - stats.stackexchange.com/questions/32794/... - steadyfish
"कुछ पासा रोल" से आपका क्या मतलब है? क्या इसमें रोबोट बांह और कैमरा संलग्न है? - starblue
जबकि मैं आपके स्वर के सामान्य ज्ञान से सहमत हूं, कि हम अक्सर इस बारे में बहुत चिंतित हैं, लेकिन वास्तविक जीवन में इसका शोषण किया गया है: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
देख इस एक ऑनलाइन पोकर गेम के बारे में लेख वास्तविक मायने रखता है कि यह क्यों मायने रखता है। - Varaquilex
यदि आप केवल 0-5 काउंटर रखते हैं और 666 गोरियन बार तदनुसार एक पासा रोल करते हैं, तो आपको एक समान वितरण भी मिल जाएगा। - jcora


जवाब:


आइए कुछ कंप्यूटर पोकर खेलते हैं, बस आप, मैं और एक सर्वर जिसे हम दोनों भरोसा करते हैं। सर्वर एक छद्म-यादृच्छिक संख्या जेनरेटर का उपयोग करता है जिसे हम खेलने से पहले 32 बिट बीज के साथ शुरू किया जाता है। तो लगभग चार अरब संभावित डेक हैं।

मुझे अपने हाथ में पांच कार्ड मिलते हैं - जाहिर है कि हम टेक्सास होल्ड 'एम नहीं खेल रहे हैं। मान लीजिए कि कार्ड मेरे लिए एक हैं, एक आप के लिए, एक मेरे लिए, एक आप के लिए, और इसी तरह। तो मेरे पास डेक में पहला, तीसरा, पांचवां, सातवां और नौवां कार्ड है।

इससे पहले मैंने प्रत्येक बीज के साथ छद्म-यादृच्छिक संख्या जनरेटर चार अरब बार भाग लिया, और प्रत्येक के लिए डेटाबेस में प्रत्येक के लिए जेनरेट किया गया पहला कार्ड लिखा। मान लीजिए मेरा पहला कार्ड हुकुम की रानी है। यह उन संभावित डेक में से प्रत्येक 52 में से एक में पहला कार्ड दिखाता है, इसलिए हमने संभावित डेक को चार बिलियन से लगभग 80 मिलियन या उससे भी कम कर दिया है।

मान लीजिए मेरा दूसरा कार्ड दिल में से तीन है। अब मैं 80 मिलियन बीजों का उपयोग करके अपने आरएनजी 80 मिलियन बार अधिक चलाता हूं जो पहले नंबर के रूप में हुकुम की रानी उत्पन्न करते हैं। यह मुझे कुछ सेकंड लेता है। मैं उन सभी डेक लिखता हूं जो तीनों दिल को तीसरे कार्ड के रूप में उत्पन्न करते हैं - मेरे हाथ में दूसरा कार्ड। यह फिर से डेक के लगभग 2% है, इसलिए अब हम 2 मिलियन डेक तक हैं।

मान लीजिए कि मेरे हाथ में तीसरा कार्ड क्लबों में से 7 है। मेरे पास 2 मिलियन बीज का डेटाबेस है जो मेरे दो कार्ड्स को सौदा करता है; मैं अपने आरएनजी को 2 मिलियन बार चलाता हूं ताकि उन डेक का 2% पता चल सके जो 7 क्लबों को तीसरे कार्ड के रूप में पेश करते हैं, और हम केवल 40 हजार डेक तक हैं।

आप देखते हैं कि यह कैसे जाता है। मैं अपने चौथे कार्ड का उत्पादन करने वाले सभी बीजों को खोजने के लिए अपने आरएनजी 40000 बार चलाता हूं, और यह हमें 800 डेक तक ले जाता है, और उसके बाद मेरे पांचवें कार्ड का उत्पादन करने वाले ~ 20 बीज प्राप्त करने के लिए 800 बार इसे चलाता है, और अब मैं बस कार्ड के उन बीस डेक उत्पन्न करें और मुझे पता है कि आपके पास बीस संभव हाथों में से एक है। इसके अलावा, मेरे पास एक अच्छा विचार है कि मैं आगे क्या करने जा रहा हूं।

अब आप देखते हैं कि वास्तविक यादृच्छिकता क्यों महत्वपूर्ण है? जिस तरह से आप इसका वर्णन करते हैं, आपको लगता है कि वितरण महत्वपूर्ण है, लेकिन वितरण वह नहीं है जो प्रक्रिया को यादृच्छिक बनाता है। अनिश्चितता एक प्रक्रिया यादृच्छिक बनाता है।

अद्यतन करें

(अब उनकी अनियंत्रित प्रकृति के कारण हटाए गए) टिप्पणियों के आधार पर, कम से कम 0.3% लोगों ने इसे पढ़ा है जो मेरे बिंदु के रूप में उलझन में हैं। जब लोग उन बिंदुओं के खिलाफ बहस करते हैं जिन्हें मैंने नहीं बनाया है, या बदतर है, तो तर्क दें के लिये अंक है कि मैं किया था पर बनाओ धारणा है कि मैंने उन्हें नहीं बनाया है, तो मुझे पता है कि मुझे अधिक स्पष्ट और सावधानीपूर्वक व्याख्या करने की आवश्यकता है।

शब्द के चारों ओर विशेष भ्रम प्रतीत होता है वितरण इसलिए मैं सावधानी से उपयोग करना चाहता हूं।

हाथ में सवाल हैं:

  • छद्म यादृच्छिक संख्या और वास्तव में यादृच्छिक संख्या कैसे भिन्न होती है?
  • अंतर महत्वपूर्ण क्यों है?
  • क्या पीआरएनजी के आउटपुट के वितरण के साथ मतभेदों का कोई संबंध है?

चलो इस पर विचार करके शुरू करते हैं उत्तम पोकर खेलने के लिए कार्ड के यादृच्छिक डेक उत्पन्न करने का तरीका। फिर हम देखेंगे कि डेक उत्पन्न करने के लिए अन्य तकनीकें अलग-अलग हैं, और यदि उस अंतर का लाभ उठाना संभव है।

आइए मान लीजिए कि हमारे पास एक जादू बॉक्स है TRNG। इसके इनपुट के रूप में हम इसे एक पूर्णांक एन से अधिक या बराबर देते हैं, और इसके आउटपुट के रूप में यह हमें एक और एन, समावेशी के बीच वास्तव में यादृच्छिक संख्या देता है। बॉक्स का आउटपुट है पूरी तरह से अप्रत्याशित (जब एक से अधिक संख्या दी जाती है) और एक और एन के बीच कोई भी संख्या दूसरे की तरह होती है; यह कहना है कि वितरण है वर्दी। (यादृच्छिकता के अन्य उन्नत सांख्यिकीय जांच हैं जो हम कर सकते हैं; मैं इस बिंदु को अनदेखा कर रहा हूं क्योंकि यह मेरे तर्क के लिए जर्मन नहीं है। टीआरएनजी पूरी तरह से धारणा से सांख्यिकीय रूप से यादृच्छिक है।)

हम कार्ड के एक unshuffled डेक के साथ शुरू करते हैं। हम बॉक्स को एक और 52 के बीच एक संख्या के लिए पूछते हैं - यानी, TRNG(52)। जो भी नंबर वापस देता है, हम अपने सॉर्ट किए गए डेक से कई कार्ड गिनते हैं और उस कार्ड को हटा देते हैं। यह शफल डेक में पहला कार्ड बन जाता है। फिर हम पूछते हैं TRNG(51) और दूसरा कार्ड चुनने के लिए ऐसा ही करें, और इसी तरह।

इसे देखने का एक और तरीका है: 52 हैं! = 52 x 51 x 50 ... x 2 x 1 संभावित डेक, जो मोटे तौर पर 2 है226। हमने वास्तव में यादृच्छिक रूप से उनमें से एक को चुना है।

अब हम कार्ड सौदा करते हैं। जब मैं अपने कार्ड देखता हूं तो मेरे पास है कोई विचार नहीं आपके पास कौन से कार्ड हैं (स्पष्ट तथ्य के अलावा कि आपके पास मेरे पास कोई भी कार्ड नहीं है।) वे समान संभावना के साथ कोई भी कार्ड हो सकते हैं।

तो मुझे यह सुनिश्चित करने दो कि मैं इसे स्पष्ट रूप से समझाऊं। हमारे पास है वर्दी वितरण प्रत्येक व्यक्तिगत आउटपुट के TRNG(n); प्रत्येक व्यक्ति संभावना 1 / एन के साथ 1 और एन के बीच एक संख्या चुनता है। इसके अलावा, इस प्रक्रिया का नतीजा यह है कि हमने 52 में से एक चुना है! 1/52 की संभावना के साथ संभव डेक !, तो वितरण संभावित डेक के सेट पर है भी वर्दी।

ठीक है।

अब मान लीजिए कि हमारे पास एक कम जादू बॉक्स है, लेबल किया गया है PRNG। इससे पहले कि आप इसका इस्तेमाल कर सकें, यह होना चाहिए वरीयता प्राप्त 32 बिट हस्ताक्षरित संख्या के साथ।

एक ओर: क्यों 32? इसे 64 या 256 या 10000 बिट संख्या के साथ बीजित नहीं किया जा सका? ज़रूर। लेकिन (1) अभ्यास में अधिकांश ऑफ-द-शेल्फ पीआरएनजी 32 बिट संख्या के साथ बीजित होते हैं, और (2) यदि आपके पास बीज बनाने के लिए 10000 बिट्स यादृच्छिकता है तो आप पीआरएनजी का उपयोग क्यों कर रहे हैं? आपके पास पहले से ही 10000 बिट्स यादृच्छिकता का स्रोत है!

वैसे भी, पीआरएनजी कैसे काम करता है: इसके बाद बीजिंग के बाद, आप इसका उपयोग उसी तरह कर सकते हैं जिसका आप उपयोग करते हैं TRNG। यही है, आप इसे एक संख्या एन पास करते हैं और यह आपको 1 और एन समावेशी के बीच एक संख्या देता है। इसके अलावा, उस आउटपुट का वितरण कम या ज्यादा समान है। यही है, जब हम पूछते हैं PRNG 1 और 6 के बीच की संख्या के लिए, हमें 1, 2, 3, 4, 5 या 6 प्रत्येक समय के लगभग छठे हिस्से में मिलता है, इससे कोई फर्क नहीं पड़ता कि बीज क्या था।

मैं इस बिंदु पर कई बार जोर देना चाहता हूं क्योंकि ऐसा लगता है कि कुछ टिप्पणीकारों को भ्रमित कर रहा है। पीआरएनजी का वितरण कम से कम दो तरीकों से समान है। सबसे पहले, मान लीजिए कि हम कोई विशेष बीज चुनते हैं। हम अनुक्रम की उम्मीद करेंगे PRNG(6), PRNG(6), PRNG(6)... दस लाख बार 1 और 6 के बीच संख्याओं के समान वितरण का उत्पादन करेंगे। दूसरा, अगर हमने दस लाख अलग-अलग बीज चुना और बुलाया PRNG(6)  एक बार प्रत्येक बीज के लिए, हम फिर से 1 से 6 तक संख्याओं के समान वितरण की अपेक्षा करेंगे। इनमें से किसी भी परिचालन में पीआरएनजी की समानता उस हमले के लिए प्रासंगिक नहीं है जिसका मैं वर्णन कर रहा हूं

यह प्रक्रिया कहा जाता है छद्म यादृच्छिक क्योंकि बॉक्स का व्यवहार वास्तव में पूरी तरह से निर्धारिती है; यह 2 में से एक से चुनता है32 बीज पर आधारित संभावित व्यवहार। यही है, एक बार यह बीजित हो जाने पर, PRNG(6), PRNG(6), PRNG(6), ...  एक उत्पादन करता है अनुक्रम एक समान वितरण के साथ संख्याओं का, लेकिन वह अनुक्रम है पूरी तरह से बीज द्वारा निर्धारित कॉल के दिए गए अनुक्रम के लिए, पीआरएनजी (52), पीआरएनजी (51) ... और इसी तरह, केवल 2 हैं32 संभावित अनुक्रम बीज अनिवार्य रूप से चुनता है कि हमें कौन सा मिलता है।

एक डेक उत्पन्न करने के लिए सर्वर अब एक बीज उत्पन्न करता है। (कैसे? हम उस बिंदु पर वापस आ जाएंगे।) फिर वे कॉल करते हैं PRNG(52), PRNG(51) और इतने पहले डेक उत्पन्न करने के लिए।

यह प्रणाली मैंने वर्णित हमले के लिए अतिसंवेदनशील है। सर्वर पर हमला करने के लिए हम पहले समय से पहले 0 के साथ बॉक्स की अपनी प्रतिलिपि बनाते हैं और पूछते हैं PRNG(52) और इसे लिखो। फिर हम 1 के साथ फिर से बीज, पूछो PRNG(52), और इसे नीचे लिखें, सभी तरह से 2 तक32-1।

अब, पोकर सर्वर जो डेक उत्पन्न करने के लिए पीआरएनजी का उपयोग कर रहा है उसे किसी भी तरह बीज पैदा करना है। इससे कोई फर्क नहीं पड़ता कि वे ऐसा कैसे करते हैं। वे कॉल कर सकते थे TRNG(2^32) वास्तव में यादृच्छिक बीज प्राप्त करने के लिए। या वे वर्तमान समय को बीज के रूप में ले सकते हैं, जो कि शायद ही कभी यादृच्छिक है; मुझे पता है कि जितना समय आप करते हैं उतना ही है। मेरे हमले का मुद्दा यह है कि इससे कोई फर्क नहीं पड़ता, क्योंकि मेरे पास मेरा डेटाबेस है। जब मैं अपना पहला कार्ड देखता हूं तो मैं संभावित बीजों के 98% को खत्म कर सकता हूं। जब मैं अपना दूसरा कार्ड देखता हूं तो मैं 98% अधिक खत्म कर सकता हूं, और इसी तरह, जब तक कि मैं संभवतः कुछ हद तक संभव बीज तक नहीं पहुंच पाता हूं, और अपने हाथ में क्या संभावना है, इसकी उच्च संभावना के बारे में जानें।

अब, फिर, मैं इस बात पर जोर देना चाहता हूं कि यहां धारणा है अगर हम बुलाया PRNG(6) दस लाख बार हम प्रत्येक संख्या को लगभग एक छठा समय प्राप्त करेंगे। वह वितरण है (अधिक या कम) वर्दी, तथा यदि उस वितरण की एकरूपता आप की परवाह है, कोई बात नहीं। सवाल का मुद्दा था क्या अन्य चीजें हैं जो वितरण करते हैं PRNG(6) क्या हम परवाह करते हैं? और जवाब है हाँ। हम परवाह करते हैं अनिश्चितता भी।

समस्या को देखने का एक और तरीका यह है कि भले ही दस लाख का वितरण हो PRNG(6) ठीक हो सकता है, क्योंकि पीआरएनजी केवल 2 से चुन रहा है32 संभावित व्यवहार, यह हर संभव डेक उत्पन्न नहीं कर सकता है।  यह केवल 2 उत्पन्न कर सकता है32 2 में से226 संभव डेक; एक छोटा सा अंश तो वितरण सभी डेक के सेट पर ये बहुत खराब है। लेकिन फिर, यहां पर मौलिक हमला सफलतापूर्वक सक्षम होने पर आधारित है भविष्यवाणी अतीत और भविष्य का व्यवहार PRNG इसके आउटपुट के एक छोटे से नमूने से।

मुझे यह सिंक करने के लिए यह एक तिहाई या चार बार कहना है। यहां तीन वितरण हैं। सबसे पहले, उस प्रक्रिया का वितरण जो यादृच्छिक 32 बिट बीज उत्पन्न करता है। यह पूरी तरह से यादृच्छिक, अप्रत्याशित और वर्दी हो सकता है और हमला अभी भी काम करेगा। दूसरा, लाखों कॉल का वितरण PRNG(6)। यह पूरी तरह से एक समान हो सकता है और हमला अभी भी काम करेगा। तीसरा, छद्म-यादृच्छिक प्रक्रिया द्वारा चुने गए डेक का वितरण मैंने वर्णन किया है। वह वितरण बेहद खराब है; आईआरएल संभावित डेक का केवल एक छोटा सा अंश संभवतः चुना जा सकता है। हमला इस पर निर्भर करता है पूर्वानुमान पीआरएनजी के व्यवहार का इसके उत्पादन के आंशिक ज्ञान के आधार पर

ASIDE: इस हमले की आवश्यकता है कि हमलावर यह अनुमान लगा सके कि पीआरएनजी द्वारा उपयोग किए जाने वाले सटीक एल्गोरिदम का क्या अनुमान है। चाहे वह यथार्थवादी है या नहीं, एक खुला प्रश्न है। हालाँकि, एक सुरक्षा प्रणाली को डिजाइन करते समय आपको इसे हमलों के खिलाफ सुरक्षित होने के लिए डिजाइन करना होगा, भले ही हमलावर प्रोग्राम में सभी एल्गोरिदम जानता हो। एक और तरीका रखें: सुरक्षा प्रणाली का हिस्सा जो सिस्टम को सुरक्षित होने के लिए गुप्त रहना चाहिए उसे "कुंजी" कहा जाता है। यदि आपका सिस्टम एल्गोरिदम पर इसकी सुरक्षा के लिए निर्भर करता है तो आप एक रहस्य होने के बाद उपयोग करते हैं आपकी कुंजी में उन एल्गोरिदम हैं। वह एक है अत्यंत कमजोर स्थिति में होना!

आगे बढ़ते रहना।

अब मान लीजिए कि हमारे पास लेबल वाला तीसरा जादू बॉक्स है CPRNG। यह एक क्रिप्टो-ताकत का संस्करण है PRNG। यह 32 बिट बीज के बजाय 256 बिट बीज लेता है। यह साथ साझा करता है PRNG वह संपत्ति जो बीज 2 में से किसी एक से चुनती है256 संभावित व्यवहार और हमारी अन्य मशीनों की तरह, इसमें संपत्ति है जो बड़ी संख्या में कॉल करती है CPRNG(n) 1 और एन के बीच परिणामों के समान वितरण का उत्पादन: प्रत्येक समय 1 / एन होता है। क्या हम इसके खिलाफ अपना हमला चला सकते हैं?

हमारे मूल हमले के लिए हमें 2 स्टोर करने की आवश्यकता है32 बीज से मैपिंग्स PRNG(52)। लेकिन 2256 एक बहुत बड़ी संख्या है; यह चलाने के लिए पूरी तरह से अक्षम है CPRNG(52)वह कई बार और परिणाम स्टोर।

लेकिन मान लीजिए कुछ है अन्य का मूल्य लेने के लिए रास्ता CPRNG(52) और उस से बीज के बारे में एक तथ्य है? हम अब तक बहुत मूर्ख हैं, बस सभी संभव संयोजनों को मजबूर कर रहे हैं। क्या हम जादू बॉक्स के अंदर देख सकते हैं, यह पता लगा सकते हैं कि यह कैसे काम करता है, और आउटपुट के आधार पर बीज के बारे में तथ्यों को कम करता है?

नहीं। विवरणों को समझाने के लिए बहुत जटिल हैं, लेकिन सीपीआरएनजी चालाकी से डिजाइन किए गए हैं ताकि कटौती करने में असमर्थ हो कोई भी पहले आउटपुट से बीज के बारे में उपयोगी तथ्य CPRNG(52) या से कोई भी आउटपुट का सबसेट, कोई फर्क नहीं पड़ता कि कितना बड़ा है

ठीक है, तो अब मान लीजिए कि सर्वर का उपयोग कर रहा है CPRNG डेक उत्पन्न करने के लिए। इसे 256 बिट बीज की जरूरत है। यह बीज कैसे चुनता है? यदि यह कोई मूल्य चुनता है जो हमलावर भविष्यवाणी कर सकता है तो अचानक हमला फिर से व्यवहार्य हो जाता है। अगर हम 2 का निर्धारण कर सकते हैं256 संभावित बीज, तब उनमें से केवल चार बिलियन सर्वर द्वारा चुने जाने की संभावना है हम व्यापार में वापस आ गए हैं। हम इस हमले को दोबारा माउंट कर सकते हैं, केवल बीज की छोटी संख्या पर ध्यान दे सकते हैं जो संभवतः उत्पन्न किया जा सकता है।

इसलिए सर्वर को यह सुनिश्चित करने के लिए काम करना चाहिए कि 256 बिट संख्या है समान रूप से वितरित - यानी, प्रत्येक संभावित बीज को 1/2 की संभावना के साथ चुना जाता है256। मूल रूप से सर्वर को कॉल करना चाहिए TRNG(2^256)-1 के लिए बीज उत्पन्न करने के लिए CPRNG

क्या होगा यदि मैं सर्वर को हैक कर सकता हूं और देख सकता हूं कि कौन सी बीज चुना गया था? उस स्थिति में, हमलावर सीपीआरएनजी के पूर्ण अतीत और भविष्य को जानता है। सर्वर के लेखक को इस हमले के खिलाफ सुरक्षा की जरूरत है! (बेशक अगर मैं इस हमले को सफलतापूर्वक माउंट कर सकता हूं तो मैं शायद पैसे को सीधे अपने बैंक खाते में स्थानांतरित कर सकता हूं, तो शायद यह दिलचस्प नहीं है। प्वाइंट है: बीज को मुश्किल से अनुमानित रहस्य होना चाहिए, और वास्तव में यादृच्छिक 256 बिट संख्या अनुमान लगाने के लिए बहुत मुश्किल है।)

रक्षा-गहराई के बारे में मेरे पहले बिंदु पर लौट रहा है: 256 बिट बीज है कुंजी इस सुरक्षा प्रणाली के लिए। एक सीपीआरएनजी का विचार यह है कि सिस्टम सुरक्षित है जब तक कुंजी सुरक्षित है; भले ही एल्गोरिदम के बारे में हर दूसरे तथ्य को ज्ञात किया गया हो, जब तक आप मुख्य रहस्य रख सकें, प्रतिद्वंद्वी के कार्ड अप्रत्याशित हैं।

ठीक है, इसलिए बीज दोनों गुप्त और समान रूप से वितरित होना चाहिए क्योंकि यदि ऐसा नहीं है, तो हम हमले को माउंट कर सकते हैं। हमारे पास धारणा है कि आउटपुट का वितरण CPRNG(n) वर्दी है सभी संभावित डेक के सेट पर वितरण के बारे में क्या?

आप कह सकते हैं: 2 हैं256 सीपीआरएनजी द्वारा संभावित अनुक्रम आउटपुट, लेकिन केवल 2 हैं226 संभव डेक इसलिए डेक की तुलना में अधिक संभावित अनुक्रम हैं, इसलिए हम ठीक हैं; प्रत्येक संभव-आईआरएल डेक अब इस प्रणाली में संभव है (उच्च संभावना के साथ)। और यह एक अच्छा तर्क है सिवाय इसके कि ...

2226 केवल एक है सन्निकटन52 में से! इसे विभाजित करें। 2256/ 52! संभवतः एक पूर्ण संख्या नहीं हो सकती क्योंकि एक चीज़ के लिए, 52! 3 से विभाजित है लेकिन दो की कोई शक्ति नहीं है! चूंकि यह पूरी संख्या नहीं है, इसलिए हमारे पास ऐसी स्थिति है जहां सभी डेक हैं मुमकिन, परंतु कुछ डेक दूसरों की तुलना में अधिक संभावना है

यदि यह स्पष्ट नहीं है, तो छोटी संख्या वाले स्थिति पर विचार करें। मान लें कि हमारे पास तीन कार्ड हैं, ए, बी और सी मान लीजिए कि हम एक पीआरएनजी का उपयोग 8 बिट बीज के साथ करते हैं, इसलिए 256 संभावित बीज हैं। 256 संभावित आउटपुट हैं PRNG(3) बीज के आधार पर; उनमें से एक तिहाई ए होने का कोई तरीका नहीं है, उनमें से एक तिहाई बी हो और उनमें से एक तिहाई सी हो क्योंकि 256 समान रूप से 3 से विभाजित नहीं है। उनमें से एक के लिए एक छोटी पूर्वाग्रह होना चाहिए।

इसी प्रकार, 52 समान रूप से 2 में विभाजित नहीं होता है256, इसलिए पहले कार्ड चुने गए और दूसरों से दूर पूर्वाग्रह के रूप में कुछ कार्डों के प्रति कुछ पूर्वाग्रह होना चाहिए।

32 बिट बीज के साथ हमारी मूल प्रणाली में एक विशाल पूर्वाग्रह था और संभावित डेक का विशाल बहुमत कभी नहीं बनाया गया था। इस प्रणाली में सभी डेक का उत्पादन किया जा सकता है, लेकिन डेक का वितरण अभी भी त्रुटिपूर्ण है। कुछ डेक हैं बहुत हल्के से दूसरों की तुलना में अधिक संभावना है।

अब सवाल यह है: क्या हमारे पास इस दोष के आधार पर हमला है? और जवाब है अभ्यास में, शायद नहीं। सीपीआरएनजी डिजाइन किए गए हैं ताकि अगर बीज वास्तव में यादृच्छिक है फिर यह अंतर के बारे में बताने के लिए कम्प्यूटेशनल रूप से अक्षम है CPRNG तथा TRNG

ठीक है, तो चलो समेट करें।

छद्म यादृच्छिक संख्या और वास्तव में यादृच्छिक संख्या कैसे भिन्न होती है?

वे भविष्यवाणी के स्तर में भिन्न होते हैं जो वे प्रदर्शित करते हैं।

  • वास्तव में यादृच्छिक संख्या अनुमानित नहीं हैं।
  • सभी छद्म-यादृच्छिक संख्या अनुमानित हैं यदि बीज निर्धारित किया जा सकता है या अनुमान लगाया जा सकता है।

अंतर महत्वपूर्ण क्यों है?

क्योंकि ऐसे अनुप्रयोग हैं जहां सिस्टम की सुरक्षा पर निर्भर करता है अनिश्चितता

  • यदि प्रत्येक कार्ड का चयन करने के लिए एक टीआरएनजी का उपयोग किया जाता है तो सिस्टम अनुपलब्ध है।
  • यदि प्रत्येक कार्ड का चयन करने के लिए एक सीपीआरएनजी का उपयोग किया जाता है तो यदि बीज अप्रत्याशित और अज्ञात दोनों है तो सिस्टम सुरक्षित है।
  • यदि एक छोटे से बीज स्थान के साथ एक साधारण पीआरएनजी का उपयोग किया जाता है तो यह सुनिश्चित नहीं है कि बीज अप्रत्याशित या अज्ञात है या नहीं; एक छोटी सी पर्याप्त जगह अंतरिक्ष के हमलों के बलपूर्वक हमले के लिए अतिसंवेदनशील है।

क्या पीआरएनजी के आउटपुट के वितरण के साथ अंतर में कुछ अंतर है?

वितरण की एकरूपता या इसके लिए कमी व्यक्तिगत कॉल सेवा मेरे RNG(n) मैंने वर्णित हमलों के लिए प्रासंगिक नहीं है।

जैसा कि हमने देखा है, दोनों एक PRNG तथा CPRNG सभी संभावित डेक के किसी भी व्यक्तिगत डेक को चुनने की संभावना के खराब विचलन का उत्पादन करें। PRNG काफी खराब है, लेकिन दोनों में समस्याएं हैं।

एक और प्रश्न:

यदि टीआरएनजी सीपीआरएनजी की तुलना में बहुत बेहतर है, जो बदले में पीआरएनजी से बेहतर है, तो कोई भी सीपीआरएनजी या पीआरएनजी का उपयोग क्यों करता है?

दो कारण।

पहला: व्यय। टीआरएनजी है महंगा। वास्तव में यादृच्छिक संख्या उत्पन्न करना मुश्किल है। सीपीआरएनजी केवल मनमाने ढंग से कई कॉल के लिए अच्छे परिणाम देते हैं एक बीज के लिए टीआरएनजी को बुलाओ। नीचे की ओर निश्चित रूप से है आपको उस बीज को एक रहस्य रखना है

दूसरा: कभी-कभी हम चाहते हैं भविष्यवाणी और हम सभी की देखभाल अच्छी वितरण है। यदि आप एक परीक्षण सूट के लिए प्रोग्राम इनपुट के रूप में "यादृच्छिक" डेटा उत्पन्न कर रहे हैं, और यह एक बग दिखाता है, तो यह अच्छा होगा कि परीक्षण सूट चलाने से फिर से बग उत्पन्न होता है!

मुझे उम्मीद है कि अब और अधिक स्पष्ट है।

अंत में, यदि आप इसका आनंद लेते हैं तो आप यादृच्छिकता और क्रमपरिवर्तन के विषय पर कुछ और पढ़ने का आनंद ले सकते हैं:


1374



ठीक है, लड़के और लड़कियां। यह अभी के लिए पर्याप्त टिप्पणी है। यदि आप इस पर आगे चर्चा करना चाहते हैं, तो अपने आप को एक चैट रूम, kthnxbye पकड़ो! - Ivo Flipse♦
@Eric लेकिन बीज प्रत्येक नए डेक ड्रा से पहले रीसेट नहीं किया गया है, है ना? तो जब आप सही हैं कि केवल अपेक्षाकृत कम हैं प्रक्षेप पथ हम से नमूना कर रहे हैं, आप बिल्कुल नहीं जानते कि इस समय आप कहां हैं और प्रक्षेपणों में अंतर होता है। - A.S.
किसी ने वास्तव में ऐसा कुछ किया - EJoshuaS
संबंधित मुद्दों का एक अच्छा (लेकिन घना) उपचार Knuth के TAOCP वॉल्यूम 2, सेक्शन 3.5 में "रैंडम अनुक्रम क्या है?" (पृष्ठ 14 9), इक्विडिस्ट्रिब्यूटेड, के-वितरित, और वितरित अनुक्रमों की रोशनी परिभाषाओं से शुरू होता है। छद्म यादृच्छिक अनुक्रमों पर 3.5.एफ (पी। 170) में चर्चा की जाती है। छद्म यादृच्छिकता के मानदंड भी देखें जटिलता सिद्धांत तथा जर्मन बीएसआई। - ShreevatsaR


एरिक लिपर्ट कहते हैं, यह सिर्फ वितरण नहीं है। यादृच्छिकता को मापने के अन्य तरीके हैं।

शुरुआती यादृच्छिक संख्या जेनरेटर में से एक में कम से कम महत्वपूर्ण बिट में अनुक्रम है - यह 0 और 1 के वैकल्पिक है। इसलिए एलएसबी 100% अनुमानित था। लेकिन आपको इससे ज्यादा चिंता करने की ज़रूरत है। प्रत्येक बिट अप्रत्याशित होना चाहिए।

समस्या के बारे में सोचने का एक अच्छा तरीका यहां है। मान लें कि आप यादृच्छिकता के 64 बिट उत्पन्न कर रहे हैं। प्रत्येक परिणाम के लिए, पहले 32 बिट्स (ए), और अंतिम 32 बिट्स (बी) लें, और एक सरणी एक्स [ए, बी] में एक इंडेक्स बनाएं। अब परीक्षण को दस लाख बार करें, और प्रत्येक परिणाम के लिए, उस संख्या में सरणी को बढ़ाएं, यानी एक्स [ए, बी] ++;

अब एक 2 डी आरेख खींचें, जहां संख्या जितनी बड़ी होगी, उस स्थान पर पिक्सेल को उज्ज्वल करें।

यदि यह वास्तव में यादृच्छिक है, तो रंग एक समान ग्रे होना चाहिए। लेकिन आप पैटर्न प्राप्त कर सकते हैं। उदाहरण के लिए विंडोज एनटी सिस्टम के टीसीपी अनुक्रम संख्या में "यादृच्छिकता" का यह चित्र लें:

Windows NT 

या विंडोज 98 से भी यह एक:

Windows 98 

और यहां सिस्को राउटर (आईओएस) कार्यान्वयन की यादृच्छिकता है। Cisco ISO

ये आरेख सौजन्य हैं माइकल जेलवेस्की का पेपर। इस विशेष मामले में, यदि कोई भविष्यवाणी कर सकता है कि टीसीपी अनुक्रम संख्या एक प्रणाली का क्या होगा, तो कोई अन्य सिस्टम से कनेक्शन बनाते समय उस सिस्टम का प्रतिरूपण कर सकता है - जो कनेक्शन को अपहरण, संचार की रोकथाम आदि की अनुमति देगा। और अगर हम अगली संख्या 100% समय की भविष्यवाणी नहीं कर सकते हैं, तो अगर हम एक नया कनेक्शन बन सकते हैं हमारे नियंत्रण में, हम सफलता का मौका बढ़ा सकते हैं। और जब कंप्यूटर कुछ सेकंड में 100,000 कनेक्शन उत्पन्न कर सकते हैं, तो सफल हमले की बाधा खगोलीय से संभव या संभवतः भी हो जाती है।


156



यह इतना शानदार है कि यह मेरी आंखों में आँसू लाता है। ऐसा ऐप होना चाहिए जो इन सभी ओएस (मोबाइल / डेस्कटॉप / सर्वर) और प्लेटफॉर्म (जेवीएम / जावास्क्रिप्ट / आदि) के लिए बनाता है। - HDave
विंडोज रैंड () फ़ंक्शन काफी अच्छा है! यह एक बादल बनाता है जिसमें कोई स्पष्ट पैटर्न नहीं है। इसे (और अन्य एल्गोरिदम) को आज़माने के लिए मेरा कार्यान्वयन देखें: github.com/Zalastax/visualize_random - Zalastax


जबकि कम्प्यूटर द्वारा उत्पन्न छद्म यादृच्छिक संख्या कंप्यूटर उपयोगकर्ताओं द्वारा सामना किए जाने वाले अधिकांश मामलों के लिए स्वीकार्य हैं, ऐसे परिदृश्य हैं जिनकी आवश्यकता होती है पूरी तरह अप्रत्याशित यादृच्छिक संख्या।

एन्क्रिप्शन जैसे सुरक्षा-संवेदनशील अनुप्रयोगों में, एक छद्म यादृच्छिक संख्या जेनरेटर (पीआरएनजी) मूल्यों का उत्पादन कर सकता है, हालांकि उपस्थिति में यादृच्छिक रूप से, वास्तव में हमलावर द्वारा पूर्वानुमानित किया जा सकता है। कोई एन्क्रिप्शन सिस्टम क्रैक करने का प्रयास कर रहा है, यदि कोई पीआरएनजी इस्तेमाल किया गया था और हमलावर के पास पीआरएनजी की स्थिति पर जानकारी है तो एन्क्रिप्शन कुंजी का अनुमान लगाने में सक्षम हो सकता है। इसलिए, ऐसे अनुप्रयोगों के लिए, एक यादृच्छिक संख्या जनरेटर जो मूल्यों का उत्पादन करता है जो वास्तव में अनुपयोगी हैं, आवश्यक है। ध्यान दें कि कुछ पीआरएनजी क्रिप्टोग्राफिक रूप से सुरक्षित होने के लिए डिज़ाइन किए गए हैं और ऐसे सुरक्षा-संवेदनशील अनुप्रयोगों के लिए उपयोग योग्य हैं।

आरएनजी हमलों के बारे में अधिक जानकारी मिल सकती है यह विकिपीडिया लेख


92



क्रिप्टोग्राफिक पीआरएनजी मौजूद हैं, और व्यापक रूप से उपयोग किया जाता है। वे एक मामूली आकार के बीज से यादृच्छिक संख्याओं की व्यावहारिक रूप से असीमित धारा उत्पन्न कर सकते हैं। यह ऐसी यादृच्छिक संख्याओं से ऐसी धारा को अलग करने के लिए कम्प्यूटेशनल रूप से अक्षम है, इस प्रकार ऐसी धारा के किसी भी हिस्से से कोई अतिरिक्त जानकारी प्राप्त नहीं की जा सकती है, और किसी भी व्यावहारिक उद्देश्य के लिए संख्याएं वास्तविक यादृच्छिक संख्याओं के समान ही हैं। - aaaaaaaaaaaa
मुझे लगता है कि यह समझाने का सबसे आसान तरीका यह है कि यादृच्छिक रूप से संख्या जनरेटर एल्गोरिदम प्रोग्राम किए जाने हैं। इसका मतलब है कि निर्देशों का एक सेट है जिसका पालन किया जा रहा है। यदि निर्देशों का एक सेट है, तो यह यादृच्छिक नहीं हो सकता है। - Keltari
@ केल्टारी आप एंट्रॉपी के तत्व को खो रहे हैं ... अधिकांश आरएनजी (कम से कम क्रिप्टोग्राफिक वाले) बाहरी स्रोतों (जैसे माउस आंदोलन) से इनपुट इकट्ठा करते हैं और प्रारंभिक स्थिति के हिस्से के रूप में इसका उपयोग करते हैं - इस प्रकार, से रूपांतरण A सेवा मेरे B प्रोग्राम किया गया है लेकिन प्रारंभिक स्थिति है A (चाहिए) असहनीय होना चाहिए। लिनक्स के /dev/random यह अनुमान लगाएगा कि कितना एन्ट्रॉपी उपलब्ध है और यदि यह बहुत कम हो तो संख्याएं देना बंद कर दें। - Basic
जिज्ञासा से बाहर - लावा दीपक क्यों "वास्तव में यादृच्छिक" माना जाता है? मैं समझता हूं कि यह अपेक्षाकृत अप्रत्याशित व्यवहार प्रदर्शित करता है, लेकिन द्रव गतिशीलता पर पर्याप्त फर्म के साथ कोई व्यक्ति और पृथ्वी के गुरुत्वाकर्षण वातावरण में उन तरल पदार्थ कैसे बातचीत करते हैं, निश्चित रूप से "अनुमानित" परिणाम उत्पन्न कर सकते हैं, नहीं? निश्चित रूप से, लावा दीपक अप्रत्याशित हैं, लेकिन मेरे लिए, वे यादृच्छिक नहीं हैं, लेकिन अत्यधिक अनुमानित हैं। - theGreenCabbage
@theGreenCabbage: मुझे संदेह है कि लावा दीपक अराजक हैं। एक अच्छा पर्याप्त कंप्यूटर मॉडल और सटीकता के पर्याप्त अंक देखते हुए, आप (सिद्धांत रूप में) कुछ समय के लिए व्यवहार की भविष्यवाणी कर सकते हैं। लेकिन, क्योंकि प्रणाली अराजक है, प्रारंभिक स्थितियों में सबसे छोटे बदलाव के साथ दो लावा दीपक जल्दी से व्यवहार में अलग हो जाएंगी। (और यह टिप्पणी अराजक आकर्षण को अनदेखा करती है।) - dmm


मैंने इसे पायथन में आजमाया: यहां 60 मिलियन रोल का नतीजा है। उच्चतम भिन्नता 0.15 की तरह है। क्या यह यादृच्छिक नहीं है जैसा कि यह प्राप्त होगा?

दरअसल, यह है तो "अच्छा" यह बुरा है... सभी मौजूदा उत्तर पर ध्यान केंद्रित करते हैं पूर्वानुमान प्रारंभिक मूल्यों का एक छोटा अनुक्रम दिया गया। मैं एक और मुद्दा उठाना चाहता हूं:

तुंहारे वितरण यादृच्छिक रोल की तुलना में बहुत छोटा मानक विचलन होना चाहिए

सच यादृच्छिकता बिल्कुल नहीं आती है उस औसत के करीब "लगभग बिल्कुल 1 यह कितनी संख्या से चुन सकता है" कि आप गुणवत्ता के संकेत के रूप में उपयोग कर रहे हैं।

यदि आप देखते हैं एकाधिक स्टिस रोल के लिए संभाव्यता वितरण के बारे में यह स्टैक एक्सचेंज प्रश्न, आप एन पासा रोल के मानक विचलन के लिए एक सूत्र देखेंगे (वास्तव में यादृच्छिक परिणामों को मानते हुए):

 sqrt(N * 35.0 / 12.0).

उस सूत्र का उपयोग करना, मानक विचलन के लिये:

  • 1 मिलियन रोल है 1708
  • 60 मिलियन रोल है 13229

यदि हम आपके परिणामों को देखते हैं:

  • 1 मिलियन रोल: stddev (1000066, 999666, 1001523, 999452, 999294, 99 99 99) है 804
  • 60 मिलियन रोल: stddev (9997653, 9997789, 99 6 9 853, 10006533, 10002774, 99 8 9 3 9 8) है 3827

आप सूत्र से सटीक मिलान करने के लिए एक सीमित नमूने के मानक विचलन की अपेक्षा नहीं कर सकते हैं, लेकिन यह बहुत करीब आना चाहिए। फिर भी, 1 मिलियन रोल पर आपके पास आधा से अधिक उचित stddev है, और 60 मिलियन तक आप तीसरे स्थान पर हैं - यह बदतर हो रहा है, और यह कोई संयोग नहीं है ....

छद्म-आरएनजी बीज से शुरू होने और विशिष्ट अवधि के लिए मूल संख्या की समीक्षा नहीं करते हुए अलग-अलग संख्याओं के अनुक्रम के माध्यम से आगे बढ़ते हैं। उदाहरण के लिए, पुराने सी पुस्तकालय के कार्यान्वयन rand() फ़ंक्शन में आमतौर पर 2 ^ 32 की अवधि होती है, और वे बीज को दोहराने से ठीक पहले 0 और 2 ^ 32-1 के बीच प्रत्येक नंबर पर जायेंगे। इसलिए, यदि आप 2 ^ 32 पासा अनुकरण करते हैं तो प्री-मॉड्यूलस (%) परिणामों में प्रत्येक संख्या 0 से 2 ^ 32 तक शामिल होगी, प्रत्येक 1-6 परिणाम के लिए गणना 715827883 या 715827882 (2 ^ 32 6 का एक बहु नहीं है), और इसलिए मानक विचलन इसलिए केवल 0 से ऊपर है। उपरोक्त सूत्र, 2 ^ 32 रोल के लिए सही मानक विचलन 111924 है। वैसे भी, चूंकि आपकी छद्म-यादृच्छिक रोल की संख्या बढ़ जाती है तो आप 0 मानक विचलन की ओर बढ़ जाते हैं। इस मुद्दे को महत्वपूर्ण होने की उम्मीद की जा सकती है जब रोल की संख्या अवधि का एक महत्वपूर्ण अंश है, लेकिन कुछ छद्म-आरएनजी दूसरों की तुलना में कम नमूने के साथ भी बदतर समस्याएं या समस्याएं प्रदर्शित कर सकते हैं।

इसलिए यदि आपको क्रिप्टोग्राफिक भेद्यता की परवाह नहीं है, तो कुछ अनुप्रयोगों में आप उन वितरणों की परवाह कर सकते हैं जिनके पास अत्यधिक, कृत्रिम रूप से परिणाम नहीं हैं। कुछ प्रकार के सिमुलेशन काफी विशेष रूप से परिणामों के काम करने की कोशिश कर रहे हैं असमतल परिणाम जो स्वाभाविक रूप से व्यक्तिगत रूप से यादृच्छिक परिणामों के बड़े नमूने के साथ होते हैं, लेकिन वे कुछ पीआरएनजी के परिणामों में कम प्रतिनिधित्व करते हैं। यदि आप अनुकरण करने की कोशिश कर रहे हैं कि कितनी बड़ी आबादी कुछ घटनाओं पर प्रतिक्रिया करती है, तो यह समस्या हो सकती है मौलिक अपने परिणामों को जंगली रूप से गलत निष्कर्षों में बदल दें।


एक ठोस उदाहरण देने के लिए: गणितज्ञ कहें कि पोकर मशीन प्रोग्रामर बताता है कि 60 मिलियन अनुरूपित रोल के बाद - स्क्रीन के चारों ओर सैकड़ों छोटी "रोशनी" झिलमिलाहट करने के लिए प्रयोग किया जाता है, यदि 10,013,22 9 या उससे अधिक छक्के होते हैं, जो गणितज्ञ होने की अपेक्षा करता है मतलब से 1 stddev दूर, एक छोटा पेआउट होना चाहिए। प्रति 68-95-99.7 नियम (विकिपीडिया) इसके बारे में होना चाहिए 16% उस समय (~ 68% मानक विचलन के भीतर गिरते हैं / केवल आधे बाहर हैं)। अपने यादृच्छिक संख्या जनरेटर के साथ, यह औसत से ऊपर 3.5 मानक विचलन से है: अंडर 0.025% मौका - लगभग कोई ग्राहक इस लाभ को प्राप्त नहीं करता है। अभी उल्लेख किए गए पृष्ठ पर उच्च विचलन तालिका देखें, विशेष रूप से:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

76



आप यहां सेब और संतरे की तुलना कर रहे हैं। दो मानक विचलनों में एक-दूसरे के साथ बिल्कुल कुछ नहीं करना है। - Jbeuh


मैंने पासा रोल उत्पन्न करने के लिए अभी यह यादृच्छिक संख्या जेनरेटर लिखा है

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

आप इसे इस तरह इस्तेमाल करते हैं

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

इत्यादि आदि। क्या आप इस जनरेटर को ऐसे प्रोग्राम के लिए उपयोग करने में प्रसन्न होंगे जो पासा गेम चलाता है? याद रखें, इसका वितरण वही है जो आप "वास्तव में यादृच्छिक" जनरेटर से अपेक्षा करेंगे!

छद्म-यादृच्छिक संख्या जनरेटर अनिवार्य रूप से वही काम करते हैं - वे सही वितरण के साथ पूर्वानुमानित संख्याएं उत्पन्न करते हैं। वे इसी कारण से बुरे हैं कि उपरोक्त सरल यादृच्छिक संख्या जनरेटर खराब है - वे उन परिस्थितियों के लिए उपयुक्त नहीं हैं जहां आपको वास्तविक अप्रत्याशितता की आवश्यकता होती है, न केवल सही वितरण।


50



"छद्म-यादृच्छिक संख्या जेनरेटर ... सही वितरण के साथ पूर्वानुमानित संख्याएं उत्पन्न करते हैं" - सिर्फ इसलिए कि यह एक पीआरएनजी गारंटी नहीं देता है कि इसमें सही वितरण है (वास्तव में, वाणिज्यिक लोग बड़े पैमाने पर नहीं हैं, वास्तव में इन उत्तरों में उल्लिखित कारण)। जबकि वे पर्याप्त जानकारी (अनुमानित अलगो, बीज शुरू करने, आउटपुट मूल्य, डब्ल्यू / ई) के अनुमानित अनुमानित हो सकते हैं, फिर भी उनके पास भिन्नता है। - Brian S
बिंदु के अलावा, मुझे पता है, लेकिन get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on उल्लेख करने के लिए बस बहुत ही सुरुचिपूर्ण है :) - Janus Troelsen
@BrianS असल में, एक पीआरएनजी जो समय के साथ वितरण परीक्षण विफल रहा है परिभाषा के अनुसार अनुमान लगाया जाएगा। तो कुछ बड़े एन पर, यदि आप एन सिक्का फ्लिप में एन / 2 हेड से थोड़ा सा रास्ता भी प्राप्त करते हैं, तो आप सिर पर सट्टेबाजी शुरू कर सकते हैं, और आप हारने से ज्यादा जीत सकते हैं। इसी तरह, यदि आपको सिर बनाम पूंछ का सही वितरण मिल गया है, लेकिन सिर हमेशा जोड़े में आते हैं, तो फिर आपको जीतने के लिए एक नुस्खा होगा। वितरण परीक्षण यह है कि आप कैसे जानते हैं कि पीआरएनजी कोई अच्छा है। - Jon Kiparsky
तुम भूल गए nonlocal next :-)। - Kos
यहां तक ​​कि बेहतर उदाहरण: पीआई माना जाता है साधारण, जिसका अर्थ है कि किसी भी आधार में दी गई किसी भी लंबाई के अंकों का कोई भी अनुक्रम उस आधार में उस लंबाई के किसी अन्य अनुक्रम की तुलना में अक्सर नहीं होता है। एक एल्गोरिदम, जब के लिए पूछा गया n यादृच्छिक बिट्स, अगली लेता है n पीआई के बिट्स और उन्हें वापस लौटाता है ("बीज" वह चीज है जिसे आप शुरू करते हैं), लंबे समय तक पूरी तरह से वितरण का उत्पादन करना चाहिए। लेकिन आप अभी भी इसे अपने जनरेटर के लिए नहीं चाहते हैं - जो कोई भी आपके द्वारा जेनरेट किए गए बिट्स के आखिरी गुच्छा को जानता है, वह पहली बार हो सकता है कि अनुक्रम होता है, मान लें कि आपका बीज वहां है, और संभवतः सही हो सकता है। - cpast


यादृच्छिक संख्या पीढ़ी आपके कंप्यूटर को निष्पादित कर सकती है, अधिकांश जरूरतों के लिए उपयुक्त है, और आपको ऐसे समय में आने की संभावना नहीं है जहां आपको वास्तव में यादृच्छिक संख्या की आवश्यकता हो।

सही यादृच्छिक संख्या पीढ़ी के हालांकि इसके उद्देश्य हैं। कंप्यूटर सुरक्षा में, जुआ, बड़े सांख्यिकीय नमूना आदि।

यदि आप यादृच्छिक संख्या के अनुप्रयोगों में रूचि रखते हैं तो देखें विकिपीडिया लेख


26



बड़ा मुद्दा यह है कि जब आपको यादृच्छिक संख्या की आवश्यकता होती है कि हमलावर सुरक्षा कारणों से भविष्यवाणी नहीं कर सकता है। - David Schwartz
आप निश्चित रूप से नरक के रूप में आने की संभावना रखते हैं जहां आपको वास्तव में यादृच्छिक संख्या की आवश्यकता होती है। यह शुरू करने वाला एक वेब पेज खोलने के लिए पर्याप्त है https://... - Jan Hudec
@JanHudec: ठीक है, दैनिक उपयोग में, आपको किसी भी प्रोग्राम को खोलने के पल में सुरक्षित यादृच्छिक संख्या की आवश्यकता होगी, इससे पहले कि आप पता बार में टाइप कर रहे हों: देखें पता स्थान लेआउट यादृच्छिकता। इसीलिए इस तरह की चीजें हो जाता। - Reid
@ जेनहुडक मैं विशेष रूप से इस अर्थ में बोल रहा था कि आपको ऑनलाइन यादृच्छिक संख्या जनरेटर का उपयोग करने की आवश्यकता होगी। सही यादृच्छिक संख्याओं का अक्सर उपयोग किया जाता है, लेकिन बहुत कम लोगों को वास्तव में उन्हें स्वयं उत्पन्न करने की आवश्यकता होती है। - Alex McKenzie
स्लॉट मशीनें भी एक पीआरएनजी का उपयोग करती हैं, न कि एक टीआरएनजी। जनरेटर हर समय चलता है और स्पिन बटन धक्का दिया जाता है कि सही समय पर एक संख्या उठाई जाती है। पीआरएनजी का योग और वास्तव में यादृच्छिक बटन प्रेस समय एक टीआरएनजी के बराबर है। - Roger Dahl


अधिकांश प्रोग्रामिंग भाषाओं में सामान्य कार्यों द्वारा उत्पन्न यादृच्छिक संख्या पूरी तरह से यादृच्छिक संख्या नहीं हैं। वे छद्म यादृच्छिक संख्या हैं। चूंकि वे पूरी तरह से यादृच्छिक संख्या नहीं हैं, इसलिए उन्हें पहले जेनरेट की गई संख्याओं पर पर्याप्त जानकारी के साथ अनुमान लगाया जा सकता है। तो यह एक होगा क्रिप्टोग्राफी में सुरक्षा के लिए आपदा

उदाहरण के लिए निम्नलिखित यादृच्छिक संख्या जनरेटर फ़ंक्शन का उपयोग किया जाता है glibc पूरी तरह से यादृच्छिक संख्या उत्पन्न नहीं करता है। इस द्वारा उत्पन्न छद्म यादृच्छिक संख्या अनुमान लगाया जा सकता है। सुरक्षा मुद्दों के लिए यह एक गलती है। यह विनाशकारी बनने का इतिहास है। इसका उपयोग क्रिप्टोग्राफी में नहीं किया जाना चाहिए।

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

इस प्रकार के छद्म यादृच्छिक संख्या जनरेटर को कभी भी सुरक्षा संवेदनशील स्थानों में कभी भी उपयोग नहीं किया जाना चाहिए, भले ही सांख्यिकीय रूप से काफी महत्वपूर्ण हो।

छद्म यादृच्छिक कुंजी पर प्रसिद्ध हमलों में से एक पर हमला है 802.11 बी WEP। WEP में 104-बिट लंबी अवधि की कुंजी है, जो 128 बिट कुंजी बनाने के लिए 24-बिट IV (काउंटर) के साथ संयोजित है, जो बदले में लागू होती है आरसी 4 एल्गोरिदम छद्म यादृच्छिक कुंजी उत्पन्न करने के लिए।

( RC4( IV + Key ) ) XOR (message)

चाबियाँ एक दूसरे के साथ निकटता से संबंधित थीं। यहां, केवल चतुर्थ प्रत्येक चरण में 1 से बढ़ी है और बाकी सभी एक ही बने रहे हैं। चूंकि यह पूरी तरह से यादृच्छिक नहीं था, यह विनाशकारी और आसानी से टूट गया था। 40000 फ्रेम का विश्लेषण करके कुंजी को पुनर्प्राप्त किया जा सकता है, जो मिनटों का मामला है। यदि WEP पूरी तरह यादृच्छिक 24-बिट IV का उपयोग करता है, तो यह लगभग 2 ^ 24 (लगभग 16.8 मिलियन) फ्रेम तक सुरक्षित हो सकता है।

तो जब संभव हो तो सुरक्षा संवेदनशील मुद्दों में शुद्ध यादृच्छिक संख्या जनरेटर के साथ जाना चाहिए।


26



मैं एक कमजोर सिफर का उपयोग कर एक बुरी तरह से डिजाइन प्रोटोकॉल पर WEP सामान को दोष दूंगा। आधुनिक स्ट्रीम सिफर के साथ आप एक काउंटर का उपयोग IV के रूप में कर सकते हैं। - CodesInChaos
WEP के साथ मुख्य समस्या 2 ^ 24 (लगभग 16 मिलियन) फ्रेम में कुंजी दोहरा रही थी। यह संबंधित कुंजी के साथ भी बदतर था जिसने 40000 फ्रेम में कोड को क्रैक करना संभव बना दिया। यहां मुख्य बिंदु यह है कि कुंजी यादृच्छिक नहीं है। यह निकटता से संबंधित है, इसलिए यह क्रैक करना आसान है। - Prabhu
क्रिप्टोग्राफी में छद्म-यादृच्छिकता खराब है केवल क्रिप्टोग्राफिक कुंजी उत्पन्न करते समय। यह उससे परे बिल्कुल ठीक है। दरअसल, आरसी 4 संदेश के सादे पाठ पर कुंजी एक्सओआरड के 128-बिट विस्तार के साथ बीजित छद्म-यादृच्छिक संख्या जनरेटर से थोड़ा अधिक है। - Matt


अंतर यह है कि छद्म यादृच्छिक उत्पन्न संख्या कुछ समय बाद अनुमानित (दोहराई जा रही है) जहां वास्तविक यादृच्छिक संख्याएं नहीं हैं। दोहराने के लिए जो लंबाई लगती है वह बीज की लंबाई पर निर्भर करती है जिसका उपयोग इसकी पीढ़ी के लिए किया जाता है।

यहां उस विषय के बारे में एक बहुत अच्छा वीडियो है: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



भविष्यवाणी! = दोहराना। मेर्सन ट्विस्टर इसका एक अच्छा उदाहरण है। 624 इंट 32 के बाद अधिकांश कार्यान्वयन पर आप सभी अगले नंबर की भविष्यवाणी कर सकते हैं, लेकिन मेर्सन ट्विस्टर अनुक्रम उस से अधिक लंबा है (2 ^ 19937 - 1)। - HoLyVieR
मुझे समझ में नहीं आता कि यह जवाब ढेर को क्यों नहीं धकेलता है, क्योंकि ऐसा लगता है कि यह कम से कम आंशिक रूप से प्रश्न का सटीक और संक्षिप्त उत्तर है। कुछ ड्रॉ के बाद छद्म यादृच्छिक संख्याओं की आसानी से भविष्यवाणी की जा सकती है, छद्म यादृच्छिक एल्गोरिदम "गुणवत्ता" के साथ अलग-अलग ड्रॉ की संख्या। "अच्छा" एल्गोरिदम चुनना पहलुओं को देख रहा है: 1. प्रत्येक मान बराबर आवृत्ति (वितरण) में खींचा जाता है, 2. शुरुआत में अनुक्रम को पुनरारंभ करने में "लंबा समय" लगता है और फिर उसी संख्या को फिर से खींचना शुरू करता है वहीआज्ञा। - mins
"सच यादृच्छिक संख्याएं [अनुमानित] नहीं हैं"। आज के लिए यह सच है। अब अगर हम बिग बैंग सिद्धांत में विश्वास करते हैं, और हमारे पास भौतिकी के आधार पर बीबी के बाद किसी भी समय ब्रह्मांड की स्थिति की गणना करने के लिए बहुत सारी शक्ति है ... हम भविष्य की भविष्यवाणी करने में सक्षम हैं, इस तथ्य सहित मैं यह बहुत सटीक टिप्पणी लिख रहा हूं। सही? - mins
यह अनुमानित रूप से सच है, हालांकि, असली निकायों के वास्तविक कार्यों में शामिल एन्ट्रॉपी की विशाल डिग्री पर विचार करते हुए, आवश्यक कंप्यूटिंग शक्ति हास्यास्पद रूप से बड़ी होगी। कंप्यूटर में शामिल महाद्वीप सोचो। इसके अलावा, पिछले राज्य पर निर्भरता के कारण, समय पर हर बिंदु पर ब्रह्मांड में प्रत्येक शरीर की स्थिति को संग्रहीत करने की आवश्यकता होगी, जिसे परिभाषा के अनुसार ब्रह्मांड में उपलब्ध होने से अधिक जगह की आवश्यकता होगी, पूरी तरह से स्मृति उपकरण से भरा होगा - TheEnvironmentalist
@TheEnvironmentalist - आह! "कंप्यूटरों में शामिल महाद्वीप" ... क्या यह "द हिचहिकर गाइड टू गैलेक्सी" के बारे में नहीं है? ;-) - ysap


मान लें कि उत्पन्न होने से पहले किसी छद्म यादृच्छिक संख्या का अनुमान लगाया जा सकता है।

छोटे अनुप्रयोगों के लिए एक छद्म यादृच्छिकता ठीक है, जैसा कि आपके उदाहरण के साथ, आपको कुछ मामूली विविधता के साथ लगभग सही प्रतिशत (कुल परिणाम सेट का लगभग 1/6 वां) मिलेगा (जो आप देखेंगे कि क्या आप पासा 600k रोल करना चाहते हैं बार);

हालांकि, जब कंप्यूटर सुरक्षा जैसी चीजों की बात आती है; सही यादृच्छिकता की आवश्यकता है।

उदाहरण के लिए आरएसए एल्गोरिदम कंप्यूटर के साथ दो यादृच्छिक संख्या (पी और क्यू) चुनने से शुरू होता है और फिर उन नंबरों पर कई कदम उठाता है जो आपकी सार्वजनिक और निजी कुंजी के रूप में जाने वाली विशेष संख्याएं उत्पन्न करते हैं। (एक निजी कुंजी का महत्वपूर्ण हिस्सा यह है कि यह निजी है, और कोई और इसे जानता है!)

यदि कोई हमलावर यह जान सकता है कि आपके कंप्यूटर को कौन से 'यादृच्छिक' नंबरों को चुनने जा रहे हैं, तो वे आपकी निजी कुंजी की गणना करने के लिए एक ही कदम उठा सकते हैं (वह जिसे कोई और नहीं जानता है!)

आपकी निजी कुंजी के साथ एक हमलावर ए जैसी चीजें कर सकता है) अपने बैंक से बात करने का नाटक करते हुए, बी) अपने 'सुरक्षित' इंटरनेट यातायात को सुनें और इसे डीकोड करने में सक्षम हो, सी) इंटरनेट पर आप और अन्य पार्टियों के बीच मास्करेड।

यही वह जगह है जहां वास्तविक यादृच्छिकता (यानी अनुमानित / गणना करने में सक्षम नहीं है) आवश्यक है।


10





पहले यादृच्छिक संख्या जो मैंने कभी भी उपयोग की थी, उसमें लगातार दो यादृच्छिक संख्याओं की उत्कृष्ट संपत्ति थी, दूसरा 0.6 की संभावना के साथ बड़ा था। 0.5 नहीं और तीसरा संभावना 0.6 के साथ दूसरे की तुलना में बड़ा था, और इसी तरह। आप कल्पना कर सकते हैं कि यह सिमुलेशन के साथ कैसे काम करता है।

कुछ लोग मुझ पर विश्वास नहीं करेंगे यह यादृच्छिक संख्याओं को समान रूप से वितरित करने के साथ भी संभव था, लेकिन यदि आप अनुक्रम (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) जहां संभाव्यता 0.6 के साथ दो संख्याओं में से दूसरा बड़ा है।

दूसरी तरफ, सिमुलेशन के लिए यादृच्छिक संख्याओं को पुन: उत्पन्न करने में सक्षम होना महत्वपूर्ण हो सकता है। आइए मान लें कि आप यातायात सिमुलेशन करते हैं और यह जानना चाहते हैं कि आप कितनी कार्रवाइयां ले सकते हैं यातायात में सुधार कर सकते हैं। उस स्थिति में आप ट्रैफिक को बेहतर बनाने के लिए किए गए विभिन्न कार्यों के साथ सटीक वही ट्रैफ़िक डेटा (जैसे शहर में प्रवेश करने का प्रयास करने वाले लोगों) को फिर से बनाने में सक्षम होना चाहते हैं।


10





संक्षिप्त जवाब यह है कि आमतौर पर लोगों को बुरे कारण के लिए "सच्ची यादृच्छिकता" की आवश्यकता होती है, अर्थात् उन्हें क्रिप्टोग्राफी की कोई समझ नहीं है।

जैसे क्रिप्टोग्राफिक प्राइमेटिव्स धारा सिफर तथा CSPRNGs एक बार अप्रत्याशित बिट्स खिलाए जाने के बाद अप्रत्याशित बिट्स की विशाल धाराओं का उत्पादन करने के लिए उपयोग किया जाता है।

सावधान पाठक को अब एहसास हुआ होगा कि बूटस्ट्रैपिंग समस्या यहां है: हमें इसे शुरू करने के लिए एंट्रॉपी के कुछ बिट्स इकट्ठा करना होगा। फिर उन्हें एक खिला सकते हैं CSPRNG जो बदले में हमें आवश्यक सभी अप्रत्याशित बिट्स प्रदान करेगा। इस प्रकार एक सीएसपीआरएनजी बीज करने के लिए एक हार्डवेयर आरएनजी की आवश्यकता होती है। यह एकमात्र मामला है जहां सत्य में एन्ट्रॉपी की आवश्यकता होती है।

(मुझे लगता है कि इसे सुरक्षा या क्रिप्टोग्राफी में पोस्ट किया जाना चाहिए था।)

संपादित करें: अंत में, किसी को एक यादृच्छिक संख्या जेनरेटर चुनना चाहिए जो कि कार्यवाही के लिए पर्याप्त है और जहां तक ​​यादृच्छिक संख्या पीढ़ी का संबंध है, हार्डवेयर आवश्यक रूप से समान नहीं है। खराब पीआरएनजी की तरह, हार्डवेयर यादृच्छिक स्रोतों में आमतौर पर पूर्वाग्रह होते हैं।

संपादित करें: यहां कुछ लोग एक खतरे का मॉडल मानते हैं जिसमें एक हमलावर सीएसपीआरएनजी की आंतरिक स्थिति पढ़ सकता है और वहां से निष्कर्ष निकाला जा सकता है कि सीएसपीआरएनजी एक सुरक्षित समाधान नहीं है। यह खराब धागा मॉडलिंग का एक उदाहरण है। यदि कोई हमलावर आपके सिस्टम का मालिक है, तो खेल खत्म हो गया है, सादा और सरल है। इससे कोई फर्क नहीं पड़ता कि आप इस बिंदु पर एक टीआरएनजी या सीएसपीआरएनजी का उपयोग करते हैं या नहीं।

संपादित करें: तो, इस सब को समेटने के लिए ... एक सीएसपीआरएनजी बीज के लिए एंट्रॉपी की आवश्यकता होती है। एक बार ऐसा करने के बाद, एक सीएसपीआरएनजी उन सभी अप्रत्याशित बिट्स प्रदान करेगी जिन्हें हमें सुरक्षा अनुप्रयोगों के लिए बहुत तेज़ी से प्रदान करना होगा (आमतौर पर) एंट्रॉपी एकत्र कर सकते हैं। यदि अप्रत्याशितता की आवश्यकता नहीं है, जैसे अनुकरण के लिए, एक मेर्सन ट्विस्टर अच्छी सांख्यिकीय संपत्तियों के साथ संख्याओं को बहुत अधिक दर पर प्रदान करेगा।

संपादित करें: सुरक्षित यादृच्छिक संख्या पीढ़ी की समस्या को समझने के लिए तैयार कोई भी इसे पढ़ना चाहिए: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf


8



यह एक सुरक्षा सवाल जरूरी नहीं है। मुझे लगता है कि वास्तव में यादृच्छिक संख्याओं का उपयोग करने के कारण हैं जिनमें सुरक्षा शामिल नहीं है। अगर मैं कुछ वैज्ञानिक शोध कर रहा था जो यादृच्छिक संख्याओं पर निर्भर करता है और यह किसी भी कारण से महत्वपूर्ण है कि संख्या जितनी संभव हो उतनी यादृच्छिक हो, तो मैं निश्चित रूप से हार्डवेयर आरएनजी का लाभ उठाऊंगा ताकि मैं आश्वस्त रह सकूं कि मनाई गई कोई भी संपत्ति देय नहीं है आरएनजी के quirks करने के लिए। - Kef Schecter
@KefSchecter यह उनके सुना हुआ हार्डवेयर पीआरएनजी आमतौर पर पक्षपातपूर्ण और / या सहसंबंधित आउटपुट होता है। उन्हें एक समान प्रसंस्करण चरण में एक समान स्वतंत्र आउटपुट में बदलने की आवश्यकता है। इस बात पर विश्वास करने का कोई कारण नहीं है कि यह पोस्ट प्रोसेसिंग चरण आधुनिक स्ट्रीम सिफर से अधिक विश्वसनीय है। मैं निश्चित रूप से स्ट्रीम सिफर पर भरोसा करता हूं। एक अतिरिक्त बोनस के रूप में यह पुनरुत्पादित है, जो विज्ञान में मूल्यवान है। - CodesInChaos
ठीक है पर्याप्त ठीक है। लेकिन क्या क्रिप्टोग्राफी अनुप्रयोगों के लिए समान रूप से लागू नहीं होगा? यहां तक ​​कि उत्तर देने का जवाब भी कहता है कि आपको सीएसपीआरएनजी के बीज के लिए हार्डवेयर आरएनजी की आवश्यकता है। - Kef Schecter
@KefSchecter हां, क्रिप्टो अनुप्रयोगों को सीएसपीआरएनजी के बीज के लिए सही यादृच्छिक संख्या की आवश्यकता होती है। लेकिन बाकी सब कुछ के लिए हम उस सीएसपीआरएनजी का उपयोग कर सकते हैं। - CodesInChaos
@KefSchecter: क्रिप्टोग्राफिक अनुप्रयोगों की आवश्यकता है कि स्ट्रीम को दुनिया द्वारा बड़े पैमाने पर पुन: उत्पन्न नहीं किया जा सके। इसके विपरीत, वैज्ञानिक अनुप्रयोगों में, यह दिखाने में सक्षम होने के कारण कि "यादृच्छिक" संख्याओं का उपयोग करने के लिए केवल एक अच्छा प्रकाश में किसी के विश्लेषण को दिखाने के लिए चुना नहीं गया है। उदाहरण के लिए, यदि कोई व्यक्ति किसी के तरीकों की घोषणा करने के बाद घोषणा करता है कि कोई व्यक्ति अगले दिन की राज्य लॉटरी संख्याओं का उपयोग करके किसी निश्चित फैशन में डेटा उत्पन्न करेगा, तो पाठकों को कुछ हद तक आश्वस्त किया जा सकता है कि किसी ने अपने परिणामों को झुकाया नहीं है, भले ही सप्ताहांत ड्राइंग में केवल दो दर्जन हों एंट्रॉपी के बिट्स। - supercat