supercomputer
プログラムsupercomputer.pyと、その出力output.txtが与えられた。
supercomputer.pyは、以下の処理をするものだった。
- ランダムな2048ビットの素数
p、q、rを生成する。
p、q、rを出力する。pのq乗にrを掛けたものをnとする。- 0～
nの整数乱数a1を生成する。
a1のn乗と、n-a1のn乗の和を計算し、tとする。tが何回pで割り切れるかの値と、flagのXORを出力する。
性質を調査するため、以下のプログラムを用い、小さい素数で実験を行った。
A program supercomputer.py and its output output.txt were given.
What supercomputer.py does is:
- Generate random 2048-bit prime numbers
p, q, and r.
- Output
p, q, and r.
- Calculate
p to the q-th power multiplied by r and name it n.
- Generate an random integer between 0 and
n, and name it a1.
- Calculate the sum of "
a1 to the n-th power" and "n-a1 to the n-th power", and name it t.
- Output an exclusive-or of
flag and "the times t can be divided by p".
To find its properties, I used this program to do some experiments with some small prime numbers.
small_test.py
実験の結果、例外は見られたが、多くの場合においてtがpで割り切れる回数はqの2倍となった。
そこで、qの2倍の値を出力にXORしたところ、flagが得られた。
As a result, with some exception, the times t can be divided by p became the double of q in many cases.
Seeing this, I applied XOR of the value of q doubled and it resulted in the flag.
Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> q = 19872523115298089612152987731023453644084277408261276810219001288407280019889227914287760742936580023163800626696116882213533508813201232707621762739857924392306902336092739272758773377952936022982446120177174082641600741522817135305633293579042208014735900229922142564590095968054337719254632703676737069746032384348392244892496672044899073391936273280270753785076044108870166304800552404013519058026991588856235381264192387525832530187004466616791531223421070547342377071358044704265893255021275811622959301157507095984825182110574434699593886509171425701861331576642311553357835312334349976576969220483604368671153
>>> hex(q * 2)
'0x13ad766cd0fc5b02ac7f60ca217b51b92e1cbc5cc5b800cb1a56d6510270fa25477b266ac31210bd9551b163c467c514479d6b8ca4d6294c9bf946c597998e31861295ff92b2391431a87789692caf9f1da61c07fee7675892fef9124d04ecd2352e6dfd2bbe7b151a5958aa23f8de4acbc0b2fc2534a46a55217c311dca5c57cad1de3b11d32be5d2372b7e1c3a4a40df0d11d7df847762f76df57a3398e5cbd5a134bf21a8a256af8dd7feba7fff2258463bf3a1ee33438a4a70d1b3629b462160e21e06ebf64048bededf50078426c520b7c139e6bf20690bf533cd826688587693e594f19a65b4d47335d2648368f42a6c520816ccc29258954c53d6a8362'
From Hex, XOR - CyberChef
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
corCTF 2021