Pythonのプログラムsource.pyと、その出力output.txtが与えられた。
source.pyは、以下の処理をするものだった。
nとする。nと、flagを数値化したものを65537乗してnで割った結果を出力する。
まず、nの値を
実行すると数秒で一部の素因数を出力した後進捗が止まったので、
一旦止めて素因数分解できていない部分を次の入力として再スタートする、という操作を繰り返した。
最終的に、以下の素因数が得られた。
A Python program source.py and its output output.txt were given.
What source.py does is:
n.n, and flag converted to a number to the 65537th power modulo n.
Firstly, I factorized n via
The factorization stucked after printing some prime factors in a few seconds.
Seeing this, I stopped the process and used the unfactorized part as a new input for a new factorization until completing the factorization.
Finally, this resulted in these prime factors:
この素因数を用いて、以下のプログラムでφ(n)の値を求めた。
オイラーのφ関数 - Wikipediaを参考にすると、
全て互いに異なる素因数の積として表される数については、それぞれの素因数から1を引いた値の積として計算できることがわかる。
Using the prime factors, I calculated φ(n) via the following program.
Referring Euler's totient function - Wikipedia,
we can know that we can multiply each prime factors minus one to calculate φ(n) of a number that can be expressed as a product of unique prime factors.
さらに、このφ(n)の値を用い、以下のプログラムでRSA暗号の復号を行った。
このプログラムの出力から0xを除いた部分に
After that, I decrypted the RSA cipher using the value of φ(n) via this program.
I applied "From Hex" on 0x to obtain the flag.