leftovers

TCPサーバの接続情報と、サーバのプログラム script.py が与えられた。

サーバに接続してみると、何乗して何で割った余りをとるかと0/1列が指定され、
1のところには(指定の数)乗して指定の数で割った余りが1になる数を、0のところにはそうでない数を配置した各要素がユニークな数列を入力することを求められた。

何回か接続しなおすと、「3乗して(11桁の数)で割った余りをとる」という指定になった。
そこで、以下のプログラムで3乗して指定の数で割った余りが1になる数を全探索した。

Information to connect to a TCP server and a server program script.py were given.

Connecting to the server, "power of what modulo what" and a sequence of 0/1 were specified
and I was asked to enter a sequence of numbers whose elements are unique and the element to the (specified value)-th power modulo (specified value) is 1 iff the corresponding element in the 0/1 sequence is 1.

After connecting several times, the query became "power of 3 modulo (a 11-digit number)".
Seeing this, I created this program to brute-force search for numbers whose power of 3 modulo a specified number is 1.

attack.c

このプログラムで求めた数を用い、以下のようにflagが得られた。

Using numbers obtained via this program, I obtained the flag in this way:

log.txt

flag{pr1mes_r_pr3tty_sp3c14lll}

PBjar CTF