ECDSA 署名の 4 つの基本ルール …
1999 年、Don Johnson Alfred Menezes (1999) は、「楕円曲線デジタル署名アルゴリズム (ECDSA)」に関する古典的な論文を発表しました。
基本的には、David W. Kravitz によって作成された DSA (デジタル署名アルゴリズム) を採用し、それを楕円曲線表現に変換しました。そして、離散ログが大きくなるにつれて、楕円曲線手法の効率が大幅に向上しました。
その後、2007 年に、サトシ ナカモトはビットコイン実装用のコードを書き始め、主な署名方法として ECDSA を選択し、secp256k1 曲線を使用しました。イーサリアムの場合も、ECDSA 署名方式を使用するのが自然なアプローチでした。ただし、ECDSA 署名は正しく実装されていないと攻撃を受ける傾向があるため、4 つの基本ルールを見てみましょう。
ECDSA の真の魅力は、公開キーを保存する必要がなく、秘密キーのハッシュ バージョンから署名をチェックできることです。このようにして、ブロックチェーンはそれを使用する人の公開鍵を保存する必要がなく、これは私たちが初めて真に分散型の情報インフラストラクチャを作成したものの 1 つでした。
ECDSA 署名がどのように機能するかを理解したい場合は、ここを試してください。
ナンスを決して漏らさない
例: nonce (SECP256k1) のリークから ECDSA をクラックします。nonce を使用した ECDSA。これは、ECDSA が SECP256k1 の nonce 値のリークから秘密キーを回復する方法の概要を示しています。
ECDSA 署名では、秘密鍵 ( priv )でメッセージに署名し、公開鍵 ( pub ) で署名を証明します。次に、ランダム値 (ノンス) を使用して署名がランダム化されます。署名するたびに、ランダムな nonce 値が作成され、異なる (ただし検証可能な) 署名が生成されます。全体として、署名者は署名の要素とその公開鍵を公開するだけで済み、ノンス値は公開する必要はありません。署名者が誤って nonce 値を 1 つだけ公開した場合、侵入者が秘密鍵を発見する可能性があります。この場合、ノンス値を明らかにし、秘密鍵を決定し、secp256k1 曲線 (ビットコインで使用されているもの) を使用します。
ECDSA では、Bob はランダムな秘密鍵 ( priv ) を作成し、次に以下から公開鍵を作成します。
パブ=プライベート× G
次に、 Mのメッセージの署名を作成するために、乱数 ( k ) を作成し、次の署名を生成します。
r = k ⋅ G
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の場合:
priv = r −1( s ⋅ k − H ( M ))
これは、ノンス ( k ) が明らかになった場合に秘密キーの検出を行うコードです[ここ]:
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 が弱い nonce 値を使用して秘密キーを復元する方法の概要を示しています。
ECDSA 署名では、秘密鍵 ( priv )でメッセージに署名し、公開鍵 ( pub ) で署名を証明します。次に、ランダム値 (ノンス) を使用して署名がランダム化されます。署名するたびに、ランダムな nonce 値が作成され、異なる (ただし検証可能な) 署名が生成されます。ただし、アリスが同じノンスで 2 つの異なるメッセージに署名すると、秘密鍵を発見できます [1]。
ECDSA では、Bob はランダムな秘密鍵 ( priv ) を作成し、次に以下から公開鍵を作成します。
パブ=プライベート× G
次に、 Mのメッセージの署名を作成するために、乱数 ( k ) を作成し、次の署名を生成します。
r = k ⋅ G
s = k ^{−1}( H ( M )+ r ⋅ priv )
この場合、署名は ( r , s ) であり、rは点kGの x 座標です。H ( M ) はメッセージ ( M ) の SHA-256 ハッシュであり、整数値に変換されます。
ここで、2 つのメッセージ ( m 1 とm 2)があり、次のハッシュがあるとします。
h1 = H ( m1 )
h2 = H ( m2 )
ここで、Alice が同じ秘密鍵 ( priv)と同じ nonce ( k)を使用してメッセージに署名したとします。その後、次のコマンドで秘密鍵を回復できます。
次のように nonce を復元することもできます。
以下は、秘密キーと、同じ nonce 値を使用する場合の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
例: 2 つのキーと共有ナンスから秘密キーを明らかにする (SECP256k1)。ECDSA: 2 つのキーと共有ナンスから秘密キーを明らかにします (SECP256k1)。これは、4 つの署名付きメッセージから 2 つの秘密鍵を明らかにする方法の ECDSA の概要を示しています。
ECDSA 署名では、秘密鍵 ( priv )でメッセージに署名し、公開鍵 ( pub ) で署名を証明します。次に、ランダム値 (ノンス) を使用して署名がランダム化されます。署名するたびに、ランダムな nonce 値が作成され、異なる (ただし検証可能な) 署名が生成されます。ただし、アリスが 2 つの鍵と 2 つのノンスを使用して 4 つのメッセージに署名すると、秘密鍵を発見できます [2]。この場合、彼女は最初の秘密鍵 ( x 1) でメッセージ 1 に署名し、2 番目の秘密鍵 ( x 2) でメッセージ 2 に署名し、最初の秘密鍵 ( x 1) でメッセージ 3 に署名し、 2 番目の秘密鍵 ( x 2) 同じノンス ( k1) はメッセージ 1 と 2 の署名に使用され、別のノンス ( k 2) はメッセージ 3 と 4 の署名に使用されます。
ECDSA では、Bob はランダムな秘密鍵 ( priv ) を作成し、次に以下から公開鍵を作成します。
パブ=プライベート× G
次に、 Mのメッセージの署名を作成するために、乱数 ( k ) を作成し、次の署名を生成します。
r = k ⋅ G
s = k −1( H ( M )+ r ⋅ priv )
この場合、署名は ( r , s ) であり、rは点kGの x 座標です。H ( M ) はメッセージ ( M ) の SHA-256 ハッシュであり、整数値に変換されます。
この場合、Alice は 2 つの鍵ペアと 2 つの秘密鍵 ( x 1 とx 2)を持ちます。彼女は最初の秘密鍵 ( x 1) でメッセージ 1 ( m 1)に署名し、 2 番目の秘密鍵 ( x 2) でメッセージ 2 ( m 2) に署名し、最初の秘密鍵 ( x ) でメッセージ 3 ( m 3) に署名します。 1)、 2 番目の秘密鍵 ( x 2) を使用してメッセージ 4 ( m 4) に署名します。同じノンス ( k 1) がメッセージ 1 と 2 の署名に使用され、別のノンス ( k 2) がメッセージ 3 と 4 の署名に使用されます。 ここで、4 つのメッセージ ( m 1 .. mがあるとします)4) 次のハッシュがあります:
h1 = H ( m1 )
h2 = H ( m2 )
h3 = H ( m3 )
h4 = 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 )
ガウス消去法を使用すると、次のように秘密鍵を回復することもできます。
と：
秘密鍵を検出するコードは次のとおりです [ここ]:
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 の障害攻撃では、2 つの署名だけが必要です。1 つは障害なしで生成され ( r、s )、もう 1 つは障害あり ( rf、sf ) です。これらから秘密鍵を生成できます。
ECDSA の障害攻撃では、2 つの署名だけが必要です。1 つは障害なしで生成され ( r、s )、もう 1 つは障害あり ( rf、sf ) です。これらから秘密鍵を生成できます [3,4]。
ECDSA では、Bob はランダムな秘密鍵 ( priv ) を作成し、次に以下から公開鍵を作成します。
パブ=プライベート× G
次に、 Mのメッセージの署名を作成するために、乱数 ( k ) を作成し、次の署名を生成します。
r = k ⋅ G
s = k ^{−1}( h + r ⋅ d )
ここで、dは秘密鍵であり、h = H ( M ) です。 署名は ( r , s ) であり、rは点kGの x 座標です。hはメッセージ ( M ) の SHA-256 ハッシュであり、整数値に変換されます。
さて、2 つの署名があるとします。1 つは障害があり、もう 1 つは有効です。次に、有効なものについては ( r , s )、障害については( rf , sf ) が得られます。これらは次のとおりです。
sf = k^{ −1}.( h + d . rf )(mod p )
s = k ^{−1}.( h + d . r )(mod p )
そしてどこでh
メッセージのハッシュです。ここで 2 つのsを引くと、
得られる値:
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] Brengel, M.、Rossow, C. (2018 年 9 月)。ビットコインユーザーの鍵漏洩を特定。攻撃、侵入、防御の研究に関する国際シンポジウムにて (pp. 623–643)。スプリンガー、チャム[ここ]。
[2] Brengel, M.、Rossow, C. (2018 年 9 月)。ビットコインユーザーの鍵漏洩を特定。攻撃、侵入、防御の研究に関する国際シンポジウムにて (pp. 623–643)。スプリンガー、チャム[ここ]。
[3] ジョージア州サリバン、J. シッペ、N. ヘニンガー、E. ヴストロー (2022)。障害が発生する可能性があります: 一時的なエラーによる {TLS} キーの受動的侵害について。第31回USENIXセキュリティシンポジウム（USENIXセキュリティ22）にて（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)
