SHC 2026: Dino Vault - RSA Common Factor Attack

Challenge Overview

• Category: Cryptography
• Objective: Decrypt the DNA of the “Vexillum Rex” dinosaur

Source Analysis

The Python server used RSA-like encryption:

def get_encrypted_dna(self):
    transmission_key = getPrime(primesize)          # p — fresh every request
    dinosaur_modulation_index = transmission_key * self.vault_key  # N = p * q
    evergreen_number = 2**16 + 1                    # e = 65537
    resampled_dna = pow(bytes_to_long(self.dna.encode()), evergreen_number, dinosaur_modulation_index)

Key observation: vault_key (q) is generated once and reused. Every request gets a different p, but the same q.

The Vulnerability: Common Factor Attack

Two different moduli from the same dinosaur:

• N₁ = p₁ × q
• N₂ = p₂ × q

Since they share q:

gcd(N₁, N₂) = q

Once q is recovered, computing p₁ = N₁ / q gives us full factorization. Then we reconstruct the private key.

Exploitation

Step 1: Collect two ciphertexts

Attempt 1: C₁, N₁
Attempt 2: C₂, N₂

Step 2: Factor

from math import gcd
q = gcd(N1, N2)
p1 = N1 // q

Step 3: Reconstruct private key

phi = (p1 - 1) * (q - 1)
d = pow(e, -1, phi)          # modular inverse
M = pow(C1, d, N1)           # decrypt

Step 4: Decode DNA

The challenge used a custom to_dna mapping (bits → A/T/G/C). Reversed the mapping to recover ASCII.

Flag: SHC{...} — found in: “Has a crown and SHC{…} written on its back.”

Conclusion

This challenge demonstrates why both primes in RSA must be unique across all sessions. Reusing even one prime allows an attacker to break encryption with simple GCD — a calculation taking microseconds.