Title: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 02, 2022, 03:08:00 PM 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 Title: Re: the same r and the same s but another xpubkey Post by: garlonicon on March 02, 2022, 03:49:23 PM Quote 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.Title: Re: the same r and the same s but another xpubkey Post by: stanner.austin on March 03, 2022, 08:22:30 AM @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. Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 08:21:37 AM @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 it works for smaller numbers -> now I'm thinking for huge numbers -> any clue, or idea that it will not work? Title: Re: the same r and the same s but another xpubkey Post by: vjudeu on March 04, 2022, 08:36:07 AM 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).
Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 08:43:24 AM @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 Title: Re: the same r and the same s but another xpubkey Post by: vjudeu on March 04, 2022, 08:53:34 AM Quote I do not know that it will work for huge numbers You have r=1, s=1. One is not a huge number.Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 09:28:02 AM @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:) Title: Re: the same r and the same s but another xpubkey Post by: COBRAS on March 04, 2022, 01:46:05 PM @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 Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 01:58:31 PM 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:) Title: Re: the same r and the same s but another xpubkey Post by: COBRAS on March 04, 2022, 02:02:18 PM 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? Title: Re: the same r and the same s but another xpubkey Post by: COBRAS on March 04, 2022, 02:04:54 PM 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).
... ... ... Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 02:07:14 PM 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) Title: Re: the same r and the same s but another xpubkey Post by: COBRAS on March 04, 2022, 02:09:10 PM 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.. Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 02:33:20 PM Code: import collections Title: Re: the same r and the same s but another xpubkey Post by: NotATether on March 04, 2022, 04:28:14 PM 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 it works for smaller numbers -> now I'm thinking for huge numbers -> any clue, or idea that it will not work? Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 04, 2022, 04:53:43 PM @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 Title: Re: the same r and the same s but another xpubkey Post by: NotATether on March 04, 2022, 07:03:29 PM @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). Title: Re: the same r and the same s but another xpubkey Post by: COBRAS on March 04, 2022, 11:33:39 PM @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. Title: Re: the same r and the same s but another xpubkey Post by: albert0bsd on March 05, 2022, 04:41:44 AM 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 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 (r1^-1)(k1*s1 -z1) =(r2^-1)(k2*s2 -z2) is like Code: a = bc 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. Title: Re: the same r and the same s but another xpubkey Post by: Sansa_Stark on March 05, 2022, 07:38:29 AM yes, but we are not talking about r , but about diff in 2 pubkeys with the same r:)
Title: Re: the same r and the same s but another xpubkey Post by: garlonicon on March 05, 2022, 08:39:58 AM 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 Code: d=(s1/r1)k1-(z1/r1) Code: d=const1*k1-const2 Code: sk=z+rd Title: Re: the same r and the same s but another xpubkey Post by: albert0bsd on March 05, 2022, 01:12:53 PM 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 |