first bitcoin collision? | Bitcointalksearch.org

krashfire

jr. member

Activity: 96

Merit: 6

Life aint interesting without any cuts and bruises

Quote from: ecdsa123 on May 17, 2022, 10:14:18 AM

Code:

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [a, b])
G = E(G)

from hashlib import sha256

import struct

def bytes_to_long(s):
"""bytes_to_long(strinng) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = b('\000') * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc

def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)

def inverse(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n

def sign(m,k,d):
k = k
kG= k*G
rx,ry=kG.xy()
r = int(rx)
s = ((H(m) + d*r)*inverse(k, n)) % n
return r, s,H(m)

def calc_x(k_key,r,s,z):
x=(s*k_key - z)*inverse(r,n)%n
return x,n-x
def calc_k(private,r,s,z):
k=(r*private + z)*inverse(s,n)%n
return k,n-k

m1=b"bitcoin"
k_key=100
private=25
r,s,z = sign(m1,k_key,private)
print("1 rsz",r,s,z)
print("k_key=",calc_k(private,int(r),int(s),int(z)))
print("private=",calc_x(k_key,int(r),int(s),int(z)))

#new:
r2=105562457083132745572708143974180364633865373973280165462544121334166431725102
s2=103297023888398300822393645768628709580138523147555505327497101680694113007481
z2=48363072098642544965975966934959923879938723004602706934166367375051848994308

print("k_key=",calc_k(private,int(r2),int(s2),int(z2)))
print("private=",calc_x(k_key,int(r2),int(s2),int(z2)))

#test
print("r==r2",r==r2)

any explain what and why it is work? , and any attack?

what do you mean "what and why it works?" what do you also mean "any attack?" please be more specific. Stupid phuck.

vjudeu

hero member

Activity: 667

Merit: 1529

Just use some deterministic nonce, derived from the private key and some information around it. For example "function(privkey,message)" can be used to produce 256-bit pseudorandom value that will be strong enough for everyday use. The simplest thing would be just "k=SHA-256d(privkey||SHA-256d(message))", but I think we can do it better than that.

n0nce

hero member

Activity: 882

Merit: 5818

not your keys, not your coins!

Quote from: stanner.austin on May 18, 2022, 04:39:57 AM

Hello By using 2 same K or weak K is already known weakness of ECDSA nothing new on this. and this happened long time go. Now days K is not only secure random 256 bit but hashed to make sure get valid 256 bit random.

Exactly; it's also known as nonce reuse vulnerability.

Quote from: https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/

Therefore, not only does a signer need to keep their secret key secret, but they also must keep all of their nonces they ever generate secret.

Anyhow, for a good while now, we've finally transitioned to Schnorr's signature scheme anyway, so I'd focus on that instead.
Interestingly, it has the same flaw.

Quote from: https://en.wikipedia.org/wiki/Schnorr_signature

Just as with the closely related signature algorithms DSA, ECDSA, and ElGamal, reusing the secret nonce value k on two Schnorr signatures of different messages will allow observers to recover the private key.[2] In the case of Schnorr signatures, this simply requires subtracting s s values:

s' − s = (k' − k) − x(e' − e).

If k' = k but e' ≠ e then x can be simply isolated. In fact, even slight biases in the value k or partial leakage of k can reveal the private key, after collecting sufficiently many signatures and solving the hidden number problem.

fxsniper

member

Activity: 406

Merit: 45

Quote from: ecdsa123 on May 17, 2022, 10:14:18 AM

any explain what and why it is work? , and any attack?

What collision did you mean?

stanner.austin

member

Activity: 66

Merit: 53

Hello
By using 2 same K or weak K is already known weakness of ECDSA nothing new on this. and this happened long time go. Now days K is not only secure random 256 bit but hashed to make sure get valid 256 bit random.

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

making fake pubkey is this vay:

original Q = G * k

copy of original Q = randomK1 *(this is a fake G: (modinv(randomK1))*Q )= Q original

I think in this crypt modinv do same operation, and posible to make fake r in this way.

ymgve2

full member

Activity: 161

Merit: 230

Are you copy pasting correctly? In one of the pastes you write k_key = 85 and get r=10368879287274847063683326775245528892741533064032799844366072780982279055029, but that's for k_key = 115.

And I get verification failure with priv=25 anyway, are you sure the signatures are actually valid?

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: ecdsa123 on May 17, 2022, 11:09:31 AM

Code:

private=25
k_key = 85
r=10368879287274847063683326775245528892741533064032799844366072780982279055029
s=44682668155818600992173137533155827851900045079586924109984745069549131526906
z=65042133943224045035503970676469909507838576791821421761396617141574358581175
print("k_key=",calc_k(private,int(r),int(s),int(z)))
print("private=",calc_x(k_key,int(r),int(s),int(z)))

r2 = 9882445446243370679019973441389370914782298169440461435976781902375353582684
s2 = 2100982064131629085884104838554481736960146626300897659396216122167769160017
z2 = 47314428532420400748220560251084582624892573278639669531863985966394700528682
print("k_key=",calc_k(private,int(r2),int(s2),int(z2)))
print("private=",calc_x(k_key,int(r2),int(s2),int(z2)))

the same r!=r2 but k is still the same.

any explanation?

Code:

k_key= (85, 115792089237316195423570985008687907852837564279074904382605163141518161494252)
private= (25, 115792089237316195423570985008687907852837564279074904382605163141518161494312)
k_key= (85, 115792089237316195423570985008687907852837564279074904382605163141518161494252)
private= (25, 115792089237316195423570985008687907852837564279074904382605163141518161494312)

because this i think :

private=25

kan you make same r with different private ?

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Code:

private=25
k_key = 85
r=10368879287274847063683326775245528892741533064032799844366072780982279055029
s=44682668155818600992173137533155827851900045079586924109984745069549131526906
z=65042133943224045035503970676469909507838576791821421761396617141574358581175
print("k_key=",calc_k(private,int(r),int(s),int(z)))
print("private=",calc_x(k_key,int(r),int(s),int(z)))

r2 = 9882445446243370679019973441389370914782298169440461435976781902375353582684
s2 = 2100982064131629085884104838554481736960146626300897659396216122167769160017
z2 = 47314428532420400748220560251084582624892573278639669531863985966394700528682
print("k_key=",calc_k(private,int(r2),int(s2),int(z2)))
print("private=",calc_x(k_key,int(r2),int(s2),int(z2)))

the same r!=r2 but k is still the same.

any explanation?

Code:

k_key= (85, 115792089237316195423570985008687907852837564279074904382605163141518161494252)
private= (25, 115792089237316195423570985008687907852837564279074904382605163141518161494312)
k_key= (85, 115792089237316195423570985008687907852837564279074904382605163141518161494252)
private= (25, 115792089237316195423570985008687907852837564279074904382605163141518161494312)

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Try another rsz, after this talk aboutit working of this code...

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Code:

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [a, b])
G = E(G)

from hashlib import sha256

import struct

def bytes_to_long(s):
"""bytes_to_long(strinng) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = b('\000') * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc

def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)

def inverse(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n

def sign(m,k,d):
k = k
kG= k*G
rx,ry=kG.xy()
r = int(rx)
s = ((H(m) + d*r)*inverse(k, n)) % n
return r, s,H(m)

def calc_x(k_key,r,s,z):
x=(s*k_key - z)*inverse(r,n)%n
return x,n-x
def calc_k(private,r,s,z):
k=(r*private + z)*inverse(s,n)%n
return k,n-k

m1=b"bitcoin"
k_key=100
private=25
r,s,z = sign(m1,k_key,private)
print("1 rsz",r,s,z)
print("k_key=",calc_k(private,int(r),int(s),int(z)))
print("private=",calc_x(k_key,int(r),int(s),int(z)))

#new:
r2=105562457083132745572708143974180364633865373973280165462544121334166431725102
s2=103297023888398300822393645768628709580138523147555505327497101680694113007481
z2=48363072098642544965975966934959923879938723004602706934166367375051848994308

print("k_key=",calc_k(private,int(r2),int(s2),int(z2)))
print("private=",calc_x(k_key,int(r2),int(s2),int(z2)))

#test
print("r==r2",r==r2)

any explain what and why it is work? , and any attack?

Topic: first bitcoin collision? (Read 330 times)