babyrsa

チャットの画面と思われる画像babyrsa.PNG、プログラムscript.pyとその出力output.txtが与えられた。
output.txtの内容は以下のものであった。

これらの情報から、画像中の数字列は上から順にnpqに対応し、かつn = p * qであると考えられた。
また、最初に与えられたnと数字列の関係から、pqはそれぞれ途中の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:

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:

RSA暗号運用でやってはいけない n のこと #ssmjp

を参考に、pqの半分程度の情報がわかっているので、 Coppersmith's Attack が適用可能な可能性があると考えた。

Using this, I tried to obtain the value of p with Sage Cell Server:

SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー

これを利用し、Sage Cell Serverpの値を求めることを試みた。
しかし、与えられた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_givenx * (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:

solve.txt

pの値がわかったので、npで割ることでqの値もわかる。
これらの値を用いてRSA暗号の復号を行い、 結果を16進数で表してCyberChefの From Hex を適用することで、flagが得られた。

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 CyberChef.

corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}

corCTF 2021