The intuition behind elliptic curve digital signatures (ECDSA)

Last updated on Sep 25, 2024

यह लेख बताता है कि ECDSA (Elliptic Curve Digital Signature Algorithm) कैसे काम करता है और साथ ही यह क्यों काम करता है।

हम इस ट्यूटोरियल में मूल सिद्धांतों (first principles) से धीरे-धीरे एल्गोरिदम को “फिर से खोजेंगे”।

पूर्व आवश्यकताएं (Prerequisites)

हम मानकर चलते हैं कि आपको पहले से ही निम्नलिखित का ज्ञान है:

डिजिटल सिग्नेचर का संक्षेप (Recap)

डिजिटल सिग्नेचर एल्गोरिदम एक प्रोटोकॉल है जो किसी उपयोगकर्ता को किसी स्ट्रिंग के लिए क्रिप्टोग्राफ़िक स्वीकृति की मुहर (cryptographic seal of approval) देने में सक्षम बनाता है।

ऐसे उपयोगकर्ता के पास एक पब्लिक की (public key) (एक $(x,y)$ पेयर जो इलिप्टिक कर्व पॉइंट से मेल खाता है) होती है। यह पॉइंट एक प्राइवेट की (private key) से जनरेट किया गया था, जो एक सीक्रेट स्केलर वैल्यू होती है।

पब्लिक की, एक मैसेज और एक सिग्नेचर दिए जाने पर, दूसरा उपयोगकर्ता यह वेरिफाई कर सकता है कि सिग्नेचर उस व्यक्ति द्वारा बनाया गया था जिसके पास उस पब्लिक की की प्राइवेट की है, और केवल वही व्यक्ति वह सिग्नेचर जनरेट कर सकता था।

उदाहरण के लिए, क्रिप्टोकरेंसी यह वेरिफाई करने के लिए डिजिटल सिग्नेचर का उपयोग करती हैं कि क्या उपयोगकर्ता वास्तव में लेनदेन करना चाहता था। एक उपयोगकर्ता, Alice, ब्लॉकचेन को एक मैसेज भेज सकती है जिसमें लिखा हो “मेरे 10 टोकन Bob को भेजें।” ब्लॉकचेन नेटवर्क को यह सुनिश्चित होना चाहिए कि Alice ने वास्तव में उस मैसेज को अपनी स्वीकृति दी है और Bob, Alice के कॉइन नहीं चुरा रहा है।

जनरेट किया गया सिग्नेचर केवल उसी मैसेज के लिए विशिष्ट होना चाहिए और अन्य मैसेजों के लिए स्वीकार नहीं किया जाना चाहिए। अन्यथा एक हमलावर (attacker) सिग्नेचर का उपयोग करके शिकार (victim) से एक दुर्भावनापूर्ण लेनदेन को स्वीकृति दिला सकता है। यदि “transfer 10 coins to Bob” मैसेज के सिग्नेचर का उपयोग “transfer 10 coins to Eve” मैसेज की स्वीकृति के लिए भी किया जा सकता है, तो Eve उस सिग्नेचर का उपयोग करके Alice से कॉइन चुरा सकती है।

हम सिग्नेचर जनरेट करने वाले व्यक्ति को प्रूवर (prover) या साइनर (signer) कहते हैं, और जो व्यक्ति यह परीक्षण करता है कि (Public Key, message, signature) टपल वैध है या नहीं, उसे वेरिफायर (verifier) कहते हैं।

मूल रूप से, एक इलिप्टिक कर्व डिजिटल सिग्नेचर किसी प्राइवेट की के ज्ञान का प्रमाण (proof of knowledge) है। विशेष रूप से, यह इलिप्टिक कर्व पॉइंट के डिस्क्रीट लॉग (discrete log) के ज्ञान का प्रमाण है।

उन पाठकों के लिए जिन्होंने पहले ही ECDSA एल्गोरिदम देखा है:

\begin{align*} r &= kG\\ s &= k^{-1}(h + rp)\\ r &\stackrel{?}= s^{-1}(hG + rP) \end{align*}

लेकिन यह नहीं जानते कि ये फॉर्मूले कहां से आए, आप यह सीखेंगे कि इन्हें कैसे प्राप्त (derive) किया गया, इसके पीछे की सोच क्या है।

शब्दावली और संकेत (Terminology and Notation)

हम इलिप्टिक कर्व पॉइंट्स को कैपिटल अक्षरों से दर्शाते हैं, जैसे कि $Q$ । जनरेटर को $G$ कहा जाएगा। $G$ का मान शामिल सभी पक्षों को ज्ञात होता है। एक स्केलर और एक पॉइंट के बीच के गुणा को $aG$ के रूप में लिखा जाता है, जिसका अर्थ है कि $G$ को स्वयं में $a$ बार जोड़ा गया है।

दो पॉइंट $P$ और $Q$ दिए जाने पर, हम कहते हैं कि किसी को $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप का ज्ञान है यदि वे $x$ जानते हैं जिससे $xP = Q$ , या वैकल्पिक रूप से, $y$ जानते हैं जिससे $P = yQ$ हो।

हम कहते हैं कि किसी को पॉइंट $Q$ का डिस्क्रीट लॉग पता है यदि वे एक स्केलर $q$ जानते हैं जिससे $Q = qG$ हो।

जब तक अन्यथा न कहा जाए, हम किसी पॉइंट के डिस्क्रीट लॉग को उसी अक्षर के छोटे (lowercase) संस्करण से दर्शाते हैं।

सभी अंकगणितीय गणनाएँ एक finite field में की जाती हैं, लेकिन संक्षिप्तता के लिए हम $\pmod p$ नोटेशन को हटा देते हैं।

डिजिटल सिग्नेचर के विफल प्रयास

सरल दृष्टिकोण (Naive approach): प्राइवेट की को प्रकट करना

हम साबित करना चाहते हैं कि हम पब्लिक की $P$ के लिए प्राइवेट की $p$ जानते हैं, जहां $P = pG$ है।

सरल दृष्टिकोण यह है कि वेरिफायर के सामने प्राइवेट की $p$ को प्रकट कर दिया जाए ताकि वेरिफायर यह जांच सके कि वास्तव में $P = pG$ है।

बेशक, यह $p$ को प्राइवेट रखने के उद्देश्य को ही खत्म कर देता है।

$P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप के ज्ञान को साबित करना

यह साबित करना कि हम $p$ जानते हैं, यह साबित करने के बराबर है कि हम जनरेटर $G$ और पब्लिक की $P$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं। अर्थात्, $P$ प्राप्त करने के लिए $G$ को स्वयं में $p$ बार जोड़ा जाता है। $G$ और $P$ के बीच डिस्क्रीट लॉग रिलेशनशिप को प्रकट करने से प्राइवेट की का खुलासा हो जाता है।

इसलिए, यह साबित करने के बजाय कि हम जनरेटर $G$ और पब्लिक की $P$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं, हम यह साबित कर सकते हैं कि हम $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं, जहां $Q$ प्रूवर द्वारा चुना गया है और जिसका डिस्क्रीट लॉग $q$ वेरिफायर को ज्ञात नहीं है। यदि $Q$ का डिस्क्रीट लॉग वेरिफायर को ज्ञात नहीं है, तो वेरिफायर $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप दिए जाने पर प्राइवेट की प्राप्त (derive) नहीं कर सकता है।

मान लें कि $Q$ उत्पन्न करने के लिए $P$ को स्वयं में $s$ बार जोड़ने की आवश्यकता है; दूसरे शब्दों में, $sP = Q$ । यदि प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग को क्रमशः $p$ और $q$ के रूप में जानता है, तो वे आसानी से $s$ की गणना $s = q/p$ के रूप में कर सकते हैं।

$s = q/p$ को इस प्रकार प्राप्त किया गया था:

\begin{align*} Q &= sP\\ Q &= qG\\ P &= pG\\ qG &= spG \\ q &= sp \\ \frac{q}{p} &= s\\ \end{align*}

फिर वेरिफायर यह जांच सकता है कि वास्तव में $Q = sP$ है, और यह दर्शाता है कि प्रूवर $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानता है।

हालाँकि, यह दृष्टिकोण विफल हो जाता है क्योंकि एक दुर्भावनापूर्ण प्रूवर किसी और का $P$ ले सकता है (जिसकी प्राइवेट की उन्हें नहीं पता है), और एक रैंडम वैल्यू $s$ चुन सकता है, $Q = sP$ की गणना कर सकता है, और फिर वेरिफायर को $(P, Q, s)$ भेज सकता है।

इसलिए, प्रूवर का यह दिखाना कि वे $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं, यह साबित करने के लिए पर्याप्त नहीं है कि वे स्वयं $P$ का डिस्क्रीट लॉग जानते हैं। यह केवल यह दर्शाता है कि उन्होंने $Q$ उत्पन्न करने के लिए किसी $P$ को $s$ से गुणा किया।

रैंडम रूप से चुने गए $Q$ को रोकना

उपरोक्त दृष्टिकोण विफल हो गया क्योंकि प्रूवर वास्तव में $Q$ के डिस्क्रीट लॉग को जाने बिना ही $Q$ प्रस्तुत कर सकता है।

क्या हो यदि, यह स्थापित करने के लिए कि प्रूवर $Q$ का डिस्क्रीट लॉग जानता है, प्रूवर $q$ ( $Q$ का डिस्क्रीट लॉग) को वेरिफायर के सामने प्रकट कर दे?

इस मामले में, प्रूवर को वेरिफायर के सामने $q$ और $s$ दोनों प्रकट करने होंगे। तब, $s$ यह साबित करता है कि प्रूवर जानता है कि $Q$ प्राप्त करने के लिए $P$ को स्वयं में कितनी बार जोड़ा जाना चाहिए, और $q$ यह साबित करता है कि प्रूवर $Q$ का डिस्क्रीट लॉग जानता है। $q$ प्रस्तुत करना यह प्रदर्शित करता है कि $Q$ को किसी वैल्यू $s$ को चुनकर और $P$ को स्वयं में $s$ बार जोड़कर नहीं चुना गया था।

उस स्थिति में, वेरिफायर यह जांचता है कि

\begin{align*} qG &\stackrel{?}{=} Q &&\text{ // प्रूवर Q का डिस्क्रीट लॉग जानता है}\\ sP &\stackrel{?}{=} Q &&\text{ // प्रूवर जानता है कि Q प्राप्त करने के लिए P को स्वयं में कितनी बार जोड़ा जाना चाहिए} \end{align*}

इन चेक्स के साथ, प्रूवर $Q$ के डिस्क्रीट लॉग और $P$ के डिस्क्रीट लॉग को जाने बिना कोई वैध संबंध (valid relation) नहीं बना सकता या प्रस्तुत नहीं कर सकता।

हालाँकि, वेरिफायर इस जानकारी के आधार पर प्राइवेट की की गणना कर सकता है।

\begin{align*} Q &= sP\\ s^{-1}Q&=P\\ s^{-1}(qG)&=P\\ s^{-1}q &= P/G\\ s^{-1}q &= p\\ \end{align*}

तो हमारे सामने एक दुविधा है: यदि हम $Q$ का डिस्क्रीट लॉग प्रकट करते हैं, तो वेरिफायर प्राइवेट की की गणना कर सकता है। यदि प्रूवर अपनी मर्जी से $Q$ चुन सकता है, तो प्रूवर उन पब्लिक की के लिए सिग्नेचर बना सकता है जिनका डिस्क्रीट लॉग वे नहीं जानते हैं।

हम वेरिफायर को प्राइवेट की की गणना करने में सक्षम नहीं होने दे सकते, इसलिए $q$ को प्रकट करने का तो सवाल ही नहीं उठता।

इसलिए, हमारे समाधान में प्रूवर द्वारा $Q$ को चुनना शामिल होना चाहिए – लेकिन हमें प्रूवर को पूरी तरह से मनमाने ढंग से $Q$ चुनने से रोकना होगा (जैसे कि एक मनमाना $s$ चुनकर और $Q = sP$ उत्पन्न करके)।

आगे बढ़ते हुए, प्रूवर को यह साबित करना होगा कि वे $Q$ का डिस्क्रीट लॉग और $P$ का डिस्क्रीट लॉग जानते हैं, लेकिन $p$ या $q$ में से किसी भी डिस्क्रीट लॉग को प्रकट नहीं कर सकते।

यह देखा गया है कि दो पॉइंट्स के डिस्क्रीट लॉग को प्रकट किए बिना उन्हें जानने का प्रमाण देना, एक पॉइंट के डिस्क्रीट लॉग को प्रकट किए बिना उसे जानने का प्रमाण देने से आसान है।

यदि प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग जानता है, तो उसे और क्या पता होना चाहिए?

मुख्य विचार यह है:

यदि प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग जानता है, तो उसे न केवल $s$ जानना चाहिए जिससे कि $sP = Q$ , बल्कि उसे $s'$ भी जानना चाहिए जिससे कि $s'(hG + P) = Q$ हो, जहां $h$ वेरिफायर द्वारा चुनी गई एक मनमानी (arbitrary) वैल्यू है और यह एक ऐसी वैल्यू है जिसकी प्रूवर भविष्यवाणी नहीं कर सकता।

दूसरे शब्दों में, हम $P$ और $Q$ के बीच के संबंध में एडिटिव (additive) और मल्टीप्लिकेटिव (multiplicative) “शिफ्ट्स” को शामिल करना शुरू करने जा रहे हैं – और यदि प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग को जानता है, तो वे $s'$ की गणना करने में सक्षम होने चाहिए ताकि $s'(hG +P) = Q$ हो, बशर्ते प्रूवर को यह पता हो कि शिफ्ट $h$ कितना है।

एक एडिटिव शिफ्ट जालसाजी (forgeries) को रोकता है

प्रूवर को $Q$ इस तरह से चुनने से रोकने के लिए कि यह $P$ का एक साधारण स्केलर गुणा हो, वेरिफायर एक एडिटिव शिफ्ट $h$ इंजेक्ट कर सकता है।

प्रूवर द्वारा वेरिफायर को $P$ और $Q$ भेजने के बाद, वेरिफायर $h$ (एक पब्लिक स्केलर वैल्यू) के साथ प्रतिक्रिया देता है। इसके बाद प्रूवर को $s$ प्रस्तुत करना होगा जिससे कि $Q = s(hG + P)$ हो (अब हमें $s'$ नोटेशन की आवश्यकता नहीं है)।

अब $P$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप प्रूवर के नियंत्रण में नहीं है, इसके बजाय उन्हें यह दिखाना होगा कि वे $(hG + P)$ और $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं।

चूँकि वेरिफायर के पास पहले से ही $P$ और $Q$ मौजूद हैं, प्रूवर केवल एक रैंडम $s$ चुनकर $Q$ उत्पन्न नहीं कर सकता जिससे कि $Q = s(hG + P)$ हो। प्रूवर को यह साबित करना होगा कि वे नए पॉइंट $(hG + P)$ और मूल $Q$ के बीच डिस्क्रीट लॉग रिलेशनशिप को जानते हैं।

यदि प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग को जानता है, तो $s$ की गणना करना आसान है:

s = \frac{q}{h + p}

विशेष रूप से, प्रूवर ने इसे हल किया

\begin{align*} s(hG + P)&=Q\\ s(h + p) &= q\\ s&=\frac{q}{h+p} \end{align*}

आइए हमारे द्वारा अभी बनाए गए इंटरैक्टिव एल्गोरिदम को संक्षेप में समझें:

हम मान लेते हैं कि $G$ (और वह इलिप्टिक कर्व ग्रुप जिससे वह संबंधित है) पर दोनों पक्ष सहमत हैं।
प्रूवर अपनी पब्लिक की $P$ प्रकाशित करता है और यह साबित करना चाहता है कि वह प्राइवेट की $p$ जानता है।
वेरिफायर एक स्केलर $h$ के साथ प्रतिक्रिया देता है।
प्रूवर एक रैंडम $q$ चुनता है और $Q = qG$ की गणना करता है।
प्रूवर $s = q(h + p)^{-1}$ की गणना करता है और वेरिफायर को $(s, Q)$ भेजता है।
वेरिफायर जांचता है कि क्या $Q \stackrel{?}= s(hG + P)$ है।

अंतिम चेक काम करता है क्योंकि आंतरिक रूप से $s$ , $h$ और $p$ के डिस्क्रीट लॉग्स को कैंसिल कर देता है:

\begin{align*} Q &= s(hG + P)\\ qG &= \frac{q}{h + p}(hG+P)\\ qG &= \frac{q}{h + p}(hG+pG)\\ qG &= \frac{q}{h + p}(h+p)G\\ qG &= \frac{q}{\cancel{h + p}}(\cancel{h+p})G\\ qG &= qG \end{align*}

जाली सिग्नेचर (forged signatures) से बचाव

आइए देखें कि कैसे एक दुर्भावनापूर्ण प्रूवर $P$ और $Q$ के डिस्क्रीट लॉग को जाने बिना $s$ की गणना करने का प्रयास कर सकता है और देखें कि यह प्रयास क्यों विफल हो जाता है।

प्रूवर एक वैल्यू $\tilde{q}$ बनाता है और $Q = \tilde{q}P$ जनरेट करता है और $Q$ को वेरिफायर को भेजता है। मान लें कि $\tilde{q}$ दुर्भावनापूर्ण प्रूवर द्वारा बनाई गई एक वैल्यू है, न कि $Q$ का डिस्क्रीट लॉग।

वेरिफायर स्केलर $h$ के साथ प्रतिक्रिया देता है।

दुर्भावनापूर्ण प्रूवर को अब इस समीकरण को हल करना होगा

s(P + hG) = Q

चूंकि प्रूवर जानता है कि $Q = \tilde{q}P$ (लेकिन $p$ नहीं जानता) तो वे दो सब्स्टीट्यूशन्स (substitutions) आजमा सकते हैं:

$Q = \tilde{q}P$
$P = \tilde{q}^{-1}Q$

हालाँकि, प्रूवर $Q$ या $P$ को किसी भी तरह से सब्स्टीट्यूट करे, उन्हें इस समस्या का सामना करना पड़ता है कि वे $s$ को हल नहीं कर सकते क्योंकि $P$ का डिस्क्रीट लॉग उन्हें ज्ञात नहीं है।

$Q$ को सब्स्टीट्यूट करना

यहां प्रूवर $Q$ को सब्स्टीट्यूट करता है:

s(P + hG) = \boxed{Q}

s(P + hG) = \boxed{\tilde{q}P}

s = \frac{\tilde{q}P}{P + hG}

हम इलिप्टिक कर्व पॉइंट्स को विभाजित (divide) नहीं कर सकते हैं, इसलिए ऊपर दिए गए अंश (fraction) की गणना करने के लिए, हमें $p$ पता होना चाहिए:

s = \frac{\tilde{q}p}{p + h}

लेकिन प्रूवर $p$ नहीं जानता, इसलिए वे $s$ की गणना नहीं कर सकते।

$P$ को सब्स्टीट्यूट करना

अब दुर्भावनापूर्ण प्रूवर $Q$ के बजाय $P$ को सब्स्टीट्यूट करने का प्रयास करता है लेकिन इस समस्या का सामना करता है कि उसे $Q$ का डिस्क्रीट लॉग नहीं पता है:

s(\tilde{q}^{-1}Q + hG) = Q

s = \frac{Q}{(\tilde{q}^{-1}Q + hG)}

अब दुर्भावनापूर्ण प्रूवर को उपरोक्त फॉर्मूले की गणना करने के लिए $Q$ का डिस्क्रीट लॉग जानने की आवश्यकता है। हालाँकि, प्रूवर $Q$ का डिस्क्रीट लॉग नहीं जानता है, वे केवल यह जानते हैं कि यह $\tilde{q}P$ है, लेकिन वे $p$ नहीं जानते हैं। इसलिए, दुर्भावनापूर्ण प्रूवर $s$ उत्पन्न नहीं कर सकता।

शिफ्ट का एडिटिव (additive) होना क्यों आवश्यक है

हमें कैसे पता चला कि $P$ में $hG$ को जोड़ना है, बजाय इसके कि $hP$ का गुणा किया जाए और प्रूवर से एक $s$ लाने को कहा जाए जिससे $Q = hsP$ हो?

समस्या यह है कि एक मल्टीप्लिकेटिव शिफ्ट के साथ, प्रूवर $Q$ और $P$ के डिस्क्रीट लॉग्स के फैक्टर्स को कैंसिल कर सकता है।

संक्षेप में: एक दुर्भावनापूर्ण प्रूवर $q$ ( $Q$ का डिस्क्रीट लॉग) या $p$ ( $P$ का डिस्क्रीट लॉग) नहीं जानता है। हालाँकि, वे यह जानते हैं कि $Q$ , $P$ से $\tilde{q}$ गुना बड़ा है, जहाँ $\tilde{q}$ एक ऐसी संख्या है जिसे उन्होंने बनाया है और यह $q$ का वास्तविक डिस्क्रीट लॉग नहीं है।

यदि वेरिफायर $h$ प्रस्तुत करता है, और प्रूवर से एक ऐसा $s$ लाने के लिए कहता है जिससे कि $Q = shP$ हो, तो प्रूवर आसानी से $s = \tilde{q}/h$ की गणना कर लेता है।

यह वेरिफायर के टेस्ट को पास कर लेगा:

\begin{align*} Q &= shP \\ Q &= \frac{\tilde{q}}{h}h P\\ Q &= \frac{\tilde{q}}{\cancel{h}}\cancel{h} P\\ Q &= qP \\ \end{align*}

इसलिए, प्रोटोकॉल में एक एडिटिव शिफ्ट शामिल होना चाहिए ताकि पहले पॉइंट ( $P + hG$ ) और दूसरे पॉइंट $Q$ के बीच कोई सरल मल्टीप्लिकेटिव रिलेशनशिप $sh$ न हो।

हमारे प्रोटोकॉल को नॉन-इंटरएक्टिव (non-interactive) बनाना

दुर्भाग्य से, हमारे समाधान में वेरिफायर को $P$ और $Q$ प्राप्त करने के बाद $h$ भेजने की आवश्यकता होती है, जिसके लिए प्रूवर और वेरिफायर को एक-दूसरे के साथ इंटरैक्ट (interact) करने की आवश्यकता होती है।

यदि हम अपने प्रोटोकॉल को नॉन-इंटरएक्टिव बनाना चाहते हैं, तो $h$ वेरिफायर की ओर से नहीं आ सकता और इसे प्रूवर को ही उत्पन्न करना होगा।

यदि प्रूवर को $h$ पहले से पता है (जो आवश्यक है यदि प्रूफ़ नॉन-इंटरएक्टिव है), तो हम वापस अपनी मूल समस्या पर आ जाते हैं।

इस परिदृश्य में, एक दुर्भावनापूर्ण प्रूवर रैंडम रूप से $h$ चुन सकता है, फिर रैंडम रूप से $s$ चुन सकता है, और गणना कर सकता है

Q = s(hG + P)

और फिर वेरिफायर को $(P, Q, s, h)$ भेज सकता है। वेरिफायर को यह नहीं पता होता कि क्या $Q$ किसी रैंडम $s$ द्वारा जनरेट किया गया था।

प्रूवर द्वारा $h$ चुनने और वेरिफायर के साथ इंटरैक्शन से बचने के लिए, हम केवल $Q$ को हैश करके वेरिफायर द्वारा $h$ चुनने की प्रक्रिया को सिम्युलेट (simulate) कर सकते हैं:

h = \mathsf{hash}(Q)

चूँकि वेरिफायर वैसे भी रैंडम रूप से $h$ चुनेगा, प्रूवर एक हैश फ़ंक्शन का उपयोग करके छद्म-यादृच्छिक (pseudo-random) तरीके से $h$ की गणना कर सकता है। इस तकनीक को Fiat-Shamir Transform कहा जाता है।

प्राइवेट की के ज्ञान का एक कार्यात्मक प्रमाण (functional proof of knowledge)

एल्गोरिदम इस प्रकार है:

प्रूवर एक रैंडम स्केलर $q$ चुनता है और $Q = qG$ की गणना करता है।
प्रूवर $h = \mathsf{hash}(Q)$ की गणना करता है।
प्रूवर $s = \frac{q}{h + p}$ की गणना करता है।
प्रूवर वेरिफायर को $(P, Q, s, h)$ भेजता है।
वेरिफायर $h = \mathsf{hash}(Q)$ की गणना करता है।
वेरिफायर जांचता है कि $Q = s(hG + P)$ है।

इसके सुरक्षित होने का कारण यह है कि एक दुर्भावनापूर्ण प्रूवर $Q$ के डिस्क्रीट लॉग और $P$ के डिस्क्रीट लॉग को जाने बिना चरण 3 को निष्पादित (execute) नहीं कर सकता है।

जालसाजी (Forgery) असंभव है

मान लीजिए कि एक दुर्भावनापूर्ण प्रूवर $\tilde{q}$ चुनता है और $Q = \tilde{q}G$ जनरेट करता है। यहाँ, प्रूवर $Q$ का डिस्क्रीट लॉग जानता है, लेकिन $P$ का डिस्क्रीट लॉग नहीं। $h$ प्राप्त करने के लिए $Q$ को हैश करने के बाद, दुर्भावनापूर्ण प्रूवर को $s$ की गणना इस प्रकार करनी होती है कि $Q = s(hG + P)$ हो। हालाँकि, वे ऐसा नहीं कर सकते क्योंकि वे $(hG + P)$ का डिस्क्रीट लॉग नहीं जानते हैं, क्योंकि $P$ का डिस्क्रीट लॉग उन्हें ज्ञात नहीं है।

इस प्रकार, हमने प्राइवेट की को प्रकट किए बिना प्राइवेट की के ज्ञान को साबित करने के लिए एक सुरक्षित एल्गोरिदम का प्रदर्शन किया है।

प्री-ECDSA (pre-ECDSA) एल्गोरिदम

ऊपर हमने जिस एल्गोरिदम का परिचय दिया है वह केवल एक प्राइवेट की के ज्ञान को साबित करता है, यह साइनर को किसी मैसेज पर हस्ताक्षर (sign) करने की अनुमति नहीं देता है।

ECDSA में, सिग्नेचर इस बात का प्रमाण है कि हम उस पॉइंट का डिस्क्रीट लॉग जानते हैं जो हमारी पब्लिक की को $hG$ द्वारा एडिटिवली शिफ्ट (additively shifting) करके जनरेट किया गया है, जहाँ $h$ मैसेज का हैश है, और एक अन्य पॉइंट $Q$ का डिस्क्रीट लॉग है।

हालाँकि, यह वर्तमान तरीका एक सुरक्षा बग (security bug) पेश करता है क्योंकि प्रूवर पहले $h = \mathsf{hash}(\text{message})$ की गणना कर सकता है और फिर एक रैंडम $s'$ चुनकर $Q = s'(hG + P)$ की गणना कर सकता है। $Q$ अब फिर से पूरी तरह से प्रूवर के नियंत्रण में है, इसलिए हम यह भरोसा नहीं कर सकते कि प्रूवर वास्तव में डिस्क्रीट लॉग $q$ जानता है।

इसे सुरक्षित करने के लिए, हमें फिर से कुछ अतिरिक्त छद्म-यादृच्छिकता (pseudo-randomness) पेश करने की आवश्यकता है जो प्रूवर के नियंत्रण से बाहर हो।

रैंडमनेस $r$ जोड़ना

मान लें कि $r$ , $Q$ को हैश करने से प्राप्त एक रैंडम वैल्यू है। यदि हम $r$ को $P$ से इस प्रकार गुणा करते हैं, तो हमारे पास एक सुरक्षित डिजिटल सिग्नेचर एल्गोरिदम आ जाता है। शुरुआत में, ऐसा लगता है कि यह एक सर्कुलर डिपेंडेंसी (circular dependency) बनाता है, लेकिन यह वास्तव में एल्गोरिदम को सुरक्षित बनाने का मुख्य आधार है। प्रूवर द्वारा यह दिखाने के लिए एल्गोरिदम कि वे $(rP + hG)$ और $Q$ का डिस्क्रीट लॉग जानते हैं

Q = s(hG + rP)

प्रूवर एक रैंडम $p$ चुनता है और अपनी पब्लिक की $P$ को $P = pG$ के रूप में प्रकाशित करता है।
प्रूवर एक रैंडम स्केलर $q$ चुनता है और $Q = qG$ की गणना करता है।
प्रूवर एक मैसेज स्ट्रिंग $\text{message}$ चुनता है और $h = \mathsf{hash}(\text{message})$ की गणना करता है।
प्रूवर $r = \mathsf{hash}(Q)$ की गणना करता है।
प्रूवर $s = q\cdot(h + rp)^{-1}$ की गणना करता है।
प्रूवर वेरिफायर को $(\text{message}, Q, s)$ भेजता है।
वेरिफायर $r' = \mathsf{hash}(Q)$ की गणना करता है।
वेरिफायर $h = \mathsf{hash}(\text{message})$ की गणना करता है।
वेरिफायर जांचता है कि $Q \stackrel{?}= s(hG + r'P)$ है।

भले ही प्रूवर एक मनमाना $h$ चुन सकता है, वे पॉइंट $(hG + rP)$ के डिस्क्रीट लॉग को नियंत्रित नहीं कर सकते क्योंकि $r$ को $Q$ को हैश करके जनरेट किया गया है। इसलिए, $Q$ और $(hG + rP)$ के बीच डिस्क्रीट लॉग रिलेशनशिप $s$ की गणना करने के लिए, प्रूवर को वास्तव में $P$ का डिस्क्रीट लॉग $p$ जानना होगा।

प्री-ECDSA एल्गोरिदम को ऑप्टिमाइज़ (Optimize) करना

ऑप्टिमाइज़ेशन 1: $Q$ की हैशिंग अनावश्यक है क्योंकि इलिप्टिक कर्व मल्टीप्लीकेशन पहले से ही एक हैश फ़ंक्शन की तरह व्यवहार करता है

आइए वापस सोचें कि $r = \mathsf{hash}(Q)$ क्या हासिल करने की कोशिश कर रहा था। अंतिम वेरिफिकेशन फॉर्मूला है:

Q \stackrel{?}= s(hG + rP)

विचार यह है कि हम चाहते हैं कि $r$ , $Q$ पर निर्भर हो ताकि $Q$ पूरी तरह से उस वैल्यू $s$ द्वारा निर्धारित न हो जिस पर प्रूवर का पूर्ण नियंत्रण होता है। $s$ की गणना करने के लिए, प्रूवर को $P$ का डिस्क्रीट लॉग पता होना चाहिए।

हम हैशिंग का एक सस्ता विकल्प चाहते हैं जो $r$ को $Q$ पर निर्भर बनाए।

विचार करें कि यदि $r$ , $Q$ पर निर्भर है, तो यह $Q$ के डिस्क्रीट लॉग $q$ पर भी निर्भर है, क्योंकि $q$ पूरी तरह से $Q$ को निर्धारित करता है।

अब विचार करें कि यदि हमें एक स्केलर वैल्यू $a$ दी जाती है, तो $A = aG$ द्वारा बनाया गया इलिप्टिक कर्व पॉइंट $A$ रैंडम दिखाई देता है। $A$ और $a$ के बीच कोई स्पष्ट संबंध नहीं होता है। किसी स्पष्ट संबंध का यह अभाव ही डिस्क्रीट लॉग की गणना को कठिन बनाता है।

हैश फ़ंक्शन्स का आउटपुट भी रैंडम दिखाई देता है: हैश के इनपुट और आउटपुट के बीच कोई स्पष्ट संबंध नहीं होता है।

इसलिए, हम $Q = qG$ को उसी तरह मान सकते हैं जैसे हम $\mathsf{hash}(q)$ को मानेंगे। अर्थात्, $Q$ स्वयं एक हैश के आउटपुट की तरह व्यवहार करता है। हालाँकि, हम $r = Q$ सेट नहीं कर सकते क्योंकि वे एक ही प्रकार के नहीं हैं। इसके बजाय, हम बस $Q$ की $x$ वैल्यू ले सकते हैं और उसे $r$ बना सकते हैं (याद रखें, $Q$ एक $(x, y)$ पॉइंट है)।

अब $r$ अनिवार्य रूप से $q$ का हैश है, और चूँकि $Q$ सीधे $q$ पर निर्भर करता है, $r$ , $Q$ के हैश की तरह व्यवहार करता है।

इसलिए, $r = \mathsf{hash}(Q)$ की गणना करने के बजाय, हम $r = Q.x$ (जिसका अर्थ है पॉइंट $Q$ की $x$ वैल्यू) सेट करते हैं।

ऑप्टिमाइज़ेशन 2: हमें पूरा पॉइंट $Q$ भेजने की आवश्यकता नहीं है, केवल $Q$ की $x$ वैल्यू पर्याप्त है

इलिप्टिक कर्व पॉइंट्स में दो स्केलर होते हैं: पॉइंट की $x$ और $y$ वैल्यू। प्रत्येक $x$ वैल्यू में केवल दो संभावित $y$ वैल्यूज़ होती हैं, जो $\sqrt{x^3 + b} \mod p$ के समाधान (solutions) हैं।

इस प्रकार, $Q$ भेजने की कोई आवश्यकता नहीं है, केवल $r$ भेज सकते हैं क्योंकि $r$ , $Q$ की $x$ वैल्यू है।

सम्पूर्ण ECDSA एल्गोरिदम: स्टेप-बाय-स्टेप (Step-by-Step)

अब हम सबसे अधिक उपयोग किए जाने वाले नोटेशन (notation) के साथ मानक ECDSA एल्गोरिदम दिखाते हैं। हम यह भी बताते हैं कि हमारा नोटेशन कहाँ अलग है।

प्रूवर एक रैंडम $p$ चुनता है और अपनी पब्लिक की $P$ को $P = pG$ के रूप में प्रकाशित करता है।
प्रूवर वह मैसेज चुनता है जिसे वे साइन करना चाहते हैं और $h = \mathsf{hash}(\text{message})$ प्राप्त करने के लिए उसे हैश करता है।
प्रूवर एक रैंडम स्केलर $k$ चुनता है (जिसे हम $q$ कहते आ रहे हैं, लेकिन साहित्य में इसे $k$ कहा जाता है) और $R = kG$ की गणना करता है। फिर से, जिसे हमने $Q$ कहा उसे साहित्य में $R$ कहा जाता है। $R$ की केवल $x$ वैल्यू को $r = R.x$ के रूप में रखा जाता है।
प्रूवर $R = s^{-1}(hG + rP)$ के लिए $s$ की गणना इस प्रकार करता है:

s = \frac{h + rp}{k}

ध्यान दें कि $s$ हमारे पिछले कार्यान्वयन (implementation) की तुलना में “इनवर्टेड (inverted)” है। वास्तविक ECDSA एल्गोरिदम में, प्रूवर $s^{-1}$ की गणना करता है और वेरिफायर बाद में $s$ को इनवर्ट करता है, जैसा कि हम देखेंगे।

साइनर वेरिफायर को $(P, h, r, s)$ भेजता है।
वेरिफायर $R' = s^{-1}(hG + rP)$ की गणना करता है और जांचता है कि $R'$ की $x$ वैल्यू $r$ के बराबर है या नहीं।

यह फॉर्मूला आंतरिक रूप से इस प्रकार काम करता है:

\begin{align*} &=s^{-1}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rpG)\\ &=\frac{k}{h + rp}(h + rp)G\\ &=\frac{k}{\cancel{h + rp}}(\cancel{h + rp})G\\ &=kG \end{align*}

यह वही पॉइंट $R$ उत्पन्न करता है, और इसलिए $r$ , $s^{-1}(hG + rP)$ द्वारा गणना किए गए पॉइंट की $x$ वैल्यू से मेल खाएगा।

सिग्नेचर दिए जाने पर पब्लिक की प्राप्त (derive) करना

Ethereum और Bitcoin ब्लॉकचेन पब्लिक की, मैसेज और सिग्नेचर दिए जाने पर सिग्नेचर को वेरिफाई नहीं करते हैं। इसके बजाय, मैसेज और सिग्नेचर दिए जाने पर, वे पब्लिक की के लिए हल (solve) करते हैं, और जांचते हैं कि पब्लिक की अपेक्षित की (expected one) से मेल खाती है या नहीं।

यह देखने के लिए कि यह कैसे काम करता है, हम सिग्नेचर और मैसेज के हैश के दिए जाने पर पब्लिक की प्राप्त करने के लिए वेरिफिकेशन फॉर्मूले पर थोड़ा सा बीजगणित (algebra) लागू कर सकते हैं।

\begin{align*} R &= s^{-1}(hG + rP)\\ R &= s^{-1}hG + s^{-1}rP\\ R - s^{-1}hG &= s^{-1}rP\\ sr^{-1}R-r^{-1}hG&=P\\ \end{align*}

हालाँकि, केवल $(\text{message}, r, s)$ पर्याप्त नहीं है क्योंकि $r$ , $r = R.x$ की दो $y$ वैल्यूज़ के लिए दो संभावित पॉइंट्स से मेल खाता है। इस अस्पष्टता को दूर करने के लिए, साइनर को एक बुलियन (Boolean) वेरिएबल भी भेजना होगा जो यह दर्शाए कि $y$ की कौन सी वैल्यू उपयोग की जा रही है। पूरा $y$ भेजने में अधिक स्पेस लगेगा।

सिग्नेचर दिए जाने पर पब्लिक की को “रिकवर” करने के लिए ECDSA एल्गोरिदम इस प्रकार है:

प्रूवर अपनी पब्लिक की $P$ को $P = pG$ के रूप में प्रकाशित करता है।
प्रूवर एक मैसेज $\text{message}$ चुनता है जिसे वे साइन करना चाहते हैं और $h = \mathsf{hash}(\text{message})$ प्राप्त करने के लिए उसे हैश करता है।
प्रूवर एक रैंडम स्केलर $k$ चुनता है और $R = kG$ की गणना करता है।
प्रूवर $h = \mathsf{hash}(\text{message})$ की गणना करता है।
प्रूवर $R = s^{-1}(hG + rP)$ में $s$ को $s = \frac{h + rp}{k}$ के रूप में हल करता है।
साइनर वेरिफायर को $(\text{message}, r, s, v)$ भेजता है जहाँ $v$ एक बुलियन है जो यह दर्शाता है कि $r$ की कौन सी $y$ वैल्यू उपयोग की जा रही है।
वेरिफायर $v$ और $r$ से $R$ प्राप्त (derive) करता है।
वेरिफायर पब्लिक की $P$ इस प्रकार प्राप्त करता है:

P = sr^{-1}R - r^{-1}hG

और यदि गणना की गई $P$ , प्रूवर द्वारा प्रकाशित पब्लिक की $P$ से मेल खाती है तो सिग्नेचर को स्वीकार करता है।

यदि दुरुपयोग किया जाए तो ECDSA में कमजोरियां (Vulnerabilities)

ECDSA में मैलिएबिलिटी (Malleability)

एक सिग्नेचर $(\text{message}, r, s, v)$ दिए जाने पर, एक हमलावर एक दूसरा सिग्नेचर $(\text{message}, r, s', v')$ इस तरह से गणना कर सकता है कि $v \neq v'$ और $s \neq s'$ जो उसी पब्लिक की $P$ पर रिकवर होता है।

हमलावर केवल $s$ के एडिटिव इनवर्स की गणना $s' = s^{-1}$ के रूप में करता है और $v$ की वैल्यू को पलट (flip) देता है ताकि $R$ अपना एडिटिव इनवर्स बन जाए। अनिवार्य रूप से, हमने $s$ को $-s$ से और $R$ को $-R$ से बदल दिया है। चूंकि इन दोनों वैल्यूज़ को एक साथ गुणा किया जाता है, -1 आपस में कैंसिल हो जाते हैं और रिकवर की गई पब्लिक की समान रहती है:

\begin{align*}P &= (-s)r^{-1}(-R) - r^{-1}hG\\ &= sr^{-1}R - r^{-1}hG \end{align*}

इस हमले को रोकने के लिए, वेरिफायर को उसी मैसेज के लिए कोई दूसरा सिग्नेचर स्वीकार नहीं करना चाहिए जिसे वे पहले देख चुके हों। अधिक सामान्य और मजबूत समाधान एक नॉन्स (nonce) का उपयोग करना है, जो हमेशा बढ़ने वाली एक संख्या है जिसे प्रूवर को अपने मैसेज में शामिल करना चाहिए। एक नॉन्स (जिसका अर्थ है “number used once”) प्रत्येक सिग्नेचर के लिए एक विशिष्ट पहचानकर्ता (unique identifier) के रूप में कार्य करता है। प्रूवर को प्रत्येक सिग्नेचर के साथ एक नया, बड़ा नॉन्स शामिल करने की आवश्यकता बनाकर, वेरिफायर पिछले सिग्नेचर का पुन: उपयोग करने या उसे संशोधित करने के प्रयासों का आसानी से पता लगा सकता है और उन्हें अस्वीकार कर सकता है।

यदि वेरिफायर मैसेज को हैश नहीं करता है, तो नकली प्रमाण (fake proofs) बनाए जा सकते हैं।

आइए विचार करें कि एक हमलावर एक ऐसी वैल्यू $R$ बना सकता है जिसका हम डिस्क्रीट लॉग नहीं जानते हैं, लेकिन हम उसके कंपोनेंट्स (components) जानते हैं। उदाहरण के लिए, हमलावर रैंडम वैल्यूज़ $a$ और $b$ चुनता है और $R = aG + bP$ , और $r = R.x$ की गणना करता है।

फिर, हमलावर $s = r/b$ और $h = ar / b$ की गणना करता है।

हम वेरिफिकेशन फॉर्मूले में $s$ और $h$ के लिए गलत वैल्यूज़ (false values) डालकर देख सकते हैं कि यह हमला कैसे काम करता है:

\begin{align*} R &\stackrel{?}= s^{-1}(hG + rP) \\ R &\stackrel{?}= (\frac{r}{b})^{-1}((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (\frac{b}{r})((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (aG + bP) \end{align*}

इस हमले से बचाव सरल है: $h$ को वेरिफायर द्वारा मैसेज को हैश करने का परिणाम होना चाहिए। जब किसी मैसेज को हैश किया जाता है, तो इसकी संभावना बहुत कम होती है कि हैश बिल्कुल $ar/b$ हो।

सारांश (Summary)

ECDSA एल्गोरिदम एक मनमाने (arbitrary) पॉइंट $R$ और एक ऐसे पॉइंट के बीच डिस्क्रीट लॉग रिलेशनशिप के ज्ञान का प्रमाण है जो जनरेटर और पब्लिक की द्वारा गुणा किए गए मैसेज हैश के योग (sum) को दर्शाता है, और जहाँ पब्लिक की को एक ऐसी छद्म-यादृच्छिक (pseudorandom) वैल्यू से गुणा किया जाता है जिस पर साइनर का नियंत्रण नहीं होता है।

विशेष रूप से, यह $R$ और $(hG + rP)$ के बीच डिस्क्रीट लॉग रिलेशनशिप के ज्ञान का प्रमाण है।

यद्यपि साइनर अपनी मर्जी से $R$ चुन सकता है, वे पॉइंट $(hG + rP)$ के डिस्क्रीट लॉग को नियंत्रित नहीं कर सकते क्योंकि $r$ छद्म-यादृच्छिक रूप से $R$ पर निर्भर करता है। साइनर $R = s(hG + rP)$ में $s$ की गणना केवल तभी कर सकता है जब वे वास्तव में $P$ का डिस्क्रीट लॉग, यानी प्राइवेट की जानते हों।

श्रेय और आभार (Credits and Acknowledgements)

इस लेख के निर्माण के दौरान निम्नलिखित संसाधनों (resources) से परामर्श लिया गया था:

एलिप्टिक कर्व डिजिटल सिग्नेचर (ECDSA) के पीछे का अंतर्ज्ञान