Featured image of post निर्धारित प्रक्रिया से 'यादृच्छिकता (Randomness)' कैसे बनाई जाती है?: अप्रत्याशितता का विज्ञान और क्रिप्टोग्राफी
कंप्यूटर विज्ञान

निर्धारित प्रक्रिया से 'यादृच्छिकता (Randomness)' कैसे बनाई जाती है?: अप्रत्याशितता का विज्ञान और क्रिप्टोग्राफी

नियतिवादी (deterministic) कंप्यूटर यादृच्छिक संख्याएँ कैसे उत्पन्न करते हैं, और क्यों मर्सेन ट्विस्टर (MT19937) के केवल 624 आउटपुट देखकर हमलावर उसके भविष्य और अतीत के 100% आउटपुट की भविष्यवाणी कर सकता है? PRNG बनाम TRNG, लीनियर कॉन्ग्रुएंशियल जनरेटर (LCG) और IBM RANDU की 15-समतल त्रासदी, MT19937, PCG64, Xoshiro256++, एंड्रयू याओ का प्रमेय, CSPRNG (ChaCha20, AES-CTR_DRBG, NSA Dual_EC_DRBG बैकडोर), थर्मल नॉइज़, मिन-एन्ट्रॉपी और डेबियन OpenSSL बग का संपूर्ण विश्लेषण।

प्रस्तावना: वॉन न्यूमैन की “पाप की अवस्था” और नियतिवादी संयोग का विरोधाभास

1951 में, आधुनिक कंप्यूटर के जनक जॉन वॉन न्यूमैन (John von Neumann) ने कंप्यूटर विज्ञान के इतिहास का एक अमर वाक्य कहा था: “जो कोई भी यादृच्छिक अंक (random digits) उत्पन्न करने के लिए अंकगणितीय विधियों पर विचार करता है, वह निस्संदेह ‘पाप की अवस्था (in a state of sin)’ में है।" एक डिजिटल कंप्यूटर पूर्णतः नियतिवादी परिमित-अवस्था मशीन (deterministic finite-state machine) है: समान प्रारंभिक अवस्था और निर्देश दिए जाने पर उसका प्रत्येक अगला बिट 100% पूर्वनिर्धारित होता है। फिर भी, परमाणु भौतिकी में मोंटे कार्लो सिमुलेशन और वीडियो गेम की दुनिया के निर्माण से लेकर TLS सत्र कुंजियों, SSH की-पेयर्स और ECDSA डिजिटल हस्ताक्षरों तक, हमारी आधुनिक सभ्यता प्रति सेकंड खरबों यादृच्छिक संख्याओं का उपभोग करती है।

एक पूर्णतः निर्धारित एल्गोरिदम अप्रत्याशितता कैसे पैदा कर सकता है? और क्यों सांख्यिकीय रूप से उत्कृष्ट जनरेटर जैसे मर्सेन ट्विस्टर (MT19937) को पासवर्ड रीसेट टोकन बनाने में उपयोग करने पर वह भयानक रूप से असुरक्षित हो जाता है, जिससे केवल 624 क्रमिक आउटपुट देखने वाला हमलावर भविष्य और अतीत की 100% संख्याओं की भविष्यवाणी कर सकता है?

अध्याय 1: PRNG की गणितीय संरचना ── बीज (Seed), परिमित अवस्था समष्टि और कबूतरखाना सिद्धांत

औपचारिक रूप से, एक छद्म-यादृच्छिक संख्या जनरेटर (PRNG) एक नियतिवादी ऑटोमैटोन $(\mathcal{S}, \mathcal{O}, f, g, s_0)$ है जिसमें $|\mathcal{S}| = 2^b$ आकार की परिमित आंतरिक अवस्था समष्टि $\mathcal{S}$, एक प्रारंभिक बीज (Seed) $s_0 \in \mathcal{S}$, अवस्था संक्रमण फलन $f: \mathcal{S} \to \mathcal{S}$ और आउटपुट फलन $g: \mathcal{S} \to \mathcal{O}$ होता है:

$$s_{i+1} = f(s_i), \qquad r_i = g(s_i) \qquad \left(|\mathcal{S}| = 2^b \implies \text{Period } P \le 2^b\right)$$

एक बार बीज $s_0$ तय हो जाने पर संपूर्ण अनुक्रम $r_0, r_1, r_2, \dots$ पूर्णतः निर्धारित हो जाता है। यह पुनरुत्पादनीयता (Reproducibility) वैज्ञानिक सिमुलेशन की डिबगिंग के लिए अमूल्य है। किंतु कबूतरखाना सिद्धांत (Pigeonhole Principle) के अनुसार, अधिकतम $2^b$ चरणों के भीतर मशीन को किसी पूर्व अवस्था $s_{k+P} = s_k$ पर लौटना ही पड़ता है, जिससे वह आवर्तकाल (Period) $P \le 2^b$ के अनंत चक्र में फँस जाती है।

  flowchart LR
    S0["प्रारंभिक बीज s0"] --> S1["अवस्था s1 = f(s0)"]
    S1 --> S2["अवस्था s2 = f(s1)"]
    S2 -. "पूर्व-आवर्तकाल (Tail)" .-> Sk["चक्र प्रवेश sk"]
    Sk --> Sk1["अवस्था s(k+1)"]
    Sk1 -. "आवर्तकाल P <= 2^b का चक्र" .-> Skm1["अवस्था s(k+P-1)"]
    Skm1 -- "f(s(k+P-1)) = sk" --> Sk

वॉन न्यूमैन की 1949 की मध्य-वर्ग विधि (Middle-Square Method) ($2k$ अंकों की संख्या का वर्ग करके बीच के $2k$ अंक निकालना) बीजगणितीय संरचना के अभाव में तुरंत 0000 या लंबाई 4 के छोटे चक्रों में सिमट जाती है।

अध्याय 2: लीनियर कॉन्ग्रुएंशियल जनरेटर (LCG) और मार्सग्लिया का प्रमेय ── IBM RANDU की 15-समतल त्रासदी

1949 में डी. एच. लेहमर ने लीनियर कॉन्ग्रुएंशियल जनरेटर (LCG) प्रस्तुत किया: $X_{n+1} = (a X_n + c) \bmod m$। हल-डोबेल प्रमेय (Hull-Dobell Theorem, 1962) के अनुसार, LCG पूर्ण आवर्तकाल $P = m$ तभी प्राप्त करता है जब: (1) $\gcd(c, m) = 1$, (2) $m$ का प्रत्येक अभाज्य गुणनखंड $p$, $a-1$ को विभाजित करे, और (3) यदि $4 \mid m$ तो $4 \mid (a-1)$ हो।

1968 में सांख्यिकीविद् जॉर्ज मार्सग्लिया (George Marsaglia) ने अपने प्रसिद्ध शोधपत्र “Random numbers fall mainly in the planes” में सिद्ध किया कि किसी भी LCG द्वारा उत्पन्न क्रमिक $d$-आयामी बिंदु $(X_n, \dots, X_{n+d-1})$ अधिकतम $(d! \cdot m)^{1/d}$ समानांतर हाइपरप्लेन (क्रिस्टल जालक) पर ही स्थित होते हैं!

इतिहास का सबसे कुख्यात उदाहरण IBM System/360 मेनफ़्रेम का मानक जनरेटर RANDU ($m = 2^{31}, c = 0, a = 65539 = 2^{16} + 3$) था:

$$X_{n+1} = 65539 X_n \bmod 2^{31} = (2^{16} + 3) X_n \bmod 2^{31}$$$$X_{n+2} \equiv (2^{16}+3)^2 X_n \equiv \left(\underbrace{2^{32}}_{\equiv 0} + 6\cdot 2^{16} + 9\right) X_n \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$$$$\implies 9 u_n - 6 u_{n+1} + u_{n+2} = k \in \{-5, -4, \dots, 9\} \quad (\text{15 Parallel Planes!})$$

सर्वसमिका $X_{n+2} \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$ के कारण, इकाई घन (unit cube) में RANDU द्वारा उत्पन्न सभी 3D बिंदु केवल 15 समानांतर समतलों पर कैद हो गए जिनके बीच विशाल खाली अंतराल थे, जिससे दशकों तक हज़ारों मोंटे कार्लो भौतिकी सिमुलेशन दूषित हो गए!

अध्याय 3: मर्सेन ट्विस्टर (MT19937) और आधुनिक सांख्यिकीय PRNG (PCG64, Xoshiro256++)

1997 में जापानी गणितज्ञ माकोतो मात्सुमोतो और ताकुजी निशिमुरा ने परिमित क्षेत्र $\mathbb{F}_2 = \{0, 1\}$ पर आधारित मर्सेन ट्विस्टर (MT19937) का आविष्कार किया (जो Python random, R, MATLAB, C++ std::mt19937 का डिफ़ॉल्ट इंजन बना):

  1. विशाल आवर्तकाल और 623-आयामी समवितरण: 32-बिट के $624$ शब्दों ($19,937$ सक्रिय बिट) की आंतरिक अवस्था मर्सेन अभाज्य आवर्तकाल $P = 2^{19937} - 1 \approx 4.315 \times 10^{6001}$ और 623 आयामों तक पूर्ण समवितरण (equidistribution) सुनिश्चित करती है!
  2. टेम्परिंग रूपांतरण (Tempering): आउटपुट से पहले प्रत्येक अवस्था शब्द $x$ को $\mathbb{F}_2^{32}$ पर एक व्युत्क्रमणीय (invertible) मैट्रिक्स से गुणा किया जाता है:
$$\begin{aligned} y_1 &= x \oplus ((x \gg 11) \mathbin{\&} \texttt{0xFFFFFFFF}) \\ y_2 &= y_1 \oplus ((y_1 \ll 7) \mathbin{\&} \texttt{0x9D2C5680}) \\ y_3 &= y_2 \oplus ((y_2 \ll 15) \mathbin{\&} \texttt{0xEFC60000}) \\ z &= y_3 \oplus (y_3 \gg 18) \end{aligned}$$

MT19937 के बड़े स्टेट आकार ($2.5\text{ KB}$) और TestU01 (BigCrush) में दो $\mathbb{F}_2$-रैखिकता परीक्षणों में विफलता को दूर करने के लिए, 2010 के दशक में PCG64 (मेलिसा ओ’नील 2014: डेटा-निर्भर बिट रोटेशन के साथ 128-बिट LCG; NumPy में डिफ़ॉल्ट) और Xoshiro256++ (ब्लैकमैन और विग्ना 2018: गैर-रैखिक स्क्रैम्बलर के साथ 256-बिट स्टेट; Rust और Java में प्रयुक्त) विकसित किए गए, जो 100% BigCrush परीक्षणों को उत्तीर्ण करते हैं।

अध्याय 4: सांख्यिकीय पूर्णता $\neq$ क्रिप्टोग्राफिक सुरक्षा ── 624 आउटपुट से MT19937 का क्लोन और CSPRNG

4.1 Tempering का व्युत्क्रमण: 624 आउटपुट से MT19937 की आंतरिक अवस्था चुराना

सेशन टोकन या पासवर्ड के लिए MT19937 का उपयोग एक घातक भूल है: Tempering के चारों चरण $\mathbb{F}_2^{32}$ पर $O(1)$ समय में पूर्णतः व्युत्क्रमणीय (invertible) हैं!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def untemper(z: int) -> int:
    # Invert MT19937 32-bit output z back to internal state word x in O(1)
    y3 = z ^ (z >> 18)
    y2 = y3 ^ ((y3 << 15) & 0xEFC60000)
    y1 = y2
    for _ in range(4):
        y1 = y2 ^ ((y1 << 7) & 0x9D2C5680)
    x = y1
    for _ in range(2):
        x = y1 ^ (x >> 11)
    return x & 0xFFFFFFFF

यदि कोई हमलावर MT19937 का उपयोग करने वाले सर्वर के केवल 624 क्रमिक 32-बिट आउटपुट ($2,496\text{ बाइट्स}$) देख लेता है, तो वह प्रत्येक पर untemper(z) चलाकर सर्वर की संपूर्ण 624-शब्द आंतरिक अवस्था को 100% क्लोन कर लेता है! उस क्षण से वह भविष्य के 100% आउटपुट की भविष्यवाणी कर सकता है और अतीत के सभी टोकन भी निकाल सकता है।

4.2 एंड्रयू याओ का प्रमेय (1982) और क्रिप्टोग्राफिक रूप से सुरक्षित जनरेटर (CSPRNG)

क्रिप्टोग्राफी के लिए CSPRNG (Cryptographically Secure PRNG) अनिवार्य है, जो तीन सिद्धांतों पर आधारित है:

  1. अगले बिट की अप्रत्याशितता $\iff$ कम्प्यूटेशनल अविभेद्यता (याओ का प्रमेय 1982 / ब्लम-मिकाली): प्रथम $k$ बिट्स जानने वाला कोई भी बहुपद-समय हमलावर $\mathcal{A}$, $(k+1)$-वें बिट का अनुमान सिक्का उछालने ($1/2$) से बेहतर नहीं लगा सकता:
$$\left| \Pr\left[\mathcal{A}(r_1, r_2, \dots, r_k) = r_{k+1}\right] - \frac{1}{2} \right| \le \text{negl}(\lambda)$$
  1. फॉरवर्ड सीक्रेसी (Forward Secrecy / पश्चगामी प्रतिरोध): प्रत्येक आउटपुट के तुरंत बाद आंतरिक कुंजी को एकदिशीय फलन द्वारा मिटाकर बदल दिया जाता है (Fast-Key-Erasure), जिससे वर्तमान अवस्था लीक होने पर भी पुरानी कुंजियाँ सुरक्षित रहती हैं।
  2. बैकवर्ड सीक्रेसी (Backward Secrecy / भविष्यवाणी प्रतिरोध): ताज़ा हार्डवेयर एन्ट्रॉपी के निरंतर मिश्रण (Reseeding) से लीक के बाद भी भविष्य की सुरक्षा बहाल हो जाती है।
  flowchart TD
    subgraph Insecure ["सांख्यिकीय PRNG (LCG / MT19937 / Xoshiro)"]
        StateM["आंतरिक अवस्था s_i (624 शब्द)"] -- "व्युत्क्रमणीय F2-रैखिक Tempering" --> OutM["आउटपुट r_i"]
        OutM -- "untemper() 624 आउटपुट से पूरी अवस्था क्लोन करता है!" --> StateM
    end
    subgraph Secure ["क्रिप्टोग्राफिक CSPRNG (ChaCha20 / AES-CTR_DRBG)"]
        Entropy["हार्डवेयर एन्ट्रॉपी स्रोत<br/>(थर्मल नॉइज़ / RDSEED)"] -- "नियमित Reseeding (Backward Secrecy)" --> StateC["256-बिट गुप्त कुंजी और काउंटर"]
        StateC -- "एकदिशीय साइफ़र (ChaCha20 / AES)<br/>[उलटने में 2^256 संक्रियाएँ!]" --> OutC["क्रिप्टोग्राफिक यादृच्छिक धारा r_i"]
        StateC -- "Fast-Key-Erasure Key' = PRF(Key)<br/>[Forward Secrecy!]" --> StateC_Next["नवीनीकृत कुंजी Key'"]
    end

आधुनिक CSPRNG में ChaCha20-RNG (Linux कर्नेल, OpenBSD, Rust) और AES-CTR_DRBG (NIST SP 800-90A) या गुणनखंडन समस्या पर आधारित Blum-Blum-Shub ($x_{n+1} = x_n^2 \bmod M$) शामिल हैं। इसके विपरीत, 2006 में NIST द्वारा मानकीकृत दीर्घवृत्तीय वक्र जनरेटर Dual_EC_DRBG में NSA का क्लेप्टोग्राफिक बैकडोर छिपा था (जिसकी पुष्टि 2013 के स्नोडेन दस्तावेजों से हुई: $P = d \cdot Q$ का गुप्त असतत लघुगणक $d$ जानने वाला व्यक्ति केवल 32 बाइट आउटपुट से आंतरिक अवस्था निकालकर संपूर्ण TLS ट्रैफ़िक डिक्रिप्ट कर सकता था)।

जनरेटर वर्गप्रतिनिधि एल्गोरिदमअवस्था आकारआवर्तकाल $P$BigCrush परीक्षणक्रिप्टोग्राफिक सुरक्षामुख्य उपयोग
शास्त्रीय LCGRANDU, C rand()32–64 बिट$\le 2^{64}$विफल (हाइपरप्लेन)असुरक्षितकेवल पुराने कोड में
आधुनिक सांख्यिकीय PRNGMT19937, PCG64, Xoshiro256++128 बिट – 2.5 KB$2^{128} \sim 2^{19937}-1$उत्तीर्णअसुरक्षित (624 आउटपुट / Z3)मोंटे कार्लो, सिमुलेशन, गेम
क्रिप्टोग्राफिक (CSPRNG)ChaCha20-RNG, AES-CTR_DRBG256–512 बिट$\ge 2^{256}$100% उत्तीर्णसुरक्षित (Forward/Backward Secret)TLS/SSH कुंजियाँ, पासवर्ड, टोकन
भौतिक यादृच्छिक (TRNG)थर्मल नॉइज़, ज़ेनर ब्रेकडाउन, रिंग ऑसिलेटर (RDSEED)भौतिक सातत्यअनावर्ती ($\infty$)व्हाइटनिंग के बादसच्ची भौतिक एन्ट्रॉपीCSPRNG सीडिंग और रीसीडिंग

अध्याय 5: भौतिक जनरेटर (TRNG), मिन-एन्ट्रॉपी ($H_\infty$) और OS एन्ट्रॉपी पूल

CSPRNG का प्रारंभिक बीज हार्डवेयर ट्रू रैंडम नंबर जनरेटर (TRNG / HRNG) से आता है जो सूक्ष्म भौतिक हलचल को मापता है: प्रतिरोधकों में जॉनसन-नाइक्विस्ट थर्मल नॉइज़, ज़ेनर डायोड एवलांच ब्रेकडाउन का क्वांटम शॉट नॉइज़, और रिंग ऑसिलेटर फेज़ जिटर (Intel/AMD CPU में RDSEED/RDRAND निर्देश)। क्रिप्टोग्राफी (NIST SP 800-90B) में सबसे खराब स्थिति की अप्रत्याशितता को औसत शैनन एन्ट्रॉपी $H_1$ के बजाय मिन-एन्ट्रॉपी ($H_\infty$) से मापा जाता है:

$$V_{\text{rms}} = \sqrt{4 k_B T R \Delta f}, \qquad H_\infty(X) = -\log_2 \left(\max_{x} P(X = x)\right) \le H_1(X)$$

कच्चे भौतिक शोर को वॉन न्यूमैन डीबायसिंग या क्रिप्टोग्राफिक हैश एक्सट्रैक्टर (Linux कर्नेल में BLAKE2s, Leftover Hash Lemma के तहत) द्वारा व्हाइटनिंग (Whitening) करके CSPRNG में भेजा जाता है।

आधुनिक Linux (5.6+) में /dev/random और /dev/urandom दोनों एक ही ChaCha20 कर्नेल CSPRNG का उपयोग करते हैं; डेवलपर्स को हमेशा getrandom(2) (या Python secrets, JS crypto.getRandomValues(), Rust OsRng/ThreadRng, Go crypto/rand) का उपयोग करना चाहिए। 2008 की डेबियन OpenSSL त्रासदी (CVE-2008-0166) — जहाँ Valgrind चेतावनी हटाने के लिए एक पंक्ति को कमेंट करने से दो वर्षों तक दुनिया भर में बनी सभी RSA/SSH कुंजियों की एन्ट्रॉपी केवल 15-बिट प्रोसेस ID ($32,768$ संभावित कुंजियाँ!) तक सिमट गई — और सोनी PlayStation 3 की ECDSA स्थैतिक नॉनस ($k$) विफलता (2010) यह अकाट्य नियम सिद्ध करती हैं: किसी भी क्रिप्टोग्राफिक प्रणाली की सुरक्षा कभी भी उसकी कुंजियाँ बनाने वाले रैंडम नंबर जनरेटर की एन्ट्रॉपी से अधिक नहीं हो सकती।

comments powered by Disqus