Breaking a hybrid RSA-ECC cryptosystem through weak prime generation.

TL;DR

This challenge presented a hybrid encryption scheme combining RSA and Elliptic Curve Cryptography (ECC). The primary vulnerability lay in the RSA prime generation, where a significant portion of the least significant bits (LSBs) of both prime factors was generated using a predictable pattern.

The exploitation involved three stages:

1. Exploit weak RSA primes: Recover LSBs using the fixed 0x3 nibble vulnerability
2. Factor the modulus: Apply Coppersmith’s method to find remaining MSBs
3. Extract the flag: Use polynomial GCD to find the common root of two equations

Initial Analysis

The challenge source code main.py reveals a multi-layered encryption process:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

from Crypto.Util.number import *
from random import *
from sage.all import *

def generate_custom_prime():
    while True:
        suffix = str(getRandomNBitInteger(140)).encode().hex()[2:]
        prefix = hex(getRandomNBitInteger(100))[2:]
        candidate = int(prefix + suffix, 16)
        if isPrime(candidate):
            return candidate

def get_flag_value():
    with open("flag.txt", "rb") as f:
        return bytes_to_long(f.read().strip())

def elliptic_curve_encrypt(flag_val):
    p = getPrime(512)
    q = getPrime(512)
    modulus = p * q
    y = randint(0, modulus - 1)
    a = randint(1, modulus)
    b = (y**2 - (flag_val**3 + a * flag_val)) % modulus
    curve = EllipticCurve(Zmod(modulus), [a, b])
    base = curve(flag_val, y)
    result_point = 2 * base
    encrypted = pow(bytes_to_long(b'ANA M9WD'), 0x10001, modulus)
    return {
        "a": a,
        "b": b,
        "point": result_point.xy(),
        "modulus": modulus,
        "ciphertext": encrypted
    }

def hybrid_encrypt(flag_val, ecc_modulus):
    P = generate_custom_prime()
    Q = generate_custom_prime()
    rsa_modulus = P * Q
    pub = pow(flag_val + P, 0x10001, ecc_modulus)
    rsa_ciphertext = pow(bytes_to_long(b'ANA CHIKOUR'), 0x10001, rsa_modulus)
    return {
        "rsa_modulus": rsa_modulus,
        "pub": pub,
        "ciphertext": rsa_ciphertext
    }

def main():
    flag_val = get_flag_value()
    ecc_data = elliptic_curve_encrypt(flag_val)
    hybrid_data = hybrid_encrypt(flag_val, ecc_data["modulus"])
    save_all(ecc_data, hybrid_data)
main()

RSA Weakness: generate_custom_prime()

Elliptic Curve Encryption

An elliptic curve is defined over the ECC modulus:

$$E: y^2 \equiv x^3 + ax + b \pmod{n}$$

The flag value is used as the x-coordinate of the base point:

• \(\text{base} = ({\tt flag_val}, y)\)
• \(\text{result_point} = 2 \cdot \text{base}\)

The x-coordinate of result_point is leaked as point[0].

Hybrid Encryption Layer

The crucial equation linking everything:

$${\tt pub} = ({\tt flag_val} + P)^{0x10001} \pmod{n}$$

where \(P\) is one of the weak RSA primes and \(n\) is the ECC modulus.

Task Analysis

The challenge requires three sequential stages:

Exploitation

Part 1: Recovering RSA Prime LSBs

Since each byte has the first nibble fixed to 0x3, we only need to brute-force the second nibble (0-9, not 0-F). This reduces the search space from \(16 \times 16\) to \(10 \times 10\) per byte pair.

Algorithm: Iterate from LSB upward, recovering bytes incrementally by checking if the product matches modulo powers of 16.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def bf_2nd_nibbles(N, A, B, n):
    for x in range(16):
        for y in range(16):
            bfA = 0x3 * pow(16, n - 1) + pow(16, n - 2) * x + A
            bfB = 0x3 * pow(16, n - 1) + pow(16, n - 2) * y + B
            if bfA * bfB % pow(16, n) == N % pow(16, n):
                return bfA, bfB
    return None, None

p = q = 0
for i in range(2, 86, 2):
    p, q = bf_2nd_nibbles(rsa_n, p, q, i)

Part 2: Factoring RSA with Coppersmith’s Method

After recovering \(p_{\text{known}}\) and \(q_{\text{known}}\) (sufficient LSBs), we have:

$$P = x \cdot R + p_{\text{known}}$$ $$Q = y \cdot R + q_{\text{known}}$$

where \(R = 2^{\text{known_bits}}\) and \(x, y\) are the unknown high parts (small relative to \(N\)).

Substituting into \(N = P \cdot Q\):

$$N = (x \cdot R + p_{\text{known}})(y \cdot R + q_{\text{known}})$$

This is a bivariate polynomial with small roots \(x\) and \(y\). Coppersmith’s theorem finds them efficiently:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

R = 2 ** (p.bit_length())
x, y = var('x y')
p_ = x * R + p
q_ = y * R + q
f = (p_ * q_ - rsa_n).expand()

PR = PolynomialRing(Zmod(rsa_n), names=('x', 'y'))
f = PR(f)
x, y = f.parent().gens()

roots = small_roots(f, [R, R], m=3, d=4)
x_root, y_root = roots[0]

P = int(x_root * R + p)
Q = rsa_n // P

Part 3: Recovering the Flag via Polynomial GCD

The flag is the common root of two polynomials over \(\mathbb{Z}_n\) (ECC modulus).

Polynomial from hybrid encryption

From \({\tt pub} = (z + P)^{0x10001} \pmod{n}\), we get:

$$f(z) = (z + P)^{0x10001} - {\tt pub}$$

Polynomial from elliptic curve point doubling

For a point \((x_1, y_1)\) on \(y^2 = x^3 + ax + b\), the x-coordinate of \(2(x_1, y_1)\) is:

$$x_2 = \left(\frac{3x_1^2 + a}{2y_1}\right)^2 - 2x_1$$

With \(x_1 = z\) (the flag) and \(x_2 = {\tt point}[0]\) (known), we can eliminate \(y_1\) using \(y_1^2 = z^3 + az + b\):

$$4(z^3 + az + b)({\tt point}[0] + 2z) = (3z^2 + a)^2$$

Therefore:

$$g(z) = (3z^2 + a)^2 - 4(z^3 + az + b)(2z + {\tt point}[0])$$

Finding the common root

Both polynomials share \(z = {\tt flag_val}\) as a root. Computing their GCD gives \((z - m)\) where \(m = {\tt flag_val}\):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

F = Zmod(n)
PR = PolynomialRing(F, names=('z',))
z = PR.gen()

f = (z + Q) ** 0x10001 - pub
g = (3 * z**2 + a)**2 - 4 * (z**3 + a * z + b) * (2 * z + point[0])

def pgcd(g1, g2):
    return g1.monic() if not g2 else pgcd(g2, g1 % g2)

result = pgcd(f, g)
m = -result.coefficients()[0]

print(long_to_bytes(int(m)))

Behind the Math

Weak Prime Suffix

The ASCII hex encoding of digits constrains the LSBs of primes to a highly predictable pattern. This reduces brute-force complexity from exponential to tractable.

Coppersmith’s Method

A cornerstone of RSA cryptanalysis:

Coppersmith’s Theorem (1997): If you know a significant portion (MSBs or LSBs) of a prime factor of \(N\), you can recover the remaining bits in polynomial time.

This applies to our scenario where we’ve recovered \(\approx 140\) bits of \(P\) (the suffix) out of \(\approx 240\) bits total.

Elliptic Curve Point Doubling Formula

On the curve \(y^2 = x^3 + ax + b\), point doubling uses the tangent line’s slope:

$$\lambda = \frac{3x^2 + a}{2y}$$

The resulting x-coordinate is:

$$x(2P) = \lambda^2 - 2x(P)$$

By substituting known values and using the curve equation, we derive a polynomial constraint on \(x(P)\).

Polynomial GCD for Common Roots

The Euclidean algorithm for polynomials finds \(\gcd(f, g)\) by successive remainder operations. If both polynomials share a root, that root appears in the GCD. For a linear GCD \((z - m)\), the constant term is \(-m\).

Conclusions

“Vrai Sahl” exemplified sophisticated cryptographic vulnerabilities:

This challenge demonstrates how cryptographic implementations with subtle flaws can be completely compromised through sophisticated mathematical attacks.