zer0pts CTF OK writeup（競技プログラマー向け）

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">競技プログラマ、OK好きそうだと思ってるので解いてください</p>&mdash; 日​暮唯愛🌇 (@keymoon_) <a href="https://twitter.com/keymoon_/status/1505591252762255369?ref_src=twsrc%5Etfw">March 20, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

「OK」というのは、zer0pts CTF 2022で出題されたCrypto（暗号）の問題。

https://2022.ctf.zer0pts.com/tasks/2835887078

この問題に限らず、競技プログラミングに取り組んでいる人はCTFが楽しめると思っている。特にcryptoジャンル。ということで、普段は端折っている細かい説明を加えながら、この問題のwriteup（解説）を書いてみる。あくまで1個のジャンルの1個の問題の解説なので、この記事だけでCTFを戦うのは無理だと思うけれど、きっかけになれば嬉しい。

## なぜ競技プログラマーにCTFを勧めるのか

競技プログラミングの技術がCTFに生きるし、逆も真……と思っていたが、あまり関係無いかもしれない。「競技プログラミングが業務のプログラミングに生きるか？」と同程度だろうか。根っこの部分は共通だけれど、先に進むにつれて道が分かれていく感じ。

むしろ、補完し合う関係だと思う。競技プログラミングで不満に思うことがCTFならば満たされる……かもしれない。

- 競プロはコンテスト時間が2時間くらいと短い。もっとじっくり取り組みたい
  - CTFは時間が1日～2日くらいのコンテストが多い
- 競プロは、多倍長整数が使えない言語に配慮しているのか知らないけど、出てくる整数を無理に $2^{64}$ に収めている感じがある
  - CTFのcryptoなら $2^{1024}$ とかが普通に出てくる
- 色々なライブラリとか、Mathematicaのようなツールとかを自由に使いたい
  - CTFなら何でもあり
- 競プロは個人戦が多い。皆でワイワイ参加したい
  - CTFはチーム戦が多い
- 競プロだとフレームワークとかデータベースの使い方が問われないから、業務の役に立たなそう
  - CTFだとwebジャンルの問題だとその辺も色々と出てくるので、「これ前にCTFで見たな」となる
    - それでどの程度役に立つのかは知らないが……
- 競プロはもう広まりすぎた。就活などで他の人に差を付けたい
  - CTFのほうがマイナーかも

CTFを勧める記事なのでこのような書き方をしているけれど、別にどちらが良いというものではない。箇条書きを逆に書こうと思えば書ける。

チーム戦について、そういえば、ACM-ICPCだと1チームは厳密に3人だが、CTFのチーム戦は、人数の制限は（たいていは）無い。チーム戦でも1人で参加して良い。逆に100人いても良いので、誰かをチームに入れると他の誰かを外さないといけないということはなく、手が増えるだけなので、知り合いのチームがCTFに参加するというときに「混ぜてくれ」と言えば快く迎え入れてくれる（かもしれない）。

## 問題に取りかかるまで

「CTFのサイトに登録したよ。で、コンテストの登録はどこからするの？」という質問を聞いたことがある。毎週コンテストを開いているAtCoderと異なり、各主催がコンテストを開催するのは、だいたい年1回。コンテストごとに一から登録。1週間前くらいにサイトが開いて、1週間後くらいに綺麗さっぱり消える。

問題も消える。昔はコンテストが終了した瞬間に問題も見えなくなることが多かった気がする。今は（温情で？）1週間くらいは復習ができるようにサイトを残していたり、その後もGitHubなどに問題を公開するコンテストも多い。サーバーは止まるので、サーバーとやりとりする問題を解こうと思うと、手元で動かさないといけないけど。

コンテストの運営について、競技プログラミングの厳密さに比べると、だいぶ緩い感じがある。例えば、AtCoderで数分間ジャッジが詰まると「これはひどい。Unratedでは？？？」という話になるところ、開始後しばらくはアクセスが集中して重いことは普通にあるし、それで何らかの対応が行われることはまず無い。一部の問題がずっと落ちているということもある。まあ、競技プログラミングのジャッジは定型処理だが、CTFだと問題ごとにジャッジシステムを一から作っているようなものなのでしょうがない。

非想定解法があることも多い。これはこれで悪くない。決まった解法に辿り着けますか？　よりも、「作問者が想定していない解法があるかも」と探すのは楽しい。

コンテスト開始と同時に全ての問題が公開されず、数時間ごとに公開されるコンテストが多い。何なら非想定解法が見つかった問題の非想定解法を潰した版が出題されることもある。正解チームが少なければ、途中で問題のヒントが公開されることもある。

## 問題概要

表題の「OK」を見ていく。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/47b1d0dc-9e50-9f98-c7fa-b74cb9fd87a2.png)

> 289pt

点数。解いた問題の点数が多いチームが勝ち。

最近のCTFは、解いたチーム数が増えるにつれてスコアが減っていく仕組みが多い。作問者による難易度推定が難しすぎて諦めたのでしょう。この動的スコアリングは競技プログラミングでは見ないけど、競技プログラミングが導入するのありなのでは？

> GOLDEN SUN provides you a key and SILVER MOON provides you a ciphertext.

問題文。この問題の場合は、一応この問題がどのようなことをしているのかを風流に書いているけれど、何の意味も無いことが多い。

「じゃあ何をすればいいんだよ」という話になる。問題のサーバーや配布ファイルのどこかに、特定の形式（このコンテストの場合は `zer0pts{...}` ）の「フラグ」があるので、それを探す。配布ファイルの中に `flag = zer0pts{REDACTED}` のようなものがあれば、それに対応するものを探す。無ければ、SQL Injectionの問題ならDBの中にあったり、サーバー側で任意コード実行をする問題ならサーバーにファイルとして置かれていたり。

> `nc crypto.ctf.zer0pts.com 10333`

`nc` は[Netcat](https://ja.wikipedia.org/wiki/Netcat)。ホスト名とポート番号が指定されているので、このまま端末にコピペすれば、問題サーバーに繋ぐことができる。手作業でポチポチして何とかなることは少なく、プログラムを書いて繋ぐことになる。「やりとりは生のTCPですよ」くらいの意味だと思っておけば良い。ここにHTTPのURLが書かれていることもある。

実際に繋ぐとこんな感じ。これだけ見ても何も分からない。

```
$ nc crypto.ctf.zer0pts.com 10333
P = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668068131
n = 114256805246940525611482754747454595449559729608818071313344793832445755989939488643773335594890099356849720658442571042525733229246793343113804623395844868531426171780018890674134280367460352242836116425905293184625886859286479111075648027169332364772612063457624635629644385798001679112393339114859821806943
e = 65537
x1 = 39917361338023929237723097615621722553279938276746420849801924456052542277926686883380045878494841977601078675758045891908193978003233733003186318862383139294643179981654741389203115429003832020431512963869915410794338982171052863139877184375678570234734563824059462408037229826019393356661149186573091208067
x2 = 79284631983236579293209034832385359038438197734387980924919996769622400385833434134978559327810246367092025367444667572531187861243399468806151572951998222588763553100480045704350055947981232085209136617541905715527294808962902873512248335550483274790539068710421024823467177169860877363405006811455380543828
v: 0
c1 = 59956068633032250407983772096599885489782990959187232528151081991034236681380177928888110542732677735829229590579164568737400942882006445685106734255108597968649812928630283158106533282983089153500314997040946684519906966031634396329477886578552906184468507930616846457161666001451512822377502354189989172631
c2 = 23188114334396971030062001803132958624391727170995980546827595718193627940880388102616152259631625889504492558556491578930964545784457699898251483137215509818017650098655503656145715419533999623882914971911200718036895840924574804471807863303528211182481780039822928697357632086078977514112820301032199430353
```



> ok_1e2ed0e14e...

配布ファイル。明記はされていなくても、配布ファイルと `nc ...` がある問題では、配布ファイルのプログラムがサーバーで動いている。

## 問題のコード

ダウンロードした配布ファイルを解凍すると、server.pyが出てくる。

```server.py
from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse
import os
import signal

signal.alarm(300)

flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}")
flag = int(flag.encode().hex(), 16)

P = 2 ** 1000 - 1
while not isPrime(P): P -= 2

p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q

key = getRandomRange(0, n)
ciphertext = pow(flag, e, P) ^ key

x1 = getRandomRange(0, n)
x2 = getRandomRange(0, n)

print("P = {}".format(P))
print("n = {}".format(n))
print("e = {}".format(e))
print("x1 = {}".format(x1))
print("x2 = {}".format(x2))

# pick a random number k and compute v = k**e + (x1|x2)
# if you add x1, you can get key = c1 - k mod n
# elif you add x2, you can get ciphertext = c2 - k mod n
v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))
```

```py
from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse
import os
import signal
```

`Crypto`は[pycryptodome](https://pypi.org/project/pycryptodome/)。各種暗号処理やその要素技術が実装されているので、cryptoで良く使われる。手元で動かすときや問題を解くスクリプトを書くときに便利なので、venvではなく、グローバルにインストールしておいて良いと思う。

```py
signal.alarm(300)
```

これで、300秒後にシグナルが発生して、プログラムが強制終了する。参加者がずっと繋ぎっぱなしでサーバーの負荷が高まるのを防ぐために良く使われている。

```py
flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}")
```

サーバー側では、`flag`に本物のフラグが入っている。これを盗み出せれば勝ち。

```py
flag = int(flag.encode().hex(), 16)
```

暗号では大きな整数を扱うことが多い。一方、フラグは文字列である。なので、フラグを整数に変換している。`flag`という整数が分かれば、次のようにして文字列に戻せる。

```py
>>> flag = "flag"
>>> flag = int(flag.encode().hex(), 16)
>>> print(flag)
1718378855
>>> from Crypto.Util.number import long_to_bytes
>>> flag = long_to_bytes(flag).decode()
>>> print(flag)
flag
```

そういえば、競技プログラミングでバイト列を扱うことは無いが、CTFだと良く出てくる。整数とバイト列と文字列の各変換はこんな感じ。

```py
>>> from Crypto.Util.number import long_to_bytes, bytes_to_long
>>> long_to_bytes(1718378855)
b'flag'
>>> int.to_bytes(1718378855, ((1718378855).bit_length()+7)//8, "big")
b'flag'
>>> bytes_to_long(b"flag")
1718378855
>>> int.from_bytes(b"flag", "big")
1718378855
>>> b"flag".decode()
'flag'
>>> "flag".encode()
b'flag'
>>> b"flag".hex()
'666c6167'
>>> bytes.fromhex("666c6167")
b'flag'
>>> str(1718378855)
'1718378855'
>>> int("1718378855")
1718378855
```

整数とバイト列の変換で、外部ライブラリであるcryptodomeを使うか、面倒だけど標準ライブラリですませるかはお好みで。

```
P = 2 ** 1000 - 1
while not isPrime(P): P -= 2
```

$2^{1000}$ 未満の最大の素数を求めている。

```py
p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q
```

RSA暗号。頻出。

https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

それなりに難しいはずだけど、競技プログラミング勢は理解しやすそう。

オイラーの定理（フェルマーの小定理を一般化したやつ）から、$m$ と $n$ が互いに素ならば、 $m^{\phi(n)} \equiv m \mod n$。$\phi(n)$はオイラー関数、$n$ と互いに素な整数の個数。$n$ が素数 $p$ と $q$ を用いて $n=pq$ と表せるならば、$\phi(n) = (p-1)(q-1)$。$e$が決まっていて、$d\equiv\frac{1}{e} \mod (p-1)(q-1)$とすると、$\left(m^e\right)^d \equiv m \mod n$。$c=m^e \mod n$ と暗号化すると、元に戻せるのは $d$ （もしくは、知っていれば $d$ を計算可能な $p$ と $q$ ）を知っている人だけ。

```py
key = getRandomRange(0, n)
ciphertext = pow(flag, e, P) ^ key
```

`^ key` で暗号化は一般的。`key`ともう1回xorを取ると元に戻せる。

`pow(flag, e, P)` は初めて見た。RSA暗号で $n$ から $d$ を計算できないのは、$n$ の素因数分解がとても難しいから。 $P$ は素数なので、 $\phi(P) = P-1$ で $d = \frac{1}{e} \mod P-1$ は計算できる。ここで一手間掛けさせるのは、「`pow(flag, e, P)` を1ビットも逃さずに正確に求めよ」ということなのだろう。ここが `flag` だと、「最初は `zer0pts` だろう」とか「ASCII文字列だから最上位ビットは全て0だろう」とか推測ができてしまう。

```py
x1 = getRandomRange(0, n)
x2 = getRandomRange(0, n)

print("P = {}".format(P))
print("n = {}".format(n))
print("e = {}".format(e))
print("x1 = {}".format(x1))
print("x2 = {}".format(x2))
```

さらに乱数を2個生成して、ここまでに出てきた（公開して良い）値を出力。実行ごとに変わる値と変わらない値は何かを気にしておくと良い。`P`は固定、`n`はそうではない、など。

`print`で標準出力に出力している。ところで、サーバーとの接続はTCP。これは、サーバー側で[xinetd](https://ja.wikipedia.org/wiki/Xinetd)を使って変換している。多くの問題がこうなので、いちいち説明されない。

```py
# pick a random number k and compute v = k**e + (x1|x2)
# if you add x1, you can get key = c1 - k mod n
# elif you add x2, you can get ciphertext = c2 - k mod n
v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))
```

この問題のキモ。

言われているとおりに $v = k^e + x_1$ を計算して渡すと、言われているとおりに `key` が得られる。RSA暗号は暗号化と復号が等価なので、 $d$ で暗号化して $e$ で復号することもできる。$c_2$ から `ciphertext` を得ることはできない。$v-x_2$ は計算できるが、$k_2$ は求められない。$v = k^e+x_2$を渡した場合も同様。

`key` と `ciphertext` の両方が得られれば、`pow(flag, e, P)`、ひいては `flag` が求められる。でも、この問題では `key` と `ciphertext` はどちらか一方しか与えられない。だから、 `flag` は求められないでしょ？　という主張である。

## 解法

こういうのは、$v=\frac{x_1+x_2}{2}$ とすると上手くいく。競技プログラミングでもこういう発想が必要になることはありそう。

$k_1 = (-x_1+x_2)^d \mod n$、$k_2 = (x_1-x_2)^d \mod n$ になる。ところで、 $d$ は常に奇数である。偶数だと、$(-a)^2 = a^2$ が成り立つから、異なる暗号文から同じ平文が出てきてしまう。これはおかしい。$d$ が奇数なので、 $k_2 = -k_1$ になる。

```math
\begin{eqnarray*}
c_1 &=& k_1 + key \mod n \\
c_2 &=& -k_1 + ciphertext \mod n
\end{eqnarray*}
```

両辺を足すと、`c1+c2 = key + ciphertext` となり $k_1$ が消える。`ciphertext`の定義から、`c1+c2 = key + (pow(flag, e, P) ^ key)`。

この`+`と`^`が絡むやつ、AtCoderでときどき出てくる。

```
c1 + c2
  = key + (pow(flag, e, P) ^ key)
  = (key ^ pow(flag, e, P) ^ key) + ((key & (pow(flag, e, P) ^ key))<<1)
  = pow(flag, e, P) + ((key & (pow(flag, e, P) ^ key))<<1)
```

後半の部分が`^`から`&`になった。`^`ではどうしようもないが、`&`は`0`になる確率が高いという偏りがある。別に1回の接続で正解を得る必要は無く、何回も接続しても良い。1になる確率が低いし、繰り上がる確率も低いし、`c1 + c2`を集めまくって多数決でも取ればいいんじゃないかなぁ。

そういえば、CTFのルールには「ブルートフォース禁止」とか「DoS攻撃してきたらBANするからな」とか書かれている。初めてCTFに取り組む人には、アウトとセーフのラインが分からなそう。まず、スコアサーバー（フラグを提出するところ）に対して、スクリプトを書いてフラグを色々試すようなのはアウト。そうではなく、問題のサーバーに対してなら、複数の接続張ったりせずに、1個の接続を何回も繰り返すくらいはセーフなんじゃないかなと個人的には思う。数千回の試行が想定解法の問題もある。とはいえ、単に$256^n$通りのフラグを仮定して総当たりするようなことはやっても意味が無い。コンテスト時間内に正解が得られる程度の試行回数かどうかは見積もりましょう。

で、多数決を試してみると、上手くいきそうでいかない。考えてみれば、`flag`が0のところは確率が1/2になる。多数決の閾値を1/2から変えてみるとか……？

競技プログラミングでもそうだけど、実験してみたほうが早い。`flag`を固定して`key`をランダムにしたとき、`x = key+(flag^key)`はどのような値を取るのか。

```test.py
import random
flag = random.randint(0, 2**100-1)
print(f"flag: {flag:0128b}")
for i in range(32):
  key = random.randint(0, 2**127-1)
  print(f"x:    {(key+(flag^key)):0128b}")
```

```
$ python3 test.py
flag: 00000000000000000000000000001001110100110001011101100000010001101110010101010001000100101011101001000111000110000011110101111011
x:    11011110010110111111000010110010001001000010011101111100101001110000010110010101010101001011101001110111011001000100001010000011
x:    01101000011000111100011000010001110110111101100001100110101001110000100110101001110111001011110001000111011000001011110101111011
x:    11100111101010011010001011010110001011001101100001100001100101101111011010100110101010110100010110101000111000001100001001111011
x:    11001110111000111010010010001001111001001101011110011010011001101111100101101010111011010100001101010111110111111100000110000011
x:    00001110010111000000001010010001110111000110011101101110101110010001101010101101111000101100010101000111110110111011110110000011
x:    00001111000111010011101101101110001010111010011101101001101110010000010110011001101010110100001010011000110110010100000110000011
x:    11101101011100011111110000101110001011001110011110001001101001110000010101100010100111001100001010011000000111101011110101111011
x:    10111110010010000111001111010010001010111001100001100110101110010000100101100110111011010011101001011000111000011011111010000011
x:    01100110111110101101011011010110000110111010011101110100010010010000101001011110111011001100010110001000110111000011111001111011
x:    01101010001010001001000111110010000101001001011110001110100101101110010101101110111010101100001101111000101000110011110110000011
x:    11111111011111010001001101101001110100111110100010001010011001101110011001100110000100110011101001000111000110011011111010000011
x:    11110000000110011110011111101110000101000101011101111100010101110000011010010001011011001100010110111000011000101011111001111011
x:    00010000111100001000110000101001110101000101011110011110101101110000101001100110110111010011101110110111000111110011110101111011
x:    00011010000011010011001101101010000111000001011101110001011001101111101010011110011010101100010101011000111000001100001010000011
x:    00001010010110111111100110101110000100110010100001110011101110001110101010010001001011001100010010110111111000001011110101111011
x:    00001010110100100010111001010001111001001110011101101001011110010000101010101110000101010100001010111000001000111100001001111011
x:    01100100011011111111001100010001110111001001011101110100011110001111010101100010010101001100010010100111110110010011110101111011
x:    00111110010100101001010110110110000110110010011110000101011010001111101001100101101011010100010101111000011000101100001010000011
x:    11011010111101000011111100010101110110110001011101100000011101110000100101101110101011010011101110010111101000011011110110000011
x:    11101011010000010011100001101010000111000101011110010100011001110000100101100010010101010100010010100111101000100100000110000011
x:    10111100000011101010101111101101111011001110100001110101011101110000010101011110111000110011101110010111100110110011110101111011
x:    10010111000101110100011111101001111011000010100010011000101010010000100101100101010100101011101110101000000110000011110101111011
x:    00101000111111110010001100110101110100111110011101101100101001101111011001101010001011010100010101001000100111101011110101111011
x:    01001100011110011101010010001001110101001110011101111010010110010000101010100110011011001100010010011000011001010011110110000011
x:    00111010000001001110100111110010000110110101011110001010100001110001101001010110111010110011110010000111000110111100000101111011
x:    11010101110110110111110100001101111011001001011110011110011101101111011001011010101001001011101110010111001000100100001010000011
x:    00111011110010011110010110001110001011001010011110000110101110010000100110011010100110101011110110001000101001011011111010000011
x:    01101000001111111010101100010110000100110110100010010111010110001111100101010101011010110011101110000111100111000100001001111011
x:    00111100111011010101101110001110001010110010100001101100101010010001011001010010011000110100001001011000001000011100000110000011
x:    10100000010011001011110011110001110110111001100010001111101010010000100101101001110101001011101001110111101000101100001001111011
x:    10100100110010001101000101001001110110111110011101110011010110010000101001010001011010101100001001000111100110010100000101111011
x:    00000001000000001101111101110101111000110010011110001111011101101111011010010110010101001100001101101000110111010011110110000011
```

ぐっと睨むと、`flag`が`11`のとき`x`は`00`か`11`になる。`01`のときは`01`か`10`になる。`00`と`10`のときは4通り全てのパターンが出てくることが分かる。

ということで、`c1+c2`を集めていき、`01`か`10`が出てきたら`11`ではないことが確定、`00`か`11`が出てきたら`01`ではないことが確定する。充分な試行回数があれば、`11`と確定しなかったら、`01`、`10`、`00`のいずれかであると見なして良い。1番目のビットが`1`なら`10`。`01`と確定しなかった場合も同様。先頭から順番に`0`と`1`を決めていける。

補足。

$x_1+x_2$が奇数だったら2で割れない → $x_1+x_2$が奇数なら捨てて、偶数のときだけ使えば良い。

```py
print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))
```

なので、`c1+c2`は、`(k1 + key)+(k2 + ciphertext)` ではなく、 `(k1 + key)+(k2 + ciphertext)-n`かもしれない。これはスクリプトを書いて動かしているときに気が付いた。`key+(flag^key)`の最下位ビットは、`key`の値に関わらず、`flag`の最下位ビットに一致する。また、`n`は常に奇数である。`flag`の最下位ビットが0であると仮定すると、`c1+c2`の最下位ビットが1ならば`n`が引かれていることが分かるので、`n`を足せば良い。これでフラグが求められなかったら、仮定が間違っていたということなので、最下位ビットが1と仮定してやり直せば良い。

## 解答スクリプト

```solve.py
from pwn import *
from Crypto.Util.number import long_to_bytes
import time

F01 = [False]*1024
F00 = [False]*1024

while True:
  s = remote("crypto.ctf.zer0pts.com", 10333)
  #s = process("python3 server.py", shell=True)

  s.recvuntil(b"P = ")
  P = int(s.recvline().decode()[:-1])
  s.recvuntil(b"n = ")
  n = int(s.recvline().decode()[:-1])
  s.recvuntil(b"e = ")
  e = int(s.recvline().decode()[:-1])
  s.recvuntil(b"x1 = ")
  x1 = int(s.recvline().decode()[:-1])
  s.recvuntil(b"x2 = ")
  x2 = int(s.recvline().decode()[:-1])

  if (x1+x2)%2==0:
    v = (x1+x2)//2
    s.sendlineafter(b"v: ", str(v).encode())

    s.recvuntil(b"c1 = ")
    c1 = int(s.recvline().decode()[:-1])
    s.recvuntil(b"c2 = ")
    c2 = int(s.recvline().decode()[:-1])

    f = (c1+c2)%n
    #if (f&1):
    if not (f&1):
      f += n
    for i in range(1, 1024)[::-1]:
      if (f>>i&1)==(f>>(i-1)&1):
        F00[i] = True
      else:
        F01[i] = True

    flag = 0
    for i in range(1022)[::-1]:
      if flag>>(i+1)&1:
        if not F01[i]:
          flag |= 1<<i
      else:
        if not F00[i]:
          flag |= 1<<i
    flag>>=1
    print(f"{flag:0256x}")

    flag = pow(flag, pow(e, -1, P-1), P)
    flag = long_to_bytes(flag)
    print(f"{flag}")

    if b"zer0pts" in flag:
      break

  s.close()
```

`pwn`は[pwntools](https://pypi.org/project/pwntools/)。本来はpwnableというジャンルの問題を解くためのライブラリ。TCP通信のプログラムを書くのに便利なので使っている。

標準ライブラリに[socket](https://docs.python.org/ja/3/library/socket.html)というライブラリがあり、これを使っても良い。が、pwntoolsを使うと「○○という文字列が来るまで受信する」という処理などが楽に書ける。

あと、上記のプログラムの

```py
  s = remote("crypto.ctf.zer0pts.com", 10333)
  #s = process("python3 server.py", shell=True)
```

この部分、これだけで問題サーバーとのTCP通信と、手元のプログラムの標準入出力とのやりとりとを切り替えられる。手元で動かせば、すぐに結果が得られるし、本来秘密の内部状態なども得られてデバッグが楽。

実際に動かすと、このように徐々に正しい値が求められていく。お疲れさまでした。

```
$ python3 solve.py
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0a3531d0e834f22f2b0afbb3c13118b2ceddf61a1ea442ce90304a341e9e179a0c48d0f2b9c579392b1fe3fcdd554dd6f494580dd824ab6036eba44ca4607523a5976e73c64ded263fe4d100fea054666f12420548de6ce2c6e19f7ebc658a3f18de2808ca8c45dce12b542d14e4364e30f6f75632390e1c2a81120e2ca25ab5
b"\x95\xb3v'c(\x9b\x8d\x1d\x02\x89\x83\xf8gC\xe8\x13s\xc4\xdb/\xbb\x19K\x02b\x82\xc1\xb4\x81\xb7\xbf\x96\x9f\xec\xc0S\x03;\x99%'\xb8\x9a\xf23\xe3\xf2\x82\x0be\xb7{B\xac_\x02\xc28\x9a\x15\xa6\x1d\xc0\x17\xbd\x94'k\xa8E\x81\xbacW\xacA+\xc6I\x8f\xab\xfcT\x84+O\x85:$Y\x11>\xb0M}\xf0\xb1\xe6q\xfd\x1e\xf5\xc7g`\xaa\xfd\x19\xce>b\xd1-k\x10\xe2\x15\x1er\x8cIO}\xfa"
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
080a312f17b4f1d0cb05044c392d16b2c91df615de9b3ace900fb5c3e15dd76203a0aeed260574a6d4e01bfb2292add68b6ba709d824a49fc8eba4335b9e751c5a68616bc64d91063fe42d00fe5fa39990d23dfa471e4ce2c4de5f7ebc55683ce721d7c7356bb9dc9ed4ab12ea94362e30e6f74632390d9c0a7c1201cc21a525
b'G\xf9\x1f\xf2G\xeb<#\xa4e{\xd8\x1a\xd5\to\xf8\n\x14Nr+\xb8%\xf2\x89\xbb;\xeeHo\xa7\xcbB\xf1\xe9\x85q\xc4\xddA\xef\x08@_h\xbb\xed\x84E\x10\x89Q\xab5W\x80\x98\xf2\xfcN\r\xdb\xac\xab\xf1\xdf\xa90\x1cc-\x9f{\x85\xcd\xde\x06\xc2\x14%K\x84\x91\xd1g\xf1-\x82^\xc3\xc2g4\xb2\xeb\x0f:\n\x8b\x81\x91\xf0\xb2\x8b\x8b@\x81L(4o=QrkR\xac}\xc2Z\x169\xb5\xc5'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0809312f17b4edd0c40283ac392114b2a09dc615de9b38cd6fcfb5c3de5dd719f380aecd260564a6ca9e1bfb2152add0844ba709d7c4a49fb6cba32c939c6a1c5988616bc5ad91063fe32cf8fd5fa25990c13dfa469e4ce2c09e5f7ebb95683ce721d7c7326bb9a29ed4a212ea9431ae30e6f601b1b90d93ca7c1201cb1da425
b'\x97\x06q\x10\xa8\x10b\xb7\xcc`\xcb\x99\xb1\x02\xa77\xcd\xaa\x9f\r7#\xd6\xb2jB\xe9\xf3\x99\xd4\x9b\xf2\x102Oj\xe9\xf61\xb1\xd4MA\x9c.\xbfk(\x8f\x1d@\xfa\x88\xb1\xd9\x1d\xef2\x92\x80\xce\xcf\x82\xa1%\xe1*\xa3\xd3\x88\x8f\r\xb5\x15\xd2\xf6N\xfa\xaf8`\x89\xc2|cN\xfa\x10\x91\xde|\x12\xa8\x9dQ>A\xae\xb1c,\xefS\xb8+\xd3\xbc\xf6vws\xf9\xdaN{\rp\xa5N\x8cr\xc1\xf2\xf7\xd1'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0801012cd7b2edd0c40283ab392014b2a09dc611de9b38cd6fcfb5c39e5dd719f340aecd25c564a6ca9e1bf32152add0804b9709d7c2a49fb6c3a32c935c691b5968616bc58d11063fe32cf8fd5f225990c03dfa469e4ae2c09e5f7ebb95683ce721d7c7316bb5a29ed4a012ea9431ae2ec6f601b1b90d93ca7c11f1ab1d9a25
b'\x81\xe5\xe9\xd4\xbd\x92\xfb\x03:\xc4@\x81\x18\x91$\xcfM\xb2\x9di\xbf\xa0P\x81\xd1\x89\xf1!\x17\xbdv\x93\xe5\x7f\xd7\x87h\xc7\xa1?\x1c\x8a:y\xda\xdc\xf4Ox\x1c\x10d\x86q`\x13\x0e\xa5\xcc\xd8\x91\xb7\xf5\x7f\x95\x8f\x1f\xe7_DqYW\xb1\x17\xd5\xc8\x94\\\r\xe7\x00\xa0\xab\x85\x05k\x1d{j\xf0\xa74\x7fO\xa9\x88c\xfb\x13\xa2z{t-\xb4\xd9^\x05y\xa8+\xa5\xc9Nl\xe0\x99\xd9\x010?L0]'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0800002cd7b2edd0c40283ab392014a2a09dc511de9a38cd6fcfb5c39e5dd719f340aecd25c564a6ca9e1bf32152add0804b9709d7c2a49fb6c3a32c935c691b5968516bc58d10c53fe32cf8fd5f22598ec03dfa469e42e2c09e5f7ebb95683ce6d9d7c7316bb5a29ed4a012ea1431adaec6f601b1b90d93ca7c11f1ab1d9a25
b'\xb1\xfc\xdcq\x11\x19\x9d\xdd\xbe!pj\xc7C\xc7\xf4\xe0\xe0\xc2\xa581\x04\xac\x18\x039W\xd6\xfcy\x91\x06\xa0"\x06\xe8\xbb\x01\xb4\xe1\xa2\xb0\xff\x022j@\xa1\xcc\xdc^\xa4\xe8\x1e\xac\x8f\xc0\x17\xec\xbd4\x9b\xdd\xa7a\x86|0m\xdc\xd9\xa1&\xf4\xcf\xa6\x85\xea\xb0\xe4vHY\xf8\x9fE\xd5\xaf\xbc\xb2\xd9\xa9\xfe3!\xd2\x99\xafy\x96\xcc\x947\xd2?\x8dX,\xfa\x1dRx\xac\x8c\x19\x93\xc0\xee\xb8\x85\xfdy\x8d\xa8'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0400002cd7b2edd0c30283ab392014a2a09dc511de5a38cd6fcfb5c39e5dd719f340aecd25c564a6ca9e1bf32152add0804b9709d7c2a45fb6c3a32c135c691b5966516bc58d10c53fe32cf8fc5f22598ec03dfa469e42e2c09e5f7ebb95683ce6d9d7c7316bb59a9ed4a012e81431a9aec6f601b1b90d93ca7c11f1ab1d9a25
b'\x1eA"\xd2\x00\x9f\xa7z\x9b\xbbj\x11N\xb1\xc8\x1d\xd8\xf4]\xb1\r\xa2Z\xa6\x95{\x04l\x9a\x82l\xd1\x9a\xb8\x08Y\xf0\xa5\xa62\x8b\xa9\x9cq\xb0\xedfH\x9a7r\xd5;\x97e\x83\x82\xbd\xa34\x92m\xf2\x13\x0c\xbbm\xc8\xe5\x1e\xc5\xee\x19e=\xe9\'wP`\xb1\x8es\xfb\xc3I\x06t\x98\x8f\xb53\x0e\xf6\x15\x95\x04\xa6R\xf5\xe0\x84\xdf\x1a\x16\xa9\xc2b\xf6\x06\xe4%+\x85,\x7fg\\\n\xabh/\xadv\xa2'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0000002cc7b2edd0c30283ab392014a2a09dc5119e5a38cd6f8fb5c39e5dd719f340aecd25c564a6ca9e1bf31952add0804b9709d7c2a45fb6c3a32c135c691b5966516bc58d10c53fe32cf8fc5f22596ec03dfa469e42e2c09e5f7ebb55683ce6d9d7c7316bb59a9ed4a012e8143129aec6f601b1b90d93ca7c11f1a31d9a25
b'~\xdbyn?yiL\x02\x927\xcb\xb9\xe2r\x9d\xd2o\x0c\x11\xc5 \xae\x1d\xe2Q!\xc8?^\xde\x88/\xf9@U\xda\x90B}\xe0\xd3\xc9\x87\xdd\xecyE\xbf\x1d\x05\xfe\xc9{\xbbJ\x06\x1fP\xb8de\xb8\x0f\xc14\xb3yU\x96\xc7\x94\x0c\xa1\x86\x80L^\x8ftS\xbf\x07\xecBw\xfbjw\x98\x94\xed\xf6\x13!\x0f\xd6\x0esc&\xa0\xec\xba\x052\xb3i0\x02\xa6\x07\xad\xeb\xcf\xadx=*\x15\x00\x95\xb6U|'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0000002cc7b2edd0c30283ab392014a2a09dc5119e1a38cd6f8fb5c39e5dd719f340aecd25c564a6ca9e1bf31952add0804b9709d7c2a45fb6c3a32c135c691b5966516bc58d10c53fe32cf8fc5f22596ec03dfa469e42e2c09e5f7ebb55683ce6d9d7c7316bb59a9ed4a012e8143129aec6f601b1b90d93ca7c11f1a31d9a25
b'\x9d\xedr\x86\x14\xe4E\xd8\x17z\x8b\x07\xebE\xb4:p?i\xfc\xaaf\x9b\xdb\xf3I\xe8+\xa3A\xbeq\xe4\x84\xa9\xcdSc\xdd\x0f\x83\xc62T\xc2\x9e\xa3\x07\x88\xb2LZ@w^?\x16\x19c\xff*\xe4&\x7f>\x15\xf13N\xc0\xa3\xd4\x1e\xb7\x81g\xafT)\xc7\xe2\x13\xb3>aKK\x01\xca\x1e\xa9\xeb\x84\xc4X\xb0\xe8\xa2\xab\xbb\xe4U\xc9\xed\xcc2?\xa9c\xea\xf3\xe3_Q4\xe9-R\x960\xee`\xf9T\xc2'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
[+] Opening connection to crypto.ctf.zer0pts.com on port 10333: Done
0000002cc7b2edd0c30283ab392014a2a09dc5119e1a38cd6f8fb5c31e5dd719f340aecd25c564a6ca9e1bf31952add0804b9709d7c2a45fb6c3a32c135c691b5966516bc58d10c53fe32cf8fc5f22596ec03dfa469e42e2c09e5f7ebb55683ce6d9d7c7316bb59a9ed4a012e8143129aec6f601b1b90d93ca7c11f1a31d9a25
b'zer0pts{hav3_y0u_unwittin91y_acquir3d_th3_k3y_t0_th3_d00r_t0_th3_N3w_W0r1d?}'
[*] Closed connection to crypto.ctf.zer0pts.com port 10333
```