2024 Cyber Apocalypse: Primary Knowledge

Challenge Information

Attribute	Details
Event	2024 Cyber Apocalypse
Category	Crypto
Challenge	Primary Knowledge
Difficulty	Easy

Primary Knowledge exploits a fundamental vulnerability in the RSA implementation: the modulus is generated as a product of a single prime number instead of two distinct primes. This results in the modulus n itself being prime, allowing straightforward computation of φ(n) = n - 1 and recovery of the private key.

Analysis

The vulnerable code:

import math
from Crypto.Util.number import getPrime, bytes_to_long

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])  # 2**0 = 1, so only ONE prime!
e = 0x10001
c = pow(m, e, n)

Key vulnerability: 2**0 = 1, so only one 1024-bit prime is generated instead of two. This makes n itself a prime number.

RSA Mathematics

In standard RSA:

n = p * q (product of two distinct primes)
φ(n) = (p - 1) * (q - 1)
d = e^(-1) mod φ(n)
m = c^d mod n

With n being prime:

φ(n) = n - 1 (Euler’s totient: all numbers less than n are coprime to n)
d = e^(-1) mod (n - 1)
m = c^d mod n

Solution

Step 1: Compute Euler’s Totient

When n is prime, φ(n) is simply:

def compute_euler_phi(n):
    return n - 1

Step 2: Calculate Private Key

def compute_private_key(n, e, phi):
    d = pow(e, -1, phi)
    return d

# Given values from output.txt
n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

phi = compute_euler_phi(n)
d = compute_private_key(n, e, phi)

Step 3: Decrypt the Message

from Crypto.Util.number import long_to_bytes

def decrypt_flag(c, d, n):
    m = pow(c, d, n)
    return long_to_bytes(m)

flag = decrypt_flag(c, d, n)
print(flag.decode())

Complete Solution

from Crypto.Util.number import long_to_bytes

def pwn():
    with open('output.txt') as f:
        exec(f.read())

    phi = n - 1  # n is prime!
    d = pow(e, -1, phi)
    m = pow(c, d, n)

    print(long_to_bytes(m).decode())

if __name__ == '__main__':
    pwn()

Key Takeaways

RSA security depends on n being a semiprime (product of exactly two distinct primes)
Code generation errors can introduce critical vulnerabilities (20 vs intended 21)
The Euler totient function dramatically changes based on n’s factorization
Prime moduli completely break RSA security
Verification of cryptographic parameters is essential before deployment