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.