SECCON 2020 Online CTF writeup

SECCON 2020 Online CTF に Wani Hackase で参戦して 44 位でした。 面白そうな問題が多かったけど、24時間が思ったより短く、あっという間に終わってしまった… This is RSA [Crypto, 62 solves] 特殊な素数生成を行っている。16 進数で 2 桁ずつ見ていくと、[$0\rm{x}30,0\rm{x}39$] の範囲に収まっている。これが枝刈りとして効いていて、下位の桁から探索していくと素因数分解できる。 1import sys 2from itertools import product 3 4from Crypto.Util.number import * 5 6from output import N, c 7 8sys.setrecursionlimit(10000) 9e = 0x10001 10 11def dfs(D, P, Q): 12 if D == 200 or P*Q == N: 13 if P*Q != N: 14 return 15 d = pow(e, -1, (P-1)*(Q-1)) 16 m = pow(c, d, N) 17 print(long_to_bytes(m)) 18 exit(0) 19 20 for i, j in product(range(10), repeat=2): 21 p = 3<<(8*D+4) | i<<(8*D) | P 22 q = 3<<(8*D+4) | j<<(8*D) | Q 23 mask = (1<<(8*D+8)) - 1 24 if (p*q)&mask == N&mask: 25 dfs(D+1, p, q) 26 27dfs(0, 0, 0) Flag: SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?} koharu [Crypto, 44 solves] Quadratic residueか否かを判定することで 0 or 1 を決める。多項式に対しても Legendre Symbol のようなものが計算できれば解けそう。