PicoCTF 2023 Cryptography— SRA Writeup

Hey everyone! I know this challenge dates back to 2023, but I wanted to create a writeup to help you understand the core concepts of RSA encryption and decryption. Even though RSA is widely used in cryptography, many people struggle to grasp how it works and why certain vulnerabilities exist. In this writeup, I’ll break down the challenge, explain the mathematics behind RSA, and show you how to approach solving it step by step. Whether you’re new to cryptography or looking to sharpen your skills, this guide will give you valuable insights into RSA security and its weaknesses. Let’s dive in!
This is the challenge description

What is RSA?
RSA (Rivest-Shamir-Adleman) is a widely used public-key cryptosystem for secure communication and encryption. It is based on the mathematical difficulty of factoring large prime numbers. Unlike symmetric encryption, where the same key is used for both encryption and decryption, RSA employs two keys: a public key for encryption and a private key for decryption. The security of RSA relies on the fact that while it is easy to multiply two large prime numbers, factoring their product back into the original primes is computationally infeasible.
How does it work?
p = large prime number (typically at least 128-bit, but usually much larger) q = large prime number (same size as p)
n = p * q (modulus used for encryption and decryption) e = 65537 (commonly chosen public exponent for efficiency and security) φ(n) = (p — 1) * (q — 1) (Euler’s totient function, used to compute the private key) d ≡ e^(-1) (mod φ(n)) (modular inverse of e, used as the private exponent)
ciphertext ≡ plaintext^e (mod n) (encrypting the message using the public key)
plaintext ≡ ciphertext^d (mod n) (recovering the original message using the private key)
Analyzing the chal.py

The challenge follows the RSA encryption process to secure a randomly generated 16-character string consisting of ASCII letters and digits. It then displays the private exponent (anger) and the encrypted message (envy). Our task is to decrypt the ciphertext and input the correct plaintext. If successful, the flag is revealed.
As you can see here, envy is the private exponent (d), computed as the modular inverse of sloth modulo φ(n), where:
φ(n)=(p−1)(q−1)
This allows decryption via:
plaintext = ciphertext^envy mod lust
REMEMBER THE PRINCIPLES OF RSA!!!
1. RSA Key Structure N = X * Y (modulus, the product of two prime numbers) Φ(N) = (X — 1) * (Y — 1) (totient function, used in key calculation)
2. Determining the Private Key (D) D ≡ E^(-1) (mod Φ(N)) (modular inverse of the public exponent) E * D ≡ 1 (mod Φ(N)) (ensuring encryption and decryption are reversible) Rearranging: E * D — 1 = Φ(N) * K (showing that the difference is a multiple of Φ(N))
3. Implications for Breaking RSA Security If only N and E are known, the goal is to factor N to find Φ(N). Once Φ(N) is obtained, computing D becomes straightforward using the modular inverse.
Application to RSA Attacks
If d is leaked, you can immediately decrypt any RSA-encrypted message without factoring n. But if only n and e are known, you'd need: Factorization and Common exponent attacks
Solution
"""
1. Key Generation:
- Choose two large prime numbers: p, q
- Compute n = p * q (modulus)
- Compute φ(n) = (p-1) * (q-1) (Euler's totient function)
- Choose a public exponent e (commonly 65537)
- Compute the private exponent d such that d * e ≡ 1 (mod φ(n))
2. Encryption:
- Convert plaintext message to an integer m
- Compute ciphertext c = m^e mod n
3. Decryption:
- Compute plaintext m = c^d mod n
- Convert the integer back to the original message
"""
from Crypto.Util.number import isPrime, long_to_bytes
from string import ascii_letters, digits
from itertools import combinations
from sympy import divisors
from math import log2
def get_prime_candidates(modulus: int):
"""Find prime candidates from the divisors of (modulus - 1)."""
return [x + 1 for x in divisors(modulus - 1) if isPrime(x + 1)]
def filter_valid_primes(prime_list):
"""Filter primes that are close to 127-bit size."""
return [p for p in prime_list if log2(p) // 1 == 127]
def decrypt_message(ciphertext: int, exponent: int, primes: list):
"""Attempt decryption using different prime combinations."""
charset = ascii_letters + digits
for p, q in combinations(primes, 2):
try:
decrypted = long_to_bytes(pow(ciphertext, exponent, p * q))
decoded_message = decrypted.decode("ascii")
if all(c in charset for c in decoded_message):
return decoded_message
except UnicodeDecodeError:
continue
return None
def decrypt():
ciphertext = <anger>
exponent = <envy>
public_exponent = 65537
prime_candidates = get_prime_candidates(exponent * public_exponent)
valid_primes = filter_valid_primes(prime_candidates)
decrypted_message = decrypt_message(ciphertext, exponent, valid_primes)
if decrypted_message:
print(f"Decrypted String: {decrypted_message}")
else:
print("No valid decrypted string found.")
decrypt()
The core idea behind this method is that both p−1 and q−1 must be factors of ed−1. This means we can generate a list of all divisors of ed−1 and identify those that are exactly one less than a 128-bit prime. By adding one to these divisors, we obtain potential values for p and q. Next, we iterate through all possible pairs of these values and attempt to decrypt the ciphertext. If the decryption results in a readable string consisting of ASCII letters and digits, we can be confident that we have found the correct primes. If we’re fortunate, the number of divisors will be small, making the process more efficient.
Run the script and it should give us the decrypted string to access the flag.

Here it is!!! Now let’s use this to read the flag!

There you have it! We now have the flag!
And that’s a wrap, guys! Hope this write-up gave you a solid understanding of how RSA works!!!!
Add-ons…
RSA relies heavily on prime factorization for its security. The core idea behind RSA encryption is that it is easy to multiply two large prime numbers together, but extremely difficult to reverse the process (i.e., factorizing the product back into its prime components).
The reason RSA is considered secure (for sufficiently large key sizes) is that factoring a large number (n = p × q) into its prime components (p and q) is computationally infeasible with current classical algorithms.
The only threats to RSA are Quantum Computing and Insufficient Key Size
Shor’s algorithm, a quantum algorithm, can factor large numbers efficiently, breaking RSA encryption. This is why post-quantum cryptography is being developed.
If n is too small (e.g., 512-bit), modern factoring algorithms can break RSA. Use at least 2048-bit keys for security.
RSA’s security is built on the assumption that prime factorization of large numbers is infeasible with classical computing. If an efficient classical or quantum algorithm for prime factorization is discovered, RSA encryption will be broken.
That’s all! Adios!
Last updated