ECDSA İmzalarının Dört Temel Kuralı…
1999'da Don Johnson Alfred Menezes (1999), "Eliptik Eğri Dijital İmza Algoritması (ECDSA)" üzerine klasik bir makale yayınladı:
Temel olarak, David W. Kravitz tarafından oluşturulan DSA'yı (Dijital İmza Algoritması) aldı ve onu eliptik bir eğri temsiline dönüştürdü. Ve böylece, ayrı günlükler büyüdükçe, eliptik eğri yöntemleri çok daha verimli hale geldi.
Ardından 2007 yılında Satoshi Nakamoto, Bitcoin uygulaması için kod yazmaya başladı ve ana imza yöntemi olarak ECDSA'yı seçti ve secp256k1 eğrisini kullandı. Ethereum için de doğal yaklaşım ECDSA imza yöntemiydi. Ancak, ECDSA imzaları doğru şekilde uygulanmadığı takdirde saldırıya eğilimlidir, bu nedenle dört temel kurala bir göz atalım.
ECDSA'nın gerçek büyüsü, genel anahtarı saklamak zorunda olmayıp, özel anahtarın hashlenmiş bir versiyonundan imzanın kontrol edilebileceği yerdeydi. Bu şekilde, blockchain'in onu kullananların ortak anahtarlarını saklamasına gerek kalmadı ve gerçekten merkezi olmayan bir bilgi altyapısı oluşturduğumuz ilk zamanlardan biriydi.
ECDSA imzalarının nasıl çalıştığını anlamak istiyorsanız burayı deneyin .
Asla Sızdırma
Örnek: ECDSA'yı nonce sızıntısından (SECP256k1) kırın . ECDSA ile nonce . Bu, ECDSA'nın özel anahtarın SECP256k1 için nonce değerinde bir sızıntı ile nasıl kurtarılabileceğini özetlemektedir.
ECDSA imzasıyla, bir mesajı özel anahtarla ( priv ) imzalarız ve imzayı genel anahtarla ( pub ) kanıtlarız. Daha sonra imzayı rasgele hale getirmek için rasgele bir değer (a nonce) kullanılır. Her imzaladığımızda, rastgele bir nonce değeri yaratırız ve bu, farklı (ama doğrulanabilir) bir imza üretir. Genel olarak imzalayan, nonce değerini değil, yalnızca imzanın unsurlarını ve bunların ortak anahtarını ifşa etmelidir. İmzalayan yanlışlıkla yalnızca bir nonce değeri gösterirse, davetsiz misafir özel anahtarı keşfedebilir. Bu durumda nonce değerini ortaya çıkaracağız ve özel anahtarı belirleyeceğiz ve secp256k1 eğrisini (Bitcoin ile kullanıldığı gibi) kullanacağız.
ECDSA'da Bob, rastgele bir özel anahtar ( priv ) ve ardından şunlardan bir genel anahtar oluşturur:
bar = özel × G
Daha sonra, M'nin bir mesajına imza oluşturmak için rastgele bir sayı ( k ) yaratır ve şu imzayı üretir:
r = k ⋅ G
s = k ^{−1}( H ( M )+ r ⋅ özel )
İmza o zaman ( r , s ) olur ve burada r, kG noktasının x koordinatıdır . H ( M ), mesajın ( M ) SHA-256 karmasıdır ve bir tamsayı değerine dönüştürülür. İmzalardan herhangi biri için k değeri ortaya çıkarsa, izinsiz giren bir kişi aşağıdakileri kullanarak özel anahtarı belirleyebilir:
özel = r ^{−1}×(( k ⋅ s )− H ( M ))
Bu işe yarar çünkü:
s ⋅ k = H ( M )+ r ⋅ özel
ve bu yüzden:
r ⋅ özel = s ⋅ k - H ( M )
ve özel için :
özel = r -1( s ⋅ k - H ( M ))
Nonce ( k ) [ burada ] ortaya çıkarsa, özel anahtarı keşfeden bazı kodlar :
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
Örnek: ECDSA'yı zayıf nonces (sepc256k1) ile kırın . ECDSA: Aynı nonce'dan özel anahtarın açığa çıkarılması . Bu, ECDSA'nın özel anahtarın zayıf nonce değerleri ile nasıl kurtarılabileceğini özetlemektedir.
ECDSA imzasıyla, bir mesajı özel anahtarla ( priv ) imzalarız ve imzayı genel anahtarla ( pub ) kanıtlarız. Daha sonra imzayı rasgele hale getirmek için rasgele bir değer (a nonce) kullanılır. Her imzaladığımızda, rastgele bir nonce değeri yaratırız ve bu, farklı (ama doğrulanabilir) bir imza üretir. Özel anahtar, Alice iki farklı mesajı aynı nonce [1] ile imzalarsa keşfedilebilir.
ECDSA'da Bob, rastgele bir özel anahtar ( priv ) ve ardından şunlardan bir genel anahtar oluşturur:
bar = özel × G
Daha sonra, M'nin bir mesajına imza oluşturmak için rastgele bir sayı ( k ) yaratır ve şu imzayı üretir:
r = k ⋅ G
s = k ^{−1}( H ( M )+ r ⋅ özel )
İmza o zaman ( r , s ) olur ve burada r, kG noktasının x koordinatıdır . H ( M ), mesajın ( M ) SHA-256 karmasıdır ve bir tamsayı değerine dönüştürülür.
Şimdi iki mesajımız ( m 1 ve m 2) olduğunu ve aşağıdakilerin karma değerlerine sahip olduğumuzu varsayalım :
h 1= H ( m 1)
h 2= H ( m 2)
Şimdi, Alice'in mesajları aynı özel anahtar ( priv) ve aynı nonce ( k) ile imzaladığını varsayalım , daha sonra özel anahtarı şu şekilde kurtarabiliriz:
Nonce'ı şu şekilde de kurtarabiliriz:
İşte özel anahtarın ve aynı nonce değerini [ burada ] kullanırsak nonce'nin ( k ) keşfini yapan bazı kodlar :
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
Örnek: Özel anahtarın iki anahtardan ve paylaşılan olmayanlardan (SECP256k1) açığa çıkarılması . ECDSA: Özel anahtarın iki anahtardan ve paylaşılan olmayanlardan (SECP256k1) açığa çıkarılması . Bu, ECDSA'nın dört imzalı mesajdan iki özel anahtarı nasıl açığa çıkarabileceğini özetlemektedir.
ECDSA imzasıyla, bir mesajı özel anahtarla ( priv ) imzalarız ve imzayı genel anahtarla ( pub ) kanıtlarız. Daha sonra imzayı rasgele hale getirmek için rasgele bir değer (a nonce) kullanılır. Her imzaladığımızda, rastgele bir nonce değeri yaratırız ve bu, farklı (ama doğrulanabilir) bir imza üretir. Ancak özel anahtar, Alice dört mesajı iki anahtar ve iki sıfır [2] ile imzalarsa keşfedilebilir. Bu durumda, 1. mesajı birinci özel anahtarla ( x 1), 2. mesajı ikinci bir özel anahtarla ( x 2), 3. mesajı birinci özel anahtarla ( x 1) ve 4. mesajı şu şekilde imzalar: ikinci özel anahtar ( x 2) Aynı olmayan ( k1) 1 ve 2 numaralı mesajların imzalanmasında kullanılır ve 3 ve 4 numaralı mesajların imzalanmasında başka bir nonce ( k 2) kullanılır.
ECDSA'da Bob, rastgele bir özel anahtar ( priv ) ve ardından şunlardan bir genel anahtar oluşturur:
bar = özel × G
Daha sonra, M'nin bir mesajına imza oluşturmak için rastgele bir sayı ( k ) yaratır ve şu imzayı üretir:
r = k ⋅ G
s = k −1( H ( M )+ r ⋅ özel )
İmza o zaman ( r , s ) olur ve burada r, kG noktasının x koordinatıdır . H ( M ), mesajın ( M ) SHA-256 karmasıdır ve bir tamsayı değerine dönüştürülür.
Bu durumda, Alice'in iki anahtar çifti ve iki özel anahtarı olacaktır ( x 1 ve x 2). Mesaj 1'i ( m 1) birinci özel anahtarla ( x 1 ), mesaj 2'yi ( m 2 ) ikinci özel anahtarla ( x 2 ), mesaj 3'ü ( m 3) birinci özel anahtarla ( x ) imzalayacaktır. 1) ve mesaj 4'ü ( m 4) ikinci özel anahtarla ( x 2) imzalayın. Aynı nonce ( k 1) 1. ve 2. mesajların imzalanmasında kullanılır ve başka bir nonce ( k 2) 3. ve 4. mesajların imzalanmasında kullanılır. Şimdi diyelim ki dört mesajımız var ( m 1 .. m4) ve hash değerlerine sahiptir:
h 1= H ( m 1)
h 2= H ( m 2)
h 3= H ( m 3)
h 4= H ( m 4)
Mesajların imzaları ( s 1, r 1), ( s 2, r 1), ( s 3, r 2) ve ( s 4, r 2) olacaktır:
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 )
Gauss eleme yöntemini kullanarak özel anahtarları şu şekilde de kurtarabiliriz:
Ve:
İşte [ burada ] özel anahtarları keşfeden bazı kodlar:
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
Örnek: Hata Saldırısı . ECDSA: Hata Saldırısı . ECDSA'daki hata saldırısında sadece iki imzaya ihtiyacımız var . Biri hatasız ( r , s ) üretilir ve diğeri hatalıdır ( rf , sf ). Bunlardan özel anahtarı oluşturabiliriz.
ECDSA'daki hata saldırısında sadece iki imzaya ihtiyacımız var . Biri hatasız ( r , s ) üretilir ve diğeri hatalıdır ( rf , sf ). Bunlardan özel anahtarı [3,4] üretebiliriz.
ECDSA'da Bob, rastgele bir özel anahtar ( priv ) ve ardından şunlardan bir genel anahtar oluşturur:
bar = özel × G
Daha sonra, M'nin bir mesajına imza oluşturmak için rastgele bir sayı ( k ) yaratır ve şu imzayı üretir:
r = k ⋅ G
s = k ^{−1}( h + r ⋅ d )
ve burada d özel anahtardır ve h = H ( M ) İmza o zaman ( r , s ) ve burada r , kG noktasının x koordinatıdır . h, mesajın ( M ) SHA-256 karmasıdır ve bir tamsayı değerine dönüştürülür.
Şimdi diyelim ki iki imzamız var. Birinde hata var, diğeri geçerli. O zaman geçerli olan için ( r , s ) ve hata için ( rf , sf ) var . Bunlar:
sf = k^{ −1}.( h + d . rf )(mod p )
s = k ^{−1}.( h + d . r )(mod p )
ve nerede h
mesajın hash'idir. Şimdi iki s'yi çıkarırsak
aldığımız değerler:
s − sf = k ^{−1}.( h + d . r )− k^{ −1}.( h + d . rf )
Daha sonra:
Bu daha sonra şu şekilde değiştirilebilir:
s = k^{ −1}( h + r . d )(mod p )
Bu verir:
Daha sonra, özel anahtarı ( d ) şuradan türetmek için yeniden düzenleyebiliriz :
İşte bunu [ burada ] uygulamak için kod :
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 harika, ancak dikkatle ele alınması gerekiyor!
Referanslar
[1] Brengel, M., & Rossow, C. (2018, Eylül). Bitcoin kullanıcılarının anahtar sızıntısını belirleme. Uluslararası Saldırılar, İzinsiz Girişler ve Savunmalar Üzerine Araştırmalar Sempozyumunda (s. 623–643). Springer, Çam [ burada ].
[2] Brengel, M., & Rossow, C. (2018, Eylül). Bitcoin kullanıcılarının anahtar sızıntısını belirleme. Uluslararası Saldırılar, İzinsiz Girişler ve Savunmalar Üzerine Araştırmalar Sempozyumunda (s. 623–643). Springer, Çam [ burada ].
[3] Sullivan, GA, Sippe, J., Heninger, N., & Wustrow, E. (2022). Bir hataya açık: {TLS} anahtarlarının geçici hatalar yoluyla pasif olarak ele geçirilmesi üzerine. 31. USENIX Güvenlik Sempozyumunda (USENIX Security 22) (s. 233–250).
[4] Poddebniak, D., Somorovsky, J., Schinzel, S., Lochter, M., & Rösler, P. (2018, Nisan). Arıza saldırılarını kullanarak deterministik imza şemalarına saldırmak. 2018'de IEEE Avrupa Güvenlik ve Gizlilik Sempozyumu (EuroS&P) (s. 338–352). IEEE.
![Bağlantılı Liste Nedir? [Bölüm 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
