チャットの画面と思われる画像babyrsa.PNG
、プログラムscript.py
とその出力output.txt
が与えられた。
output.txt
の内容は以下のものであった。
n
e = 65537
flag
をe
乗してn
で割った余りct
babyrsa.PNG
にかかれている数字列(n, p, q)
」
これらの情報から、画像中の数字列は上から順にn
、p
、q
に対応し、かつn = p * q
であると考えられた。
また、最初に与えられたn
と数字列の関係から、p
とq
はそれぞれ途中の41桁が抜けていることが読み取れた。
An image like a chat application babyrsa.PNG
, a program script.py
and its output output.txt
were given.
The contents of output.txt
was:
n
e = 65537
ct
, which is flag
to the e
-th power modulo n
babyrsa.PNG
(n, p, q)
"
From these information, I thought that the sequences of numbers in the image corresponds to n
, p
, and q
from the top, and that n = p * q
.
Also, from the relation of the sequence of numbers and the given n
, I could say that 41 digits in the middle are dropped from each of p
and q
.
I thought that Coppersmith's Attack should be useful because about a half of p
and q
are known, referring to:
を参考に、p
やq
の半分程度の情報がわかっているので、
Coppersmith's Attack が適用可能な可能性があると考えた。
Using this, I tried to obtain the value of p
with
SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー
これを利用し、p
の値を求めることを試みた。
しかし、与えられたp
の下位の情報を無視して上位の情報だけで解こうとしても、解けなかった。
また、方程式f = p_given + x * (10^30)
の解を求めようとすると、
However, the answer didn't appear when I tried to solve it using only the information of the upper part of p
, ignoring the lower part.
Also, when I tried to solve an equation f = p_given + x * (10^30)
, it said:
ArithmeticError: Polynomial must be monic.
と出てしまった。「monic」とは、最高次の係数が1であることらしい。
ここで、p*q
で割って1余る数は、整数k
を用いてk*p*q+1
と表すことができ、
p
で割っても1余る。
このことを利用すると、p_given
とx * (10^30)
の両方にn
を法とする10^30
の逆元を掛けることで、
x
の係数を1にすることができ、解を求めることができるようになる。
実際に、以下のプログラムをSage Cell Serverで実行すると、p
の足りない部分を求めることができた。
"monic" looks like to mean that the coefficient of the term of highest degree is 1.
By the way, when a number modulo p*q
is 1, the number can be expressed as k*p*q+1
with an integer k
, so the number modulo p
is also 1.
Using this property, the equation becomes solvable after multiplying the inverse of 10^30
(modulo n
)
to both of p_given
and x * (10^30)
to make the coefficient of x
to be 1.
I succeeded to obtain the missing part of p
by executing this program on Sage Cell Server:
p
の値がわかったので、n
をp
で割ることでq
の値もわかる。
これらの値を用いてRSA暗号の復号を行い、
結果を16進数で表して
Getting the value of p
, we can know the value of q
by dividing n
by p
.
Using these values, I obtained the flag by decrypting the RSA cipher,
expressing the result in hexadecimal and applying "From Hex" on