Alsavoudomila

Mind your Ps and Qs picoCTF Writeup

author:

rudy_candy

category:

Description

In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values

📝 Challenge Overview
In this challenge, we are given an RSA ciphertext c along with its prime factors p and q. By performing RSA decryption, we can recover the plaintext message (the flag). This is a classic RSA challenge where the modulus n is provided indirectly via its factors.

🔢 Step 1: Factor the modulus

  1. The challenge provides p and q (the prime factors of n).
  2. Optionally, you can verify n = p * q.
  3. Using a website like FactorDB, you can check the correctness of the factors.

📝 Explanation: Knowing the prime factors of n makes RSA decryption trivial. Normally, n is large enough that factoring it is hard. Here, the factors are provided, so the problem focuses on applying RSA math.

🔐 Step 2: Compute RSA parameters

  1. Compute the modulus: n = p * q
  2. Compute Euler’s totient: phi = (p - 1) * (q - 1)
  3. Compute the private key exponent: d = e^(-1) mod phi

Python example:

from Crypto.Util.number import *
p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

📝 Explanation: RSA decryption requires d, the modular inverse of e modulo phi. Once we have d, we can decrypt the ciphertext.

🔓 Step 3: Decrypt the ciphertext

  1. Use the RSA formula: m = c^d mod n
  2. Convert the resulting number to bytes to get the plaintext.

Python example:

c = 62324783949134119159408816513334912534343517300880137691662780895409992760262021
plaintext = long_to_bytes(pow(c, d, n))
print(plaintext)

📝 Explanation: pow(c, d, n) efficiently computes c^d mod n. long_to_bytes converts the integer back into readable text, revealing the flag.

🏁 Capture the Flag
📎 After decryption, the plaintext contains the flag:
(example: picoCTF{rsa_decrypted_success})
(Replace with the actual flag output from your Python script.)

📊 Summary

StepCommand / ActionPurposeKey Result
1Verify p and q (FactorDB optional)Ensure modulus factors are correctCorrect factors obtained
2Compute n, phi, and dPrepare RSA private key parametersPrivate key ready
3Decrypt ciphertext c using pow(c, d, n)Recover plaintextFlag revealed

💡 Beginner Tips

  • 🔢 Always verify the provided primes and modulus first.
  • 🧮 Use Python libraries like Crypto.Util.number for large number operations.
  • 🔑 Understand the relationship: n = p*q, phi = (p-1)*(q-1), and d = e^-1 mod phi.
  • 💻 Test your script with smaller RSA examples to understand the process.

🎓 What you learn (takeaways)

  • Knowing the prime factors of n makes RSA decryption trivial.
  • Python makes it easy to handle large integers and modular arithmetic.
  • Understanding RSA internals (modulus, totient, private key) is crucial for cryptography challenges.
  • Conversion between integers and bytes is essential to recover readable messages.

⚡ Short explanations for commands/techniques used

  • 🧮 RSA key calculation (d = pow(e, -1, phi))
    • What: Computes modular inverse of e modulo phi.
    • Why: Needed to decrypt RSA ciphertext.
  • 🔓 RSA decryption (pow(c, d, n))
    • What: Calculates c^d mod n efficiently.
    • Why: This is the core decryption step.
  • 🐍 long_to_bytes()
    • What: Converts integer message to byte string.
    • Why: Converts decrypted number into readable plaintext.
  • 🌐 FactorDB
    • What: Online factorization database.
    • Why: Useful to verify known factors or find small factors quickly.

Load more posts