elikaski/ecc_attacksएलिप्टिक कर्व क्रिप्टोग्राफी पर ज्ञात हमले
हाल के वर्षों में एलिप्टिक कर्व क्रिप्टोग्राफी दृष्टिकोण अपनी उच्च दक्षता और मजबूत सुरक्षा के कारण लोकप्रिय हो गया है। इस लेख का उद्देश्य इस विषय को आज इंटरनेट पर मौजूद जानकारी की तुलना में अपेक्षाकृत अधिक स्पष्ट तरीके से प्रस्तुत करना है।
इस लेख में मैं बताऊँगा कि एलिप्टिक कर्व्स क्या हैं, उन पर किए जा सकने वाले मूल संचालन क्या हैं, और उन्हें क्रिप्टोग्राफ़िक संदर्भ में कैसे उपयोग किया जा सकता है। इस लेख का अधिकांश भाग गलत कार्यान्वयनों या उनके गलत उपयोगों पर ज्ञात हमलों के उदाहरणों से बना है। पूरे लेख में मैं व्याख्या को एक सहज और उच्च-स्तरीय भाग, और एक गणितीय भाग जो अधिक विवरण में जाता है, में अलग करने का प्रयास करता हूँ। पाठक को आमंत्रित किया जाता है कि वह उस स्थान पर जिस भाग में उनकी रुचि हो उस पर ध्यान केंद्रित करें, और जो भाग कम प्रासंगिक हों उन्हें छोड़ दें।
पढ़ने का आनंद लीजिए!
सामान्यतः, एक एलिप्टिक कर्व एक प्रकार की घुमावदार रेखा होती है। इसका एक उदाहरण परवलय (parabola) है, जिसका समीकरण $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ के रूप का होता है और यह इस प्रकार दिखता है:
क्रिप्टोग्राफी के संदर्भ में, ऐसे एलिप्टिक कर्व्स का उपयोग करना प्रचलन है जिनका समीकरण इस रूप का होता है
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
उदाहरण के लिए, समीकरण $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ के अनुरूप एक एलिप्टिक कर्व इस प्रकार दिखता है:
वक्र का समीकरण वक्र पर स्थित किसी बिंदु के 𝑥 निर्देशांक और उसके 𝑦 निर्देशांक के बीच संबंध को परिभाषित करता है। क्रिप्टोग्राफ़िक संदर्भ में, हम 𝑥, 𝑦, 𝑎, 𝑏 को पूर्णांकों तक सीमित रखते हैं, और गणनाओं को किसी बड़ी अभाज्य संख्या के मॉड्यूलो तक सीमित रखते हैं। अतः एलिप्टिक कर्व का समीकरण है:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$।
इसका अर्थ है कि वक्र पर बिंदुओं की संख्या सीमित है। गणितीय भाषा में, वक्र को क्रम 𝑝 वाले एक परिमित क्षेत्र (finite field) के ऊपर परिभाषित कहा जाता है। परिणामस्वरूप, अब आवश्यक नहीं कि प्रत्येक 𝑥 निर्देशांक के अनुरूप वक्र पर कोई बिंदु हो, क्योंकि हो सकता है कि उसके अनुरूप 𝑦 निर्देशांक पूर्णांक न हो।
वक्र पर बिंदुओं का समुच्चय पूर्णांकों के उन युग्मों (𝑥, 𝑦) से बना होता है जो वक्र के समीकरण को संतुष्ट करते हैं। इन बिंदुओं के अतिरिक्त, "इनफिनिटी" (Infinity) नामक एक और विशेष बिंदु परिभाषित किया जाता है, जिसे 𝒪 से निरूपित किया जाता है। गणितीय भाषा में, यह बिंदु वक्र पर स्थित बिंदुओं के समुच्चय का, जोड़ संक्रिया के सापेक्ष, तत्समक अवयव (neutral element) है, जिसे हम अगले खंड में परिभाषित करेंगे। वक्र पर बिंदुओं की संख्या (बिंदु 𝒪 सहित) को "वक्र का क्रम" (order of the curve) कहा जाता है।
एक और अवलोकन यह है कि एलिप्टिक कर्व्स X अक्ष के सापेक्ष सममित होते हैं। इसका अर्थ है कि यदि बिंदु 𝑃 = (𝑥, 𝑦) वक्र पर है, तो बिंदु −𝑃 = (𝑥, −𝑦) भी वक्र पर होगा। वास्तव में, ये बिंदु एक-दूसरे के "व्युत्क्रम" (inverse) माने जाते हैं (इसलिए दूसरे बिंदु के लिए चिह्न −𝑃), और इनके बीच जोड़ संक्रिया का परिणाम तत्समक अवयव 𝒪 परिभाषित किया जाता है।
हैसी प्रमेय (Hasse's Theorem) नामक एक प्रमेय #𝐸, अर्थात वक्र के क्रम, का अनुमान प्रदान करती है, और यह Θ(𝑝) के परिमाण की कोटि है। अधिक सटीक रूप से:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
वक्र पर दो बिंदु दिए जाने पर, उनके बीच एक जोड़ संक्रिया परिभाषित की जा सकती है, जिसका परिणाम एक तीसरा बिंदु होता है जो वक्र पर भी स्थित होता है। इस बिंदु को ज्यामितीय रूप से खोजने के लिए, हम दो दिए गए बिंदुओं के बीच एक रेखा खींचते हैं, और उसे तब तक आगे बढ़ाते हैं जब तक वह वक्र को एक तीसरे बिंदु पर प्रतिच्छेद न कर ले। इस बिंदु को 𝑋 अक्ष के सापेक्ष परावर्तित किया जाता है, और परिणामी बिंदु को जोड़ का परिणाम परिभाषित किया जाता है।
यहाँ एक आरेख है जो दर्शाता है कि बिंदुओं 𝑃 और 𝑄 दिए जाने पर, बिंदु 𝑃 + 𝑄 कैसे खोजा जा सकता है:
इस विवरण से एक प्रश्न उठ सकता है: यदि दो बिंदुओं के बीच खींची गई रेखा वक्र को पुनः प्रतिच्छेद न करे तो क्या होता है? ऐसी स्थिति में कहा जाता है कि रेखा वक्र को "इनफिनिटी" पर प्रतिच्छेद करती है, और जोड़ का परिणाम बिंदु 𝒪 होता है। ध्यान दें कि यह स्थिति तब होती है जब खींची गई रेखा ऊर्ध्वाधर होती है, अर्थात हम किसी बिंदु 𝑃 को उसके व्युत्क्रम बिंदु −𝑃 के साथ जोड़ने का प्रयास कर रहे होते हैं:
इससे दो मूल सर्वसमिकाएँ प्राप्त होती हैं। प्रत्येक बिंदु 𝑃 के लिए यह सत्य है:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
ज्यामितीय विवरण से उठने वाला एक और प्रश्न यह है कि हम किसी बिंदु को उसी में कैसे जोड़ें? हमने देखा कि दो भिन्न बिंदुओं 𝑃 और 𝑄 को जोड़ने के लिए, हम उनके बीच एक रेखा खींचते हैं और उसके विस्तार का वक्र के साथ प्रतिच्छेदन बिंदु देखते हैं। सहज रूप से, हम 𝑃 को स्थिर रखेंगे, और उस रेखा को देखेंगे जो 𝑄 को 𝑃 के "अधिक से अधिक निकट" ले जाने पर बनती है, जब तक 𝑄 𝑃 में विलीन नहीं हो जाता। हमें जो मिलेगा वह बिंदु 𝑃 पर वक्र की अधिक से अधिक "स्पर्श रेखा" (tangent) जैसी रेखा होगी, और यही वह रेखा है जिसे हम तब देखेंगे जब हम 𝑃 को स्वयं में जोड़ना चाहेंगे:
किसी बिंदु 𝑃 को स्वयं में जोड़ने के लिए, हम बिंदु 𝑃 पर वक्र की एक स्पर्श रेखा खींचते हैं, और उसे तब तक आगे बढ़ाते हैं जब तक वह वक्र को दूसरे बिंदु पर प्रतिच्छेद न कर ले। इस बिंदु को 𝑋 अक्ष के सापेक्ष परावर्तित किया जाता है, और परिणामी बिंदु को जोड़ का परिणाम परिभाषित किया जाता है। जोड़ के परिणाम को 𝑃 + 𝑃 = 2𝑃 के रूप में चिह्नित करना प्रचलन है। पुनः, यदि स्पर्श रेखा वक्र को दूसरे बिंदु पर प्रतिच्छेद नहीं करती है, तो कहा जाता है कि यह वक्र को "इनफिनिटी" पर प्रतिच्छेद करती है, और इस स्थिति में जोड़ का परिणाम बिंदु 𝒪 होता है।
ये दृश्य ज्यामितीय विवरण अच्छे ढंग से चित्रित करते हैं और हमें यह समझने में सहायता करते हैं कि बिंदु जोड़ कैसे काम करता है। लेकिन हम वास्तव में इसकी गणना कैसे करें? गणितीय समीकरणों से, बिल्कुल!
बिंदुओं $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ और $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$ दिए जाने पर, उनके जोड़ का परिणाम बिंदु $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ है, जहाँ:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
