treasure

TCPサーバの接続情報と、サーバのプログラム treasure.py が与えられた。
このプログラムは、以下の処理をするものであった。

  1. 秘密の値REAL_COORDS、および既知の値FAKE_COORDSとpを用意する。
  2. 乱数r1, r2を用意する。
  3. shares[0] = r1*r2*REAL_COORDS mod pの値を出力する。
  4. 数値s1の入力を受け付け、secret = s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod p の値を出力する。
  5. secretがある条件を満たした場合は、終了する。
  6. もう一度数値s1の入力を受け付ける。
  7. 新しいs1について、s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod pの値がFAKE_COORDSでなければ終了する。
  8. 数値の入力を受け付ける。読み込んだ数値がREAL_COORDSなら、flagを含むデータを出力する。

最初のs1としてshares[0]の値をそのまま入力すると、 REAL_COORDSの値が出力され、終了した。
これを数回繰り返した結果、REAL_COORDSの値は固定のようだった。

そこで、s1^3にFAKE_COORDS / REAL_COORDS (mod p)の値を掛ければ、 s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod pの値をFAKE_COORDSにすることができる。
すなわち、s1にFAKE_COORDS / REAL_COORDS (mod p)の3乗根を掛ければよい。

剰余を取る場合の3乗根の求め方を調べたところ、以下のページが見つかった。

Information to connect to a TCP server and a program for the server treasure.py were given.
What the program does is:

  1. Prepare a secret value REAL_COORDS, and public values FAKE_COORDS and p.
  2. Generate random numbers r1, r2.
  3. Output the value of shares[0] = r1*r2*REAL_COORDS mod p.
  4. Accept an input of a number s1, and output the value of secret = s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod p.
  5. Exit if the value of secret satisfies a condition.
  6. Accept an input of a number s1 again.
  7. Using the new value of s1, exit if the value of s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod p is not FAKE_COORDS.
  8. Accept an input of a number. If the value entered is REAL_COORDS, output some data that contains the flag.

Entering the value of shares[0] without modifying as the first s1, it printed the value of REAL_COORDS and exited.
Repeating this several times, I found the the value of REAL_COORDS looks fixed.

Now, we can make the value of s1^3 / (r1^3 * r2^3 * REAL_COORDS^2) mod p to be FAKE_COORDS by multiplying the value of FAKE_COORDS / REAL_COORDS (mod p) to s1^3.
In other words, we should multiply the cube root of FAKE_COORDS / REAL_COORDS (mod p) to s1.

I searched for how to calculate cube roots under modulo, and found this page:

python - Cube root modulo P -- how do I do this? - Stack Overflow

factordb.comでチェックした結果、pの値は素数であった。
さらに、pを3で割ると2余ったので、このページよりaの3乗根はpow(a,(2*p - 1)/3, p)となることがわかる。

最初の入力は、0を入力することで処理を続行させることができた。
2番目の入力は、出力されたshares[0]にFAKE_COORDS / REAL_COORDS (mod p)の3乗根を掛け、pで割った余りを入力する。
最後に、REAL_COORDSの値をそのまま入力すると、flagが得られた。

Checking on factordb.com, I found that the p is a prime number.
I also found that p modulo 3 is 2, so the cube root of a becomes pow(a,(2*p - 1)/3, p), according to the page.

I succeeded to have it proceed by entering 0 as the first input.
For the second input, I use "the cube root of FAKE_COORDS / REAL_COORDS (mod p)" times shares[0] modulo p.
Finally, I entered the value of REAL_COORDS and obtained the flag.

DUCTF{m4yb3_th3_r34L_tr34sur3_w4s_th3_fr13nDs_w3_m4d3_al0ng_Th3_W4y.......}

DownUnderCTF 2021