Quote from: amaclin1 on September 19, 2017, 01:46:26 PM

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

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 :

Code:

5221023F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED57421033F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED57452AE

asm:

Code:

2 0x21 0x023F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574 0x21 0x033F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574 2 OP_CHECKMULTISIG

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 :

Code:

3045022100B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E49799702200E503CE27C5D94A3D9A164037B51FD13A67EB392FCFB4073A7EB63AE6272532801

signature for P2 :

Code:

304402200A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD2402202A58D3F55356A656F2A1E65A66083B680AEC6C704093CB3A3BCD566FA7120C8A01

r1 = B68E234D58FEAFC61E733CC95C16E1E042D6D5AAD849A0763704D63C4E497997 s1 = 0E503CE27C5D94A3D9A164037B51FD13A67EB392FCFB4073A7EB63AE62725328 r2 = 0A35A7B0D6A2EEE7EBD83F730DC6CC359C15515F704706C57EB8D70E59A7AD24 s2 = 2A58D3F55356A656F2A1E65A66083B680AEC6C704093CB3A3BCD566FA7120C8A
reconstruct the midstate:

Code:

01000000
01
  B947AB129956139E2ADF1185D384273E145AF8AF35CE55328E5032EC2832D1A7
  00000000
  47
   52 21 023F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574 21 033F3C3501D05E6151F5B483C3962251EA2113D8F5B76F58C44A4252B4580ED574 52 AE
  FDFFFFFF
02
  4023050600000000
  19
   76 A9 14 456B2B3D018F69A8D79CDE078C710D986F26820D 88 AC
  4023050600000000
  19
   76 A9 14 B878B15A1FA6C940F83A28BB7ACE9A0F08AEF7CD 88 AC
00000000
01000000

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

arubi

Posts

Merits