Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Crypto transaction puzzle on the testnet address 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1

here are steps to get private keys from address - according Secp256k1 - addres type p2sh

could someone explain some steps from here? some questions are in code: but I will list on the begining to:

1. *how to find redeemScript? from transaction"
2. "sighash (same for both signatures) : **How to calculate sigHash?**
3. **Question: how to calculate cube roots of 1 mod p?** 
        the three X coordinates share a property with the cube roots of 1 mod p 
4.  **Question : how calculate the cube roots of 1 mod n?**
    when this is true for some three points on secp256k1, for the cube roots of 1 mod n

we want to grab the funds from 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o www.blockchain.com/btc-testnet/address/2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o

p2sh scriptpubkey :
OP_HASH160 0x14 0x186A98FF714EF8DDE99847F6769C3913E770E172 OP_EQUAL

from transaction 4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a we can tell:
www.blockchain.com/btc-testnet/tx/4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a

redeemScript below : how to find 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) : How to calculate sigHash?

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..

  1. R1_y == R2_y from this we can tell that..
  2. k1 = -k2 - the nonce used in both signatures is basically the same ! but also..
  3. 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

    Question: how to calculate cube roots of 1 mod p? 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


 **Question : how calculate the cube roots of 1 mod n?**
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

Crypto transaction puzzle on the testnet address 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1

here are steps to get private keys from address - according Secp256k1 - addres type p2sh

could someone explain some steps from here? some questions are in code: but I will list on the begining to:

1. *how to find redeemScript? from transaction"
2. "sighash (same for both signatures) : **How to calculate sigHash?**
3. **Question: how to calculate cube roots of 1 mod p?** 
        the three X coordinates share a property with the cube roots of 1 mod p 
4.  **Question : how calculate the cube roots of 1 mod n?**
    when this is true for some three points on secp256k1, for the cube roots of 1 mod n

we want to grab the funds from 2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o www.blockchain.com/btc-testnet/address/2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o

www.blockchain.com/btc-testnet/address/2MuUKuRSr5sbj9HA9dDo5RS4QVMDrcnyu1o

p2sh scriptpubkey :
OP_HASH160 0x14 0x186A98FF714EF8DDE99847F6769C3913E770E172 OP_EQUAL

from transaction 4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a we can tell:
 www.blockchain.com/btc-testnet/tx/4c004c3f06f5b76ae3f325cfb26ff305146bda0a3f9e5662462653b41324ac4a

redeemScript below : how to find 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) : How to calculate sigHash?

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..

  1. R1_y == R2_y from this we can tell that..
  2. k1 = -k2 - the nonce used in both signatures is basically the same ! but also..
  3. 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

    Question: how to calculate cube roots of 1 mod p? 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


 **Question : how calculate the cube roots of 1 mod n?**
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