ECDSA 서명의 네 가지 기본 규칙…
1999년 Don Johnson Alfred Menezes(1999)는 "The Elliptic Curve Digital Signature Algorithm(ECDSA)"에 대한 고전적인 논문을 발표했습니다.
기본적으로 David W. Kravitz가 만든 DSA(Digital Signature Algorithm)를 가져와 타원 곡선 표현으로 변환했습니다. 따라서 불연속 로그가 커짐에 따라 타원 곡선 방법이 훨씬 더 효율적이었습니다.
그 후 2007년에 Satoshi Nakamoto는 비트코인 구현을 위한 코드 작성을 시작했고 ECDSA를 주요 서명 방법으로 선택하고 secp256k1 곡선을 사용했습니다. 이더리움의 경우에도 ECDSA 서명 방식을 자연스럽게 사용했습니다. 그러나 ECDSA 서명은 올바르게 구현되지 않으면 공격당하는 경향이 있으므로 네 가지 기본 규칙을 살펴보겠습니다.
ECDSA의 진정한 마법은 공개 키를 저장할 필요가 없지만 개인 키의 해시된 버전에서 서명을 확인할 수 있다는 것입니다. 이렇게 블록체인은 그것을 사용하는 사람들의 공개 키를 저장할 필요가 없었고, 진정한 탈중앙화 정보 인프라를 만든 최초의 사례 중 하나였습니다.
ECDSA 서명이 작동하는 방식을 이해하려면 여기에서 시도하십시오 .
Nonce를 유출하지 마십시오
예: nonce(SECP256k1)의 누출로 인한 ECDSA 크랙 . nonce가 있는 ECDSA . 이것은 SECP256k1에 대한 nonce 값의 유출로 개인 키를 복구할 수 있는 방법을 ECDSA에 대해 설명합니다.
ECDSA 서명을 사용하여 개인 키( priv ) 로 메시지에 서명 하고 공개 키( pub )로 서명을 증명합니다. 그런 다음 무작위 값(nonce)을 사용하여 서명을 무작위화합니다. 서명할 때마다 임의의 임시 값을 생성하고 다른(그러나 검증 가능한) 서명을 생성합니다. 전반적으로 서명자는 nonce 값이 아닌 서명의 요소와 공개 키만 공개하면 됩니다. 서명자가 실수로 nonce 값 하나만 공개하면 침입자가 개인 키를 알아낼 수 있습니다. 이 경우 nonce 값을 공개하고 개인 키를 결정하고 secp256k1 곡선(비트코인에서 사용됨)을 사용합니다.
ECDSA에서 Bob은 임의의 개인 키( priv )를 생성한 다음 다음에서 공개 키를 생성합니다.
술집 = 개인 × G
다음으로, M 의 메시지에 대한 서명을 생성하기 위해 그는 난수( k )를 생성하고 다음과 같은 서명을 생성합니다.
r = 케이 ⋅ 지
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 ⋅ priv
그래서:
r ⋅ priv = s ⋅ k − H ( M )
개인용 : _
priv = r -1( s · k - H ( M ))
다음은 nonce( k )가 [ here ] 공개된 경우 개인 키를 검색하는 코드입니다 .
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: 동일한 nonce에서 개인 키를 공개합니다 . 이는 ECDSA에서 약한 난스 값으로 개인 키를 복구하는 방법을 설명합니다.
ECDSA 서명을 사용하여 개인 키( priv ) 로 메시지에 서명 하고 공개 키( pub )로 서명을 증명합니다. 그런 다음 무작위 값(nonce)을 사용하여 서명을 무작위화합니다. 서명할 때마다 임의의 임시 값을 생성하고 다른(그러나 검증 가능한) 서명을 생성합니다. 그러나 개인 키는 Alice가 동일한 nonce[1]로 두 개의 다른 메시지에 서명하는 경우 발견될 수 있습니다.
ECDSA에서 Bob은 임의의 개인 키( priv )를 생성한 다음 다음에서 공개 키를 생성합니다.
술집 = 개인 × G
다음으로, M 의 메시지에 대한 서명을 생성하기 위해 그는 난수( k )를 생성하고 다음과 같은 서명을 생성합니다.
r = 케이 ⋅ 지
s = k ^{−1}( H ( M )+ r ⋅ priv )
그러면 서명은 ( r , s )이고 여기서 r은 점 kG 의 x 좌표입니다 . H ( M )는 메시지( M )의 SHA-256 해시이며 정수 값으로 변환됩니다.
이제 두 개의 메시지( m 1 및 m 2)가 있고 다음과 같은 해시가 있다고 가정해 보겠습니다.
시간 1= H ( m 1)
시간 2= H ( m 2)
이제 Alice가 동일한 개인 키( priv) 및 동일한 nonce( k) 로 메시지에 서명한다고 가정하면 다음을 사용하여 개인 키를 복구할 수 있습니다.
다음을 사용하여 nonce를 복구할 수도 있습니다.
다음은 동일한 논스 값을 사용하는 경우 프라이빗 키와 논스( 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: 두 개의 키와 공유 nonce에서 개인 키 공개(SECP256k1) . 이것은 4개의 서명된 메시지에서 2개의 개인 키를 공개하는 방법을 ECDSA에 대해 설명합니다.
ECDSA 서명을 사용하여 개인 키( priv ) 로 메시지에 서명 하고 공개 키( pub )로 서명을 증명합니다. 그런 다음 무작위 값(nonce)을 사용하여 서명을 무작위화합니다. 서명할 때마다 임의의 임시 값을 생성하고 다른(그러나 검증 가능한) 서명을 생성합니다. 그러나 Alice가 2개의 키와 2개의 nonce[2]로 4개의 메시지에 서명하면 개인 키를 찾을 수 있습니다. 이 경우 첫 번째 개인 키( x 1)로 메시지 1에 서명하고 두 번째 개인 키( x 2)로 메시지 2에 서명하고 첫 번째 개인 키( x 1)로 메시지 3에 서명하고 두 번째 개인 키( x 2) 동일한 nonce( k1)은 메시지 1과 2의 서명에 사용되고 또 다른 nonce( k 2)는 메시지 3과 4의 서명에 사용됩니다.
ECDSA에서 Bob은 임의의 개인 키( priv )를 생성한 다음 다음에서 공개 키를 생성합니다.
술집 = 개인 × G
다음으로, M 의 메시지에 대한 서명을 생성하기 위해 그는 난수( k )를 생성하고 다음과 같은 서명을 생성합니다.
r = 케이 ⋅ 지
s = k −1( H ( M )+ r ⋅ priv )
그러면 서명은 ( r , s )이고 여기서 r은 점 kG 의 x 좌표입니다 . H ( M )는 메시지( M )의 SHA-256 해시이며 정수 값으로 변환됩니다.
이 경우 Alice는 두 개의 키 쌍과 두 개의 개인 키( x 1 및 x 2)를 갖게 됩니다. 그녀는 첫 번째 개인 키( x 1)로 메시지 1( m 1)에 서명하고 두 번째 개인 키( x 2)로 메시지 2( m 2)에 서명 하고 첫 번째 개인 키( x )로 메시지 3( m 3)에 서명합니다. 1) 두 번째 개인 키( x 2)로 메시지 4( m 4)에 서명합니다 . 동일한 논스( k 1)가 메시지 1과 2의 서명에 사용되고 다른 논스( k 2)가 메시지 3과 4의 서명에 사용됩니다. 이제 4개의 메시지( m 1 .. m4) 다음과 같은 해시가 있습니다.
시간 1= H ( m 1)
시간 2= H ( m 2)
시간 3= H ( m3 )
시간 4= H ( m4 )
그러면 메시지의 서명은 ( 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 )
가우시안 소거법을 사용하면 다음을 통해 개인 키를 복구할 수도 있습니다.
그리고:
다음은 개인 키를 검색하는 코드입니다. [ here ]:
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]를 생성할 수 있습니다.
ECDSA에서 Bob은 임의의 개인 키( priv )를 생성한 다음 다음에서 공개 키를 생성합니다.
술집 = 개인 × G
다음으로, M 의 메시지에 대한 서명을 생성하기 위해 그는 난수( k )를 생성하고 다음과 같은 서명을 생성합니다.
r = 케이 ⋅ 지
s = k ^{−1}( h + r ⋅ d )
여기서 d 는 개인 키이고 h = H ( M ) 서명은 ( r , s )이고 여기서 r 은 점 kG 의 x 좌표입니다 . h 는 메시지( M )의 SHA-256 해시이며 정수 값으로 변환됩니다.
이제 두 개의 서명이 있다고 가정해 보겠습니다. 하나는 결함이 있고 다른 하나는 유효합니다. 그런 다음 유효한 항목에 대한 ( r , s )와 오류에 대한 ( rf , sf ) 가 있습니다 . 다음과 같습니다.
sf = k^{ −1}.( h + d . rf )(mod p )
s = k ^{−1}.( h + d . r )(mod p )
그리고 여기서 h
메시지의 해시입니다. 이제 두 s를 빼면
우리가 얻는 값:
s − sf = k ^{−1}.( h + d . r )− k^{ −1}.( h + d . rf )
그 다음에:
그런 다음 다음으로 대체할 수 있습니다.
s = k^{ −1}( h + r . d )(mod p )
이는 다음을 제공합니다.
그런 다음 이를 재배열하여 다음에서 개인 키( d )를 파생할 수 있습니다.
[ here ] 를 구현하는 코드는 다음과 같습니다 .
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] Brengel, M., & Rossow, C. (2018년 9월). 비트코인 사용자의 키 유출 식별. 공격, 침입 및 방어 연구에 관한 국제 심포지엄에서(pp. 623–643). Springer, Cham [ 여기 ].
[2] Brengel, M., & Rossow, C. (2018년 9월). 비트코인 사용자의 키 유출 식별. 공격, 침입 및 방어 연구에 관한 국제 심포지엄에서(pp. 623–643). Springer, Cham [ 여기 ].
[3] Sullivan, GA, Sippe, J., Heninger, N., & Wustrow, E. (2022). 결함에 대한 개방: 일시적인 오류를 통한 {TLS} 키의 수동적 손상에서. 31회 USENIX 보안 심포지엄(USENIX 보안 22)(pp. 233–250).
[4] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M., & Rösler, P. (2018년 4월). 결함 공격을 사용하여 결정적 서명 체계를 공격합니다. 2018 IEEE 유럽 심포지엄 보안 및 개인 정보 보호(EuroS&P)(pp. 338–352). IEEE.
![연결된 목록이란 무엇입니까? [1 부]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
