poweRSA

以下の処理をするソースコードと、その出力が与えられた。

  1. FLAGを bytes_to_long 関数に渡し、その返り値を m とする。
  2. 素数 p, q を生成し、Nをpとqの積とする。
  3. 定数 e = 0x10001 を用意する。
  4. pのq乗をNで割った余りを求め、rとする。
  5. mのe乗をNで割った余りを求め、cとする。
  6. N, r, cを出力する。

とりあえずNをrで割ってみると割り切れたので、これを用いてcに対しRSA暗号の復号を行った。
その結果にCyberChefで To Base と From Hex をかけることで、flagが得られた。

A source code and its output were given. What the code does was:

  1. Call bytes_to_long function with FLAG as the argument, and store the return value to m.
  2. Generate prime numbers p, q, and store product of p and q to N.
  3. Define a constant value e = 0x10001.
  4. Store p to the q-th power modulo N to r.
  5. Store m to the e-th power modulo N to c.
  6. Print the values of N, r, c.

I tried dividing N by r, and found that N is a multiple of r. Then, I performed RSA decryption of c using the values.
I obtained the flag by applying "To Base" and "From hex" on CyberChef to the result.

To Base, From Hex - CyberChef

CPCTF{c0mm0n_d1v1s0r_1s_c0mm0n_tr1gg3r}

CPCTF22