यादृच्छिक संख्या जनरेटर के बारे में बहुत कुछ लिखा गया है, लेकिन लगभग हमेशा, जब यह कार्यान्वयन की बात आती है, तो यह निहित है (या स्पष्ट रूप से कहा गया है) कि हम x86 / x64 और अन्य "वयस्क" आर्किटेक्चर के बारे में बात कर रहे हैं। इसी समय, माइक्रोकंट्रोलर पर उपकरणों के विकास के लिए समर्पित फ़ोरम "सवालों से भरा कैसे हो सकता है? इसके अलावा, उत्तर की सीमा "मानक फ़ंक्शन का उपयोग करने के लिए" Google / विकिपीडिया देखें "से फैली हुई है। हमेशा दूर से यह "मानक फ़ंक्शन" मौजूद होता है और डेवलपर को सभी तरह से सूट करता है, अधिक बार दूसरे तरीके से: या तो संख्याएं यादृच्छिक से बहुत दूर हैं, गति बहुत कम है, या परिणामस्वरूप कोड बिल्कुल भी मुफ्त मेमोरी में फिट नहीं होता है।
आइए यह पता लगाने की कोशिश करें कि यादृच्छिक संख्या पीढ़ी एल्गोरिदम क्या हैं, एक उपयुक्त एक का चयन कैसे करें, और सबसे महत्वपूर्ण बात, नियंत्रक पर इन एल्गोरिदम के कार्यान्वयन की विशेषताएं क्या हैं।
"यादृच्छिकता" का आकलन
खिलौनों से लेकर गंभीर क्रिप्टोग्राफी तक, RNG के लिए कई तरह से आवेदन मिल सकते हैं। तदनुसार, जनरेटर के लिए आवश्यकताएं भी बहुत भिन्न होती हैं। जनरेटर की गुणवत्ता ("यादृच्छिकता" का स्तर) का आकलन करने के लिए, विशेष परीक्षण हैं। यहाँ सबसे बुनियादी हैं:
- आवृत्ति परीक्षण। इसमें बिट्स के अनुक्रम में शून्य और लोगों की संख्या की गिनती होती है। इकाइयाँ और शून्य लगभग बराबर होनी चाहिए।
- समरूप बिट्स के अनुक्रम के लिए परीक्षण करें। हम फॉर्म के समान बिट्स की पंक्तियों को खोजते हैं 000 ... 0 या 111 ... 1। श्रृंखला द्वारा सामना की जाने वाली आवृत्तियों का वितरण, उनकी लंबाई के आधार पर, वास्तव में यादृच्छिक संकेत के लिए इस तरह के वितरण के अनुरूप होना चाहिए।
- वर्णक्रम परीक्षण। असतत फूरियर रूपांतरण मूल अनुक्रम पर लागू होता है। परिणामस्वरूप स्पेक्ट्रम में महत्वपूर्ण चोटियां नहीं होनी चाहिए जो आवधिक अनुक्रम गुणों की उपस्थिति का संकेत देंगी।
- स्वायत्तता परीक्षण। एक दूसरे के सापेक्ष स्थानांतरित किए गए अनुक्रम की प्रतियों के बीच सहसंबंध मूल्य की गणना की जाती है। परीक्षण आपको एक अनुक्रम में डुप्लिकेट अनुभाग खोजने की अनुमति देता है।
विशेष किट हैं जिनमें दर्जनों समान परीक्षण शामिल हैं:
एनआईएसटी - एईएस प्रतियोगिता में एन्क्रिप्शन एल्गोरिदम का मूल्यांकन करने के लिए उपयोग किया जाता है।
DIEHARD सबसे कठोर उपलब्ध सेटों में से एक है।
PRSP एल्गोरिदम
हार्ड-कोडित एल्गोरिथ्म द्वारा उत्पन्न किसी भी अनुक्रम को वास्तव में यादृच्छिक नहीं माना जा सकता है, इसलिए, जब एल्गोरिथम जनरेटर के बारे में बात की जाती है, तो वे
छद्म यादृच्छिक अनुक्रम शब्द का उपयोग करते हैं। किसी भी छद्म आयामी संख्या जनरेटर (PRNG) को जल्द या बाद में लूप किया जाता है, एक और बात यह है कि यह "देर" कुछ मिलीसेकंड में, या शायद कुछ वर्षों में हो सकती है। चक्र की लंबाई जनरेटर एन की आंतरिक स्थिति के आकार पर निर्भर करती है (वास्तव में, यह जनरेटर द्वारा आवश्यक मेमोरी की मात्रा है), और 2
(एन / 2) से 2
एन बिट्स तक होती है।
PRSP एल्गोरिदम की एक बड़ी संख्या का आविष्कार किया गया है, लेकिन उनमें से सभी माइक्रोकंट्रोलर पर कार्यान्वयन के लिए सुविधाजनक नहीं हैं। हम गति और उपलब्ध स्मृति में बहुत सीमित हैं, कई नियंत्रक वास्तविक अंकगणित और यहां तक कि गुणा निर्देश का समर्थन नहीं करते हैं। ऐसी सीमाओं को ध्यान में रखते हुए, हम कुछ प्रसिद्ध एल्गोरिदम पर विचार करते हैं।
रैखिक सर्वांगसम विधि
अनुक्रम के अगले सदस्य की गणना सूत्र द्वारा की जाती है
X
i + 1 = (aX
i + c) mod m
संख्या
एम अनुक्रम की अधिकतम अवधि निर्धारित करती है, पूर्णांक
एक और
सी "जादू" गुणांक हैं। दो की शक्ति के बराबर संख्या
एम का चयन करना उचित है, जिस स्थिति में कमी ऑपरेशन मोडुलो सबसे महत्वपूर्ण बिट्स को छोड़ने के लिए कम करता है। अधिकतम अवधि प्राप्त करने के लिए, निम्नलिखित शर्तों का पालन करना चाहिए:
-
सी और एम कोप्रेम होना चाहिए
- संख्या
-1 के सभी प्रमुख विभाजकों
p के लिए a-1 बहु गुणक होना चाहिए,
- यदि
m 4
का एक गुणक है (और हमारे मामले में यह एक बहु होगा), तो
a-1 का गुणक 4 होना चाहिए।
एक और सूक्ष्मता है: नतीजतन, केवल राज्य चर एक्स के उच्च बिट्स को लिया जाना चाहिए, क्योंकि यादृच्छिकता के सांख्यिकीय पैरामीटर निचले बिट्स के लिए बहुत खराब हैं। एक लीनियर कांग्रेजेंट एल्गोरिथ्म आमतौर पर कई पुस्तकालयों में मानक रैंड () के रूप में लागू किया जाता है।
पेशेवरों:- राज्य चर के दिए गए आकार के लिए अधिकतम संभव अवधि;
- काफी तेज;
- अक्सर पहले से ही संकलक पुस्तकालय में लागू किया गया।
विपक्ष:- गुणन ऑपरेशन की आवश्यकता है;
- सभी बिट्स समान रूप से यादृच्छिक नहीं हैं।
सारांश: नहीं-महत्वपूर्ण अनुप्रयोगों के लिए
एक त्वरित और आसान एल्गोरिथ्म।
देरी के साथ फाइबोनैचि विधि
यह एल्गोरिथ्म संबंध का उपयोग करता है
X
i = X
ia - X
ib ,
जहां राज्य चर
X एक अहस्ताक्षरित पूर्णांक है। विलंब मानों को
ए और
बी न केवल लिया जाता है, बल्कि सख्ती से निर्धारित किया जाता है; अधिकतम गुणवत्ता प्राप्त करने के लिए, जोड़े (17.5), (55.24) या (97.33) की सिफारिश की जाती है। विलंब जितना अधिक होगा, अवधि और अनुक्रम के वर्णक्रमीय गुण बेहतर होंगे। दूसरी ओर, जनरेटर को काम करने के लिए, पिछली संख्याओं के अधिकतम {ए, बी} को स्टोर करना आवश्यक है, जो हमेशा स्वीकार्य नहीं होता है। इसके अलावा, जनरेटर शुरू करने के लिए, आपको अधिकतम {a, b} संख्याओं की आवश्यकता होती है, जो आमतौर पर एक सरल PRNG का उपयोग करके प्राप्त की जाती है।
पेशेवरों:- गुणन संचालन की आवश्यकता नहीं है;
- यादृच्छिक संख्या के सभी बिट्स सांख्यिकीय गुणों के बराबर हैं।
विपक्ष:- स्मृति की एक बड़ी मात्रा की आवश्यकता होती है;
- चलाने के लिए बड़ी संख्या में संख्याओं की आवश्यकता होती है।
सारांश: एक बहुत ही उच्च गुणवत्ता, लेकिन संसाधन-गहन एल्गोरिथ्म।
रैखिक प्रतिक्रिया पारी रजिस्टर
राज्य चर को N की लंबाई के रजिस्टर में संग्रहित किया जाता है। निम्न अवस्था उत्पन्न करने में दो चरण शामिल हैं:
- बिट मान C = X i1 xor X i2 xor ... X ik की गणना की जाती है , जहां i1, i2 ... ik रजिस्टर होते हैं जिन्हें टैप कहा जाता है।
- रजिस्टर को दाईं ओर 1 बिट स्थानांतरित किया गया है, बाईं ओर बिट मान C लेता है ।
जनरेटर का उत्पादन सबसे सही (या सबसे बाईं ओर, या किसी अन्य) रजिस्टर बिट है, अर्थात्, छद्म यादृच्छिक अनुक्रम प्रति पुनरावृत्ति में एक बिट उत्पन्न होता है। सही ढंग से चयनित शाखा संख्याओं के साथ, जनरेटर अवधि 2
एन - 1. "माइनस एक" होगी, क्योंकि रजिस्टर की निषिद्ध शून्य स्थिति है। 3 से 168 तक
एन के लिए शाखा संख्या
इस दस्तावेज़ में पाई जा सकती है।
ऊपर वर्णित कॉन्फ़िगरेशन के अलावा, जो, वैसे, फाइबोनैचि कॉन्फ़िगरेशन कहा जाता है (उसी नाम के PRNG विधि के साथ भ्रमित नहीं होना चाहिए!), एक तथाकथित है। गैलोज विन्यास।
नए सबसे बाएं बिट को उत्पन्न करने के लिए टैप अनुक्रम के बिट्स के योग का उपयोग करने के बजाय, सही अनुक्रम के साथ टैप अनुक्रम के प्रत्येक बिट को निष्पादित किया जाता है, फिर पूरे रजिस्टर को दाईं ओर साइकिल किया जाता है। इस योजना को समझना अधिक कठिन है, लेकिन इसे लागू करना आसान है, क्योंकि सभी XOR ऑपरेशन एक साथ किए जा सकते हैं। फाइबोनैचि और गैलोज़ योजनाएं अवधि की लंबाई और छद्म आयामी संख्या की गुणवत्ता के बराबर हैं।
पेशेवरों:- बहुत सरल कार्यान्वयन, यहां तक कि अंकगणित की आवश्यकता नहीं है, केवल बिट संचालन और पारियों;
- बहुत तेज एल्गोरिथ्म (विशेषकर गैलोज़ योजना);
- अच्छे सांख्यिकीय गुण।
विपक्ष:- आपको शून्य के लिए असमानता के लिए प्रारंभिक मूल्य की जांच करने की आवश्यकता है।
सारांश: एक बहुत तेज और काफी उच्च गुणवत्ता वाला एल्गोरिथ्म।
क्रिप्टोग्राफिक एल्गोरिदम
क्रिप्टोग्राफी में उपयोग के लिए, PRSP को एक और आवश्यक आवश्यकता के साथ प्रस्तुत किया गया है:
अपरिवर्तनीयता । उपरोक्त सभी एल्गोरिदम के पास यह संपत्ति नहीं है: PRNG के कई आउटपुट मानों को जानते हुए, यह संभव है कि समीकरणों की एक सरल प्रणाली को हल किया जाए, एल्गोरिदम के मापदंडों (बहुत "जादू" को
एक, बी, सी , आदि को खोजने के लिए)। और मापदंडों को जानते हुए, आप पूरे छद्म यादृच्छिक क्रम को पुन: उत्पन्न कर सकते हैं।
किसी भी पर्याप्त रूप से मजबूत ब्लॉक सिफर को क्रिप्टोग्राफिक रूप से मजबूत PRNG एल्गोरिदम के रूप में इस्तेमाल किया जा सकता है। एक गुप्त कुंजी चुनना, आप एल्गोरिथ्म को लगातार प्राकृतिक संख्याओं पर लागू करके छद्म आयामी संख्याओं के ब्लॉक प्राप्त कर सकते हैं। एन-बिट ब्लॉक सिफर के लिए, अवधि 2
एन से अधिक नहीं होगी
। ऐसी योजना की सुरक्षा पूरी तरह से कुंजी की सुरक्षा पर निर्भर करती है।
सभी आधुनिक क्रिप्टोग्राफ़िक एल्गोरिदम को PRNG के रूप में उपयोग करने के लिए परीक्षण किया जाता है, अर्थात्, प्रमाणित एल्गोरिथ्म का उपयोग करके, आपको आउटपुट स्ट्रीम के सांख्यिकीय और वर्णक्रमीय गुणों के बारे में विशेष रूप से ध्यान रखने की आवश्यकता नहीं है। आपको केवल क्रिप्टोग्राफिक एल्गोरिदम के कम्प्यूटेशनल "ग्लुटोनी" के बारे में चिंता करने की आवश्यकता है। यदि आपको बड़ी संख्या में एन्क्रिप्शन ऑपरेशन करने की आवश्यकता है, तो हार्डवेयर क्रिप्टोग्राफ़िक इकाइयों के साथ नियंत्रक का चयन करना समझ में आता है। अक्सर ऐसे नियंत्रकों में एक बहुत अच्छा क्रिप्टो-प्रतिरोधी हार्डवेयर PRNG भी होता है।
एन्ट्रॉपी के स्रोत
जैसा कि पहले ही उल्लेख किया गया है, केवल नियतात्मक एल्गोरिदम का उपयोग करके, वास्तव में यादृच्छिक संख्या उत्पन्न करना असंभव है। इसलिए, आमतौर पर PRNG +
एन्ट्रॉपी के बाहरी
स्रोत का एक संयोजन
उपयोग किया जाता है । एनआरपीजी के लिए प्रारंभिक मूल्य निर्धारित करने के लिए एन्ट्रापी के स्रोत का उपयोग किया जाता है, और बाद का कार्य अनुक्रम के वर्णक्रमीय और सांख्यिकीय शुद्धता को सुनिश्चित करना है। एंट्रोपी के स्रोत के रूप में क्या इस्तेमाल किया जा सकता है? हाँ, लगभग कुछ भी।
उपयोगकर्ता गतिविधि
यदि डिवाइस किसी भी तरह से उपयोगकर्ता के साथ बातचीत करता है, तो यह एक स्रोत के रूप में उपयोगकर्ता की एन्ट्रापी का उपयोग करने के लिए एक अच्छा समाधान होगा। उदाहरण के लिए, एक बटन को दबाने में लगने वाला समय, माइक्रोसेकंड (या इसके निचले अंक) तक सटीक मापा जाता है, पूरी तरह से अप्रत्याशित है। हालांकि, अक्सर डिवाइस को स्वायत्त रूप से काम करना चाहिए, जिसका अर्थ है कि हम जानकारी के इस अद्भुत चैनल को खो रहे हैं।
डिजिटल कनवर्टर के अनुरूप
कई नियंत्रकों में अंतर्निहित ADCs हैं। और कई नियंत्रकों में वे बहुत औसत दर्जे की गुणवत्ता के हैं, बस "होने के लिए।" एडीसी परिणाम के कम-क्रम बिट्स में हमेशा महत्वपूर्ण शोर होता है, भले ही एक स्थिर वोल्टेज मापा जाता हो। इसका उपयोग किया जा सकता है: डिवाइडर के माध्यम से एडीसी इनपुट को आपूर्ति वोल्टेज से कनेक्ट करें, कुछ दर्जन माप लें, कम-ऑर्डर बिट्स लें - यह एक महान यादृच्छिक संख्या है। यदि ADC में एक अंतर्निहित preamplifier है, तो इसे चालू करें, यह भी शोर है।
अतुल्यकालिक जेनरेटर
आप दो असंबद्ध घड़ियों के बीच की अवधि के अंतर का उपयोग कर सकते हैं। अधिकांश नियंत्रक होते हैं, उदाहरण के लिए, एक प्रहरी। विश्वसनीयता बढ़ाने के लिए, यह एक अलग जनरेटर से देखा जाता है, मुख्य घड़ी संकेत के साथ किसी भी तरह से जुड़ा नहीं है। यह एक घड़ी की अवधि के लिए मुख्य घड़ी संकेत के घड़ी चक्रों की संख्या की गणना करने के लिए पर्याप्त है। यदि आप अवधि का चयन करते हैं ताकि माप के दौरान काउंटर कई बार ओवरफ्लो हो जाए, तो आप एक काफी यादृच्छिक संख्या प्राप्त कर सकते हैं। इस पद्धति का नुकसान यह है कि इसमें कई सेकंड तक बहुत समय की आवश्यकता होती है।
वास्तविक समय घड़ी
यदि सर्किट में
वास्तविक समय की घड़ी है , तो आप PRNG को इनिशियलाइज़ करने के लिए उनके वर्तमान रीडिंग का उपयोग कर सकते हैं। उदाहरण के लिए, वर्तमान दिनांक / समय को
यूनिक्स समय प्रारूप में परिवर्तित करते हुए, हमें तुरंत 32 बिट्स मिलते हैं, जो
कभी भी दोहराए
नहीं जाएंगे, जब तक कि आप रीडिंग को प्रति सेकंड एक बार से अधिक बार न लें। वास्तविक समय का उपयोग करना मूल्यों की विशिष्टता देता है, लेकिन कोई अप्रत्याशितता नहीं देता है, इसलिए इस पद्धति को दूसरों के साथ जोड़ना बेहतर है।
आरसी सर्किट
यदि नियंत्रक के पास I / O पोर्ट के अलावा कोई परिधीय उपकरण नहीं है, तो आप निम्न कार्य कर सकते हैं: एक पैर कैपेसिटर के माध्यम से जमीन पर जुड़ा हुआ है, और एक प्रतिरोध के माध्यम से आपूर्ति वोल्टेज के लिए। यदि नियंत्रक इनपुट में आंतरिक पुल-अप प्रतिरोध है, तो बाहरी अवरोधक की आवश्यकता नहीं है।
हम इस पोर्ट पर सिग्नल "0" आउटपुट करते हैं - कैपेसिटर को डिस्चार्ज किया जाता है। पोर्ट को इनपुट मोड में स्विच करें - कैपेसिटर चार्ज करना शुरू कर देता है। जब यह भर में वोल्टेज दहलीज पर पहुंच जाता है, तो इनपुट "0" से "1" स्थिति में बदल जाएगा। चार्ज समय कई कारकों पर निर्भर करता है: आपूर्ति वोल्टेज, आरसी-सर्किट मापदंडों का बहाव, थ्रेशोल्ड अस्थिरता, तापमान, रिसाव, हस्तक्षेप। पर्याप्त सटीकता के साथ इसे मापने और कम से कम महत्वपूर्ण बिट्स लेने से, आपको एक अच्छा मौका मिल सकता है।
हार्डवेयर शोर जनरेटर
कई गंभीर अनुप्रयोगों (मुख्य रूप से क्रिप्टोग्राफी) के लिए, ऊपर सूचीबद्ध लोगों की तुलना में एन्ट्रापी का अधिक विश्वसनीय स्रोत आवश्यक है। ऐसे मामलों में,
थर्मल ,
शॉट या
क्वांटम प्रभाव के आधार पर एक शोर जनरेटर से सिग्नल को
डिजिटल रूप में उपयोग किया जाता है। शोर तत्व आमतौर पर एक विशेष डायोड या जेनर डायोड होता है, जिसमें से संकेत को प्रवर्धित किया जाता है और एक द्विआधारी बिट स्ट्रीम बनाने वाले तुलनित्र को खिलाया जाता है।
आदेश में कि तुलनित्र की सीमा प्राप्त संकेत के सांख्यिकीय गुणों को प्रभावित नहीं करती है, एक तुलनित्र पर काम करने वाले दो शोर जनरेटर का उपयोग किया जाता है:
निष्कर्ष
अंत में, मैं आपको जीवन की एक कहानी सुनाऊंगा। यह मंच पर पूछे गए अगले प्रश्न के साथ शुरू हुआ: "मैं नियंत्रक पर एक यादृच्छिक संख्या कैसे उत्पन्न करूं?"। प्रश्न के लेखक ने समझाया कि वह एक शब्द के रूप में क्या कर रहा था एक उपकरण जो पासा फेंकने का अनुकरण करता है। एल्गोरिदम को समझने की कई असफल कोशिशों के बाद, शीर्ष स्टार्टर ने अपना निर्णय साझा किया: उसने सिर्फ 1000 बार एक वास्तविक मौत को फेंक दिया और प्राप्त संख्याओं के साथ नियंत्रक की संपूर्ण मुफ्त मेमोरी को स्कोर किया। जनरेटर ने "यादृच्छिकता" के लिए सभी परीक्षणों को शानदार ढंग से पारित किया, यह देखते हुए कि प्रदर्शन के दौरान यह अपने "स्टॉक" के एक तिहाई से भी कम खर्च किया।
इसलिए, इस तरह के निर्णय में जीवन का अधिकार भी होता है, खासकर यदि संख्याओं की यादृच्छिकता पर बहुत सख्त आवश्यकताएं लागू की जाती हैं, लेकिन उन्हें बहुत बार आवश्यकता नहीं होती है। मेमोरी के लिए तेजी से गिरती कीमतों को देखते हुए, डिवाइस को "फ्लैश मार्जिन" के साथ यूएसबी फ्लैश ड्राइव से लैस करना बुद्धिमान हो सकता है, जो डिवाइस के पूरे जीवन के लिए पर्याप्त है।
आपका ध्यान के लिए धन्यवाद!
UPD1: जैसा कि टिप्पणियों में सही लिखा गया था, यदि RNG पर हमला माना जाता है, और हमलावर के पास डिवाइस तक हार्डवेयर पहुंच है, तो बड़ी सावधानी से एंट्रोपी के बाहरी स्रोतों का उपयोग करना आवश्यक है, क्योंकि सिग्नल को बाहरी स्रोत से बदलना बहुत मुश्किल नहीं है। बाहरी स्रोतों के अलावा, आंतरिक स्रोतों का उपयोग किया जाना चाहिए।
अपने सभी खाली समय में एन्ट्रापी को जमा करना भी एक अच्छा विचार है, और इसका उपयोग तब करें जब आपको एक और यादृच्छिक संख्या उत्पन्न करने की आवश्यकता हो। आमतौर पर ऐसे मामलों में तथाकथित
एन्ट्रॉपी पूल - एक ऐसा सरणी जिस पर PRNG के कार्यों में से एक को समय-समय पर निष्पादित किया जाता है, और जहां एन्ट्रॉपी के स्रोतों के डेटा को लगातार मिलाया जाता है।
UPD2: कई मामलों में, यह EEPROM में एंट्रोपी पूल की सामग्री को बचाने के लिए उपयोगी है (क्षमा करें, मुझे सामान्य रूसी अनुवाद नहीं पता है) ताकि डिवाइस को बंद करने के बाद और उस पर फिर से जमा न हो। यह संदर्भित करता है, सबसे पहले, अतुल्यकालिक जनरेटर की विधि द्वारा एन्ट्रापी प्राप्त करना: काफी स्थिर परिस्थितियों में, प्रत्येक स्विचिंग पर एक ही अनुक्रम उत्पन्न किया जा सकता है।
यदि किसी हमले की उम्मीद है, तो EEPROM सामग्री को ख़राब करने के खिलाफ कार्रवाई करें। यदि नियंत्रक अनुमति देता है, तो लॉक बिट्स का उपयोग करके रीड / इरेज़ / राइट को लॉक करें, जब चालू हो, तो EEPROM की अखंडता की निगरानी करें, कम से कम सरलतम चेकसम का उपयोग करें।