Euler's Theorem in Cryptography in Hindi: प्रमेय, प्रमाण और उपयोग

Euler's Theorem in Cryptography: प्रमेय, प्रमाण और उपयोग

परिचय

Euler's Theorem (ऑयलर का प्रमेय) गणित की एक महत्वपूर्ण अवधारणा है, जिसका उपयोग **Cryptography** और **Modular Arithmetic** में किया जाता है। यह प्रमेय विशेष रूप से **RSA Algorithm**, **Modular Inverse**, और **Exponentiation** में महत्वपूर्ण भूमिका निभाता है।

1. Euler's Theorem क्या है?

Euler's Theorem के अनुसार, यदि कोई संख्या ( a ) और ( n ) सह-अपरिपूर्ण (Coprime) हैं, यानी कि उनका GCD(ग्रेस्टेस्ट कॉमन डिवाइजर) **1** है, तो:

[ a^{phi(n)} equiv 1 mod n ]

जहाँ ( phi(n) ) **Euler's Totient Function** है, जो दर्शाता है कि ( n ) से छोटी कितनी संख्याएँ ( n ) के साथ सह-अपरिपूर्ण हैं।

1.1 विशेष रूप:

• यदि ( n ) एक प्राइम संख्या **p** है, तो (phi(p) = p-1) होगा।
• Euler's Theorem, Fermat’s Little Theorem का सामान्यीकरण है, क्योंकि यदि ( p ) एक प्राइम है, तो Fermat's Theorem से यह साबित होता है कि:

[ a^{p-1} equiv 1 mod p ]

2. Euler's Theorem का प्रमाण

Euler's Theorem के प्रमाण के लिए हम **Modular Arithmetic** और **Euler's Totient Function** का उपयोग करते हैं।

प्रमाण के चरण:

• Euler's Totient Function के अनुसार, किसी संख्या ( n ) के लिए ( phi(n) ) उन संख्याओं की संख्या है जो ( n ) के साथ सह-अपरिपूर्ण हैं।
• हम इन सह-अपरिपूर्ण संख्याओं के सेट को ( S ) मान सकते हैं:

[ S = {a_1, a_2, ..., a_{phi(n)}} ]

• यदि ( a ) और ( n ) सह-अपरिपूर्ण हैं, तो ( a imes S ) का प्रत्येक तत्व अभी भी ( n ) के साथ सह-अपरिपूर्ण होगा।
• इसका मतलब है कि सेट ( S ) को ( a ) के साथ गुणा करने से पुनः वही संख्याएँ मिलेंगी लेकिन मॉड्यूलो ( n ) के तहत पुनर्व्यवस्थित होंगी।
• इससे हमें यह समीकरण मिलता है:

[ (a imes a_1) imes (a imes a_2) imes ... imes (a imes a_{phi(n)}) equiv a_1 imes a_2 imes ... imes a_{phi(n)} mod n ]

• चूँकि सभी ( a_i ) के साथ ( a ) गुणा हुआ है, इसे पुनः व्यवस्थित करने पर:

[ a^{phi(n)} imes (a_1 imes a_2 imes ... imes a_{phi(n)}) equiv (a_1 imes a_2 imes ... imes a_{phi(n)}) mod n ]

• अब, यदि दोनों पक्षों को ( a_1 imes a_2 imes ... imes a_{phi(n)} ) से विभाजित करें, तो हमें:

[ a^{phi(n)} equiv 1 mod n ]

3. क्रिप्टोग्राफी में Euler's Theorem का उपयोग

3.1 RSA एल्गोरिदम में उपयोग

RSA एन्क्रिप्शन में Euler's Theorem का उपयोग सार्वजनिक और गुप्त कुंजियों (Public and Private Keys) को उत्पन्न करने में किया जाता है।

• यदि दो प्राइम संख्याएँ ( p ) और ( q ) हैं, तो ( n = p imes q ) होगा।
• ( phi(n) = (p-1) imes (q-1) ) होगा।
• एक सार्वजनिक कुंजी **e** का चयन किया जाता है, जो (phi(n)) के साथ सह-अपरिपूर्ण होता है।
• गुप्त कुंजी **d** निकालने के लिए Euler's Theorem और Modular Inverse का उपयोग किया जाता है:

[ d = e^{-1} mod phi(n) ]

3.2 मॉड्यूलर इन्वर्स (Modular Inverse)

Euler's Theorem का उपयोग मॉड्यूलर इन्वर्स निकालने के लिए किया जाता है। यदि हमें किसी संख्या ( a ) का **Modular Inverse** निकालना हो, तो:

[ a^{-1} equiv a^{phi(n)-1} mod n ]

3.3 डिजिटल सिग्नेचर (Digital Signatures)

डिजिटल सिग्नेचर एल्गोरिदम में सुरक्षित संदेशों की पुष्टि के लिए Euler's Theorem का उपयोग किया जाता है।

4. उदाहरण: Euler's Theorem का उपयोग

उदाहरण 1: ( a = 7 ), ( n = 10 ) के लिए Euler's Theorem लागू करें

• पहले, ( phi(10) ) निकालें:

[ phi(10) = 10 imes left(1 - frac{1}{2} ight) imes left(1 - frac{1}{5} ight) = 10 imes frac{1}{2} imes frac{4}{5} = 4 ]

• अब Euler's Theorem के अनुसार:

[ 7^4 equiv 1 mod 10 ]

• गणना करें:

[ 7^4 = 2401 ]

[ 2401 mod 10 = 1 ]

तो प्रमेय सत्यापित होता है।

निष्कर्ष

Euler's Theorem क्रिप्टोग्राफी के लिए बहुत महत्वपूर्ण है। यह RSA, डिजिटल सिग्नेचर, और मॉड्यूलर इन्वर्स में उपयोग किया जाता है।