チャットの画面と思われる画像babyrsa.PNG、プログラムscript.pyとその出力output.txtが与えられた。
output.txtの内容は以下のものであった。
ne = 65537flagをe乗してnで割った余りctbabyrsa.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:
ne = 65537ct, which is flag to the e-th power modulo nbabyrsa.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