MRSA2

TCPサーバの接続情報と、サーバのプログラム script.py が与えられた。
script.py は、以下の処理をするものだった。

  1. flag.txt の内容を読み込み、それをもとに整数mを生成する
  2. ランダムな256ビットの素数を2個生成し、p, qとする
  3. mの257乗をp*qで割った余りを計算し、ctとする
  4. 257の法(p-1)*(q-1)における逆元dを求める
  5. n, 257, ctを出力する
  6. 1以上2の140乗未満の整数sの入力を受け付ける
  7. dをsで割った余りを出力する

sとして1 << 139 = 696898287454081973172991196020261297061888を与えると、 この値は2の140乗未満になり、出力される余りはdの下位139ビットになる。

すると、dの下位ビットがp*qのビット数の1/4程度得られるので、 SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー を参考にdの値が復元できそうに思えた。

しかし、このページのプログラムをそのまま動かしてもdの値は得られなかった。
そこで、得られているdの値の上位に何ビットかを全探索で補うようにした。

Information to connect to a TCP server and a server program script.py were given.
What script.py does is:

  1. Read the contents of flag.txt and generate an integer m based on that.
  2. Generate two random 256-bit prime numbers p, q.
  3. Calculate m to the 257th power modulo p*q and name it ct.
  4. Calculate the inverse of 257 modulo (p-1)*(q-1) and name it d.
  5. Output n, 257, ct.
  6. Accept an input of an integer s which is not less than 1 and less than 2 to the 140th power.
  7. Output d modulo s.

Entering 1 << 139 = 696898287454081973172991196020261297061888 as s, this value should be less than 2 to the 140th power and the remainder will be the least 139 bits of d.

This means that we can obtain the lower part of p and its length is about 1/4 of the bit length of p*q.
Referring to SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー, it seemed the value of d can be recovered.

However, the value of d wasn't found by simply running the program on the page.
Seeing this, I had it to add several bits to the top of the obtained part of d by brute-forcing.

sage_code.sage

SageMathのShellを用い、 このプログラムで追加する8ビットを4並列で探索すると、約45分で以下の結果が得られた。

Using the Shell in SageMath, I searched for the 8 bits to add with 4 parallelly running processes using this program.
I got this result after about 45 minutes:

found p: 86737275946298262277485817907643480178183219004845052491356796760479697259853 q = 112664669547842092048996257248434493294513215444901594302159430136565251077411 d = 7794966688925236080167103936550651584746077303278206913803386944790190704050985248271744639319852868822685702696411661836330283587062484623770285549083193

得られたdの値を用い、以下のように復号を行った。

I decrypted the message with the obtained value of d in this way:

Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> d = 7794966688925236080167103936550651584746077303278206913803386944790190704050985248271744639319852868822685702696411661836330283587062484623770285549083193 >>> n = 9772226531969686207819247374114719303803618863134142326085221682005263468005580908315437419891898127379693763792876584687800394851062094511331012685480583 >>> ct = 6977727691773754238277894069331309815949455361393067569843930026119895832757111683531071628183058552709607252447346448131044285575630042658209398240276791 >>> hex(pow(ct, d, n)) '0x666c61677b306f70735f6d347962335f345f6231745f743030306f3030306f6f30306f305f6d7563685f7273617d' >>>

この復号結果にCyberChefで From Hex を適用することで、flagが得られた。

I obtained the flag by applying "From Hex" on CyberChef to this decryption result.

flag{0ops_m4yb3_4_b1t_t000o000oo00o0_much_rsa}

PBjar CTF