dividing_secrets

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

  1. ランダムな512ビットの素数を生成し、pとする。
  2. 1～pの乱数を生成し、gとする。
  3. flagを数値化し、xとする。
  4. g、p、「gをx乗してpで割った余り」を出力する。
  5. 64回、以下を繰り返す。
    1. 整数divの入力を受け付ける。
    2. gを「xをdivで割って整数に切り捨てたもの」乗してpで割った余りを出力する。

「gのx÷div乗」をdiv乗すると、 gのx乗に比べてx÷divの余りの数だけgを掛ける回数が少ない数になるはずである。
したがって、この数にgを何回掛けるとgのx乗になるかを探索することで、 x÷divの余りを求めることができる。
この余りの情報を集めることで、中国剰余定理によりxを求めることができそうである。

これを実行するため、指定した数以上の素数を64個出力するプログラムprime_gen.plと、 サーバの出力からflagを求めるプログラムsolve.pyを用意した。

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

  1. Generate a random 512-bir prime number and store it to p.
  2. Generate a random number between 1 and p, and store it to g.
  3. Convert the flag to a number and store it to x.
  4. Output g, p, and "g to the x-th power modulo p".
  5. Repeat this 64 times:
    1. Read an integer div.
    2. Output g to the "x divided by div and truncated to an integer"-th power modulo p.

"g to the (x divided by div)-th power" to the div-th power will be a value generated by multiplying g(x modulo div) times lesser than g to the x-th power.
Therefore, we can obtain the x modulo div by searching for the number of g to multiply to make the value g to the x-th power.
Correcting the modulo information, x should be able to be calculated via the Chinese remainder theorem.

To realize this, I created a program prime_gen.pl to output 64 prime number that are not less than the specified value and solve.py to obtain the flag from the output of the server.

prime_gen.pl

solve.py

以下の手順によりflagが得られた。100以上という設定では上手くflagが得られなかったので、10000以上に設定した。

  1. prime_gen.plを用い、10000以上の素数を生成する。
  2. Tera Termでサーバに接続し、ローカルエコーオフの状態で生成した素数のデータを送信する。
  3. サーバの出力データをコピーし、solve.pyに入力する。このときコマンドライン引数で10000を指定する。

I obtained the flag by the following process. Using prime numbers from 100 didn't work well, so I used prime numbers from 10000.

  1. Generate prime numbers from 10000 via prime_gen.pl.
  2. Connect to the server via Tera Term, set Local echo to OFF, and send the prime numbers.
  3. Copy the output from the server and use it as an input for solve.py. Specify "10000" as the command-line argument to do this.
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}

corCTF 2021