HackMyVM 090（crypto）题解

原题

I gave you p and q, it should be easy now or not?

e = 15
p=5787222305777209512262474249244794237065756326718637677563926399912102998238238932691915883680852764360339657453541520126740501334731391462921270092825561
q=10111241397646344099231145262379017618139453896281400953386716762942327959742747939245765751686811392320346902374279922240577945339761221088737443752162629
c=32966311998568049751620491316882873597067466204334745472749990770205777075918461832930873069801888997659326011373601710520150688126730186357963781365253139365104376745890253761612763280897233928482429448491903090758335034298212464171556884740072764043302348824188102589373055730702026853687688157030795220298

解题

这题给了 RSA 的四个数：e、p、q、c。直觉是：有 p 和 q 就能算出私钥 d，然后把 c 解出来。但实际一跑会错：e 和 φ(n)（一个跟 p、q 有关的数）不是“互相配套”的，导致 d 根本算不出来。

把“加密”想成一个工厂流水线，把明文 m 放进去，出来一个密文 c。正常情况下，这条线可逆：你能找到一条“反向流水线”把 c 变回 m。这里的“反向流水线”就是 d。

但这题的 e=15 跟工厂的齿轮比不搭（数学上叫“不是互素”），所以这条“反向流水线”不存在。怎么办？我们就得从“两个分厂”分别入手：
• 分厂 A：模 p 的世界
• 分厂 B：模 q 的世界

因为 n = p × q，可以把问题拆成两个小问题，分别在 A 和 B 中尝试把 c 逆过来。

直接上代码：

# hackmyvm_090_solve.py
#!/usr/bin/env python3
import sys
from math import gcd

# given from the challenge
e = 15
p = 5787222305777209512262474249244794237065756326718637677563926399912102998238238932691915883680852764360339657453541520126740501334731391462921270092825561
q = 10111241397646344099231145262379017618139453896281400953386716762942327959742747939245765751686811392320346902374279922240577945339761221088737443752162629
c = 32966311998568049751620491316882873597067466204334745472749990770205777075918461832930873069801888997659326011373601710520150688126730186357963781365253139365104376745890253761612763280897233928482429448491903090758335034298212464171556884740072764043302348824188102589373055730702026853687688157030795220298

n = p * q

# basic helpers
def inv_mod(a, m):
    # modular inverse when gcd(a,m)==1
    try:
        return pow(a, -1, m)
    except TypeError:
        # fallback extended gcd
        def egcd(x, y):
            if y == 0:
                return (x, 1, 0)
            g, s, t = egcd(y, x % y)
            return (g, t, s - (x // y) * t)
        g, x, _ = egcd(a, m)
        if g != 1:
            raise ValueError("inverse does not exist")
        return x % m

def crt(a1, m1, a2, m2):
    # Chinese Remainder Theorem: solve x ≡ a1 (mod m1), x ≡ a2 (mod m2)
    # m1, m2 coprime (p, q) ⇒ unique mod m1*m2
    # x = a1 + m1 * t, where t ≡ (a2 - a1) * inv(m1, m2) (mod m2)
    t = ((a2 - a1) * inv_mod(m1 % m2, m2)) % m2
    return (a1 + t * m1) % (m1 * m2)

def int_to_bytes(x):
    return x.to_bytes((x.bit_length() + 7) // 8, "big")

def printable_utf8(b):
    try:
        s = b.decode("utf-8")
    except UnicodeDecodeError:
        return None
    # relaxed printable check
    if all((32 <= byte <= 126) or byte in (10, 13, 9) for byte in b):
        return s
    return None

# On each prime field F_p and F_q:
# We know c ≡ m^15 (mod p) and mod q
# Let phi_p = p-1, phi_q = q-1. We work inside multiplicative groups of these orders.
phi_p = p - 1
phi_q = q - 1

gp = gcd(e, phi_p)  # expected to have factor 3 or/and 5
gq = gcd(e, phi_q)

# Decompose e = 3*5, and handle in two stages:
# Stage A: remove factor 3 by exponentiating with s ≡ 3^{-1} mod (phi/g), restricting to the 5th-power image subgroup.
# For a prime field, the map x -> x^5 has kernel size gcd(5, phi) and image size phi / gcd(5, phi).
# We will proceed similarly to the prime-modulus trick but per-prime.

def per_prime_candidates(c_mod, prime):
    phi = prime - 1
    # gcd with e=15
    g = gcd(e, phi)
    # We want to target the 5-th power image subgroup; define k = phi / gcd(5, phi).
    g5 = gcd(5, phi)
    k = phi // g5  # order of the image subgroup of 5th powers

    # Step 1: remove factor 3: choose s ≡ 3^{-1} (mod k), then y = c^s ≡ m^5 (mod prime)
    # 3 and k must be coprime for inverse to exist; if not, the subgroup trick fails.
    if gcd(3, k) != 1:
        raise ValueError(f"On prime {prime}, 3 is not invertible modulo k={k}; cannot reduce exponent 15 to 5.")

    s = inv_mod(3 % k, k)
    y = pow(c_mod, s, prime)  # y ≡ m^5 (mod prime)

    # Step 2: take a 5th root within the image subgroup: t ≡ 5^{-1} (mod k), r = y^t
    if gcd(5, k) != 1:
        raise ValueError(f"On prime {prime}, 5 is not invertible modulo k={k}; cannot take 5th root.")
    t = inv_mod(5 % k, k)
    r = pow(y, t, prime)  # one root up to multiplying by 5th roots of unity

    # Step 3: enumerate all 5th roots of unity to get full candidate set in this field
    # omega in μ_5: omega^5 ≡ 1 (mod prime). We can project small bases to μ_5 using base^k.
    omegas = set()
    for base in (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53):
        z = pow(base, k, prime)
        if pow(z, 5, prime) == 1:
            omegas.add(z)
    # Ensure we have nontrivial root(s)
    if omegas == {1} or len(omegas) == 0:
        # fallback random search to find at least one nontrivial omega
        import random
        for _ in range(500):
            base = random.randrange(2, prime - 1)
            z = pow(base, k, prime)
            if z != 1 and pow(z, 5, prime) == 1:
                omegas.add(z)
                break
        if len(omegas) == 0:
            # If even then only trivial root exists (rare), still enumerate with omega=1
            omegas.add(1)

    candidates = []
    # multiply r by each distinct omega^i, i=0..4
    # construct one generator omega0 if possible
    omega0 = None
    for z in omegas:
        if z != 1:
            omega0 = z
            break
    if omega0 is None:
        # only trivial root found
        cand = [r]
    else:
        cand = [(r * pow(omega0, i, prime)) % prime for i in range(5)]
    candidates.extend(cand)
    # Remove duplicates
    candidates = list(dict.fromkeys(candidates))
    return candidates

# Reduce c modulo p, q
c_p = c % p
c_q = c % q

# Get per-prime candidate sets
cand_p = per_prime_candidates(c_p, p)
cand_q = per_prime_candidates(c_q, q)

# Combine with CRT to get candidates modulo n
combined = []
for mp in cand_p:
    for mq in cand_q:
        m = crt(mp, p, mq, q)
        combined.append(m)

# Deduplicate combined candidates
combined = list(dict.fromkeys(combined))

# Try to find a readable plaintext among candidates
found_printable = []
for m in combined:
    b = int_to_bytes(m)
    s = printable_utf8(b)
    if s is not None:
        found_printable.append((m, s))

# Output
print(f"n = {n}")
print(f"number of per-prime candidates: |P|={len(cand_p)}, |Q|={len(cand_q)}, combined={len(combined)}")
if found_printable:
    print("Readable UTF-8 candidates:")
    for m, s in found_printable:
        print("----")
        print(s)
else:
    # If no readable, still show hex for inspection
    print("No readable UTF-8 candidate found. Showing hex of all candidates:")
    for i, m in enumerate(combined):
        hb = int_to_bytes(m).hex()
        print(f"[{i}] {hb}")

flag 的内容自然回答了上面我说的问题。