Defective RSA
テキストファイル chall.py が与えられた。
このファイルには、以下の処理をするプログラムと、その出力が書かれていた。
- 定数
e = 1440 を用意する。
- 1024ビットの素数
p, q を用意する。
flag を bytes_to_long で変換した値を e 乗して p * q で割った余りを求め、その値を c とする。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.
- Preaoare a constant value
e = 1440.
- Create 1024-bit prime numbers
p, q.
- Convert
flag using bytes_to_long and calculate it to the e-th power modulo p * q. Name the result as c.
- 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???}
writeup by MikeCAT
BuckeyeCTF 2021