1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
| # solve.py -- pure Python exp (no Sage) import math from collections import Counter from Crypto.Cipher import AES from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import unpad import sympy as sp
# --------------------- paste instance data here --------------------- p = 14668080038311483271 C = [ [11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707], ] D = [ [1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395], ] msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j" # -------------------------------------------------------------------
def mat_eigs_modp(M_list, p): """Return eigenvalues of integer matrix modulo p (with multiplicity).""" M = sp.Matrix([[x % p for x in row] for row in M_list]) lam = sp.symbols('lam') # charpoly over ZZ then reduce mod p to avoid Mod-wrapping headaches cpZZ = sp.Poly(M.charpoly(lam).as_expr(), lam, domain='ZZ') coeffs = [int(c) % p for c in cpZZ.all_coeffs()] poly_mod = sp.Poly( sum(coeffs[i] * lam ** (len(coeffs) - 1 - i) for i in range(len(coeffs))), lam, modulus=p ) # factor over F_p _, factors = poly_mod.factor_list() eigs = [] for fac, mult in factors: # fac is (lam - alpha) or lam + beta, all linear over F_p for our instance if fac.degree() != 1: # Fallback: numerically find roots over F_p (rare) # Try brute over small deg - should not happen for 5x5 here raise ValueError("Nonlinear factor appeared; adjust routine.") # root of a*lam + b ≡ 0 => lam ≡ -b * a^{-1} a = fac.all_coeffs()[0] % p b = fac.all_coeffs()[1] % p root = (-b * pow(a, -1, p)) % p eigs.extend([root] * mult) return eigs
def crt(remainders, moduli): """Chinese remainder theorem, pairwise coprime moduli.""" x, M = 0, 1 for (r, m) in zip(remainders, moduli): # solve x ≡ r (mod m) and x ≡ x (mod M) # -> find t: M*t ≡ (r - x) (mod m) t = ((r - x) * pow(M, -1, m)) % m x += M * t M *= m return x % M, M
def baby_step_giant_step(g, h, p, order): """Solve g^x = h in subgroup of order 'order' ⊂ F_p^* using BSGS.""" m = int(math.isqrt(order)) + 1 # baby steps: g^0..g^{m-1} table = {} e = 1 for j in range(m): table.setdefault(e, j) e = (e * g) % p g_inv_m = pow(pow(g, m, p), -1, p) gamma = h for i in range(m + 1): if gamma in table: return (i * m + table[gamma]) % order gamma = (gamma * g_inv_m) % p raise ValueError("log not found (inconsistent inputs)")
def discrete_log_pohlig_hellman(g, h, p): """Return x s.t. g^x = h mod p, using PH over factors of p-1.""" n = p - 1 # factorization of n (64-bit here; sympy is fine). If too slow for you, replace with Pollard-Rho. fac = sp.factorint(n) # {q: e} residues = [] moduli = [] for q, e in fac.items(): q_pow = q ** e # Work in subgroup of order q_pow # Set g1 = g^{n/q_pow}, h1 = h^{n/q_pow} g1 = pow(g, n // q_pow, p) h1 = pow(h, n // q_pow, p) # Solve for x modulo q_pow by lifting (standard PH lifting) x_qe = 0 g_inv = pow(g1, -1, p) for k in range(e): # Compute c_k = h1 * (g1^{-x_qe})^{1} then raise to (q^{e-1-k}) c = (h1 * pow(g_inv, x_qe, p)) % p # exponent to collapse to order q exp = pow(q, e - 1 - k) c_k = pow(c, exp, p) g_k = pow(g1, exp, p) d = baby_step_giant_step(g_k, c_k, p, q) # in subgroup of order q x_qe = x_qe + d * pow(q, k) residues.append(x_qe) moduli.append(q_pow) x, _ = crt(residues, moduli) return x % n
def recover_key_from_eigs(p, eigC, eigD): """Try all pairings; return the consistent key (mod p-1).""" nonzeroC = [x for x in eigC if x % p != 0] nonzeroD = [x for x in eigD if x % p != 0] candidates = [] for lam in nonzeroC: for mu in nonzeroD: # same subgroup check if mu == 1 and lam == 1: candidates.append(0) continue try: k = discrete_log_pohlig_hellman(lam % p, mu % p, p) except Exception: continue candidates.append(k) if not candidates: raise RuntimeError("No candidate keys found.") # pick the most frequent k (they应当一致) k, _ = Counter(candidates).most_common(1)[0] return k
def main(): eigC = mat_eigs_modp(C, p) eigD = mat_eigs_modp(D, p) # print("eigC =", eigC) # print("eigD =", eigD)
key_mod = recover_key_from_eigs(p, eigC, eigD) # key is in [2^62, p), 但我们只需要与 p-1 同余,即用于 AES 不影响(原题直接 pad(long_to_bytes(key),16)) key_bytes = long_to_bytes(key_mod) # pad 至 16 的倍数与出题脚本一致 padlen = (16 - (len(key_bytes) % 16)) % 16 if padlen: key_bytes = key_bytes + b"\x00" * padlen
aes = AES.new(key_bytes, AES.MODE_ECB) pt = aes.decrypt(msg) # 原题对 flag 做了 pad(flag, 64) try: flag = unpad(pt, 64) except ValueError: # 如果出题脚本用了固定 blocksize=64 的 pad,这里尝试手动剥离 # 简单兜底:去掉末尾整块的 PKCS#7(若失败就直接打印原文) try: flag = unpad(pt, 16) except ValueError: flag = pt
print("[+] key (mod p-1) =", key_mod) print("[+] AES key bytes (padded) =", key_bytes) print("[+] flag =", flag)
if __name__ == "__main__": main()
|