Defective RSA

テキストファイル chall.py が与えられた。
このファイルには、以下の処理をするプログラムと、その出力が書かれていた。

  1. 定数 e = 1440 を用意する。
  2. 1024ビットの素数 p, q を用意する。
  3. flagbytes_to_long で変換した値を e 乗して p * q で割った余りを求め、その値を c とする。
  4. e, p, q, c の値を出力する。

通常通りRSA暗号の復号をしようとすると、(p - 1) * (q - 1) を法とする e の逆数が存在せず、できなかった。
e の約数で (p - 1) * (q - 1) を法とする逆数が求まるものを探すと、9 の逆数が求まった。

平文の e = 1440 = 9 * 160 乗は、「平文の160乗」の9乗とみなすことができる。
従って、9の逆数を使うことで、「平文の160乗」を復号できるはずである。

そこで、SageMathを用い、復号後pおよびqそれぞれを法として復号結果の160乗根を求めてみた。

A text file chall.py was given.
The file had a program to do following process and its output.

  1. Preaoare a constant value e = 1440.
  2. Create 1024-bit prime numbers p, q.
  3. Convert flag using bytes_to_long and calculate it to the e-th power modulo p * q. Name the result as c.
  4. Output values of e, p, q, c.

Trying to perform decryption of RSA cipher as usual, I found it impossible because the inverse of e modulo (p - 1) * (q - 1) didn't exist.
Searching for a number that divides e and an inverse of the number modulo (p - 1) * (q - 1) exists, I found that an inverse of 9 can be obtained.

The plaintext to the e = 1440 = 9 * 160-th power can be seen as "the plaintext to the 160th power" to the 9th power.
Therefore, "the plaintext to the 160th power" should be recovered using the inverse of 9.

I used SageMath to calculate the 160th roots of the result of decryption modulo p and q.

solve.sage

実行開始後、約5分後に実行結果が出た。
得られたqを法とする復号結果の160乗根をCyberChefで変換すると、flagが得られた。

After about 5 minuts, it produced some results.
I obtained the flag by converting the 160th root modulo q using CyberChef.

To Base, From Hex - CyberChef

buckeye{r0ots_0f_uN1Ty_w0rk_f0r_th1s???}

BuckeyeCTF 2021