テキストファイル chall.py が与えられた。
このファイルには、以下の処理をするプログラムと、その出力が書かれていた。
e = 1440 を用意する。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乗」を復号できるはずである。
そこで、pおよびqそれぞれを法として復号結果の160乗根を求めてみた。
A text file chall.py was given.
The file had a program to do following process and its output.
e = 1440.p, q.flag using bytes_to_long and calculate it to the e-th power modulo p * q. Name the result as c.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 p and q.
実行開始後、約5分後に実行結果が出た。
得られたqを法とする復号結果の160乗根を
After about 5 minuts, it produced some results.
I obtained the flag by converting the 160th root modulo q using