Published on

Cyber Grabs CTF 0x03 – Unbr34k4bl3

Authors
  • avatar
    Name
    michael
    Description
    Associate Researcher at SIFT

Unbr34k4bl3

No one can break my rsa encryption, prove me wrong !!

Flag Format: cybergrabs{}

Author: Mritunjya

output.txt source.py

Looking at the source code, this challenge looks like a typical RSA challenge at first, but there are some important differences to note:

  • n=pqrn = pqr (line 34). This is a twist but RSA strategies can easily be extended to 3 prime components.
  • p,q3mod4p, q \equiv 3 \bmod 4 (line 19). This suggests that the cryptosystem is actually a Rabin cryptosystem.
  • We’re not given the public keys e1e_1 and e2e_2, but they are related through xx.

Finding e1e_1 and e2e_2

We know that e1e_1 and e2e_2 are related through xx, which is some even number greater than 2, but we’re not given any of their real values. We’re also given through an oddly-named functor function that:

1+e1+e12++e1x=1+e2+e221 + e_1 + e_1^2 + \cdots + e_1^x = 1 + e_2 + e_2^2

Taking the entire equation mod e1\bmod\ e_1 gives us:

11+e2+e22(mode1) 0e2+e22 0e2(1+e2)\begin{aligned} 1 &\equiv 1 + e_2 + e_2^2 \pmod {e_1} \\\ 0 &\equiv e_2 + e_2^2 \\\ 0 &\equiv e_2(1 + e_2) \end{aligned}

This means there are two possibilities: either e1=e2e_1 = e_2 or e1e_1 is even (since we know e2e_2 is a prime). The first case isn’t possible, because with x>2x > 2, the geometric series equation would not be satisfied. So it must be true that e1=2\boxed{e_1 = 2}, the only even prime.

Applying geometric series expansion, 1+e2+e22=2x+111 + e_2 + e_2^2 = 2^{x + 1} - 1. We can rearrange this via the quadratic equation to e2=1±14(22x+1)2e_2 = \frac{-1 \pm \sqrt{1 - 4 (2 - 2^{x + 1})}}{2}. Trying out a few values we see that only x=4\boxed{x = 4} and e2=5\boxed{e_2 = 5} gives us a value that make e2e_2 prime.

Finding pp and qq

We’re not actually given pp or qq, but we are given ip=p1modqip = p^{-1} \bmod q and iq=q1modpiq = q^{-1} \bmod p. In order words:

p×ip1modq q×iq1modp\begin{aligned} p \times ip &\equiv 1 \bmod q \\\ q \times iq &\equiv 1 \bmod p \end{aligned}

We can rewrite these equations without the mod by introducing variables k1k_1 and k2k_2 to be arbitrary constants that we solve for later:

p×ip=1+k1q q×iq=1+k2p\begin{aligned} p \times ip &= 1 + k_1q \\\ q \times iq &= 1 + k_2p \end{aligned}

We’ll be trying to use these formulas to create a quadratic that we can use to eliminate k1k_1 and k2k_2. Multiplying these together gives:

(p×ip)(q×iq)=(1+k1q)(1+k2p) pq×ip×iq=1+k1q+k2p+k1k2pq\begin{aligned} (p \times ip)(q \times iq) &= (1 + k_1q)(1 + k_2p) \\\ pq \times ip \times iq &= 1 + k_1q + k_2p + k_1k_2pq \end{aligned}

I grouped pp and qq together here because it’s important to note that since we have xx, we know rr and thus pq=nrpq = \frac{n}{r}. This means that for purposes of solving the equation, pqpq is a constant to us. This actually introduces an interesting structure on the right hand side, we can create 2 new variables:

α=k1q β=k2p\begin{aligned} \alpha &= k_1q \\\ \beta &= k_2p \end{aligned}

Substituting this into our equation above we get:

pq×ip×iq=1+α+β+αβ\begin{aligned} pq \times ip \times iq &= 1 + \alpha + \beta + \alpha\beta \end{aligned}

Recall from whatever algebra class you last took that (xx0)(xx1)=x2(x0+x1)x+x0x1(x - x_0)(x - x_1) = x^2 - (x_0 + x_1)x + x_0x_1. Since we have both αβ\alpha\beta and (α+β)(\alpha + \beta) in our equation, we can try to look for a way to isolate them in order to create our goal.

pq×ip×iq=1+k1q+k2p+k1k2pq k1k2pq=pq×ip×iq1k1qk2p k1k2=ip×iq1pqk1pk2q\begin{aligned} pq \times ip \times iq &= 1 + k_1q + k_2p + k_1k_2pq \\\ k_1k_2pq &= pq \times ip \times iq - 1 - k_1q - k_2p \\\ k_1k_2 &= ip \times iq - \frac{1}{pq} - \frac{k_1}{p} - \frac{k_2}{q} \end{aligned}

1pq\frac{1}{pq} is basically 00, and since k1k_1 and k2k_2 are both smaller than pp or qq, then we’ll approximate this using k1k2=ip×iq1k_1k_2 = ip \times iq - 1. Now that k1k2k_1k_2 has become a constant, we can create the coefficients we need:

α+β=pq×ip×iq1k1k2pq αβ=k1k2pq\begin{aligned} \alpha + \beta &= pq \times ip \times iq - 1 - k_1k_2pq \\\ \alpha\beta &= k_1k_2pq \end{aligned}
(xα)(xβ)=0 x2(α+β)x+αβ=0 x=(α+β)±(α+β)24αβ2\begin{aligned} (x - \alpha)(x - \beta) &= 0 \\\ x^2 - (\alpha + \beta)x + \alpha\beta &= 0 \\\ x &= \frac{(\alpha+\beta) \pm \sqrt{(\alpha+\beta)^2 - 4\alpha\beta}}{2} \end{aligned}

Putting this into Python, looks like:

from decimal import Decimal
getcontext().prec = 3000 # To get all digits

k1k2 = ip * iq - 1
alpha_times_beta = k1k2 * pq
alpha_plus_beta = pq * ip * iq - 1 - k1k2 * pq

def quadratic(b, c):
  b, c = Decimal(b), Decimal(c)
  disc = b ** 2 - 4 * c
  return (-b + disc.sqrt()) / 2, (-b - disc.sqrt()) / 2

alpha, beta = quadratic(-alpha_plus_beta, alpha_times_beta)

Now that we have α\alpha and β\beta, we can try GCD’ing them against pqpq to get pp and qq:

from math import gcd

p = gcd(pq, int(alpha))
q = gcd(pq, int(beta))
assert p * q == pq # Success!

Alternative method

@sahuang used the sympy library to do this part instead, resulting in much less manual math. It’s based on this proof from Math StackExchange that p(p1modq)+q(q1modp)=pq+1p \cdot (p^{-1} \bmod q) + q \cdot (q^{-1} \bmod p) = pq + 1.

from sympy import *
p,q = symbols("p q")
eq1 = Eq(ip * p + iq * q - pq - 1, 0)
eq2 = Eq(p * q, pq)
sol = solve((eq1, eq2), (p, q))

Decrypting the ciphertexts

Now that we know pp and qq, it’s time to plug them back into the cryptosystem and get our plaintexts. c2c_2 is actually easier than c1c_1, because with e2=5e_2 = 5 we can just find the modular inverse:

phi = (p - 1) * (q - 1) * (r - 1)
d2 = pow(e2, -1, phi)
m2 = pow(c2, d2, n)
print(long_to_bytes(m2))
# ... The last part of the flag is: 8ut_num83r_sy5t3m_15_3v3n_m0r3_1nt3r35t1n6} ...

This trick won’t work with c1c_1 however:

d1 = pow(e1, -1, phi)
# ValueError: base is not invertible for the given modulus

Because ϕ\phi is even (it’s the product of one less than 3 primes), there can’t possibly be a d1d_1 such that 2d11modϕ2 \cdot d_1 \equiv 1 \bmod \phi. According to Wikipedia, the decryption for a standard two-prime nn takes 3 steps:

  1. Compute the square root of cmodpc \bmod p and cmodqc \bmod q:
    • mp=c14(p+1)modpm_p = c^{\frac{1}{4}(p + 1)} \bmod p
    • mq=c14(q+1)modqm_q = c^{\frac{1}{4}(q + 1)} \bmod q
  2. Use the extended Euclidean algorithm to find ypy_p and yqy_q such that ypp+yqq=1y_p \cdot p + y_q \cdot q = 1.
  3. Use the Chinese remainder theorem to find the roots of cc modulo nn:
    • r1=(yppmq+yqqmp)modnr_1 = (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \bmod n
    • r2=nr1r_2 = n - r_1
    • r3=(yppmqyqqmp)modnr_3 = (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n
    • r4=nr3r_4 = n - r_3
  4. The real message could be any rir_i, but we don’t know which.

Converting this to work with n=pqrn = pqr, it looks like:

  1. Compute the square root of cmodpc \bmod p, cmodqc \bmod q, and cmodrc \bmod r:
    • mp=c14(p+1)modpm_p = c^{\frac{1}{4}(p + 1)} \bmod p
    • mq=c14(q+1)modqm_q = c^{\frac{1}{4}(q + 1)} \bmod q
    • mr=c14(r+1)modrm_r = c^{\frac{1}{4}(r + 1)} \bmod r
  2. Using the variable names from AoPS’s definition of CRT:
    • For k{p,q,r},bk=nkk \in \{ p, q, r \}, b_k = \frac{n}{k}.
    • For k{p,q,r},akbk1modkk \in \{ p, q, r \}, a_k \cdot b_k \equiv 1 \bmod k.
  3. Let r=k{p,q,r}±(akbkmk)modnr = \displaystyle\sum_k^{\{ p, q, r \}} \pm (a_k \cdot b_k \cdot m_k) \bmod n.
  4. The real message could be any rr, but we don’t know which.

In code this looks like:

# Step 1
mp = pow(c1, (p + 1) // 4, p)
mq = pow(c1, (q + 1) // 4, q)
mr = pow(c1, (r + 1) // 4, r)

# Step 2
bp = n // p
bq = n // q
br = n // r
ap = pow(bp, -1, p)
aq = pow(bq, -1, q)
ar = pow(br, -1, r)

# Step 3
from itertools import product
for sp, sq, sr in product((-1, 1), repeat=3):
  m = (sp * ap * bp * mp + sq * aq * bq * mq + sr * ar * br * mr) % n
  m = long_to_bytes(m)

  # Step 4
  # We know that the real flag starts with `cybergrabs{`...
  if b"cybergrabs" in m: print(m)

# Congratulations, You found the first part of flag cybergrabs{r481n_cryp70sy5t3m_15_1nt3r35t1n6_ ...

The final flag, then, is:

cybergrabs{r481n_cryp70sy5t3m_15_1nt3r35t1n6_8ut_num83r_sy5t3m_15_3v3n_m0r3_1nt3r35t1n6}

Big thanks to @10, @sahuang, and @thebishop in the Project Sekai discord for doing a lot of the heavy-lifting to solve this challenge.