プログラム gen.py とその出力 output.txt が与えられた。
gen.py は、以下の処理をするものだった。
key を生成する。key のそれぞれの要素について、その次の要素から最後の要素までからランダムに選んだkeyの要素数の3分の1の要素のxorをとることで、数列 fake を生成する。fake の最後3分の1の要素は0とする。key と fake の対応する要素をペアにした列を生成する。どっちをペアの先にするかは乱数で決める。fakeを先にしていたら1、keyを先にしていたら0というビット列を用意し、flagのビット列とxorする。
これは fake の生成方法以外はAlkaloid Streamと同じである。
まず、0が入っているペアを参照し、key の最後3分の1の要素を集める。
得られた要素をガウスの消去法の要領で変形し、ある要素の最上位のビットがそれより後の要素で立たないようにしておく。
すると、上位のビットを見ることでxorをするべきかどうかを簡単に判定できるようになる。
これを用いて、これまでに集めた key の要素を指定の数xorした数を含むペアを探すことで、新たな key の要素を探していくことができる。
これらの性質を利用し、以下のプログラムでflagを求めた。
A program gen.py and its output output.txt were given.
What gen.py does is:
key.fake by randomly choosing one third of the number of elements in key from the elements from the next position to the end, and calculating exclusive-or of them. The last one third elements of fake are 0.key and fake. Which to put to the first element of the pair is chosen randomly.fake is coming first and putting 0 otherwise. Calculate exclusive-or of the sequence and a sequence of bits from flag.
This process is the same as one in Alkaloid Stream except for how to generate fake.
Firstly, we can correct the last one third elements of key by searching pairs that contains 0.
Then, transform the elements like Gaussian elimination to eliminate a top bit of one element from elements after the element.
This makes it easy to judge if some elements should be included to exclusive-or by checking the top bits.
Then, we can search for a pair that contain a number generated by exclusive-oring the specified number of elements of key seen before to obtain a new element of key.
Using this characteristics, I obtained the flag using this program: