TCPサーバの接続情報と、サーバのプログラム script.py が与えられた。
script.py は、以下の処理をするものだった。
flag.txt の内容を読み込み、それをもとに整数mを生成するp, qとするmの257乗をp*qで割った余りを計算し、ctとする(p-1)*(q-1)における逆元dを求めるn, 257, ctを出力するsの入力を受け付けるdをsで割った余りを出力する
sとして1 << 139 = 696898287454081973172991196020261297061888を与えると、
この値は2の140乗未満になり、出力される余りはdの下位139ビットになる。
すると、dの下位ビットがp*qのビット数の1/4程度得られるので、
SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー
を参考にdの値が復元できそうに思えた。
しかし、このページのプログラムをそのまま動かしてもdの値は得られなかった。
そこで、得られているdの値の上位に何ビットかを全探索で補うようにした。
SageMathのShellを用い、 このプログラムで追加する8ビットを4並列で探索すると、約45分で以下の結果が得られた。
found p: 86737275946298262277485817907643480178183219004845052491356796760479697259853
q = 112664669547842092048996257248434493294513215444901594302159430136565251077411
d = 7794966688925236080167103936550651584746077303278206913803386944790190704050985248271744639319852868822685702696411661836330283587062484623770285549083193
得られたdの値を用い、以下のように復号を行った。
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が得られた。
writeup by MikeCAT