テキストファイル 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