Fortuna: पैरानॉयड रैंडम नंबर जेनरेटर

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

यदि आपके पास ऐसा कोई उपकरण नहीं है, तो मैं एक बिल्ली के लिए पूछता हूं।

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

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

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

शोर

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

• आवक / जावक अनुरोध \ संदेश
• ओएस स्थिति (मुफ्त मेमोरी \ सीपीयू लोड)
• वर्तमान माउस निर्देशांक
• विभिन्न काउंटर
• वर्तमान स्क्रीनशॉट

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

यदि आप एन्ट्रापी के स्रोतों में सीमित हैं, तो यहाँ आपके लिए इसे खरोंच से लगभग लेने का एक नुस्खा है:

1. हम एक अलग धागा शुरू करते हैं जिसमें एक अनंत लूप में हम एक पूर्णांक चर बढ़ाते हैं
2. एक बार मिलीसेकंड में हम एक दूसरे धागे को उसके पिछले बिट से देखते हैं और उसे सहेजते हैं (बिना रोक-टोक के)
3. 1 सेकंड के बाद, आपके पास अच्छी गुणवत्ता के एंट्रोपी के ~ 1000 बिट्स हैं

आप प्रत्येक मिलीसेकंड एक बार बिट्स की संख्या को भिन्न कर सकते हैं। एंट्रॉपी की गुणवत्ता बिट्स की संख्या के विपरीत आनुपातिक होगी, लेकिन इसकी पीढ़ी की दर बिट्स की संख्या अधिक होगी।
इसके अलावा, आप 1 से अधिक एमएस प्रतीक्षा कर सकते हैं, फिर इस वितरित अंतिम पक्ष पर साइड प्रक्रियाओं का प्रभाव और भी अधिक होगा, और तदनुसार, इसकी "यादृच्छिकता" की गुणवत्ता में सुधार होगा।

ऐसे जनरेटर के नुकसान स्पष्ट हैं:

• बहुत कम पीढ़ी दर।
• संचालन के दौरान प्रोसेसर कोर में से एक का पूर्ण भार

लेकिन वह तेजी से दुकानदारों के लिए "बीज" की भूमिका के लिए अच्छी तरह से अनुकूल है।

Fortuna

तो, हमारे पास एंट्रोपी के कुछ निश्चित स्रोत हैं, उनके साथ क्या करना है?

लगातार उन्हें एक PRNG खिलाएं

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

इसमें दो स्तर होते हैं।

1. एन्ट्रापी पूल
2. आंतरिक जनरेटर

पहले वाले 32 टुकड़े हैं, वे 32 से अधिक हैश (आपकी पसंद में से कोई भी) का प्रतिनिधित्व नहीं करते हैं, जिसमें हिंडोला सिद्धांत के अनुसार एंट्रोपी जोड़ा जाता है। संग्रह की अवधि के दौरान इन हैश को अंतिम रूप नहीं दिया जाता है (यानी, वे अंतिम मूल्य की गणना नहीं करते हैं), इस प्रकार ऑपरेशन के दौरान यादृच्छिक डेटा जमा करते हैं।

यह कल्पना करना आसान बनाने के लिए, समय के लिए ये 32 हैश बड़ी, बड़ी, बड़ी फाइलें और हैश नहीं है । बोल्ड में हाइलाइट करना महत्वपूर्ण है, इसके बाद स्पष्टीकरण दिया जाता है।

यही है, एक नया संदेश / अनुरोध आपके पास आया, आपने इसे फॉर्च्यून को दिया, उसने इसे संसाधित करने के लिए पूल नंबर 1 से पूछा।
ऊपर वर्णित जनरेटर द्वारा कई बाइट्स उत्पन्न किए गए थे, वहां भी, उसने पहले ही उन्हें दूसरे को दे दिया था।
और इसी तरह।

चूंकि ये हैश हैं, सभी आने वाले डेटा मेमोरी में जमा नहीं होते हैं, लेकिन उनकी आंतरिक स्थिति को बदलते हैं, अर्थात। स्मृति व्यर्थ नहीं है।

और इसलिए, हमारे पास 32 अच्छी तरह से खिलाए गए पूल हैं, आगे क्या है?

सबसे पहले, थोड़ा सा

इनर मंगोलिया डोमेस्टिक जेनरेटर

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

उदाहरण के लिए, हमने 100 बाइट के लिए जनरेटर से पूछा, यह 116 उत्पन्न करता है, हमें 100 देता है, और ब्लॉक सिफर के लिए नई एन्क्रिप्शन कुंजी के रूप में 16 (128 बिट) का उपयोग करता है।

उसी समय, काउंटर रीसेट नहीं किया जाता है, और प्रत्येक बाद के मूल्य को अलग-अलग कुंजी के साथ एन्क्रिप्ट किया जाता है।

मिक्स में

जनरेटर के लिए बहुत पहले एन्क्रिप्शन कुंजी मूल्य कहां से आता है और पूल सिस्टम कैसे काम करता है?

प्रारंभ में, आंतरिक जनरेटर को बाहरी डेटा के साथ आरंभ किया जाता है, जैसे सभी सामान्य जनरेटर। कोई जादू नहीं है।

लेकिन जब नंबर 1 पर पूल (हैश) द्वारा संसाधित बाइट्स की संख्या एक निश्चित सीमा (64 बाइट्स) से अधिक हो जाती है, तो एल्गोरिथ्म का सबसे सुंदर हिस्सा शुरू होता है।

फोर्टुना इस तरह की सकारात्मकता पर नज़र रखता है। इस काउंटर को रेसीड काउंट कहा जाता है और इसका अर्थ है "हमने कितनी बार आंतरिक जनरेटर की एन्क्रिप्शन कुंजी को बदल दिया है?"

वर्तमान रेसीड काउंट उन पूलों के सेट पर निर्भर करता है जो नई एन्क्रिप्शन कुंजी की पीढ़ी में भाग लेंगे

चूंकि हमारे पास 32 पूल हैं, "उनकी भागीदारी की डिग्री" इस बात पर निर्भर करती है कि ड्यूस गिनती तक किस सीमा तक पहुंच गया है।

हर बार पहले पूल का उपयोग किया जाता है।
दूसरा - यदि शेष संख्या को 2 से विभाजित करने का शेष शून्य है
तीसरा - यदि शेष संख्या को 4 से विभाजित करने का शेष शून्य है
आईटीडी

यही है, पूल संख्या जितनी अधिक होती है, उतनी ही कम बार इसका उपयोग किया जाता है और लंबे समय तक यह एन्ट्रॉपी जमा करता है। 32 वें पूल केवल 2 ^ 32 रेजीड ऑपरेशन के बाद वापस आ जाएंगे।

reseed

तो, यह आंतरिक जनरेटर की एन्क्रिप्शन कुंजी को बदलने का समय है।
हम अंत में उन पूलों के हैश को अंतिम रूप देते हैं जो वर्तमान रेसेड में भाग ले रहे हैं। हमें भाग लेने वाले पूलों की संख्या का एक बाइट सरणी मिलता है * हैश बाइट्स की संख्या।
और इसे आंतरिक जनरेटर को दें।
जनरेटर इन सभी बाइट्स को लेता है, वहां अपनी वर्तमान एन्क्रिप्शन कुंजी को मिलाता है (जो, जैसा कि हम याद करते हैं, डेटा पीढ़ी के बाद हर बार बदलते हैं), सब कुछ हैश भी करता है और इस हैश को अपने लिए एक नई एन्क्रिप्शन कुंजी के रूप में उपयोग करता है।

वह सब है।

इस सब के लिए क्या?

पूल प्रणाली Fortuna को आत्म-चिकित्सा बनाती है । यदि पहले आपके पूल में अच्छा डेटा आया था, और फिर खराब डेटा आना शुरू हो गया, तो एक पूल के साथ एक और रेजिडेंस जिसमें अच्छे डेटा से एन्ट्रॉपी था, ब्रह्मांड में बलों के संतुलन को बहाल करेगा।

आप यह भी देख सकते हैं कि पिछली जानकारी जिस पर यादृच्छिक डेटा की पीढ़ी निर्भर करती है (वही एन्ट्रॉपी) खोई नहीं है। प्रत्येक रेजिड में, नई चाबियों को वर्तमान के साथ मिलाया जाता है, लेकिन इसे प्रतिस्थापित नहीं किया जाता है।

इसके साथ ही

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

यह सब, आपके ध्यान के लिए धन्यवाद।

PS बहुत सारे कार्यान्वयन हैं, उदाहरण के लिए, जावा पर, प्रिय बाउंसीकैस्टल का उपयोग किया जाता है:
searchcode.com/codesearch/raw/16881031