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 のようなものが計算できれば解けそう。
ググったらそれらしきものが出てきた。
http://www.fen.bilkent.edu.tr/~franz/nt/ch12.pdf
1from sage.all import *
2from Crypto.Util.number import *
3
4p = 4832823609987476353
5PR.<x> = PolynomialRing(GF(p))
6sage.repl.load.load('output.sage', globals())
7
8
9fac = PQ.factor()
10P, Q = fac[0][0], fac[1][0]
11
12NP = p**P.degree()
13NQ = p**Q.degree()
14flag = 0
15
16for i, poly in enumerate(c):
17 if power_mod(poly, (NP-1)//2, P) == 1 and power_mod(poly, (NQ-1)//2, Q) == 1:
18 flag |= 1<<i
19
20print(long_to_bytes(flag))
Flag: SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}