the same r and the same s but another xpubkey

[Sansa_Stark]

Hello



Is any way to recover k as nonce (r in transaction) when we have two or more transactions for 2 or more diff pubkeys?
with informartion : r = r and s=s (it means all s is the same , and all r (nonce) are the same)
only message hash is different and xpubkey is different.
example:

the nonce used for this example is

    
k = 86006170020059030419694064257100848158479312228443658208588163077306574850307

# transaction 1
r1 = 77043604703837860533853444406453725082195756835019831845050964553536863633142  
s1= 77156945794617562845248853605957385196967721348292410152565322709143296655454  
z1= 81550283294213774526750480549508848506784961076269394706854338639766815622493
private_key= 5263766247322699202248800353990561120926407954519219308434909686134852297665  
print(ecdsa_verify(private_key*P, z1, r1, s1))

# transaction 2
r1 = 77043604703837860533853444406453725082195756835019831845050964553536863633142  
s1= 77156945794617562845248853605957385196967721348292410152565322709143296655454  
z2= 112710939834674381891490534574286238812990049775193245234732798801085022004640
private_key2= 18053941553956308838190635484463951897269933417088761207596304974788524979748    
print(ecdsa_verify(private_key2*P, z2, r1, s1))


# transaction 3
r1 = 77043604703837860533853444406453725082195756835019831845050964553536863633142  
s1= 77156945794617562845248853605957385196967721348292410152565322709143296655454  
z3= 110548948083746279701632615734640929686598089716293774722132137960638193691299
private_key3= 22600770345200368895146862074361256781354839926598930725374757459334004043901      
print(ecdsa_verify(private_key3*P, z3, r1, s1))

accoding :

S*k - r*x = z

we have

S1*k - r1*x1 = z1

S1*k - r1*x2 = z2

S1*k - r1*x3 = z3

so :

we can detect : what is beetwen equation "linear" distance:

S1*k - r1*x1 = z1

S1*k - r1*x2 = z2
===

s1*k - s1*k - r1*x1 + r1*x2 = z1-z2        => (x2 - x1) =  (z1 - z2) *inverse_mod(r1,n) mod n

but is there any possibility to found "K" as nonce?

If for you is good to give any clue , you are so welcome.

regards Sansa


 

[garlonicon]

is there any possibility to found "K" as nonce?

No, because you can start from r=1, s=1, use R as 020000000000000000000000000000000000000000000000000000000000000001, and then choose any z-value you want. You can also choose R=G, then s will be the x-value of the base point, then you will have "d=const-(z/const)". Because it is possible to choose any public key as a signature nonce and make multiple signatures with the same r and s, reaching random z-values, it is impossible to break that, just because then breaking any key would be possible.

[stanner.austin]

@Sansa_Stark
If you have 2 different S for same private key or public key then its possible to break X,K
If you have 2 same R of different private key or public key and have 1 of private key still you can break X,K each others.
Chance of having same R is less then 0.00000001% all possible issue related to same R are eliminated many year go.

[Sansa_Stark]

@garlonicon
@stanner.austin

I think we can try to find "private key"

my IDEA:

so we have two transactions:
#transaction 1
r1=r1
s1=s1
z1=z1
xpubkey1 = xpubkey1 ( we don't know the private key)

#transaction 2
r1=r1
s1=s1
z2=z2
xpubkey2 = xpubkey2 ( we don't know the private key)

we see r1=r1 and s1=s1 , different only in z (message hash) and xpubkeys

we use equation:

S1*k1 - r1*xpubkey1 = z1
S1*k1 - r1*xpubkey2 = z2
==> x2-x1 = (z1-z2)*modinv(r1,n) % n
so we know only diff as x2_x1

then:

Code:

n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
import random
a=random.randrange(1,1000) # private_key 1
b=random.randrange(1,1000) # private_key 2

print("priv1",a)
print("priv2",b)

if b>a: # must priv1 be largest that priv 2
    a1=a
    a=b
    b=a1
    
dict_priv={}
c=(a-b)% n
 
print("diff priv1-priv2",c)

for i in range(1,1000000):
    # making dict of largest private_key multiply by i
    w=a*i
    dict_priv[w]=i
     
print("start")

for i in range(1,10000):
    a=a+c
    #print(i,"a",a)
    if a in dict_priv : 
        print("found in dict_priv!")
        #print("a",a)
        #print("i",i)
        #print("www",dict_priv[a],b*dict_priv[a])
        count=i*c
        
        li=dict_priv[a]
         
        re_count=li-1
        res=count / re_count
        print("result=",res)
        

it works for smaller numbers -> now I'm thinking for huge numbers -> any clue, or idea that it will not work?

[vjudeu]

It won't work. If you think it is possible, then try to recover the key used in 3952b35bde53eb3f4871824f0b6b8c5ad25ca84ce83f04eb1c1d69b83ad6e448 testnet transaction (here you have r=1, s=1, also known as "the smallest signature"). If you could somehow do that, then you would know the private key for 032baf163f5e27261ab3228e61fb86dc98054abd514751fce93d7444e8fbc6a293, that would mean you could take a thousand of real satoshis on the mainchain (under Segwit address).

[Sansa_Stark]

@vjudeu

I do not know that it will work for huge numbers, for small numbers as privatekeys it works. - you can see my script - run it in sagemath
For huge numbers I want to implement fractions - but it is " future song".

It is only IDEA , thats why I ask for some information that maybe someone of You have tried to do the same?

and I do not know that will be possibly or not:) That whay I'm ask for "information", any clue or whatever

Regards Sansa

[vjudeu]

I do not know that it will work for huge numbers

You have r=1, s=1. One is not a huge number.

[Sansa_Stark]

@vjudeu

I'm talking about small number as privatekey

not about r,s s is canceled.

see equaition and run my code -> then you will see about I'm talking:)

[COBRAS]

@vjudeu

I'm talking about small number as privatekey

not about r,s s is canceled.

see equaition and run my code -> then you will see about I'm talking:)

Interesting, I will try this today or tomorrow. Continue your this thread, this is interesting.

But, you using a nonce in your formulas, there you think get nonce for real word use this formulas ? Fucking nonce...

For your formulas you need NONCE FIRST , for continue use yes ? If this so, you need formula for get nonce first !!! You have this formula ?

As I remember sach formulas work then nonce < N/2

[Sansa_Stark]

NO,

first what you need :

EXAMPLE:

I Know tha public addres has output transaction and have "BTC"
I know that :
1. nonce used by him
2. his pubkey as x,y

3. Make fake transaction with :
a. nonce
b. or as nonce his x of his (x,y) of pubkey.

generate for find 2 transaction for the same s=s and r=r (where our r is : nonce or x of his pubkey)

then we calculate as in my code
we have new private key, and we can recalculate then "nonce"
and it depends if nonce is a pubkey = we have private key of pubkey
if we have privatekey as nonce => then we back to first transaction of pubkey:)

[COBRAS]

NO,

first what you need :

EXAMPLE:

I Know tha public addres has output transaction and have "BTC"
I know that :
1. nonce used by him
2. his pubkey as x,y

3. Make fake transaction with :
a. nonce
b. or as nonce his x of his (x,y) of pubkey.

generate for find 2 transaction for the same s=s and r=r (where our r is : nonce or x of his pubkey)

then we calculate as in my code
we have new private key, and we can recalculate then "nonce"
and it depends if nonce is a pubkey = we have private key of pubkey
if we have privatekey as nonce => then we back to first transaction of pubkey:)




You provide two very different examples, in 1) you need NONCE, in 2) you use nonce as a x coordinate of pubkey. Second variant -2) worked?

[COBRAS]

Nonce is fucking hard to get, as I know nonce gets from sorted R records, filter R records what hase same bit range for ex 64 but(this is for example, I don't remember exact range of R records).

...
...

...

[Sansa_Stark]

at the moment for small numbers.

But I'm trying Fraction implement, should work for huge numbers.

from my hand calculation when I'm using fraction -should work

The code which I pasted - it is JUST IDEA. and will work even for huge number -> but in this stage need a lot of hell time. Need upgrade for fraction.


PS . you do not know nonce as Integer  K -> but you know " k*G" ax (x,y)

[COBRAS]

at the moment for small numbers.

But I'm trying Fraction implement, should work for huge numbers.

from my hand calculation when I'm using fraction -should work

The code which I pasted - it is JUST IDEA. and will work even for huge number -> but in this stage need a lot of hell time. Need upgrade for fraction.


PS . you do not know nonce as Integer  K -> but you know " k*G" ax (x,y)

Provide example of nonce calculation ?

In this formula you get EXACT variable for privkey+nonce then calculate (z - z) ... I apologize
 (z1 - z2) *inverse_mod(r1,n) mod n

Then you mult random number to modinv(pubkey) you get EXACT pubkey, this is named fake base point publick key generation, used especially in generating fake www sites certificates generation..

[Sansa_Stark]

Code:

import collections
import hashlib
import random
EllipticCurve_1 = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve_1(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)


# Modular arithmetic ##########################################################

def inverse_mod(k, p):
    """Returns the inverse of k modulo p.
    This function returns the only integer x such that (x * k) % p == 1.
    k must be non-zero and p must be a prime.
    """
    if k == 0:
        raise ZeroDivisionError('division by zero')

    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p)

    # Extended Euclidean algorithm.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p


# Functions that work on curve points #########################################

def is_on_curve(point):
    """Returns True if the given point lies on the elliptic curve."""
    if point is None:
        # None represents the point at infinity.
        return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Returns -point."""
    assert is_on_curve(point)

    if point is None:
        # -0 = 0
        return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Returns the result of point1 + point2 according to the group law."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
        # 0 + point2 = point2
        return point2
    if point2 is None:
        # point1 + 0 = point1
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
        # point1 + (-point1) = 0
        return None

    if x1 == x2:
        # This is the case point1 == point2.
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # This is the case point1 != point2.
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result
 


for i in range(1,180):
    print("---------------"+str(i))
    k=2**32
    d=scalar_mult(k, curve.g)
    r_x=d[0]                           # here you can put x of pubkey or x of nonce
    print("r",r_x) 
    message=random.randrange(2**255,curve.n-1)
    print("message",message)
    b=random.randrange(1,10)
    #print("b",b)
    a= message*inverse_mod(r_x*inverse_mod(b,curve.n),curve.n)%curve.n
    #print("a",a)
    s = r_x * inverse_mod(b, curve.n) % curve.n
    print("s",s)
     
     
    d_a=scalar_mult(a, curve.g)
    d_a_n=point_neg(d_a)
    dr=point_add(d,d_a_n)
     
    print(dr)
     

[NotATether]

I actually do not think your code is scalable to extremely large numbers because the iterations will take an exponential amount of time. Not to mention that dict_priv collection will take an exponental amount of memory as welll.

I wonder how this coe would look like if xpubkey1=xpubkey2 i.e. two transactions from the same key. Maybe it would be more feasible (without the huge dict_priv dictionary and storing PKs there).

@garlonicon
@stanner.austin

I think we can try to find "private key"

my IDEA:

so we have two transactions:
#transaction 1
r1=r1
s1=s1
z1=z1
xpubkey1 = xpubkey1 ( we don't know the private key)

#transaction 2
r1=r1
s1=s1
z2=z2
xpubkey2 = xpubkey2 ( we don't know the private key)

we see r1=r1 and s1=s1 , different only in z (message hash) and xpubkeys

we use equation:

S1*k1 - r1*xpubkey1 = z1
S1*k1 - r1*xpubkey2 = z2
==> x2-x1 = (z1-z2)*modinv(r1,n) % n
so we know only diff as x2_x1

then:

Code:

n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
import random
a=random.randrange(1,1000) # private_key 1
b=random.randrange(1,1000) # private_key 2

print("priv1",a)
print("priv2",b)

if b>a: # must priv1 be largest that priv 2
    a1=a
    a=b
    b=a1
    
dict_priv={}
c=(a-b)% n
 
print("diff priv1-priv2",c)

for i in range(1,1000000):
    # making dict of largest private_key multiply by i
    w=a*i
    dict_priv[w]=i
     
print("start")

for i in range(1,10000):
    a=a+c
    #print(i,"a",a)
    if a in dict_priv : 
        print("found in dict_priv!")
        #print("a",a)
        #print("i",i)
        #print("www",dict_priv[a],b*dict_priv[a])
        count=i*c
        
        li=dict_priv[a]
         
        re_count=li-1
        res=count / re_count
        print("result=",res)
        

it works for smaller numbers -> now I'm thinking for huge numbers -> any clue, or idea that it will not work?

[Sansa_Stark]

@NotATether

You are right , it is only IDEA, it is not for huge / extremally numbers
first IDEA -> then maybe "upgrade"? who knows.

for your ask about xpubkey=xpubkey (two transaction with the same priv key) , I will try design and put here code


regards Sansa

[NotATether]

@NotATether

You are right , it is only IDEA, it is not for huge / extremally numbers
first IDEA -> then maybe "upgrade"? who knows.

for your ask about xpubkey=xpubkey (two transaction with the same priv key) , I will try design and put here code


regards Sansa

Implementing MPI support and client-server distributed networking inside the program to divide the iterations among thousands of machines would make for a good research project (something similar to Prime95 the prime number-finding program).

[COBRAS]

@NotATether

You are right , it is only IDEA, it is not for huge / extremally numbers
first IDEA -> then maybe "upgrade"? who knows.

for your ask about xpubkey=xpubkey (two transaction with the same priv key) , I will try design and put here code


regards Sansa

If possible use pubkey as a nonce this is good idea. And I think mod in can some help ... I will try asap and answer there. Lattice Attack not need a MPI and other brute force greede methods. I apologize your idea is not a brute force.

[albert0bsd]

but is there any possibility to found "K" as nonce?

NO because the equations are not solvable in that way.

This is basic algebra, think in this.

Code:

private key = r^-1(k*s -z) mod N

if you have same r for two different signatures with the same private key the equation is solvable because you have

Code:

private key = (r[sub]1[/sub]^-1)(k[sub]1[/sub]*s[sub]1[/sub] -z[sub]1[/sub]) mod N
private key = (r[sub]2[/sub]^-1)(k[sub]2[/sub]*s[sub]2[/sub] -z[sub]2[/sub]) mod N

in the equations above the original private key is the same so you can eliminate the privatekey element of the equation and found the K (nonce) value

 (r₁^-1)(k₁*s₁ -z₁) =(r₂^-1)(k₂*s₂ -z₂)

is like

Code:

a = bc
a = de

hence you can eliminate a and do bc = de most of the equations to solve the k nonce with the repeated R value come from that premise.

So how you have different Privatekeys for every transaction you can't do those eliminations.

Repeat this is basic Algebra.

[Sansa_Stark]

yes, but we are not talking about r , but about diff in 2 pubkeys with the same r:)

[garlonicon]

It does not matter, because you have the same linear relation between your private key "d" and your signature nonce "k".

Code:

s=(z+rd)/k
sk=z+rd
sk-z=rd
d=(sk-z)/r
d=(s/r)k-(z/r)
d+(z/r)=(s/r)k
Q=d*G
R=k*G
Q+(z/r)=(s/r)R

If you have "d=(s/r)k-(z/r)", then you can have the same "d", so that "d1=d2", so:

Code:

d=(s1/r1)k1-(z1/r1)
d=(s2/r2)k2-(z2/r2)

Here, "(s/r)" and "(z/r)" are known, so:

Code:

d=const1*k1-const2
d=const3*k2-const4

You can also have the same signature nonce "k" and different private keys "d", it does not matter at all:

Code:

sk=z+rd
k=(z+rd)/s
k=(z/s)+(r/s)d
k=const1+const2*d1
k=const3+const4*d2

See? You have two new variables for each equation, so you always have one more variable than equation. That means, from algebraic point of view, it has many solutions. For example, assign k=1, you will get some solutions for d1 and d2. Assign k=2, you will get completely different solutions. The same for assigning d-values above.

[albert0bsd]

yes, but we are not talking about r , but about diff in 2 pubkeys with the same r:)

I think that you have NO idea of what are you doing.

Well is not the same thing yes I agree with that, but the mathmatics behind what are you trying to do is exactly the same.

The things that I wrote still apply because you have new different variables that is why you can't mix those equations. if you do it, any results that you get will be wrong.

See? You have two new variables for each equation, so you always have one more variable than equation. That means, from algebraic point of view, it has many solutions. For example, assign k=1, you will get some solutions for d1 and d2. Assign k=2, you will get completely different solutions. The same for assigning d-values above.

Exactly