プログラム gen.py とその出力 output.txt が与えられた。
gen.py は、以下の処理をするものだった。
key を生成する。key のそれぞれの要素について、その次の要素から最大keyの要素数の3分の1の要素のxorをとることで、数列 fake を生成する。key と fake の対応する要素をペアにした列を生成する。どっちをペアの先にするかは乱数で決める。fakeを先にしていたら1、keyを先にしていたら0というビット列を用意し、flagのビット列とxorする。
fake の生成のしかたより、シャッフル前の fake の最後の要素は0であり、
0を含むペアがあれば、そのペアのもう一方の要素は key の最後の要素である。
さらに、fake の最後から2番目の要素は key の最後の要素となり、
それを含むペアのもう一方は key の2番目の要素である。
したがって、ペアになっている key の要素を利用し、fake の要素を後ろから求めていくことができる。
さらに、ペアのどっちが key かもわかるので、これを利用して flag にxorした値を求めることもできる。
これらの性質を利用し、以下のプログラムでflagを求めた。
A program gen.py and its output output.txt were given.
What gen.py does is:
key.fake by calculating exclusive-or of elements of key from the next position. The number of elements to exclusive-or is at most one third of the number of elements in key.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.
Regarding how to generate fake, we can tell that the last element of fale before shuffling is 0,
and that another element of the pair that contains 0 is the last element of key.
Also, the second last element of fake should be the last element of key,
and another element of the pair that contains the element should be the second last element of key.
In this way, using the paired element of key, we can obtain the elements of fake from the end.
We also can tell which element of the pairs are from key, so we can use this to obtain the sequence exclusive-ored to flag.
Using this characteristics, I obtained the flag using this program: