first bitcoin collision?

[ecdsa123]

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?

[1715113467]

1715113467

[1715113467]

1715113467

[COBRAS]

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

[ecdsa123]

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]

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 ?

[ymgve2]

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]

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.

[stanner.austin]

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.

[fxsniper]

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

What collision did you mean?

[n0nce]

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.

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.

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.

[vjudeu]

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.