यादृच्छिकता और छद्म-यादृच्छिकता

यादृच्छिकता क्रिप्टोग्राफी की जीवनरेखा है — कुंजियाँ, नॉनस (nonces), और चुनौतियाँ अप्रत्याशित होनी चाहिए — और छद्म-यादृच्छिकता एक छोटे, वास्तव में यादृच्छिक बीज को लंबी अनुक्रमों में फैलाने की अनुमति देती है जो किसी भी कुशल विरोधी के लिए यादृच्छिक से अप्रभेद्य होते हैं।

Definition

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

Scope

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

Core questions

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

Key concepts

• एन्ट्रॉपी और वास्तविक यादृच्छिकता
• यादृच्छिक संख्या जनरेटर
• छद्म-यादृच्छिक जनरेटर (PRG)
• छद्म-यादृच्छिक कार्य (PRF)
• छद्म-यादृच्छिक क्रमचय (PRP)
• कम्प्यूटेशनल अप्रभेद्यता
• बीज और कुंजी व्युत्पत्ति
• यादृच्छिकता के पुन: उपयोग की विफलताएं
• एन्ट्रॉपी कंडीशनिंग

Key theories

छद्म-यादृच्छिक जनरेटर

एक छद्म-यादृच्छिक जनरेटर एक छोटे बीज को एक लंबी स्ट्रिंग में विस्तारित करता है जो किसी भी कुशल भेदक के लिए एकसमान यादृच्छिकता से अप्रभेद्य होता है; ऐसे जनरेटर तभी मौजूद होते हैं जब वन-वे फ़ंक्शन मौजूद हों, जो छद्म-यादृच्छिकता को क्रिप्टोग्राफी की नींव से जोड़ता है।

छद्म-यादृच्छिक कार्य और क्रमचय

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

Mechanisms

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

Clinical relevance

यादृच्छिकता की विफलताएं विनाशकारी वास्तविक-विश्व विफलताओं का एक आवर्ती स्रोत हैं: 2008 के डेबियन ओपनएसएसएल बग ने कुंजी निर्माण को बाधित कर दिया, अनुमानित ईसीडीएसए नॉनस (ECDSA nonces) ने निजी कुंजियों को लीक कर दिया (सोनी प्लेस्टेशन 3, कुछ बिटकॉइन वॉलेट), और कमजोर एम्बेडेड-डिवाइस एन्ट्रॉपी ने बड़े पैमाने पर अनुमान लगाने योग्य कुंजियों का उत्पादन किया। इसलिए, मजबूत यादृच्छिकता — उचित एन्ट्रॉपी संग्रह और जाँचे गए छद्म-यादृच्छिक जनरेटर — प्रत्येक क्रिप्टोग्राफिक परिनियोजन के लिए आवश्यक है।

Evidence & guidelines

एनआईएसटी एसपी 800-90ए/बी/सी अनुमोदित नियतात्मक यादृच्छिक-बिट जनरेटर, एन्ट्रॉपी-स्रोत सत्यापन और निर्माण मार्गदर्शन निर्दिष्ट करते हैं। सर्वोत्तम अभ्यास ऑपरेटिंग सिस्टम के जाँचे गए क्रिप्टोग्राफिक आरएनजी (RNG) का उपयोग करता है (अपने स्वयं के बनाने के बजाय), कुंजियों को उत्पन्न करने से पहले पर्याप्त एन्ट्रॉपी सुनिश्चित करता है, और कभी भी नॉनस (nonces) का पुन: उपयोग नहीं करता है। सांख्यिकीय परीक्षण सूट सकल दोषों का पता लगाने में मदद करते हैं लेकिन क्रिप्टोग्राफिक शक्ति स्थापित नहीं कर सकते हैं।

History

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

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

मैं क्रिप्टोग्राफी के लिए rand() जैसे सामान्य यादृच्छिक फ़ंक्शन का उपयोग क्यों नहीं कर सकता?

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

वास्तविक यादृच्छिकता और छद्म-यादृच्छिकता में क्या अंतर है?

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