PCAT - Mission Impossible

Name: Mission Impossible
Type: crypto
Author: badmonkey
Desc: 希望你也有阿汤哥一般的数理基础（本题附件于2021.8.9更新）
Link: nc 159.75.177.153 10000
Attach: http://159.75.177.153/att/task_new.py
Tips: None

Challenge source

#!/usr/bin/env python3

flag = open("/home/ctf/flag", "rb").read()


def isPrime(n):
    if int(n).bit_length() < 444:
        return False
    basis = [
        2,
        3,
        5,
        7,
        11,
        13,
        17,
        19,
        23,
        29,
        31,
51 collapsed lines
        37,
        41,
        43,
        47,
        53,
        59,
        61,
        67,
        71,
        73,
        79,
    ]
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for b in basis:
        x = pow(b, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def get_flag():
    try:
        p = int(input("give me your P:"))
        q = int(input("give me your Q:"))
        r = int(input("give me your R:"))
        n = int(input("give me your N:"))

        if isPrime(p) and isPrime(q) and isPrime(r) and isPrime(n) and p * q * r == n:
            if n.bit_length() < 1024:
                print("It's 2021 now,young man.")
                return
            m = int.from_bytes(flag, "big")
            print("here is your flag %d" % pow(m, 0x10001, n))
        else:
            print("mission impossible. CIA needed")
        return
    except:
        print("wrong")
    return


if __name__ == "__main__":
    get_flag()
    exit(1)

Core idea

The service asks for P, Q, R, N such that:

isPrime(P), isPrime(Q), isPrime(R), and isPrime(N) are all true.
$N = P \times Q \times R$ .
N has at least 1024 bits.

N is obviously composite, so the key is to make N a strong pseudoprime for all hardcoded Miller-Rabin bases.

Construction outline

Use an Arnault-style construction with:

$P = ak + 1$
$Q = bk + 1$
$R = ck + 1$

Choose a, b, c as distinct primes with $a,b,c \equiv 1 \pmod{8}$ (for base-2 behavior), e.g. 89, 113, 137.

To make $(P-1), (Q-1), (R-1)$ divide $(N-1)$ , solve the congruence system:

k ≡ -(b+c)(bc)^(-1) (mod a)
k ≡ -(a+c)(ac)^(-1) (mod b)
k ≡ -(a+b)(ab)^(-1) (mod c)

For odd MR bases $B \in \{3,5,\ldots,79\}$ , force $k \equiv 0 \pmod{B}$ . Also force $k \equiv 2 \pmod{4}$ so $P,Q,R \equiv 3 \pmod{4}$ .

Then scan k until P, Q, R are all truly prime (with a strong primality test like sympy.isprime).

Solver script

#!/usr/bin/env python3
from math import prod

import sympy
from sympy.ntheory.modular import crt


def solver():
    bases = [
        3,
        5,
        7,
        11,
        13,
        17,
        19,
        23,
        29,
        31,
        37,
49 collapsed lines
        41,
        43,
        47,
        53,
        59,
        61,
        67,
        71,
        73,
        79,
    ]
    base_prod = prod(bases)

    a, b, c = 89, 113, 137

    y_a = (-(b + c) * pow(b * c * base_prod, -1, a)) % a
    y_b = (-(a + c) * pow(a * c * base_prod, -1, b)) % b
    y_c = (-(a + b) * pow(a * b * base_prod, -1, c)) % c
    y_4 = 2

    y_base, y_mod = crt([a, b, c, 4], [y_a, y_b, y_c, y_4])

    k_base = base_prod * int(y_base)
    k_mod = base_prod * int(y_mod)

    min_k = (1 << 444) // a + 1
    start_i = (min_k - k_base) // k_mod + 1
    if start_i < 0:
        start_i = 0

    for i in range(start_i, start_i + 1_000_000):
        k = k_base + i * k_mod

        p = a * k + 1
        if not sympy.isprime(p):
            continue

        q = b * k + 1
        if not sympy.isprime(q):
            continue

        r = c * k + 1
        if not sympy.isprime(r):
            continue

        n = p * q * r
        print(f"P = {p}")
        print(f"Q = {q}")
        print(f"R = {r}")
        print(f"N = {n}")
        return p, q, r, n

    raise RuntimeError("No solution found in current search window")


if __name__ == "__main__":
    solver()

Ciphertext from remote

21903103496980081373563573693903562346746553643549818726007975948477827819459765088909748053913796144132553228584337940471254732244734196780412249598279393335004210910953390996721397236654824645841526330517109905833017093822718222876587329963794042086917871402474385749212962074053842003782042533173326441388721313429460738550791493248565473365397568505962364729491646535933145902419195195919991941091

RSA decryption (3-prime)

Once P, Q, R are known, decrypt like standard RSA:

$\varphi(N) = (P-1)(Q-1)(R-1)$
$d = e^{-1} \bmod \varphi(N)$ with $e=65537$
$m=c^{d} \bmod N$

def decrypt(p, q, r, c):
    e = 0x10001
    n = p * q * r
    phi = (p - 1) * (q - 1) * (r - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)

    size = (m.bit_length() + 7) // 8
    msg = m.to_bytes(size, "big")
    print(msg.decode("utf-8", errors="ignore"))


if __name__ == "__main__":
    P = 45427420268475430659332737993000283397102585042957378767593137448789955507087370207886940708232722175257488588695287994058256318553211
    Q = 57677511127390153533759543743921708133399911346676222480202522828238932273043514983047464045284242761843777646320983632905426561758571
    R = 69927601986304876408186349494843132869697237650395066192811908207687909038999659758207987382335763348430066703946679271752596804963931
    C = 21903103496980081373563573693903562346746553643549818726007975948477827819459765088909748053913796144132553228584337940471254732244734196780412249598279393335004210910953390996721397236654824645841526330517109905833017093822718222876587329963794042086917871402474385749212962074053842003782042533173326441388721313429460738550791493248565473365397568505962364729491646535933145902419195195919991941091

    decrypt(P, Q, R, C)