TCPサーバの接続情報と、サーバのプログラム script.py が与えられた。
script.py は、以下の処理をするものだった。
flag.txt の内容を読み込み、それをもとに整数mを生成するpとするqとするmの65537乗をp*qで割った余りを計算し、ctとするn, 65537, ctを出力するq未満の整数sの入力を受け付けるpをsで割った余りを出力する
sとして1 << 127 = 170141183460469231731687303715884105728を与えると、
この値はq未満になり、出力される余りはpの下位127ビットになる。
すると、pの下位半分程度のビットが得られるので、
RSA暗号運用でやってはいけない n のこと #ssmjpのスライド19より、
Coppersmith's Attack が使えそうであることがわかる。
SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー を参考にしつつ、 corCTF 2021 の babyrsaで用いたxの係数の逆元を掛けてxの係数を1にする方法を用い、 以下のプログラムを用意した。
Information to connect to a TCP server and a server program script.py were given.
What script.py does is:
flag.txt and generate an integer m based on that.p.q.m to the 65537th power modulo p*q and name it ct.n, 65537, ct.s which is not less than 1 and less than q.p modulo s.
Entering 1 << 127 = 170141183460469231731687303715884105728 as s,
this value should be less than q and the remainder will be the least 127 bits of p.
This means that we can obtain about a half of bits in the lower part of p,
which should enable Coppersmith's Attack, according to the slide 19 in RSA暗号運用でやってはいけない n のこと #ssmjp.
Referring to SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー, I created this program.
I also used a technique, which I used in "babyrsa" in corCTF 2021,
that multiply the inverse of the coefficient of x to make the coefficient of x be 1.
このプログラムを
Executing this program on
この値をpとして用い、以下のプログラムでRSA暗号の復号操作をすることで、flagが得られた。
Using this value as p, I obtained the flag by performing decryption of RSA cipher via this program: