[Crypto] Primordial

This is a puzzle from the ASIS CTF Final 2019.

Here, we're faced with the identical set-up to Serifin. Given $N = p_1p_2$, a product of two primes, and $c = m^{65537} \pmod{N}$ where $m$ is our message, determine $m$.

N = 129267954332200676615739227295907855158658739979210900708976549380609989409956408435684374935748935918839455337906315852534764123844258593239440161506513191263699117749750762173637210021984649302676930074737438675523494086114284695245002078910492689149197954131695708624630827382893369282116803593958219295071;

c = 123828011786345664757585942310038992331055176660679165398920365204623335291878173959876308977115607518900415801962848580747200997185606420410437572095447682798017319498742987210291931673054112968527192210375048958877146513037193636705010232608708929769672565897606711155251354598146987357344810260248226805138;

The vulnerability once again is due to poor generation of the 512-bits primes $p_1$ and $p_2$.

def primorial(p):

    # Computes the product of all primes <= p

    q = 1

    s = 1

    while q < p:

        r = gmpy2.next_prime(q)

        if r <= p:

            s *= r

            q = r

        else:

            break

    return s

def gen_prime(nbit):

    while True:

        s = getPrime(36)

        # Generates a Random 36 Bit Prime

        a = primorial(getPrime(random.randint(7, 9))) #[7, 9] inclusive

        b = primorial(getPrime(random.randint(2, 5))) #[2, 5] inclusive

        for r in range(10**3, 3*10**3, 2):

            p = (s * a // b) - r

            if gmpy2.is_prime(p) and len(bin(p)[2:]) == nbit:

                # Checks that p is prime and with nbit bits.

                return int(p)

Let us denote the primorial of $n$ as $n\#$. We can see that our primes will be of the form,

where $s$ is a 36 bit prime, $a_i \in [67, 509]$, $b_i \in [2, 31]$ and $r_i \in [10^3, 3\cdot 10^3]$. Our first step is to find $r_1$ and $r_2$.

Observe that

Hence, we expect by enumerating all the possible $r_i$, and then compute $N - r_1r_2$, we would expect to find a number that is divisible by all the primes in $(31, 67]$.

using Pkg; Pkg.add("Primes")

using Primes

function Findrs()

  Divisors = BigInt.(primes(32, 67)) # Exclude 31

  Π = prod(Divisors)

  for r1 in 1000:2:3000

    for r2 in r1:2:3000

      (N - r1*r2) % Π == 0 && return (r1, r2)

    end

  end

end

r1, r2 = Findrs()

Without loss of generality, let $r_1 \leq r_2.$ When we reach this stage we thought of two directions to proceed.

• Enumerate all the possible $s_i$, then compute the possible $a_i$ and $b_i$ such that $p_i$ is a 512-bits prime. This is potentially feasible, but may take a few hours, as such was not the direction we greatly pursued.

• If we are lucky, $\lambda_1 = \min(a_1,a_2) << \lambda_2 = \max(a_1, a_2)$. Then, we can consider modulo $\frac{\lambda_2\#}{\lambda_1\#}$ and reconstruct a small list of possible $s_i$. This was indeed the direction we have taken.

First let us compute $\max(b_1,b_2)$ and $\min(a_1,a_2)$.

filter(x -> (N - r1*r2) % x == 0, primes(1<<9) )

It is very likely that $\max(b_1,b_2) = 31$ and $\min(a_1,a_2) = 379$. We then perform the following algorithm.

function CRT(N, Residue)

  Π = prod(N)

  mod(sum(ai * invmod(Π ÷ ni, ni) * Π ÷ ni for (ni, ai) in zip(N, Residue)), Π)

end

function Finds1()

  Mods = primes(383, 419) # This is as prod(Mods) will be large than a 31 bit s_1

  Π = prod(BigInt.(Mods))

  # t = s_1*r_2*a_1#/b_1# or t = s_2*r_1*a_2#/b_1#

  t = Π - CRT(Mods, (N - r1*r2) .% Mods)

  # We try possible b_i

  b = 380 # min(a_1, a_2) + 1, we call prevprime to get 379

  while b > 2

    b = prevprime(b-1)

    t *= invmod(b, Π); t %= Π

    # Assume t = s_1

    s1 = t * invmod(r2, Π); s1 %= Π

    p1 = s1*prod(BigInt.(primes(b, 379))) - r1

    (N % p1 == 0) && return p1

    # Else t = s_2

    s2 = t * invmod(r1, Π); s2 %= Π

    p2 = s2*prod(BigInt.(primes(b, 379))) - r2

    (N % p2 == 0) && return p2

  end

  return -1

end

Finds1()

As it turns out, approach 2 doesn't work as $a_1$ and $a_2$ are too close (the precise reason will be clear in a minute). Thus, the above code sadly returns -1. While doing this process, we found a third method.

• Let $K = \frac{379\#}{29\#}.$ Then there exist $c_i$ such that $p_i = c_iK -r_i$. Then,

Hence, as $K$ is really big, we can find $c_i$ by solving a quadratic equation.

In fact, more is true as

K = prod(BigInt.(primes(31, 379)))

36 + log2(K)

Thus, $c_i = s_i$! This explains why the previous method had no chance of working, indeed we have

Let us compute $s_i$, shall we?

Sum = (K - ((N - r1*r2) ÷ K) % K)

Prod = (N - r1*r2 + Sum*K) ÷ K^2

s2, s1 = map(first, factor(Prod).pe) # The order needs to be checked

Now with the private key, we just need to undo the RSA.

function long_to_bytes(Val)

  Val == 0 && return ""

  return long_to_bytes(Val ÷ 256) * Char(Val % 256)

end

p1 = s1*K - r1

p2 = s2*K - r2

invert(message, prime) = powermod(c, invmod(65537, prime - 1), prime)

m = CRT([p1, p2], [invert(c, p1), invert(c, p2)]) % N

long_to_bytes(m)