某个老旧的认证网关会把用户登录时生成的令牌写入审计日志。为了兼容两套接口，同一个用户的令牌会以两种格式出现：一种带有固定开头，另一种带有固定结尾。管理员只找到了两条被同一把RSA公钥加密后的日志，以及这两种格式的固定部分。
附件给出了RSA公钥参数、两条日志密文和格式字段。请还原日志里真正变化的那段内容。那段内容就是本题 flag。

N = 360160431418936027647973763227730297198312456973297014753701862390944095948209710865168062900765115482676342627427860640372919930726517354690011396239360571623183867955043628673182538807306881236971281754931345759469893824333387093400665939139553170393069017697920443347
e = 5
prefix = 757365723d
suffix = 26726f6c653d6775657374
c1 = 164511231253586308095953101740242519262792546778667653506610168961040622243307867473918714863661079239715212772847859539456988301054851868890096754872652537757300421437709556647150197402896131341639158359666826016481730357151336374676700222847165503493823818845945522292
c2 = 156020674359253673064018297675062012644921552390938310215444486436462114471203666581177539177641340140411423284704895117785228370089610476884289317205046011532681884243740026683378109919087121992612230901797861149599397079780995167802981950374498456012680293558794346928

wp

# Parameters given
N = 360160431418936027647973763227730297198312456973297014753701862390944095948209710865168062900765115482676342627427860640372919930726517354690011396239360571623183867955043628673182538807306881236971281754931345759469893824333387093400665939139553170393069017697920443347
e = 5
prefix_hex = "757365723d"
suffix_hex = "26726f6c653d6775657374"
c1 = 164511231253586308095953101740242519262792546778667653506610168961040622243307867473918714863661079239715212772847859539456988301054851868890096754872652537757300421437709556647150197402896131341639158359666826016481730357151336374676700222847165503493823818845945522292
c2 = 156020674359253673064018297675062012644921552390938310215444486436462114471203666581177539177641340140411423284704895117785228370089610476884289317205046011532681884243740026683378109919087121992612230901797861149599397079780995167802981950374498456012680293558794346928

# Let's 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())

# Let's 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 Coppersmith's 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.
# Let's 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.
# Let's find L_flag.
# Let's 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!).
# Let's implement polynomial GCD modulo N or just use sage-like methods or simple resultant.
# Wait, let's 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
# Let's check typical length of flag. Usually flag format is flag{...} or just a token hex string.
# Let's 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

# Let's test lengths for L_flag. Let's find out how many bytes N is:
n_bytes = (N.nbits() + 7) // 8
print("N bytes:", n_bytes)

# Let's 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(f"Found root for L_flag = {L_flag}!")
        try:
            # L_flag = 26，对应的字节数就是 26
            flag_bytes = int(root).to_bytes(26, byteorder='big')
            # 使用 errors='ignore' 或 'replace' 防止因为极个别非 ASCII 字符导致整个解码崩溃
            print("Flag:", flag_bytes.decode('utf-8', errors='ignore'))
        except Exception as e:
            print("转换失败:", e)
        break
    elif isinstance(res, int) and res > 1:
        print(f"Found factor of N: {res}")
        break