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\ 𝑝)$
जहाँ 𝜆 को बिंदुओं को जोड़ने वाली रेखा का ढलान (slope) परिभाषित किया जाता है, यदि वे भिन्न हैं, और बिंदु पर वक्र की स्पर्श रेखा का ढलान, यदि बिंदु को स्वयं में जोड़ा जाता है। औपचारिक रूप से:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
बिंदुओं के जोड़ के पीछे की गणितीय गणनाएँ लेख के शेष भाग के लिए महत्वपूर्ण नहीं हैं। इस दृष्टि से, हम बिंदु जोड़ को एक ब्लैक बॉक्स के रूप में देख सकते हैं जो वक्र पर दो बिंदु प्राप्त करता है और एक तीसरा बिंदु लौटाता है जो वक्र पर भी होता है।
हमने देखा कि किसी बिंदु 𝑃 को स्वयं में जोड़ना संभव है, और हमने परिणामी बिंदु को 2𝑃 से निरूपित किया। यदि हम बिंदु 𝑃 को इस परिणाम में पुनः जोड़ते हैं, तो हम 3𝑃 से निरूपित एक बिंदु पर पहुँचेंगे, और इसी प्रकार आगे। इस प्रकार, बिंदु को बार-बार स्वयं में जोड़कर, किसी बिंदु को एक स्थिरांक से "गुणा" परिभाषित करना संभव है (संख्याओं के बीच गुणन के समान):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
प्रतीत होता है कि किसी बिंदु को किसी संख्या 𝑛 से गुणा करने के लिए हमें बिंदुओं के बीच 𝑛 जोड़ संक्रियाएँ करनी होंगी। ऐसा इसलिए है क्योंकि प्रारंभिक बिंदु दिए जाने पर, "अंतिम" बिंदु कहाँ गिरेगा, यह पहले से जानना कठिन है, बिना उस तक "चरण-दर-चरण" पहुँचे। ऐसी गणना बहुत अक्षम होगी, क्योंकि 𝑛 बहुत बड़ा हो सकता है।
इस उद्देश्य के लिए, Double And Add एल्गोरिदम मौजूद है, जिसमें हम बिंदु 𝑃 से शुरू करते हैं, फिर 𝑛 के द्विआधारी निरूपण में प्रत्येक बिट के लिए, वर्तमान बिंदु को 2 से गुणा किया जाता है (अर्थात उसे स्वयं में जोड़ा जाता है), और यदि बिट मान 1 है तो उसे परिणाम में जोड़ा जाता है। इस एल्गोरिदम की रनटाइम जटिलता 𝑂(log 𝑛) है, और यह बिंदुओं को बहुत बड़ी संख्याओं से कुशलतापूर्वक गुणा करने की अनुमति देता है।
बिंदु गुणन का एक महत्वपूर्ण गुण जिसका उपयोग हम बाद में करेंगे, वह यह है कि प्रत्येक बिंदु 𝑃 और संख्याओं के युग्म 𝑎, 𝑏 के लिए यह सत्य है:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
सहज रूप से, मान लीजिए हम बिंदु 𝑃 से शुरू करते हैं, उससे 𝑎 कदम चलते हैं, और बिंदु 𝑎𝑃 पर पहुँचते हैं। इस बिंदु से, हम "आकार" 𝑎 के 𝑏 कदम चलते हैं और बिंदु 𝑏(𝑎𝑃) पर पहुँचते हैं। वैकल्पिक रूप से, एक अन्य परिदृश्य में, हम बिंदु 𝑃 से शुरू कर सकते हैं, उसके साथ 𝑏 कदम चलकर बिंदु 𝑏𝑃 पर पहुँच सकते हैं। इस बिंदु से "आकार" 𝑏 के 𝑎 कदम चलकर बिंदु 𝑎(𝑏𝑃) पर पहुँच सकते हैं।
दोनों परिदृश्यों में हमने कुल मिलाकर बिंदु 𝑃 से 𝑎𝑏 कदम चले, इसलिए दोनों परिदृश्यों में हम समान अंतिम बिंदु पर पहुँचे। गणितीय रूप से, किसी बिंदु को एक स्थिरांक से गुणा करना साहचर्य (associative) होता है।
यदि हम किसी बिंदु 𝑃 से शुरू करते हैं और उसे बार-बार स्वयं में जोड़ते हैं, तो ऐसे प्रत्येक चरण पर हम वक्र पर किसी नए बिंदु पर पहुँचेंगे। चूँकि वक्र पर बिंदुओं की संख्या सीमित है, किसी अवस्था पर हम उन बिंदुओं पर पुनः पहुँचेंगे जिन पर हम पहले पहुँच चुके हैं, और हम किसी प्रकार के लूप, या "वृत्त" (circle) में होंगे। अधिक सटीक रूप से, किसी अवस्था पर हम बिंदु -𝑃 पर पहुँचेंगे, अगले चरण में हम बिंदु 𝒪 पर पहुँचेंगे, और उसके अगले चरण में हम पुनः उस बिंदु 𝑃 पर पहुँचेंगे जहाँ से हमने शुरुआत की थी।
ऐसा "वृत्त" बनाने वाला बिंदु जनरेटर (Generator) कहलाता है, क्योंकि संपूर्ण "वृत्त" उससे उत्पन्न किया जा सकता है, और इसे अक्षर 𝐺 से चिह्नित करना प्रचलन है। "वृत्त" में बिंदुओं की संख्या (बिंदु 𝒪 सहित) को "जनरेटर 𝐺 का क्रम" कहा जाता है, और इसे सामान्यतः 𝑛 से निरूपित किया जाता है। वक्र पर प्रत्येक बिंदु किसी न किसी प्रकार का "वृत्त" बनाता है। गणितीय रूप से, इस "वृत्त" पर बिंदुओं का समुच्चय एक चक्रीय समूह (cyclic group) है।
इससे प्राप्त एक रोचक गुण यह है कि किसी बिंदु 𝐺 को उसके क्रम 𝑛 से गुणा करने पर हमें इनफिनिटी का बिंदु प्राप्त होता है:
𝑛𝐺 = 𝒪
“ऐसे बिंदु 𝑃 और 𝑄 दिए जाने पर, जहाँ किसी 𝑥 के लिए 𝑄 = 𝑥𝑃, 𝑥 को खोजना कठिन है।”
और शब्दों में, मान लीजिए किसी व्यक्ति ने किसी प्रारंभिक बिंदु से शुरुआत की, उससे एक निश्चित संख्या में कदम चला, और एक अंतिम बिंदु पर पहुँचा। प्रारंभिक बिंदु और अंतिम बिंदु दिए जाने पर, हम कैसे जानें कि उन्होंने कितने कदम चले?
इस प्रश्न का उत्तर उतना सहज नहीं है, क्योंकि किसी प्रारंभिक बिंदु से आगे बढ़ने पर कौन से बिंदु प्राप्त होंगे, यह पहले से अनुमान लगाना कठिन है। एक सरल (naive) समाधान यह हो सकता है कि हम स्वयं 𝑃 से शुरू करें, उससे एक-एक कदम आगे बढ़ें और जब तक 𝑄 तक न पहुँच जाएँ, कदमों की गिनती करते रहें। इस समाधान की जटिलता 𝑂(𝑥) है, और यह अव्यवहारिक है यदि यह ज्ञात हो कि 𝑥 एक बड़ी संख्या है, उदाहरण के लिए यदि 𝑥 256 bit है।
इस समस्या को एलिप्टिक कर्व असतत लघुगणक समस्या (Elliptic Curve Discrete Logarithm Problem, ECDLP) कहा जाता है, और यह एक कठिन समस्या है। लेकिन यह कितनी कठिन है?
क्रिप्टोग्राफ़िक संदर्भ में, "समस्याओं की कठिनाई" या "क्रिप्टोग्राफ़िक सिस्टम की मजबूती" को Security Level नामक मीट्रिक से मापना प्रचलन है। इस मीट्रिक में, किसी समस्या को "𝑛 बिट सुरक्षा" वाली कहा जाता है यदि सर्वोत्तम ज्ञात हमला समस्या को $𝑂(2^𝑛)$ चरणों में हल करता है।
वर्तमान में, ECDLP समस्या को हल करने वाला सर्वोत्तम एल्गोरिदम इसे $𝑂(\sqrt n)$ की जटिलता के साथ हल करता है, जहाँ 𝑛 बिंदु 𝑃 का क्रम है, और यह Meet In The Middle हमले का उपयोग करके ऐसा करता है। जब पर्याप्त बड़े क्रम वाला बिंदु चुना जाता है, तो इसे हल करना अव्यवहारिक होता है, इसलिए समस्या की मजबूती।
उदाहरण के लिए, यदि हम 256 bit आकार का 𝑛 चुनते हैं, तो हम पाते हैं कि ECDLP समस्या में 128 bit सुरक्षा का सुरक्षा स्तर है। तुलना के लिए, पूर्णांक गुणनखंडन की समस्या पर आधारित RSA एन्क्रिप्शन में 128 bit सुरक्षा का समान स्तर प्राप्त करने के लिए 3072 bit आकार की सार्वजनिक कुंजी आवश्यक है। यह एलिप्टिक कर्व्स के उपयोग को तुलनात्मक रूप से अधिक कम्प्यूटेशनल रूप से कुशल बनाता है।
एलिप्टिक कर्व्स की दुनिया के इस पूरे परिचय के बाद, हम आगे देखेंगे कि क्रिप्टोग्राफ़िक संदर्भ में इनके साथ क्या किया जा सकता है। जैसा कि हम जानते हैं, क्रिप्टोग्राफ़िक सिस्टम आमतौर पर एक "कठिन समस्या" पर आधारित होते हैं जिसे हल करना कठिन होता है। उदाहरण के लिए RSA, जिसमें हमने जिस संख्या के गुणनखंडन की समस्या का उल्लेख किया, या Diffie-Hellman प्रोटोकॉल, जो असतत लघुगणक समस्या पर आधारित है। एक क्रिप्टोग्राफ़िक सिस्टम जो किसी एलिप्टिक कर्व में ECDLP समस्या पर आधारित है, वह एलिप्टिक कर्व क्रिप्टोग्राफी परिवार से संबंधित है, या संक्षेप में ECC।
आइए एक कहानी से शुरू करते हैं। कल्पना कीजिए कि आप एक पार्टी में हैं - एक कमरा लोगों से भरा हुआ है, जहाँ हर कोई सबसे बात कर सकता है और हर कोई सबको सुनता है। इस कमरे में ऐलिस और बॉब भी हैं, जिनकी पहले कभी मुलाकात नहीं हुई है। ऐलिस को बॉब पसंद है, और वह उससे बाहर घूमने के लिए पूछना चाहती है। ऐलिस थोड़ी शर्मीली है, इसलिए वह बॉब को यह गुप्त संदेश बिना पार्टी के अन्य मेहमानों के सुने बताना चाहती है। ऐलिस और बॉब ने पहले से कुछ भी तालमेल नहीं किया है, और ऐलिस बॉब से जो भी कहेगी, वह पार्टी के बाकी सभी मेहमान सुन लेंगे। ऐलिस बिना किसी और के सुने बॉब को संदेश कैसे बता सकती है?
यदि आपने उत्तर दिया "एलिप्टिक कर्व्स", तो आप सही हैं!
ऐलिस कुछ एलिप्टिक कर्व और उसमें एक जनरेटर चुनेगी, और उन्हें बॉब को बताएगी। विशेष रूप से, ऐलिस बॉब (और कमरे के बाकी सभी लोगों) को कर्व के दो पैरामीटर 𝑎, 𝑏, मापांक 𝑝, और जनरेटर 𝐺 प्रदान करेगी। इसके अतिरिक्त, ऐलिस $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ की सीमा में कुछ मान $𝑑_𝐴$ चुनेगी, जहाँ 𝑛 𝐺 का क्रम है। मान $𝑑_𝐴$ को ऐलिस की निजी कुंजी कहा जाता है। ऐलिस बिंदु $𝐴 = 𝑑_𝐴𝐺$ की गणना करेगी, जिसे ऐलिस की सार्वजनिक कुंजी कहा जाता है, और उसे बॉब को बताएगी। इसी प्रकार, बॉब एक निजी कुंजी $𝑑_𝐵$ चुनेगा, बिंदु $𝐵 = 𝑑_𝐵𝐺$ की गणना करेगा, जिसे बॉब की सार्वजनिक कुंजी कहा जाता है, और उसे ऐलिस को बताएगा।
ऐलिस बॉब की सार्वजनिक कुंजी लेगी, उस बिंदु को अपनी निजी कुंजी से गुणा करेगी, और एक तीसरे बिंदु $𝑃_𝐴 = 𝑑_𝐴𝐵$ पर पहुँचेगी। इसी प्रकार, बॉब ऐलिस की सार्वजनिक कुंजी लेगा, उसे अपनी निजी कुंजी से गुणा करेगा, और अपना एक तीसरा बिंदु $𝑃_𝐵 = 𝑑_𝐵𝐴$ प्राप्त करेगा। यदि हम उन बिंदुओं की जाँच करें जिन पर ऐलिस और बॉब अलग-अलग पहुँचे, तो हम पाते हैं कि वे समान बिंदु पर पहुँचे! यह तथ्य किसी बिंदु को एक स्थिरांक से गुणा करने के साहचर्य गुण से आता है, जिसे हमने पहले देखा था:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
पूरी प्रक्रिया के अंत में, ऐलिस और बॉब वक्र पर किसी बिंदु पर सहमति बनाने में सफल रहे, और किसी भी चरण में उनमें से किसी ने भी उस बिंदु को दूसरे व्यक्ति को नहीं भेजा। सभी ने जो जानकारी सुनी है वह है: 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵। कमरे में इस जानकारी को सुनने वाला व्यक्ति उस बिंदु को नहीं खोज सकता जिस पर ऐलिस और बॉब सहमत हुए हैं।
ऐसा इसलिए है क्योंकि यदि कमरे में कोई अन्य व्यक्ति उस बिंदु को खोजना चाहता, तो उसे 𝐵 या 𝐴 को उनसे गुणा करने के लिए या तो ऐलिस की निजी कुंजी या बॉब की निजी कुंजी जानने की आवश्यकता होती। उदाहरण के लिए, ऐलिस की निजी कुंजी खोजने के लिए, वे $𝐴 = 𝑑_𝐴𝐺$ को देखेंगे, क्योंकि यह एकमात्र जानकारी है जो भेजी गई थी और जिसमें ऐलिस की निजी कुंजी "समाहित" है। 𝐺 और $𝑑_𝐴𝐺$ दिए जाने पर, $𝑑_𝐴$ खोजना एलिप्टिक कर्व्स में असतत लघुगणक समस्या को हल करने के समतुल्य है, जो, जैसा कि उल्लेख किया गया है, एक कठिन समस्या है।
यह सुंदर प्रोटोकॉल कहलाता है: एलिप्टिक कर्व डिफी-हेलमैन (ECDH)।
हमारी कहानी अभी समाप्त नहीं हुई है। यद्यपि ऐलिस और बॉब एक साझा गोपनीय बिंदु पर सहमत हो गए, ऐलिस ने फिर भी बॉब से वह डेट नहीं पूछी जो वह बहुत चाहती थी।
पक्षों द्वारा साझा गोपनीय बिंदु पर सहमत होने के बाद, वे इसे किसी भी एन्क्रिप्शन विधि की एन्क्रिप्शन कुंजी के रूप में उपयोग कर सकते हैं, उदाहरण के लिए AES, और उस बिंदु से एन्क्रिप्शन के माध्यम से सुरक्षित रूप से संवाद कर सकते हैं।
बिंदु के 𝑥 या 𝑦 निर्देशांकों में से एक लेना और उसका उपयोग करना सामान्य है। सुरक्षा बनाए रखने के लिए, चयनित मान का हैश करने और केवल हैश परिणाम को एन्क्रिप्शन कुंजी के रूप में उपयोग करने की अनुशंसा की जाती है। व्यवहार में, कभी-कभी मान एन्क्रिप्शन कुंजी के रूप में उपयोग किए जाने के लिए बहुत बड़ा होता है। उदाहरण के लिए, यदि प्रयुक्त हैश फ़ंक्शन SHA-1 है, तो इसकी आउटपुट लंबाई 160 bit है, जबकि AES एन्क्रिप्शन के लिए केवल 128 bit की आवश्यकता होती है। ऐसी स्थिति में, 160 में से केवल 128 bits का उपयोग करना और शेष को छोड़ देना प्रचलन है।
वैसे भी, इस बिंदु पर ऐलिस और बॉब एक एन्क्रिप्शन कुंजी पर सहमत होते हैं, और केवल वे ही इसे जानते हैं। इस बिंदु से वे एन्क्रिप्शन के माध्यम से संवाद करते हैं, और कमरे में सुनने वाला कोई भी व्यक्ति यह नहीं समझ सकता कि वे क्या कह रहे हैं।
यहाँ प्रोटोकॉल का एक आरेख है:
सहमत कुंजी का उपयोग करके, ऐलिस संदेश "हे बॉब, क्या तुम कल शाम कॉफी के लिए बाहर चलना चाहोगे?" एन्क्रिप्ट करती है, और एन्क्रिप्टेड संदेश बॉब को भेजती है। बॉब उस कुंजी से संदेश डिक्रिप्ट करता है जिसे वह भी जानता है। ऐलिस को उम्मीद है कि बॉब हाँ कहेगा, लेकिन यह प्रोटोकॉल का हिस्सा नहीं है।
ज्ञात डिफी-हेलमैन (DH) प्रोटोकॉल में, पक्ष एक अभाज्य संख्या 𝑝 और एक जनरेटर 𝑔 खुले तौर पर प्रसारित करते हैं, जो मान 𝑝 के अनुरूप समूह में होता है। ऐलिस यादृच्छिक रूप से एक निजी कुंजी 𝑎 उत्पन्न करती है और अपनी सार्वजनिक कुंजी $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ खुले तौर पर प्रसारित करती है। इसी प्रकार बॉब यादृच्छिक रूप से एक निजी कुंजी 𝑏 उत्पन्न करता है और अपनी सार्वजनिक कुंजी $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$ खुले तौर पर प्रसारित करता है। फिर ऐलिस बॉब की सार्वजनिक कुंजी लेती है और उसे अपनी निजी कुंजी की घात तक बढ़ाती है, इस प्रकार मान $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ की गणना करती है। उसी प्रकार बॉब मान $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ की गणना करता है। प्रक्रिया के अंत में, ऐलिस और बॉब बिना इसे आपस में प्रसारित किए एक सामान्य 𝐾 मान पर सहमत होने में सक्षम थे।
उन्हें सुनने वाला एक हमलावर प्रसारित मानों 𝑝, 𝑔, 𝐴, 𝐵 दिए जाने पर 𝐾 नहीं खोज सकता। ऐसा करने के लिए, उन्हें ऐलिस या बॉब की निजी कुंजियों में से किसी एक को खोजना होगा। उदाहरण के लिए ऐलिस की निजी कुंजी की गणना करने के लिए, उन्हें 𝑔 और $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ दिए जाने पर 𝑎 खोजना होगा, जो एक कठिन समस्या है। इस समस्या को असतत लघुगणक समस्या (Discrete Logarithm Problem, DLP) कहा जाता है।
DH, जो DLP पर आधारित है, और ECDH, जो ECDLP पर आधारित है, के बीच बहुत स्पष्ट समानता है (वे मूल रूप से समान हैं, केवल EC उपसर्ग के साथ)। दोनों प्रोटोकॉल में, एक-दूसरे से बात करने वाले दो पक्ष बिना पहले से कुछ तालमेल किए किसी साझा गोपनीय मान पर सहमत हो सकते हैं। पक्षों के बीच संदेशों को सुनने वाला कोई भी व्यक्ति उनके द्वारा आपस में भेजी गई सार्वजनिक जानकारी के संपर्क में आएगा, लेकिन उनके बीच साझा किए गए गोपनीय मान तक नहीं पहुँच पाएगा।### अण्डाकार वक्रों का दूसरा उपयोग - संदेश पर हस्ताक्षर करना हमारी कहानी जारी रखते हुए, मान लीजिए कि ऐलिस और बॉब अपनी डेट पर गए और साथ में एक अच्छी शाम बिताई। अगले दिन ऐलिस को एक संदेश मिलता है जिसमें लिखा है, "हाय ऐलिस, यह बॉब है, मुझे कल तुम्हारे साथ बहुत अच्छा समय बीता और मैं इस सप्ताहांत तुमसे फिर मिलना चाहूँगा"। ऐलिस को संदेह है कि यह संदेश बॉब ने नहीं भेजा है, क्योंकि वह जानती है कि बॉब को कल उसके साथ इतना मज़ा आया था कि वह उससे मिलने के लिए सप्ताहांत तक इंतज़ार नहीं करेगा, बल्कि कल ही मिलना चाहेगा! ऐलिस कैसे सत्यापित कर सकती है कि संदेश बॉब ने ही लिखा है?
यदि आपने उत्तर दिया "अण्डाकार वक्र", तो आप फिर से सही हैं!
ECDLP समस्या की कठिनाई का उपयोग संदेशों पर हस्ताक्षर करने के लिए भी किया जा सकता है। अपनी डेट के दौरान, ऐलिस और बॉब ने किसी अण्डाकार वक्र और उसमें एक जनरेटर 𝐺 पर सहमति व्यक्त की। बॉब ने कुछ मान $𝑑_𝐵$ उत्पन्न किया, जिसे बॉब की निजी कुंजी कहा जाता है, और बिंदु $𝑃_𝐵 = 𝑑_𝐵𝐺$ की गणना की, जिसे बॉब की सार्वजनिक कुंजी कहा जाता है। बॉब ने ऐलिस को अपनी सार्वजनिक कुंजी दी ताकि वह बाद में यह सत्यापित कर सके कि उसे प्राप्त संदेश वास्तव में उसके द्वारा हस्ताक्षरित है या नहीं।
मान लीजिए बॉब एक निश्चित संदेश 𝑚 पर हस्ताक्षर करना चाहता है। वह किसी सुरक्षित हैश फ़ंक्शन का उपयोग करके मान $z = hash(m)$ की गणना करेगा, और परिणाम से उतने बिट्स रखेगा जितनी कि n की बिट लंबाई है, जो जनरेटर 𝐺 का क्रम है। बॉब $1 ≤ 𝑘 ≤ 𝑛 − 1$ की सीमा में कुछ यादृच्छिक मान 𝑘 उत्पन्न करेगा। फिर बॉब बिंदु $𝑘𝐺 = (𝑥_1, 𝑦_1)$ की गणना करेगा, उसका 𝑥-निर्देशांक लेगा, और $𝑟 = 𝑥1\ \ \ \ (mod\ n)$ की गणना करेगा। अंत में, बॉब मान $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$ की गणना करेगा।
संदेश 𝑚 के हस्ताक्षर को परिकलित मानों 𝑟 और 𝑠 की जोड़ी के रूप में परिभाषित किया गया है।
मान लीजिए कि ऐलिस को एक निश्चित संदेश 𝑚 प्राप्त हुआ, और उसके हस्ताक्षर में मानों 𝑟 और 𝑠 की एक जोड़ी है। ऐलिस यह सुनिश्चित करना चाहती है कि संदेश पर वास्तव में बॉब ने हस्ताक्षर किए हैं। ऐलिस बॉब के समान ही मान $z = hash(m)$ की गणना करेगी। फिर ऐलिस मानों $𝑢_1 = 𝑧𝑠^{−1}$ और $𝑢_2 = 𝑟𝑠^{−1}$ की गणना करेगी। अंत में ऐलिस बॉब की सार्वजनिक कुंजी $𝑃_𝐵$ का उपयोग करेगी, और बिंदु $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$ की गणना करेगी। हस्ताक्षर को वैध माना जाएगा यदि यह सत्य है कि $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$। यह सही होने का कारण यह है कि निम्नलिखित सत्य है:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
यदि हस्ताक्षर वैध है, तो इस बिंदु का 𝑥 निर्देशांक वास्तव में 𝑟 होना चाहिए, जैसा कि संदेश हस्ताक्षर में परिभाषित किया गया है। यह ध्यान दिया जाना चाहिए कि जनरेटर 𝐺 का क्रम, जिसे अक्षर 𝑛 से दर्शाया जाता है, एक अभाज्य संख्या होनी चाहिए, और यह इसलिए है ताकि हस्ताक्षर और सत्यापन एल्गोरिदम में व्युत्क्रम संख्याओं की गणना करना वास्तव में संभव हो सके।
यह देखा जा सकता है कि केवल वही व्यक्ति जिसके पास निजी कुंजी $𝑑_𝐵$ है, सार्वजनिक कुंजी $𝑃_𝐵$ के लिए एक वैध हस्ताक्षर बना सकता है। वह हमलावर जिसके पास मान $𝑑_𝐵$ नहीं है, हस्ताक्षर में $𝑃_𝐵$ के अनुरूप मान 𝑠 की गणना नहीं कर सकता। यदि हमलावर किसी निश्चित संदेश से मेल खाने वाला हस्ताक्षर बनाना चाहता है, तो उसे ECDLP समस्या को हल करना होगा, अर्थात $𝐺$ और $𝑃_𝐵 = 𝑑_𝐵𝐺$ दिए जाने पर निजी कुंजी $𝑑_𝐵$ खोजनी होगी, जो एक कठिन समस्या है।
इस हस्ताक्षर प्रोटोकॉल को Elliptic Curve Digital Signature Algorithm, या संक्षेप में ECDSA कहा जाता है। यह प्रोटोकॉल सुनिश्चित करता है कि हस्ताक्षरित संदेशों के साथ छेड़छाड़ या जालसाजी नहीं की गई है, और साथ ही यह भी सुनिश्चित करता है कि संदेश पर हस्ताक्षर करने वाला व्यक्ति यह अस्वीकार नहीं कर सकता कि उसने इसे बनाया है।
ECDH प्रोटोकॉल के विपरीत, जहाँ पक्षों को पहले से किसी भी चीज़ का समन्वय नहीं करना पड़ता था, ECDSA प्रोटोकॉल में पक्षों को पहले से एक सार्वजनिक कुंजी पर सहमत होना चाहिए। केवल जब प्रत्येक पक्ष को निश्चित रूप से पता हो कि उनके पास मौजूद सार्वजनिक कुंजी वास्तव में उस व्यक्ति की है जिसके साथ वे संवाद करना चाहते हैं, तभी प्रोटोकॉल का उपयोग किया जा सकता है। अन्यथा, प्रत्येक पक्ष के पास मौजूद सार्वजनिक कुंजी के साथ हस्ताक्षर को सत्यापित करने का कोई अर्थ नहीं है।
वापस हमारी कहानी पर। ऐलिस निश्चित रूप से जानती है कि उसके पास मौजूद सार्वजनिक कुंजी $𝑃_𝐵$ वास्तव में बॉब की है, क्योंकि बॉब ने इसे उनकी डेट पर स्पष्ट रूप से उसे दिया था। ऐलिस इसके साथ संदेश को सत्यापित करने की कोशिश करती है और पाती है कि कोई मेल नहीं है। बेशक! किसी और ने संदेश बनाया और उस पर हस्ताक्षर किए, ठीक जैसा ऐलिस को संदेह था।
यहाँ प्रोटोकॉल का एक आरेख है:
संदेशों पर हस्ताक्षर करने के लिए ElGamal प्रोटोकॉल में, पक्ष एक बड़ी अभाज्य संख्या 𝑝 और एक जनरेटर संख्या 𝑔 पर सहमत होते हैं। हस्ताक्षर करने वाला पक्ष $1 ≤ 𝑑 < 𝑝 − 1$ की सीमा में कुछ मान 𝑑 उत्पन्न करता है, जिसे निजी कुंजी कहा जाता है, मान $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$ की गणना करता है, जिसे सार्वजनिक कुंजी कहा जाता है, और इसे प्रकाशित करता है।
एक निश्चित संदेश पर हस्ताक्षर करने के लिए, वे मान $z = hash(m)$ की गणना करते हैं और $1 ≤ 𝑘 < 𝑝 − 1$ की सीमा में एक यादृच्छिक मान 𝑘 उत्पन्न करते हैं जो $(p-1)$ के सह-अभाज्य (co-prime) हो। वे $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ और $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$ की गणना करते हैं। संदेश m के हस्ताक्षर को परिकलित मानों 𝑟 और 𝑠 की जोड़ी के रूप में परिभाषित किया गया है।
जिस पक्ष को एक निश्चित संदेश 𝑚 प्राप्त हुआ है, और जिसके हस्ताक्षर में मानों 𝑟 और 𝑠 की एक जोड़ी है, वह सार्वजनिक कुंजी 𝑦 का उपयोग करके मानों $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ और $𝑢_2 = 𝑔^𝑧$ की गणना करके हस्ताक्षर को सत्यापित करता है। यदि $𝑢_1 = 𝑢_2$ है तो हस्ताक्षर वैध माना जाएगा। ऐसा इसलिए है क्योंकि 𝑠 की परिभाषा के अनुसार यह दर्शाता है:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, इसलिए $𝑘𝑠 = 𝑧 − 𝑑𝑟$, अतः $𝑧 = 𝑘𝑠 + 𝑑𝑟$। इसलिए:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
एक हमलावर निजी कुंजी 𝑑 को जाने बिना सार्वजनिक कुंजी 𝑦 के लिए वैध हस्ताक्षर नहीं बना सकता। सार्वजनिक कुंजी दिए जाने पर निजी कुंजी प्राप्त करने के लिए, हमलावर को DLP समस्या को हल करना होगा, जो एक कठिन समस्या है।
यहाँ भी ECDSA, जो ECDLP पर आधारित है, और ElGamal, जो DLP पर आधारित है, के बीच एक स्पष्ट समानता है। दोनों ही मामलों में, पक्षों को पहले से एक सार्वजनिक कुंजी का समन्वय करना होता है, और हर बार जब हम किसी नए संदेश पर हस्ताक्षर करना चाहते हैं तो एक यादृच्छिक 𝑘 मान उत्पन्न करना आवश्यक होता है। साथ ही, दोनों ही मामलों में, पक्षों के बीच संदेशों को सुनने वाला हमलावर ऐसी उपयोगी जानकारी नहीं निकाल सकता जो उन्हें हस्ताक्षर जाली बनाने की अनुमति दे।
हमने देखा कि कैसे अण्डाकार वक्रों का उपयोग क्रिप्टोग्राफ़िक प्रणालियों में एक गुप्त मान पर सहमति बनाने और संदेशों पर हस्ताक्षर करने के लिए किया जा सकता है। जीवन की हर चीज़ की तरह, जब किसी चीज़ को व्यवहार में लाने की बात आती है, तो चीज़ें हमेशा योजना के अनुसार काम नहीं करतीं। लेख के शेष भाग में मैं ECC-आधारित क्रिप्टोग्राफ़िक प्रणालियों पर हमला करने के विभिन्न तरीके प्रस्तुत करूँगा, जिनका उपयोगकर्ता द्वारा दुरुपयोग किया गया है, या जिन्हें असुरक्षित तरीके से लागू किया गया है।
स्वाभाविक रूप से, मैंने इस भाग को ECDH पर हमलों और ECDSA पर हमलों में विभाजित किया है। दोनों ही मामलों में हम कहेंगे कि हम हमले में "सफल" हुए हैं यदि हमें किसी एक पक्ष की निजी कुंजी मिल जाती है, और हम वहीं रुक जाएंगे। ECDH के मामले में, यह पर्याप्त है क्योंकि निजी कुंजी से साझा गुप्त मान और उसके साथ बाद में एन्क्रिप्ट की गई सभी जानकारी तक पहुँचना संभव है। ECDSA के मामले में, यह पर्याप्त है क्योंकि निजी कुंजी का उपयोग हमारी इच्छानुसार संदेशों पर हस्ताक्षर करने के लिए किया जा सकता है।
SageMath एक मुफ्त और खुला-स्रोत गणितीय सॉफ्टवेयर है। इसे लगभग Python के समान सिंटैक्स में लिखा जा सकता है, और इसे Python लाइब्रेरी के रूप में भी उपयोग किया जा सकता है। यह लाइब्रेरी अण्डाकार वक्रों से संबंधित उपयोगी फ़ंक्शन लागू करती है और इसलिए ECC के संदर्भ में हमें जो गणनाएँ करनी होती हैं, उनके लिए बहुत उपयोगी है। इस लेख के भाग के रूप में मैं इस लाइब्रेरी में लिखे गए कोड स्निपेट प्रदान करता हूँ। मुझे लगा कि इसे Ubuntu ऑपरेटिंग सिस्टम पर स्थापित करना सबसे आसान है, विशेष रूप से संस्करण 22.04। इसे स्थापित करने के लिए, बस कमांड चलाएँ: sudo apt install sagemath।
कोड वाली फ़ाइल चलाने के लिए, फ़ाइल को .sage एक्सटेंशन के साथ सहेजें और कमांड चलाएँ: sage file.sage।
इसके अतिरिक्त, Python के इंटरप्रेटर के समान, कमांड sage चलाकर एक इंटरप्रेटर का उपयोग किया जा सकता है। .py फ़ाइलें बनाना भी संभव है जिनमें sage.all लाइब्रेरी आयात की जाती है, और उन्हें कमांड python3 file.py के साथ चलाया जा सकता है। ध्यान दें कि जब कमांड sage के साथ फ़ाइल चलाई जाती है, तो संकेतन ^ को घात (power) के रूप में व्याख्यायित किया जाता है, जबकि python3 के साथ चलाने पर, इस संकेतन को xor के रूप में व्याख्यायित किया जाता है।
इस लेख में मैं मुख्य रूप से SageMath में निम्नलिखित फ़ंक्शन का उपयोग करता हूँ:
E.gens() - वक्र E में जनरेटर खोजनाG.order() - जनरेटर G के क्रम की गणना करनाn*G - जनरेटर G का संख्या n से गुणाn.factor() - संख्या n को उसके गुणनखंडों में गुणनखंडित करना - फ़ंक्शन (𝑝, 𝑒) जोड़ियों की एक सूची लौटाता है, जैसे कि 𝑝 एक अभाज्य गुणनखंड है, और 𝑒 उसका घातांक है, अर्थात n के अपघटन में 𝑝 कितनी बार आता हैcrt - चीनी शेष प्रमेय की समीकरण प्रणाली को हल करनाशायद ECDH का सबसे आसानी से हमला किया जाने वाला गलत उपयोग ऐसे जनरेटर का चयन करना है जिसका क्रम n बहुत छोटा हो।
जैसा कि बताया गया है, $O(\sqrt{n})$ की जटिलता के साथ ECDLP समस्या को हल करना संभव है। जब 𝑛 बहुत छोटा होता है, उदाहरण के लिए 32 बिट, तो इस समस्या को हल करना संभव हो जाता है। ऐसे कई एल्गोरिदम हैं जो इस समस्या को हल करते हैं, जिनमें Baby-Step Giant-Step, Pollard's Rho, और Pollard's Lambda शामिल हैं। इन एल्गोरिदम को SageMath की सहायता से, discrete_log फ़ंक्शन का उपयोग करके, एक ब्लैक बॉक्स के रूप में चलाया जा सकता है:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
इस कोड स्निपेट में हम वक्र के लिए पैरामीटर यादृच्छिक रूप से चुनते हैं, इस सीमा के साथ कि `𝑝` 32 बिट लंबा है। यह सीमा हमें गारंटी देती है कि वक्र पर बिंदुओं की संख्या $O(2^{32})$ है और इसलिए उसमें प्रत्येक बिंदु का क्रम भी अधिकतम $O(2^{32})$ है। इसके बाद हम वक्र बनाते हैं, उसमें कुछ जनरेटर चुनते हैं, एक यादृच्छिक निजी कुंजी उत्पन्न करते हैं, और सार्वजनिक कुंजी की गणना करते हैं। अंत में, जनरेटर और सार्वजनिक कुंजी से, हम निजी कुंजी खोजने के लिए असतत लघुगणक की गणना करते हैं, और सत्यापित करते हैं कि पाई गई कुंजी वास्तव में सही है। यह कोड निजी कुंजी खोजने में अधिकतम कुछ ही सेकंड लेता है।
## जनरेटर का क्रम एक स्मूथ संख्या है
जैसा कि उल्लेख किया गया है, जनरेटर का क्रम उस “वृत्त” में बिंदुओं की संख्या के रूप में परिभाषित किया जाता है जो तब बनता है जब हम जनरेटर बिंदु को बार-बार स्वयं में जोड़ते हैं, और इसे `𝑛` द्वारा निरूपित किया जाता है। यदि `𝑛` एक भाज्य संख्या है जिसे छोटे अभाज्य गुणनखंडों में विभाजित किया जा सकता है, तो ECDLP को कुशलतापूर्वक हल करना संभव है। ऐसी संख्या को स्मूथ संख्या कहा जाता है, और इस लेख के प्रयोजन के लिए, यह एक ऐसी संख्या है जिसे पर्याप्त अभाज्य गुणनखंडों में विभाजित किया जा सकता है, जिनमें से प्रत्येक इतना छोटा हो कि हमारा हमला काम कर सके। स्मूथ संख्या की औपचारिक परिभाषा थोड़ी अलग है और हमारे लिए प्रासंगिक नहीं है।
सहज रूप से, यह प्रत्येक अभाज्य गुणनखंड पर अलग-अलग “हमला” करके किया जाता है। एक जनरेटर बिंदु `𝐺` दिया गया है जो एक बहुत बड़ा “वृत्त” बनाता है, और “वृत्त” में कुछ बिंदु `𝑃` इस प्रकार है कि `𝑃 = 𝑘𝐺`। बड़े “वृत्त” को कई छोटे “वृत्तों” में विघटित किया जा सकता है, प्रत्येक का आकार `𝑛` के एक अभाज्य गुणनखंड के बराबर होता है। प्रत्येक छोटे “वृत्त” में हम `G` और `P` को अन्य संगत बिंदुओं `G'` और `P'` पर मैप कर सकते हैं जो छोटे “वृत्त” में स्थित हैं, और `𝑃′ = 𝑘′𝐺′` को संतुष्ट करते हैं। क्योंकि “वृत्त” छोटा है, समस्या को हल करना और `𝑘′` खोजना अपेक्षाकृत आसान है। अंत में, हम उन सभी छोटे `𝑘′`s को, जो हमें मिले हैं, मूल “वृत्त” में वांछित `𝑘` में संयोजित कर सकते हैं।
जो एल्गोरिथ्म मैंने वर्णित किया है उसे Pohlig-Hellman एल्गोरिथ्म कहा जाता है। इसकी रनटाइम जटिलता $O(\sqrt{p_{max}})$ है, जहाँ $p_{max}$, `𝑛` के गुणनखंडन में सबसे बड़ा अभाज्य गुणनखंड है। यह समझ में भी आता है, क्योंकि एल्गोरिथ्म में सबसे “भारी” हिस्सा छोटे “वृत्तों” में से सबसे बड़े “वृत्त” में ECDLP समस्या को हल करना है। उदाहरण के लिए, `n` एक 128-बिट संख्या हो सकती है, और यह ऐसे अभाज्य गुणनखंडों में विभाजित होती है कि उनमें से सबसे बड़ा 30-बिट की संख्या हो। एल्गोरिथ्म समस्या को हल करने की जटिलता को $2^{64}$ से घटाकर $2^{15}$ कर देता है, इस प्रकार इसे असंभव से संभव में बदल देता है।
सौभाग्य से, SageMath का `discrete_log` फ़ंक्शन अपने कार्यान्वयन में इस एल्गोरिथ्म को निष्पादित करता है। हमला चलाने के लिए आप केवल फ़ंक्शन को कॉल कर सकते हैं:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
इस कोड स्निपेट में हम एक अण्डाकार वक्र और उसमें एक जनरेटर को परिभाषित करते हैं, और इसके क्रम के अभाज्य गुणनखंडों को प्रिंट करते हैं। आउटपुट है:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
यह देखा जा सकता है कि यद्यपि जनरेटर का क्रम 128 बिट लंबा है, यह अभाज्य गुणनखंडों में इस प्रकार टूट जाता है कि सबसे बड़ा अभाज्य गुणनखंड 32 बिट है।
उसके बाद, पिछले हमले की तरह - हम एक यादृच्छिक निजी कुंजी चुनते हैं, उससे एक सार्वजनिक कुंजी की गणना करते हैं, और फिर जनरेटर और सार्वजनिक कुंजी दिए जाने पर निजी कुंजी की गणना करते हैं और सत्यापित करते हैं कि यह सही है।
हालाँकि हमारा काम हो चुका है, हमने यह नहीं देखा है कि "छोटे" वृत्त कैसे परिभाषित होते हैं, बिंदुओं `𝐺` और `𝑃` को उनके संगत बिंदुओं `𝐺′` और `𝑃′` में कैसे मैप किया जाता है, और सभी छोटे समाधानों को एक बड़े समाधान में कैसे जोड़ा जाता है। मैं इसे यहाँ सहज रूप से समझाने की कोशिश करूँगा, क्योंकि अगला हमला भी इसी भाग पर आधारित है।
मान लीजिए कि हमारे पास क्रम `3𝑥5𝑥7 = 105` का एक "वृत्त" है, और इसका जनरेटर `𝐺` है। हम एक बिंदु `𝐺′ = (5𝑥7)𝐺 = 35𝐺` परिभाषित करेंगे, और उससे उत्पन्न "वृत्त" को देखेंगे। यदि हम `𝐺′` से एक "कदम" आगे बढ़ते हैं, अर्थात हम `𝐺′` को स्वयं में जोड़ देंगे, तो यह मूल "वृत्त" में बिंदु `35𝐺` से 35 कदम आगे बढ़ने जैसा होगा, और हम बिंदु `2𝐺′ = 70𝐺` पर पहुँचेंगे। यदि हम एक और "कदम" आगे बढ़ते हैं, तो हम बिंदु `3𝐺′ = 105𝐺 = 𝒪` पर पहुँचेंगे, और यदि हम उससे एक और "कदम" आगे बढ़ते हैं, तो हम बिंदु `4𝐺′ = 35𝐺 = 𝐺′` पर पहुँचेंगे, अर्थात वापस शुरुआती बिंदु पर। `G′` द्वारा निर्मित "वृत्त" क्रम `3` का है, और यह कोई संयोग नहीं है, क्योंकि क्रम `105` वाले "वृत्त" पर आकार `35` के ठीक `3` "कदम" उठाना संभव है। इसी प्रकार, हम बिंदु `𝐺′ = (3𝑥7)𝐺 = 21𝐺` परिभाषित करके क्रम `5` का एक "वृत्त" बना सकते हैं, और `𝐺′ = (3𝑥5)𝐺 = 15𝐺` परिभाषित करके क्रम `5` का एक वृत्त बना सकते हैं।
जब हम इसे दूसरी तरफ से देखते हैं, तो यह और दिलचस्प हो जाता है। मान लीजिए कि मूल "वृत्त" में हमने बिंदु `G` से `𝑛` कदम उठाए और हम बिंदु `𝑛𝐺` पर पहुँचे। यदि छोटे "वृत्त" में भी हम बिंदु `𝐺′` से `𝑛` कदम उठाते, तो हम बिंदु `𝑛′𝐺′` पर पहुँचते, जैसे कि `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`। और यह दिलचस्प क्यों है? क्योंकि `𝐺′` का क्रम `𝐺` के क्रम से बहुत छोटा है और इसलिए `𝐺′` और `𝑛′𝐺′` दिए जाने पर, हम अपेक्षाकृत आसानी से `𝑛′` पा सकते हैं। यदि हम ऐसा करते हैं, और इसे "वृत्त" के क्रम के अन्य दो अभाज्य गुणनखंडों, जो `5` और `7` हैं, के लिए भी करते हैं, तो हमारे पास निम्नलिखित मान होंगे:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
इन तीन मानों से, चीनी शेषफल प्रमेय का उपयोग करके `𝑛` आसानी से पाया जा सकता है, और इस प्रकार मूल समस्या हल हो जाती है।
## जनरेटर का क्रम लगभग एक स्मूथ संख्या है, और निजी कुंजी छोटी है
मान लीजिए कि, पिछले हमले की तरह, हमें एक वक्र मिलता है जिसमें जनरेटर का क्रम अभाज्य गुणनखंडों में विभाजित हो जाता है, लेकिन इस बार, सबसे बड़ा अभाज्य गुणनखंड इतना बड़ा है कि उसका ECDLP हल करना व्यावहारिक नहीं है। उदाहरण के लिए, यदि जनरेटर क्रम `256 bit` है, लेकिन सबसे बड़ा अभाज्य गुणनखंड `128 bit` है।
Pohlig-Hellman एल्गोरिथ्म को निजी कुंजी खोजने के लिए लगभग $O(2^{64})$ संक्रियाओं की आवश्यकता होगी, जो अव्यवहार्य है।
यदि हम जानते हैं कि उपयोग की गई निजी कुंजी अपेक्षाकृत छोटी है, तो इसे अभी भी कुशलता से पाया जा सकता है।
मान लीजिए कि निजी कुंजी `64 bit` है (`256 bit` के बजाय)। जब सार्वजनिक कुंजी बनाई जाती है, तो जनरेटर को निजी कुंजी से गुणा किया जाता है और आपको "वृत्त" में कोई बिंदु मिलता है जिसे जनरेटर बनाता है। यद्यपि "वृत्त" लगभग $2^{256}$ बिंदुओं के आकार का है, यह बिंदु "पहले" $2^{64}$ बिंदुओं में कहीं "गिरेगा"। निजी कुंजी और "वृत्त" के उन बिंदुओं के बीच कोई "अंतःक्रिया" नहीं है जो बड़े मानों के अनुरूप हैं।
Pohlig-Hellman एल्गोरिथ्म को चलाना संभव है, लेकिन बहुत बड़े "वृत्तों" को "त्याग" दें, बशर्ते कि शेष "वृत्तों" के क्रमों का गुणनफल कम से कम निजी कुंजी की लंबाई के बराबर हो। यदि पर्याप्त छोटे अभाज्य गुणनखंड मिल जाते हैं, जिनका गुणनफल कम से कम `64 bit` है, तो संगत "वृत्त" उसी हमले को करने के लिए पर्याप्त होंगे जो हमने पहले देखा था।
यदि पहले हमें कोड लिखने के मामले में आसानी थी, तो इस बार हमें चीजों को स्वयं लागू करना होगा, क्योंकि SageMath का `discrete_log` फ़ंक्शन नहीं जानता कि हम कुछ अभाज्य गुणनखंडों को "त्याग" करना चाहते हैं। निम्नलिखित कोड स्निपेट यह करता है:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
इस कोड स्निपेट में हम एक अण्डाकार वक्र और उसमें एक जनरेटर परिभाषित करते हैं, और इसके क्रम के अभाज्य गुणनखंड प्रिंट करते हैं। आउटपुट है:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
जनरेटर का क्रम `256 bit` है, और यह कई अभाज्य गुणनखंडों में विघटित होता है, जैसे कि दो सबसे बड़े गुणनखंड `77 bit` और `107 bit` हैं। वे इतने बड़े हैं कि ECDLP को हल करना अव्यावहारिक होगा। फिर, `64 bit` की एक निजी कुंजी यादृच्छिक रूप से उत्पन्न की जाती है, और एक सार्वजनिक कुंजी की गणना की जाती है। अगले चरण में हम पर्याप्त अभाज्य गुणनखंडों को "एकत्र" करते हैं जब तक कि हमें कम से कम `64 bit` लंबाई का एक क्रम न मिल जाए। आउटपुट है:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
यह देखा जा सकता है कि दो सबसे बड़े गुणनखंड अनावश्यक हैं, और सबसे बड़ा गुणनखंड जो बचता है वह 40 bit है। अगले चरण में, शेष प्रत्येक गुणनखंड के लिए, हम बिंदु 𝐺′ और 𝑃′ की गणना करते हैं जैसा कि मैंने पहले समझाया था, और उनमें से प्रत्येक के लिए हम ECDLP हल करते हैं। परिणाम और अभाज्य गुणनखंड क्रमशः subsolutions और subgroups सूचियों में रखे जाते हैं। अंत में, सभी परिणामों को चीनी शेष प्रमेय (Chinese Remainder Theorem) का उपयोग करके निजी कुंजी में संयोजित किया जाता है, और हम सत्यापित करते हैं कि यह वास्तव में सही है।
दीर्घवृत्तीय वक्रों में बिंदु योग की परिभाषा की जाँच करने पर, हम एक दिलचस्प गुण देखते हैं जिसमें बिंदु योग में 𝑏 मान का उपयोग नहीं होता, केवल 𝑎 और 𝑝 मानों का उपयोग होता है। इसका अर्थ है कि एक वक्र पर स्थित बिंदुओं को जोड़ना किसी अन्य वक्र के लिए भी सार्थक हो सकता है, जो केवल 𝑏 मान में उससे भिन्न होता है। यह निश्चित रूप से किसी बिंदु को किसी संख्या से गुणा करने पर भी सत्य है। यदि उपयोगकर्ता यह सत्यापित नहीं करता कि दूसरे पक्ष से सार्वजनिक कुंजी के रूप में प्राप्त बिंदु वास्तव में उसके वक्र पर है, तो वह स्वयं को अमान्य वक्र आक्रमण (Invalid Curve Attack) के लिए उजागर करता है।
मान लीजिए कि दो पक्ष किसी दीर्घवृत्तीय वक्र $E_1$ पर सहमत हुए। एक हमलावर एक दुर्भावनापूर्ण वक्र $𝐸_2$ बना सकता है, जिसमें $𝐸_1$ के समान 𝑎 और 𝑝 मान होते हैं लेकिन 𝑏 मान भिन्न होता है। वक्र $𝐸_2$ में हमलावर एक बिंदु 𝑃 चुनेगा जिसका क्रम छोटा हो, उदाहरण के लिए 3। निश्चित रूप से, बिंदु 𝑃 $𝐸_1$ पर नहीं होगा, क्योंकि यह $𝐸_1$ से भिन्न 𝑏 मान वाले समीकरण को संतुष्ट करता है। हमलावर बिंदु 𝑃 को अपनी सार्वजनिक कुंजी के रूप में उपयोगकर्ता को भेजेगा। मान लीजिए कि उपयोगकर्ता यह सत्यापित करने की जहमत नहीं उठाता कि प्राप्त बिंदु वास्तव में उस वक्र $𝐸_1$ पर है जिस पर पक्ष सहमत हुए थे। उपयोगकर्ता हमलावर से प्राप्त सार्वजनिक कुंजी लेगा, उसे अपनी निजी कुंजी से गुणा करेगा, और एक ऐसे बिंदु पर पहुँचेगा जो साझा गुप्त बिंदु होना चाहिए, जैसा कि हमने ECDH प्रोटोकॉल की परिभाषा में देखा। उपयोगकर्ता के दृष्टिकोण से, वह वक्र $𝐸_1$ पर गुणन संक्रिया की गणना करेगा। लेकिन चूँकि बिंदु 𝑃 उस पर बिल्कुल नहीं है, बल्कि $𝐸_2$ पर है, उपयोगकर्ता वास्तव में वक्र $𝐸_2$ पर गुणन संक्रिया की गणना करेगा। बाद में, उपयोगकर्ता हमलावर के साथ संचार जारी रखने के लिए साझा गुप्त बिंदु का उपयोग करेगा। मान लीजिए कि पक्ष बिंदु के 𝑥-निर्देशांक को AES एन्क्रिप्शन कुंजी के रूप में उपयोग करते हैं। इस स्थिति में, उपयोगकर्ता कुछ संदेश एन्क्रिप्ट करके हमलावर को भेजेगा।
चूँकि 𝑃 का क्रम 3 है, उपयोगकर्ता द्वारा गणना किए जाने वाले साझा बिंदु के लिए केवल 3 संभावनाएँ हैं। हमलावर इन संभावित बिंदुओं की जाँच करेगा और पता लगाएगा कि उनमें से कौन सा उस कुंजी से मेल खाता है जो उपयोगकर्ता द्वारा भेजे गए एन्क्रिप्टेड संदेश को सफलतापूर्वक डिक्रिप्ट करती है। इस बिंदु और प्रारंभिक बिंदु 𝑃 को देखते हुए, हमलावर उपयोगकर्ता की निजी कुंजी को संख्या 3 से विभाजित करने पर प्राप्त शेषफल का अनुमान लगा सकता है। हमलावर उपयोगकर्ता को बढ़ते क्रम वाले अतिरिक्त दुर्भावनापूर्ण 𝑃 बिंदु भेज सकता है, उदाहरण के लिए 5, 7, इत्यादि। इस प्रकार हमलावर पर्याप्त मान एकत्र कर सकता है जो छोटी संख्याओं द्वारा उपयोगकर्ता की निजी कुंजी के विभाजन के शेषफलों को दर्शाते हैं। अंत में हमलावर चीनी शेष प्रमेय का उपयोग करके उपयोगकर्ता की निजी कुंजी की गणना कर सकता है, उसी तरह जैसे हमने पिछले आक्रमण में देखा था।
यहाँ एक अधिक सहज व्याख्या है: एक हमलावर उपयोगकर्ता को एक बहुत छोटे "वृत्त" पर एक बिंदु प्रदान कर सकता है, उदाहरण के लिए लंबाई 2 का। उपयोगकर्ता इस "वृत्त" में कितने भी कदम आगे बढ़ेगा और गंतव्य बिंदु तक पहुँचेगा। हमलावर उपयोगकर्ता के गंतव्य बिंदु को जानता है, जो 2 संभावनाओं में से एक हो सकता है। इसलिए हमलावर बता सकता है कि उपयोगकर्ता ने वृत्त पर सम या विषम संख्या में कदम उठाए हैं। हमलावर उपयोगकर्ता को लंबाई 3, 5, 7, इत्यादि वाले "वृत्तों" पर अतिरिक्त बिंदु प्रदान कर सकता है। जब तक हमलावर के पास ऐसे पर्याप्त गुणनखंड नहीं हो जाते, जिनमें से प्रत्येक में उपयोगकर्ता द्वारा उठाए गए कदमों की संख्या के बारे में थोड़ी जानकारी होती है। अंत में हमलावर इन सभी मानों को उपयोगकर्ता द्वारा उठाए गए कदमों की सटीक संख्या में संयोजित कर सकता है, जो उसकी निजी कुंजी है।
निम्नलिखित कोड आक्रमण को प्रदर्शित करता है:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
इस कोड स्निपेट में, एक वक्र और एक जनरेटर चुने जाते हैं, उपयोगकर्ता यादृच्छिक रूप से एक निजी कुंजी उत्पन्न करता है और ECDH प्रोटोकॉल के सभी उपयोगों में उसी का उपयोग करता है। फ़ंक्शन `find_curves_with_small_subgroup` बिंदुओं और क्रमों के जोड़े ढूँढता है, जैसे कि प्रत्येक बिंदु का क्रम अपेक्षाकृत छोटा हो, और बिंदु किसी ऐसे वक्र पर हो जो मूल वक्र से केवल `𝑏` के मान में भिन्न हो। कोड ऐसे जोड़े तब तक उत्पन्न करता है जब तक पर्याप्त जोड़े नहीं मिल जाते। प्रत्येक जोड़े के लिए, सार्वजनिक कुंजी उपयोगकर्ता को भेजी जाती है और उनसे एक एन्क्रिप्टेड संदेश प्राप्त किया जाता है।
एन्क्रिप्टेड संदेश पर ब्रूट फोर्स किया जाता है ताकि उपयोगकर्ता की निजी कुंजी का मान, वर्तमान क्रम के मॉड्यूलो, ज्ञात किया जा सके। इन सभी परिणामों को सहेज लिया जाता है, और अंत में हम उपयोगकर्ता की निजी कुंजी की गणना करने और उसे सत्यापित करने के लिए चीनी शेष प्रमेय का उपयोग करते हैं। इस मामले में पक्षकारों ने सहमति व्यक्त की कि संचार AES में किया जाएगा, जिसमें एन्क्रिप्शन कुंजी साझा गुप्त बिंदु का `x` निर्देशांक है, और IV उसका `𝑦` निर्देशांक है।
हमले की जटिलता $𝑂(𝑛_{𝑚𝑎𝑥})$ है, जहाँ $𝑛_{𝑚𝑎𝑥}$ दुर्भावनापूर्ण बिंदुओं के क्रमों में सबसे बड़ा क्रम है। ऐसा इसलिए है क्योंकि हमले का सबसे "भारी" हिस्सा छोटे "वृत्तों" में से सबसे बड़े "वृत्त" पर ब्रूट फोर्स है, और हमलावर के लिए सौभाग्य से, वे इस मान को लगभग पूरी तरह से नियंत्रित कर सकते हैं। इसलिए यह हमला जटिलता की दृष्टि से अपेक्षाकृत कुशल है। जैसा कि उल्लेख किया गया है, इस मामले में समस्या की जड़ यह है कि उपयोगकर्ता यह जाँच नहीं करता कि उसे प्राप्त बिंदु उस वक्र पर भी है जिसके साथ वह काम कर रहा है। इसके अलावा, उपयोगकर्ता ECDH के हर नए उपयोग में एक ही निजी कुंजी का उपयोग करता है, जो उतना सुरक्षित नहीं है।
## वक्र एकवचन है
एक दीर्घवृत्तीय वक्र को क्रिप्टोग्राफिक रूप से सुरक्षित होने के लिए आवश्यक महत्वपूर्ण गुणों में से एक यह है कि वह गैर-एकवचन हो। गैर-एकवचन वक्र वह वक्र है जिसका एक निश्चित मान, जिसे वक्र का "discriminant" कहा जाता है, अशून्य होता है। यह स्थिति तब होती है जब इसके पैरामीटर `𝑎` और `𝑏` निम्न असमानता को संतुष्ट करते हैं:
$4a^3 + 27b^2 ≠ 0$
जो वक्र इस असमानता को संतुष्ट नहीं करता, उसमें एक "समस्याग्रस्त" बिंदु होता है जिसे `singular point` कहा जाता है। ऐसे बिंदुओं के दो प्रकार हैं: node और cusp। node बिंदु ऐसे वक्र पर मौजूद होता है जिसमें एक प्रकार का लूप होता है जो एकवचन बिंदु पर स्वयं को प्रतिच्छेदित करता है, और इस बिंदु से वक्र पर दो अलग-अलग स्पर्श रेखाएँ गुजारी जा सकती हैं।
cusp बिंदु वह बिंदु है जहाँ वक्र "नुकीला" होता है, मानो उसमें से दो रेखाएँ निकल रही हों, लेकिन उस बिंदु पर वक्र की केवल एक स्पर्श रेखा होती है।
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
node प्रकार के बिंदु पर एक दोहरा मूल (double root) होता है, इसलिए वक्र का समीकरण इस प्रकार लिखा जा सकता है:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
वक्र को चर $x$ के स्थान पर चर $(𝑥 + 𝑥_0)$ रखकर बाईं ओर "खिसकाया" जा सकता है और निम्न रूप प्राप्त किया जा सकता है:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
तो अब एकवचन बिंदु अक्षों के मूल बिंदु पर है। $t = (x_0-x_1)$ का संख्यात्मक मान वक्र पर स्थित बिंदुओं से पूर्णांकों में एक मैपिंग बनाने के लिए उपयोग किया जा सकता है, जिससे वक्र पर बिंदुओं के बीच की जोड़ संक्रिया संख्याओं के बीच की गुणन संक्रिया के तुल्य होगी। प्रत्येक बिंदु `(𝑥, 𝑦)` के साथ हम संख्या $\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$ का मिलान करेंगे। विशेष रूप से, बिंदुओं `𝐺` और `𝑄` की ऐसी जोड़ी के लिए कि `𝑄 = 𝑛𝐺`, हम संख्याओं `𝑔` और `𝑞` को इस प्रकार मैप कर सकते हैं कि $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, और यह एक "सामान्य" DLP समस्या है। इस प्रक्रिया को समझाने के लिए, मैंने लेख के अंत में संदर्भों में छोटी संख्याओं वाले एक उदाहरण का लिंक जोड़ा है। हमने जो मैपिंग की, उसमें हमने रैखिक रेखाओं $y+\sqrt{t}x$ और $y-\sqrt{t}x$ के समीकरणों का उपयोग किया, और वे उन दो स्पर्श रेखाओं के अनुरूप हैं जिन्हें एकवचन बिंदु पर खींचा जा सकता है (वक्र को "खिसकाने" के बाद), और यह मूल रूप से वही कारण है जिससे इस हमले का उपयोग किया जा सकता है।
ऐसी DLP समस्या को Pohlig-Hellman एल्गोरिदम की सहायता से कुशलतापूर्वक हल किया जा सकता है, जिसे हम पहले भी देख चुके हैं, क्योंकि इसका उपयोग वक्र पर बिंदुओं के बजाय पूर्णांकों पर भी किया जा सकता है। बिंदुओं के संदर्भ में, हमने देखा कि एल्गोरिदम तब उपयोगी होता है जब जनरेटर का क्रम एक स्मूथ संख्या हो। वक्र पर बिंदुओं के एक "वृत्त" के विपरीत, जिसका क्रम कुछ भी हो सकता है, अभाज्य संख्या `𝑝` के मॉड्यूलो पूर्णांकों के क्षेत्र में क्रम `𝑝 − 1` होता है। यदि `𝑝 − 1` एक स्मूथ संख्या है, तो एल्गोरिदम DLP समस्या को कुशलतापूर्वक हल कर देगा, जिससे निजी कुंजी `n` मिल जाएगी।```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
इस कोड स्निपेट में, हम एक अण्डाकार वक्र (elliptic curve) के पैरामीटर परिभाषित करते हैं, और सत्यापित करते हैं कि यह वास्तव में singular है। हम वक्र के अनुरूप बहुपद (polynomial) के मूल (roots) निकालते हैं, और पहचानते हैं कि उनमें से कौन सा दोहरा मूल (double root) है। हम उस दोहरे मूल का उपयोग करके वक्र को "स्थानांतरित" (move) करते हैं, और "स्थानांतरित" बिंदुओं 𝐺 और 𝑄 तक पहुँचते हैं। फिर हम प्राप्त मूलों से $\sqrt{t}$ की गणना करते हैं और उसका उपयोग बिंदुओं 𝐺 और 𝑄 को संख्याओं 𝑔 और 𝑞 में मैप करने के लिए करते हैं। हम 𝑝 − 1 का अभाज्य गुणनखंडों (prime factors) में अपघटन (decomposition) प्रिंट करते हैं (यह सत्यापित करने के लिए कि DLP को वास्तव में कुशलता से हल किया जा सकता है)। अंत में हम DLP की गणना करते हैं और परिणाम को एक स्ट्रिंग के रूप में व्याख्यायित करते हैं।
आउटपुट है: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
इस बार मैंने प्राइवेट की में ही एक संदेश छिपाया। यह ध्यान दिया जाना चाहिए कि चूँकि यह एक सिंगुलर वक्र है, इसलिए SageMath में इसे सामान्य तरीके से बनाना, उस पर बिंदु निर्धारित करना और पहले की तरह उन पर संक्रियाएँ करना संभव नहीं है। इस कोड में मैंने बिंदुओं के निर्देशांकों को स्थिर चर के रूप में परिभाषित किया। बिंदु `𝑄` की गणना करने के लिए मैंने Double And Add एल्गोरिथम के अपने कार्यान्वयन का उपयोग करके प्राइवेट की को जनरेटर से स्वयं गुणा किया।
## वक्र सुपरसिंगुलर है
मॉड्युलो `𝑝` वाले दीर्घवृत्तीय वक्र और क्रम `𝑛` वाले जनरेटर के लिए, जनरेटर के सापेक्ष वक्र की एम्बेडिंग डिग्री को सबसे छोटी संख्या `k` के रूप में परिभाषित किया जाता है, जो समीकरण $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$ को संतुष्ट करती है। कुछ परिवर्तनों के साथ, ECDLP समस्या को $𝑝^𝑘$ क्रम के क्षेत्र में DLP समस्या में कम किया जा सकता है। `𝑘` का मान सामान्यतः बहुत बड़ी संख्या होता है (लगभग `𝑝` के आकार के बराबर), परंतु जब यह अपेक्षाकृत छोटा होता है (मान लीजिए, `6` से छोटा), तो वक्र को `supersingular` कहा जाता है और इस DLP समस्या को कुशलतापूर्वक हल करना संभव हो जाता है। इस हमले को MOV attack कहा जाता है, जिसका नाम इसके तीन आविष्कारकों (Menezes-Okamoto-Vanstone) के नाम पर रखा गया है।
मैंने जिन परिवर्तनों का उल्लेख किया है, वे ऐसे फलन हैं जो दो बिंदु लेते हैं और सम्मिश्र संख्याओं के क्षेत्र में कुछ संख्या लौटाते हैं। उपयोग किए जा सकने वाले परिवर्तन Weil Pairing या Tate Pairing हैं, और हम उन्हें ब्लैक बॉक्स के रूप में उपयोग करेंगे। ऐसा परिवर्तन `𝑇` प्रत्येक बिंदु युग्म `𝑃`, `𝑄` के लिए निम्नलिखित गुणधर्म संतुष्ट करता है:
$T(mP, nQ)=T(P,Q)^{mn}$
इसलिए, दो बिंदुओं `𝐺` और `𝑄 = 𝑚𝐺` को देखते हुए, हम यादृच्छिक रूप से तीसरा बिंदु `𝑅` चुन सकते हैं और दो मानों की गणना कर सकते हैं: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
यहाँ से हम $p^k$ क्रम के क्षेत्र में `𝑔` और `𝑞` के लिए DLP समस्या को हल कर सकते हैं, इस प्रकार प्राइवेट की `𝑚` ज्ञात कर सकते हैं। मैंने लेख के अंत में संदर्भों में इस हमले के पीछे के गणित की अधिक विस्तृत व्याख्या का लिंक शामिल किया है।
निम्नलिखित कोड स्निपेट यह हमला करता है:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
इस कोड स्निपेट में हम एक वक्र और उसके जनरेटर को परिभाषित करते हैं, और उसका एम्बेडिंग डिग्री मान निकालते हैं, जो इस मामले में 2 है, इसलिए हमला करना व्यावहारिक है। हम एक ऐसा वक्र परिभाषित करते हैं जो मूल वक्र के समान है, सिवाय इसके कि गणनाएँ मॉड्यूलो $𝑝$ के बजाय मॉड्यूलो $𝑝^𝑘$ के साथ की जाती हैं। दो बिंदु 𝐺 और 𝑄 भी नए वक्र पर हैं। फिर हम एक तीसरा बिंदु ढूंढते हैं जिसका क्रम 𝑛 को विभाजित करता है।
तीसरे बिंदु का उपयोग करके, हम बिंदुओं 𝐺 और 𝑄 को संख्याओं 𝑔 और 𝑞 में मैप करते हैं और उनके लिए असतत लघुगणक की गणना करते हैं। अंत में, हम सत्यापित करते हैं कि प्राप्त परिणाम वास्तव में सही है।
आउटपुट है:``` Found k: 2 Calculating private key... success! The private key is: Festivus
From a computational point of view, today there are Index Calculus algorithms that can solve the DLP problem in a relatively efficient way, and they do it with complexity of $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. This expression may seem scary, but compared to ECDLP algorithms whose complexity is $O(\sqrt{p})=e^{O(log\ p)}$, it can be seen that it is easier to solve the DLP problem, assuming that the Embedding Degree (denoted by `𝑘`) is indeed small.
## The Curve Is Anomalous
यदि किसी वक्र में यह गुण हो कि वक्र का order (उस पर मौजूद बिंदुओं की संख्या) बिल्कुल modulus `𝑝` के बराबर है, तो उसे `Anomalous Curve` कहा जाता है और वह Smart's Attack नामक हमले के प्रति संवेदनशील होता है। यह हमला `𝑝-adic numbers` का उपयोग करता है। ऐसी संख्या को `p` की घातों (धनात्मक और ऋणात्मक) के योग के रूप में गुणांकों सहित दर्शाया जा सकता है। औपचारिक रूप से, ऐसी संख्या `s` निम्न रूप की एक श्रृंखला होती है:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
जब गुणांक $0 ≤ 𝑎_𝑖 < 𝑝$ की सीमा में पूर्णांक होते हैं, और योग `𝑝` की धनात्मक घातों की दिशा में अनंत हो सकता है। ऐसी संख्याओं में, हम अंकों को बाएँ से दाएँ के बजाय दाएँ से बाएँ "देखते" हैं, और इसलिए ऐसी श्रृंखला किसी मान पर अभिसरित (converge) हो सकती है। ऐसी संख्याएँ उस संख्या प्रणाली से भिन्न प्रणाली से संबंधित होती हैं जिससे हम परिचित हैं, और "सामान्य" गणितीय नियमों से बहुत अलग व्यवहार करती हैं। इस विषय पर अकेले एक पूरा लेख लिखा जा सकता है, और जो इसमें रुचि रखते हैं, उनके लिए मैंने लेख के अंत में संदर्भों में एक वीडियो का लिंक शामिल किया है जो इसे अपेक्षाकृत स्पष्ट तरीके से प्रस्तुत करता है।
किसी भी स्थिति में, इस हमले में दिए गए वक्र से एक नया वक्र बनाया जाता है, जिसे p-adic numbers के ऊपर परिभाषित किया जाता है। मूल वक्र पर दो बिंदुओं `𝐺` और `𝑄 = 𝑚𝐺` को लेते हुए, हम उन्हें नए वक्र पर संगत बिंदुओं में मैप करते हैं। प्राप्त बिंदुओं के निर्देशांकों से `𝑚` की गणना करना आसान है।
निम्नलिखित कोड हमले को अंजाम देता है:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
इस कोड स्निपेट में, एक lift फ़ंक्शन परिभाषित किया गया है, जो मूल वक्र पर एक बिंदु प्राप्त करता है, और उसके संगत नए वक्र पर एक बिंदु निर्धारित करता है। फिर हम एक एलिप्टिक वक्र और उसमें एक जनरेटर परिभाषित करते हैं, और सत्यापित करते हैं कि वक्र का ऑर्डर वास्तव में p है। हम एक निजी कुंजी चुनते हैं और संबंधित सार्वजनिक कुंजी की गणना करते हैं, फिर हमला करते हैं। हम 𝑝-एडिक संख्याओं पर एक नया वक्र परिभाषित करते हैं, और मूल बिंदुओं 𝐺 और 𝑃 को lift फ़ंक्शन का उपयोग करके और उन्हें 𝑝 से गुणा करके नए वक्र पर संबंधित बिंदुओं में मैप करते हैं।