2026 能源网络安全大赛 crypto 1

某个老旧的认证网关会把用户登录时生成的令牌写入审计日志。为了兼容两套接口同一个用户的令牌会以两种格式出现一种带有固定开头另一种带有固定结尾。管理员只找到了两条被同一把RSA公钥加密后的日志以及这两种格式的固定部分。 附件给出了RSA公钥参数、两条日志密文和格式字段。请还原日志里真正变化的那段内容。那段内容就是本题 flag。 N 360160431418936027647973763227730297198312456973297014753701862390944095948209710865168062900765115482676342627427860640372919930726517354690011396239360571623183867955043628673182538807306881236971281754931345759469893824333387093400665939139553170393069017697920443347 e 5 prefix 757365723d suffix 26726f6c653d6775657374 c1 164511231253586308095953101740242519262792546778667653506610168961040622243307867473918714863661079239715212772847859539456988301054851868890096754872652537757300421437709556647150197402896131341639158359666826016481730357151336374676700222847165503493823818845945522292 c2 156020674359253673064018297675062012644921552390938310215444486436462114471203666581177539177641340140411423284704895117785228370089610476884289317205046011532681884243740026683378109919087121992612230901797861149599397079780995167802981950374498456012680293558794346928wp# Parameters given N 360160431418936027647973763227730297198312456973297014753701862390944095948209710865168062900765115482676342627427860640372919930726517354690011396239360571623183867955043628673182538807306881236971281754931345759469893824333387093400665939139553170393069017697920443347 e 5 prefix_hex 757365723d suffix_hex 26726f6c653d6775657374 c1 164511231253586308095953101740242519262792546778667653506610168961040622243307867473918714863661079239715212772847859539456988301054851868890096754872652537757300421437709556647150197402896131341639158359666826016481730357151336374676700222847165503493823818845945522292 c2 156020674359253673064018297675062012644921552390938310215444486436462114471203666581177539177641340140411423284704895117785228370089610476884289317205046011532681884243740026683378109919087121992612230901797861149599397079780995167802981950374498456012680293558794346928 # Lets decode the prefix and suffix strings prefix_bytes bytes.fromhex(prefix_hex) suffix_bytes bytes.fromhex(suffix_hex) print(prefix:, prefix_bytes,int.from_bytes(prefix_bytes,big).bit_length()) print(suffix:, suffix_bytes,int.from_bytes(suffix_bytes,big).bit_length()) # Lets see the bit length of N print(N bit length:, N.nbits()) # We know m1 has a fixed prefix: m1 prefix || flag - in integer: m1 prefix * 2^(8*len(flag)) flag # We know m2 has a fixed suffix: m2 flag || suffix - in integer: m2 flag * 2^(8*len(suffix)) suffix # Let x be the integer value of the flag. # Let L_flag be the byte length of the flag. # Then m1 P * 2^(8 * L_flag) x # m2 x * 2^(8 * L_suffix) S # Since e 5 is very small, and we have polynomial relationships between m1 and m2, this is a Franklin-Reiter Related Message Attack or Coppersmiths short pad attack variant, but here we can define equations in terms of x! # m1^5 - c1 0 mod N # m2^5 - c2 0 mod N # Both equations have a common root x. We can find the length of the flag first. # Lets guess the length of the flag. The prefix is 5 bytes, suffix is 10 bytes. # If N is 1024-bit (128 bytes), then the message size is usually around 128 bytes or less. # Lets find L_flag. # Lets write a script to check if we can find the GCD of the two polynomials in x. import sympy from sympy import symbols, gcd # We can use the resultant or univariate polynomial GCD modulo N. Since N is composite, standard GCD might fail if it hits a factor of N, which would actually give us p or q (even better!). # Lets implement polynomial GCD modulo N or just use sage-like methods or simple resultant. # Wait, lets look at the relation: # m1 A * x B, where A 2^(8*L_flag), B P * 2^(8*L_flag) -- wait! m1 prefix || flag - m1 (prefix_int * 2^(8*L_flag)) x # m2 flag || suffix - m2 (x * 2^(8*10)) suffix_int # Lets check typical length of flag. Usually flag format is flag{...} or just a token hex string. # Lets write a function to compute GCD of polynomials over Z_N. def poly_gcd(g1, g2, N): # g1, g2 are lists of coefficients, highest degree first # standard Euclidean algorithm with inversion mod N while len(g2) 0: # remove leading zeros while len(g2) 0 and g2[0] 0: g2 g2[1:] if len(g2) 0: break # normalize g2 so leading coefficient is 1 lc g2[0] try: inv_lc pow(lc, -1, N) except ValueError: # We found a factor of N! g math.gcd(lc, N) return g g2 [(c * inv_lc) % N for c in g2] # division: g1 q * g2 r while len(g1) len(g2): factor g1[0] deg_diff len(g1) - len(g2) for i in range(len(g2)): g1[i] (g1[i] - factor * g2[i]) % N g1 g1[1:] # leading term becomes 0 g1, g2 g2, g1 return g1 # Lets test lengths for L_flag. Lets find out how many bytes N is: n_bytes (N.nbits() 7) // 8 print(N bytes:, n_bytes) # Lets try L_flag from 1 to 100 prefix_int int(prefix_hex, 16) suffix_int int(suffix_hex, 16) L_suffix len(suffix_bytes) # Expand (A*x B)^5 - c1 and (C*x D)^5 - c2 # m1 A1*x B1, where A1 1, B1 prefix_int * 2^(8*L_flag) # m2 A2*x B2, where A2 2^(8*L_suffix), B2 suffix_int import math for L_flag in range(1, 100): B1 (prefix_int (8 * L_flag)) % N A1 1 A2 pow(2, 8 * L_suffix, N) B2 suffix_int % N # We want to find the coefficients of (A1*x B1)^5 - c1 # (x B1)^5 - c1 x^5 5*B1*x^4 10*B1^2*x^3 10*B1^3*x^2 5*B1^4*x B1^5 - c1 g1 [ 1, (5 * B1) % N, (10 * pow(B1, 2, N)) % N, (10 * pow(B1, 3, N)) % N, (5 * pow(B1, 4, N)) % N, (pow(B1, 5, N) - c1) % N ] # (A2*x B2)^5 - c2 g2 [ pow(A2, 5, N), (5 * pow(A2, 4, N) * B2) % N, (10 * pow(A2, 3, N) * pow(B2, 2, N)) % N, (10 * pow(A2, 2, N) * pow(B2, 3, N)) % N, (5 * A2 * pow(B2, 4, N)) % N, (pow(B2, 5, N) - c2) % N ] res poly_gcd(g1, g2, N) if isinstance(res, list) and len(res) 2: # degree 1 polynomial: [1, -root] - x - root 0 - x -root root (-res[1]) % N print(fFound root for L_flag {L_flag}!) try: # L_flag 26对应的字节数就是 26 flag_bytes int(root).to_bytes(26, byteorderbig) # 使用 errorsignore 或 replace 防止因为极个别非 ASCII 字符导致整个解码崩溃 print(Flag:, flag_bytes.decode(utf-8, errorsignore)) except Exception as e: print(转换失败:, e) break elif isinstance(res, int) and res 1: print(fFound factor of N: {res}) break