Topic: Transaction puzzle [testnet] (Read 2177 times)

Arubi

can you demonstate us how to calculate privatekey d1 and d2 with propoerties almost like in challenege but little small?

your challenge:

P1 = -P2

d1 = - d2
k1 = - k2

z1 for both signature,

and question:

new challenge :
P1 = -P2

d1 = - d2

but :
k1 = k2 (the same)

and z1 and z2 are different for signature?

No worries.
I'll just add that a good source for me was Hal's post at https://bitcointalksearch.org/topic/speeding-up-signature-verification-3238
Cheers.

Thank you. I have my own tools written in C++/Qt for windows.
I am not too familar with linux

If you're adventurous, you could try running it in my bc interface
https://github.com/fivepiece/btc-bash-ng

Two warnings :

• It's building a patched version of gnu bc and using it.  The patch is available in the repo
• There is little to no documentation, but I can answer questions

I think only a dozen people in the whole world can understand this math 
I will try to follow the calculations, but it will take a lot of time for my old and sand brains.
Anyway, thank you a lot for this.

Sorry @amacilin1, I missed your reply.  Seems like there are no solvers, so I'll post the full solution :

we want to grab the funds from 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o
p2sh scriptpubkey :
OP_HASH160 0x14 0x186A98FF714EF8DDE99847F6769C3913E770E172 OP_EQUAL

from 4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a we can tell:
redeemScript :
asm:

1. this is a 2-of-2 multisig of two public keys {P1,P2}
2. we can see from the parity byte that P2 = -P1, from this we know..
3. we must find two private keys {d1,d2}, where d1 = -d2

coordinates for P1 :

x1 = 3F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574
y1 = CE66AAA31BA3C747A93609B53924D8FFF549315EF352894D491DB9355FDF1528

coordinates for P2 :

x2 = 3F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574
y2 = 3199555CE45C38B856C9F64AC6DB27000AB6CEA10CAD76B2B6E246C9A020E707

let's take a look at the signatures
signature for P1 :

signature for P2 :

r1 = B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997
s1 = 0E503CE27C5D94A3D9A164037B51FD13A67EB392FCFB4073A7EB63AE62725328

r2 = 0A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD24
s2 = 2A58D3F55356A656F2A1E65A66083B680AEC6C704093CB3A3BCD566FA7120C8A

reconstruct the midstate:

sighash (same for both signatures) :
z1 = 24917770E481E6AF860E5CBECE6C8DDA74CD7A2BE90FEC53570438F54E8E38DC
when verifying the signatures ( r1 == R1_x && r2 == R2_x ), we make use of the uncompressed R point :

verify(z1,x1,y1,r1,s1)
R1_x = B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997
R1_y = 3199555CE45C38B856C9F64AC6DB27000AB6CEA10CAD76B2B6E246C9A020E707

verify(z1,x2,y2,r2,s2)
R2_x = 0A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD24
R2_y = 3199555CE45C38B856C9F64AC6DB27000AB6CEA10CAD76B2B6E246C9A020E707

we can see that ( r1 == R1_x && r2 == R2_x ), and we can also observe..

4. R1_y == R2_y
from this we can tell that..
5. k1 = -k2 - the nonce used in both signatures is basically the same !
but also..
6. R1_y == R2_y == P2_y - Both 'R' points and the second public key share the same Y coordinate !!

looking at y^2 = x^3 + 7, we can see that there are 3 'x' solutions for each 'y'.
we can find these three solutions for our r1_y :
cube_root( R1_y^2 - 7 ) mod p

sol1 = 0A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD24
sol2 = B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997
sol3 = 3F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574

the three X coordinates share a property with the cube roots of 1 mod p which are :

rm1p = 1
rm2p = 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
rm3p = 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

And really what's going on with all these points' X coordinate that we gathered is :

P2_x * rm1p = P2_x mod p  # trivial
P2_x * rm2p = R2_x mod p
P2_x * rm3p = R1_x mod p

when this is true for some three points on secp256k1, for the cube roots of 1 mod n which are :

rm1n = 1
rm2n = AC9C52B33FA3CF1F5AD9E3FD77ED9BA4A880B9FC8EC739C2E0CFC810B51283CE
rm3n = 5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72

the following is also true :

rm1n * P2 = P2  # trivial
rm2n * P2 = R1
rm3n * P2 = R2

recall step (2): ( P2 = -P1  ->  d2 = -d1 ), we now also know that {d1,d2,k1,k2} all share the same property with :

k1 = d2 * rm2n % n
k2 = -d1 * rm3n % n

an ecdsa signature is computed like :
1/k * ( z + ( r * d ) ) = s  mod n

we know that :

1/k1 * ( z1 + ( r1 * d1 ) ) = s1
1/k2 * ( z1 + ( r2 * d2 ) ) = s2

k1 = d2 * rm2n
k2 = -d1 * rm3n

d2 = -d1

substitute k2:

1/(-d1 * rm3n) * ( z1 + ( r2 * (-d1) ) ) = s2   ## multiply by rm2n
1/d1 * ( z1 + ( r2 * (-d1) ) ) = -s2 * rm3n
z1/d1 + (r2 * (-d1))/d1 = -s2 * rm3n
z1/d1 - r2 = -s2 * rm3n  
z1/d1 = ( -s2 * rm3n ) + r2   ## "divide" by z1

we get equation that we can use to solve for d1 :
1/d1 = ( ( -s2 * rm3n ) + r2 ) * 1/z1  mod n

which gives us :

d1 = C3FC5135DF80FC592FD8A8A278799F6CD493CD5786858E9022475D52EE21B654
     cU9fw5RaHJNuEEWRgxo7xpLVDtJNNwYnuPHKyzw1m9Z4B5C19dik

d2 = 3C03AECA207F03A6D027575D87866091E61B0F8F28C311AB9D8B0139E2148AED
     cPbMwEBKaLTxXdqXDLGeNYyTyzepcaoARKzxL1bwvDJodd1JynPZ

and now we can redeem the input at 10b1bbb7477d0736b4cadd18cf93f02a0ecd01d0e056b1ab9333aaf95ae914e1.
but the puzzle says that we need to "obtain ownership of the coins", so what about the very first spend at a7d13228... ?

since we had :

k1 = d2 * rm2n
k2 = -d1 * rm3n

how about we try :
from {k1, k2} we get the two keypairs :

k1 = C05A50169BBE16DB798465D7FA4B4FF95BD7FD3B83057181406AD4E31491D1AB
K1 = 03B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997
address : mkaczxMUDgN9usu7hqpBiYKjZ6zJguFr1v

k2 = 03A2011F43C2E57DB65442CA7E2E4F7378BBD01C03801D0EE1DC886FD98FE4A9
K2 = 030A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD24
address : mxLMDERfVDfiQdkrY7gVbiKRYupTfHgZqd

the address for k1 doesn't look familiar, but mxLMDERfVDfiQdkrY7gVbiKRYupTfHgZqd is the address in the second output!
maybe the spender did the same trick?

k3 = -k1 mod n

k3 = 3FA5AFE96441E924867B9A2805B4B0055ED6DFAB2C432EBA7F6789A9BBA46F96
K3 = 02B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997
address : mmr1JWt6t3szFdRpTZ7CjLBTwAzMHnxrrP

looks like we now own all coins.

The main catch in this puzzle is identifying that R1 and R2 share the same Y value.  Once that is known, you have enough information to solve for the private keys.  The last part was just a bonus

5 months passed.
nobody can solve the puzzle.
can you give any more info/clues?

From the spend redeeming the first transaction sent to the address.  The script (redeemScript) is the first input.


Maybe


Awesome!  I recommend setting up an indexing(!) testnet node with a command line interface and just start messing with it.  In no time you'll learn the names of a bunch of technical terms, and then you'll have keywords to use when searching for something new you wanna learn about.
For example you could run this with your indexing testnet node, and see the script as the bottom item in scriptSig :

bitcoin-cli -testnet getrawtransaction 4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a 1

Aside from that, I don't want to accidentally drop clues to the answer in case someone is still working on solving this, so I'll stop here

In the interests of knowledge sharing and learning... are you guys able to provide more details as to the processes and logic involved with "cracking" this puzzle? For instance, I'm not sure where amaclin got this:


Where did this script come from? was that part of the raw transaction from the receiving or sending of funds? 

Following on from that, is there some sort of weakness in the way that the multisig address has been setup (hence the colour coded 02 and 03?) that might enable one to obtain ownership of the coins?

I'd like to learn more

I know what I have to do for this puzzle
Who must have thought

Lol. poor old testnet, never any respect for it... heh.

This puzzle is super difficult to say the least 

BTW. Let me put here a direct link
https://testnet.smartbit.com.au/address/2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o

yeah good puzzle, i know what sould i do, just dont know how to do that

Yes, I wish I had the spare cash to fund this puzzle on mainnet, that would've made it a lot more exciting
If anyone wants to fund the same mainnet address, that would be awesome, but they'll have to trust me that I won't grab the prize myself.


Still, you are very close!

decodescript 5221023f3c3501d05e6151f5b483c3962251ea2113d8f5b76f58c44a4252b4580ed57421033f3c3 501d05e6151f5b483c3962251ea2113d8f5b76f58c44a4252b4580ed57452ae


{
  "asm": "2 023f3c3501d05e6151f5b483c3962251ea2113d8f5b76f58c44a4252b4580ed574
            033f3c3501d05e6151f5b483c3962251ea2113d8f5b76f58c44a4252b4580ed574 2 OP_CHECKMULTISIG",
  "reqSigs": 2,
  "type": "multisig",
  "addresses": [
    "1ASHcGqMZEtC7NwR9FC1GJUanN3sgxq1vp",
    "1GRjVeq7zjMxh6Ub48HznEh2ny4A3t8Bn6"
  ],
  "p2sh": "33v7qgWpUR6NwVXbx6BCoV59H11gsEvFgu"
}


(decoding by mainnet client)

signatures:

no more ideas
i think that there are very small number of people in the world who is able to
solve such puzzles and most of them are not interested in testnet coins

Hello all,

I set up what I think is a fun a transaction puzzle on the testnet address 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o

I've made two transactions funding the address, and one redeeming.  The goal of the puzzle is the obtain ownership of the coins.
The transactions associated with the address are :


fund :
a7d13228ec32508e3255ce35aff85a143e2784d38511df2a9e13569912ab47b9

fund :
10b1bbb7477d0736b4cadd18cf93f02a0ecd01d0e056b1ab9333aaf95ae914e1

spend from a7d13228...
4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a


Cheers