プログラム task.py と、その出力 output.txt が与えられた。
task.py は、以下の処理をするものだった。
p および2～p の乱数 g, r を生成する。p と g を出力する。
flag.txt 中の各バイト m について、g を r*m 乗して p で割った値を出力する。
flag.txt の内容が CakeCTF{ で始まっていると仮定すると、以下のことがわかる。
g の r*70 乗 (7バイト目に対応する) を g の r*67 乗 (1バイト目に対応する) で割ることで、g の r*3 乗が得られる。g の r*101 乗 (4バイト目に対応する) を g の r*97 乗 (2バイト目に対応する) で割ることで、g の r*4 乗が得られる。g の r*4 乗を g の r*3 乗で割ることで、g の r 乗が得られる。g の r 乗を何乗すると出力中の値になるかを調べることで、flag.txt の各バイトの値がわかる。これに基づき、以下のプログラムでflagが得られた。
A program task.py and its output output.txt were given.
What task.py does was:
p and random values g, r in the range from 2 to p.p and g.m in flag.txt, output g to the r*m-th power modulo p.
Assuming that the contents of flag.txt begins with CakeCTF{, we can say following things:
g to the r*4-th power
by dividing g to the r*70-th power (corresponding to the 7th byte)
by g to the r*67-th power (corresponding to the 1st byte).g to the r*3-th power
by dividing g to the r*101-th power (corresponding to the 4th byte)
by g to the r*97-th power (corresponding to the 2nd byte).g to the r-th power
by dividing g to the r*4-th power by g to the r*3-th power.flag.txt by searching for b such that g to the r-th power to the b-th power is the value in the given output.I obtained the flag via following program based on this.