ईसीडीएसए हस्ताक्षर के चार बुनियादी नियम ...

May 10 2023

1999 में, डॉन जॉनसन अल्फ्रेड मेनेजेस (1999) ने "द एलिप्टिक कर्व डिजिटल सिग्नेचर एल्गोरिथम (ECDSA)" पर एक क्लासिक पेपर प्रकाशित किया: मूल रूप से, इसने DSA (डिजिटल सिग्नेचर एल्गोरिथम) लिया - डेविड डब्ल्यू क्रावित्ज़ द्वारा बनाया गया - और इसे में परिवर्तित कर दिया। एक अण्डाकार वक्र प्रतिनिधित्व।

अनस्प्लैश पर सिग्नेचर प्रो द्वारा फोटो

1999 में, डॉन जॉनसन अल्फ्रेड मेनेजेस (1999) ने "द एलिप्टिक कर्व डिजिटल सिग्नेचर एल्गोरिथम (ECDSA)" पर एक क्लासिक पेपर प्रकाशित किया:

मूल रूप से, इसने DSA (डिजिटल सिग्नेचर एल्गोरिथम) लिया - डेविड डब्ल्यू क्रावित्ज़ द्वारा बनाया गया - और इसे एक अण्डाकार वक्र प्रतिनिधित्व में परिवर्तित कर दिया। और, इसलिए, जैसे-जैसे असतत लॉग बड़े होते जा रहे थे, अण्डाकार वक्र विधियाँ बहुत अधिक कुशल थीं।

फिर, 2007 में, Satoshi Nakamoto ने अपने Bitcoin कार्यान्वयन के लिए कोड लिखना शुरू किया, और ECDSA को मुख्य हस्ताक्षर विधि के रूप में चुना, और secp256k1 वक्र का उपयोग किया। एथेरियम के लिए भी, ईसीडीएसए हस्ताक्षर विधि का उपयोग करने का प्राकृतिक तरीका था। लेकिन, अगर सही ढंग से लागू नहीं किया गया तो ECDSA हस्ताक्षरों पर हमला होने की संभावना है, तो आइए चार बुनियादी नियमों पर एक नजर डालते हैं।

ईसीडीएसए का असली जादू यह था कि हमें सार्वजनिक कुंजी को स्टोर करने की आवश्यकता नहीं थी, लेकिन जहां निजी कुंजी के हैश संस्करण से हस्ताक्षर की जांच की जा सकती थी। इस तरह, ब्लॉकचैन को इसका इस्तेमाल करने वालों की सार्वजनिक कुंजी को स्टोर करने की आवश्यकता नहीं थी, और यह पहली बार था जब हमने वास्तव में विकेन्द्रीकृत सूचना बुनियादी ढांचे का निर्माण किया।

यदि आप यह समझना चाहते हैं कि ईसीडीएसए हस्ताक्षर कैसे कार्य करते हैं, तो यहां प्रयास करें ।

नॉन को कभी लीक न करें

उदाहरण: लीक ऑफ नॉन (SECP256k1) से ECDSA क्रैक करें । गैर के साथ ईसीडीएसए । यह ECDSA की रूपरेखा बताता है कि कैसे SECP256k1 के लिए गैर मूल्य के रिसाव के साथ निजी कुंजी को पुनर्प्राप्त किया जा सकता है।

एक ईसीडीएसए हस्ताक्षर के साथ, हम एक निजी कुंजी ( निजी ) के साथ एक संदेश पर हस्ताक्षर करते हैं और सार्वजनिक कुंजी ( पब ) के साथ हस्ताक्षर को प्रमाणित करते हैं। एक यादृच्छिक मान (एक गैर) तब हस्ताक्षर को यादृच्छिक करने के लिए उपयोग किया जाता है। हर बार जब हम हस्ताक्षर करते हैं, हम एक यादृच्छिक गैर मूल्य बनाते हैं और यह एक अलग (लेकिन सत्यापन योग्य) हस्ताक्षर उत्पन्न करेगा। कुल मिलाकर हस्ताक्षरकर्ता को केवल हस्ताक्षर के तत्वों और उनकी सार्वजनिक कुंजी को प्रकट करना होता है, न कि गैर मान को। यदि हस्ताक्षरकर्ता गलती से केवल एक अस्थायी मान प्रकट करता है, तो एक घुसपैठिया निजी कुंजी खोज सकता है। इस मामले में हम गैर मूल्य प्रकट करेंगे, और निजी कुंजी निर्धारित करेंगे, और secp256k1 वक्र (जैसा कि बिटकॉइन के साथ प्रयोग किया जाता है) का उपयोग करेंगे।

ईसीडीएसए में, बॉब एक यादृच्छिक निजी कुंजी ( निजी ) बनाता है, और उसके बाद एक सार्वजनिक कुंजी बनाता है:

पब = प्राइवेट × जी

इसके बाद, एम के संदेश के लिए हस्ताक्षर बनाने के लिए , वह एक यादृच्छिक संख्या ( के ) बनाता है और इसके हस्ताक्षर उत्पन्न करता है:

आर = के ⋅ जी

s = k ^{−1}( H ( M )+ r ⋅ priv )

हस्ताक्षर तब ( r , s ) है और जहां r बिंदु kG का x-निर्देशांक है । H ( M ) संदेश ( M ) का SHA-256 हैश है , और एक पूर्णांक मान में परिवर्तित हो गया है। यदि किसी भी हस्ताक्षर के लिए k मान प्रकट होता है, तो एक घुसपैठिया निजी कुंजी का उपयोग करके निर्धारित कर सकता है:

priv = r ^{−1}×(( k ⋅ s )− H ( M ))

यह काम करता है क्योंकि:

s ⋅ k = H ( M )+ r ⋅ निजी

इसलिए:

r ⋅ निजी = s ⋅ k − H ( M )

और निजी के लिए :

priv = r −1( s ⋅ k − H ( M ))

यहां कुछ कोड है जो निजी कुंजी की खोज करता है, अगर गैर ( के ) प्रकट होता है [ यहां ]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()
print ("Curve detail")
print (G.curve())
print ("Order:",order)
print ("Gx:",G.x())
print ("Gy:",G.y())

priv = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv)
Private_key = ecdsa.ecdsa.Private_key(Public_key, priv)
 
k1 = random.randrange(1, 2**127)
msg1="Hello"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
m1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
 
sig1 = Private_key.sign(m1, k1)

print ("\nMessage 1: ",msg1)
print ("Sig 1 r,s: ",sig1.r,sig1.s)
r1_inv = libnum.invmod(sig1.r, order)
s1 = sig1.s
 
try_private_key = (r1_inv * ((k1 * s1) - m1)) % order
print ()
print ("Found Key: ",try_private_key)
print ()
print ("Key: ",priv)
if (ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key):
 print("\nThe private key has been found")
 print (try_private_key)

Curve detail
CurveFp(p=115792089237316195423570985008687907853269984665640564039457584007908834671663, a=0, b=7, h=1)
Order: 115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424

Message 1:  hello
Sig 1 r,s:  31110256322898237264490243973699731757547476866639597679936653478826981616940 39826373609221276498318363598911660764943881869513002749160966300292770474312
Found Key:  95525957745036960168874600860927089941985475618074755510253043724286299804190
Key:  95525957745036960168874600860927089941985475618074755510253043724286299804190
The private key has been found
95525957745036960168874600860927089941985475618074755510253043724286299804190

उदाहरण: कमजोर अंक (sepc256k1) के साथ ECDSA को क्रैक करें । ECDSA: एक ही नॉन से निजी कुंजी का खुलासा करना । यह ईसीडीएसए को रेखांकित करता है कि कैसे कमजोर गैर मूल्यों के साथ निजी कुंजी को पुनर्प्राप्त किया जा सकता है।

पब = प्राइवेट × जी

आर = के ⋅ जी

s = k ^{−1}( H ( M )+ r ⋅ priv )

हस्ताक्षर तब ( r , s ) है और जहां r बिंदु kG का x-निर्देशांक है । H ( M ) संदेश ( M ) का SHA-256 हैश है , और एक पूर्णांक मान में परिवर्तित हो गया है।

अब मान लें कि हमारे पास दो संदेश हैं ( एम 1 और एम 2) और हैश हैं:

एच 1= एच ( एम 1)

एच 2= एच ( एम 2)

अब मान लें कि ऐलिस एक ही निजी कुंजी ( priv) और उसी nonce ( k) के साथ संदेशों पर हस्ताक्षर करती है , तो हम इसके साथ निजी कुंजी को पुनर्प्राप्त कर सकते हैं:

हम नॉन को भी पुनर्प्राप्त कर सकते हैं:

यहाँ कुछ कोड है जो निजी कुंजी की खोज करता है, और यदि हम उसी गैर मूल्य का उपयोग करते हैं तो नॉन ( k ) [ यहाँ ]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()
priv1 = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
x1 = ecdsa.ecdsa.Private_key(Public_key, priv1)
k = random.randrange(1, 2**127)
msg1="Hello"
msg2="Hello1"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
if (len(sys.argv)>2):
 msg2=(sys.argv[2]) 

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k)
sig2 = x1.sign(h2, k)
r1,s1 = sig1.r,sig1.s
r2,s2 = sig2.r,sig2.s
valinv = libnum.invmod( r1*(s1-s2),order)
x1rec = (   (s2*h1-s1*h2) * (valinv)) % order
print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r2}, s={s2}")

print ("\nPrivate key",priv1)
print ("\nPrivate recovered ",x1rec)
valinv = libnum.invmod( (s1-s2),order)
k1rec = (   (h1-h2) * valinv) % order
print ("\nK: ",k)
print ("\nK recovered ",k1rec)

Message 1:  hello
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=78942102071383249892109282228339664393041099900407940222266026023142592864884
Message 2:  hello1
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=83502523167965149244641473202679268630845178075816922294718909855670078364206
Private key 6542179820561127199468453109220159836323733777364616770035873205004743487369
Private recovered  6542179820561127199468453109220159836323733777364616770035873205004743487369
K:  109308891778201478280270581205739604663
K recovered  109308891778201478280270581205739604663

उदाहरण: दो चाबियों और साझा किए गए गैरों (SECP256k1) से निजी कुंजी का खुलासा करना । ECDSA: निजी कुंजी का खुलासा, दो कुंजियों और साझा गैर से (SECP256k1) । यह ईसीडीएसए की रूपरेखा देता है कि हम चार हस्ताक्षरित संदेशों से दो निजी कुंजियों को कैसे प्रकट कर सकते हैं।

एक ईसीडीएसए हस्ताक्षर के साथ, हम एक निजी कुंजी ( निजी ) के साथ एक संदेश पर हस्ताक्षर करते हैं और सार्वजनिक कुंजी ( पब ) के साथ हस्ताक्षर को प्रमाणित करते हैं। एक यादृच्छिक मान (एक गैर) तब हस्ताक्षर को यादृच्छिक करने के लिए उपयोग किया जाता है। हर बार जब हम हस्ताक्षर करते हैं, हम एक यादृच्छिक गैर मूल्य बनाते हैं और यह एक अलग (लेकिन सत्यापन योग्य) हस्ताक्षर उत्पन्न करेगा। हालाँकि, निजी कुंजी की खोज की जा सकती है यदि ऐलिस चार संदेशों को दो चाबियों और दो नॉन [2] के साथ साइन करती है। इस मामले में, वह पहली निजी कुंजी ( x 1) के साथ संदेश 1 पर हस्ताक्षर करेगी, दूसरी निजी कुंजी ( x 2) के साथ संदेश 2 पर हस्ताक्षर करेगी, पहली निजी कुंजी ( x 1) के साथ संदेश 3 पर हस्ताक्षर करेगी और संदेश 4 पर हस्ताक्षर करेगी। दूसरी निजी कुंजी ( x 2) समान संख्या ( k1) संदेश 1 और 2 के लिए हस्ताक्षर करने में उपयोग किया जाता है, और दूसरा गैर ( k 2) संदेश 3 और 4 के हस्ताक्षर में उपयोग किया जाता है।

पब = प्राइवेट × जी

आर = के ⋅ जी

s = k −1( H ( M )+ r ⋅ priv )

इस मामले में, ऐलिस के पास दो प्रमुख जोड़े होंगे, और दो निजी कुंजी ( x 1 और x 2) के साथ। वह पहली निजी कुंजी ( x 1) के साथ संदेश 1 ( m 1), दूसरी निजी कुंजी ( x 2) के साथ संदेश 2 ( m 2), पहली निजी कुंजी ( x ) के साथ संदेश 3 ( m 3) पर हस्ताक्षर करेगी। 1), और दूसरी निजी कुंजी ( x 2) के साथ संदेश 4 ( एम 4) पर हस्ताक्षर करें। संदेश 1 और 2 पर हस्ताक्षर करने के लिए समान संख्या ( k 1) का उपयोग किया जाता है, और संदेश 3 और 4 पर हस्ताक्षर करने के लिए अन्य संख्या ( k 2) का उपयोग किया जाता है। अब मान लें कि हमारे पास चार संदेश ( m 1 .. m) हैं4) और हैश है:

एच 1= एच ( एम 1)

एच 2= एच ( एम 2)

एच 3= एच ( एम 3)

एच 4= एच ( एम 4)

संदेशों के लिए हस्ताक्षर तब होंगे ( s 1, r 1), ( s 2, r 1), ( s 3, r 2), और ( s 4, r 2):

s 1= k 1−1( h 1+ r 1⋅ x 1)(mod p )

s 2= k 1−1( h 2+ r 1⋅ x 2)(mod p )

s 3= k 2−1( h 3+ r 2⋅ x 1)(mod p )

s 4= k 2−1( h 4+ r 2⋅ x 2)(mod p )

गाऊसी उन्मूलन का उपयोग करके, हम निजी कुंजियों को भी पुनर्प्राप्त कर सकते हैं:

और:

यहां कुछ कोड है जो निजी कुंजियों को खोजता है [ यहां ]:

import ecdsa
import random
import libnum
import hashlib
import sys
G = ecdsa.SECP256k1.generator
order = G.order()
priv1 = random.randrange(1,order)
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
x1 = ecdsa.ecdsa.Private_key(Public_key, priv1)
priv2 = random.randrange(1,order)
Public_key2 = ecdsa.ecdsa.Public_key(G, G * priv2)
x2 = ecdsa.ecdsa.Private_key(Public_key2, priv2)
k1 = random.randrange(1, 2**127)
k2 = random.randrange(1, 2**127)
msg1="Hello"
msg2="Hello1"
msg3="Hello3"
msg4="Hello4"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
if (len(sys.argv)>2):
 msg2=(sys.argv[2]) 
if (len(sys.argv)>3):
 msg3=(sys.argv[3]) 
if (len(sys.argv)>4):
 msg4=(sys.argv[4]) 

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
h3 = int(hashlib.sha256(msg3.encode()).hexdigest(),base=16)
h4 = int(hashlib.sha256(msg4.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k1)
sig2 = x2.sign(h2, k1)
sig3 = x1.sign(h3, k2)
sig4 = x2.sign(h4, k2)
r1,s1 = sig1.r,sig1.s
r1_1,s2 = sig2.r,sig2.s
r2,s3 = sig3.r,sig3.s
r2_1,s4 = sig4.r,sig4.s
valinv = libnum.invmod( r1*r2*(s1*s4-s2*s3),order)
x1rec = ((h1*r2*s2*s3-h2*r2*s1*s3-h3*r1*s1*s4+h4*r1*s1*s3    ) * valinv)  % order
x2rec = ((h1*r2*s2*s4-h2*r2*s1*s4-h3*r1*s2*s4+h4*r1*s2*s3    ) * valinv)  % order

print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r1_1}, s={s2}")
print ("\nMessage 3: ",msg3)
print (f"Signature r={r2}, s={s3}")
print ("\nMessage 4: ",msg4)
print (f"Signature r={r2_1}, s={s4}")
print ("\nPrivate key (x1):",priv1)
print ("\nPrivate recovered (x1): ",x1rec)
print ("\nPrivate key (x2):",priv2)
print ("\nPrivate recovered (x2):",x2rec)

Message 1:  hello
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=11930786632149881397940019723063699895405239832076777367931993614016265847425
Message 2:  hello1
Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=86716405197525298580208026914311340731533780839926210284720464080897845438167
Message 3:  hello2
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=42453302255950972549884862083375617752595228510622859389343928824741407916152
Message 4:  hello3
Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=64279036158699242111613174757286438038132181593159757823380636958768174455517
Private key (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858
Private recovered (x1):  82160419381684073393977402015108188969157550419795710258656483526045067388858
Private key (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942
Private recovered (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942

उदाहरण: फॉल्ट अटैक । ECDSA: फॉल्ट अटैक । ECDSA में फॉल्ट अटैक में हमें केवल दो हस्ताक्षरों की आवश्यकता होती है । एक दोष के बिना उत्पन्न होता है ( r , s ), और दूसरे में दोष होता है ( rf , sf )। इनसे हम निजी कुंजी उत्पन्न कर सकते हैं।

ECDSA में फॉल्ट अटैक में हमें केवल दो हस्ताक्षरों की आवश्यकता होती है । एक दोष के बिना उत्पन्न होता है ( r , s ), और दूसरे में दोष होता है ( rf , sf )। इनसे हम निजी कुंजी [3,4] उत्पन्न कर सकते हैं।

पब = प्राइवेट × जी

आर = के ⋅ जी

s = k ^{−1}( h + r ⋅ d )

और जहां डी निजी कुंजी है और एच = एच ( एम ) हस्ताक्षर तब ( आर , एस ) है और जहां आर बिंदु केजी का एक्स-समन्वय है । h संदेश का SHA-256 हैश ( M ) है, और एक पूर्णांक मान में परिवर्तित हो गया है।

अब, मान लें कि हमारे पास दो हस्ताक्षर हैं। एक में दोष है और दूसरे में दोष है। तब हमारे पास वैध के लिए ( r , s ) और दोष के लिए ( rf , sf ) है। ये होंगे:

एसएफ = के ^ { -1}। ( एच + डी । आरएफ ) (मॉड पी )

s = k ^{−1}.( h + d . r )(mod p )

और जहां एच

संदेश का हैश है। अब अगर हम दो एस घटाते हैं

हमें प्राप्त मूल्य:

s − sf = k ^{−1}.( h + d . r )− k^{ −1}.( h + d . rf )

तब:

इसके बाद इसे प्रतिस्थापित किया जा सकता है:

s = k^{ −1}( h + r . d )(mod p )

यह देता है:

फिर हम इसे निजी कुंजी ( d ) से प्राप्त करने के लिए पुनर्व्यवस्थित कर सकते हैं:

इसे लागू करने के लिए कोड यहां दिया गया है [ यहां ]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()
priv1 = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
d = ecdsa.ecdsa.Private_key(Public_key, priv1)
k = random.randrange(1, 2**127)
msg="Hello"
if (len(sys.argv)>1):
 msg=(sys.argv[1])

h = int(hashlib.sha256(msg.encode()).hexdigest(),base=16)
sig = d.sign(h, k)

r,s = sig.r,sig.s
# Now generate a fault
rf = sig.r+1
sf=(libnum.invmod(k,order)*(h+priv1*rf)) % order
k = h*(s-sf) * libnum.invmod(sf*r-s*rf,order)

valinv = libnum.invmod( (sf*r-s*rf),order)
dx =(h*(s-sf)* valinv) % order
print(f"Message: {msg}")
print(f"k: {k}")
print(f"Sig 1 (Good): r={r}, s={s}")
print(f"Sig 2 (Faulty): r={rf}, s={sf}")
print (f"\nGenerated private key: {priv1}")
print (f"\nRecovered private key: {dx}")

Message: hello
k: 15613459045461464441268016329920647751876410646419944753875923461028663912505625338208127533545920850138128660754322530221814353295370007218638086487275174473446354362246611811506735710487039390917643920660108528521515014507889120
Sig 1 (Good): r=84456595696494933440514821180730426741490222897895228578549018195243892414625, s=68818602365739991134541263302679449117335025608295087929401907013433000993001
Sig 2 (Faulty): r=84456595696494933440514821180730426741490222897895228578549018195243892414626, s=58598513613070973829759520121438538694005185742306423466103492198584643742545
Generated private key: 15195234419506006831576867959209365250058907799872905479943949602323611654898
Recovered private key: 15195234419506006831576867959209365250058907799872905479943949602323611654898

ECDSA बढ़िया है, लेकिन इसे सावधानी से संभालने की आवश्यकता है!

संदर्भ

[1] ब्रेंगल, एम।, और रोसो, सी। (2018, सितंबर)। बिटकॉइन उपयोगकर्ताओं के प्रमुख रिसाव की पहचान करना। हमलों, घुसपैठ और बचाव में अनुसंधान पर अंतर्राष्ट्रीय संगोष्ठी में (पीपी। 623-643)। स्प्रिंगर, चाम [ यहाँ ]।

[2] ब्रेंगल, एम।, और रोसो, सी। (2018, सितंबर)। बिटकॉइन उपयोगकर्ताओं के प्रमुख रिसाव की पहचान करना। हमलों, घुसपैठ और बचाव में अनुसंधान पर अंतर्राष्ट्रीय संगोष्ठी में (पीपी। 623-643)। स्प्रिंगर, चाम [ यहाँ ]।

[3] सुलिवन, जीए, सिप्पे, जे।, हेनिंगर, एन।, और वस्ट्रो, ई। (2022)। एक गलती के लिए खुला: क्षणिक त्रुटियों के माध्यम से {TLS} कुंजियों के निष्क्रिय समझौता पर। 31वें यूसेनिक्स सुरक्षा संगोष्ठी में (यूसेनिक्स सुरक्षा 22) (पृ. 233-250)।

[4] पोड्डेबनिआक, डी., सोमोरोव्स्की, जे., शिंजेल, एस., लोचर, एम., और रोस्लर, पी. (2018, अप्रैल)। गलती के हमलों का उपयोग करके नियतात्मक हस्ताक्षर योजनाओं पर हमला करना। 2018 में सुरक्षा और गोपनीयता पर आईईईई यूरोपीय संगोष्ठी (यूरोएस एंड पी) (पीपी। 338-352)। आईईईई।