📝 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
- The challenge provides
pandq(the prime factors ofn). - Optionally, you can verify
n = p * q. - 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
- Compute the modulus:
n = p * q - Compute Euler’s totient:
phi = (p - 1) * (q - 1) - 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
- Use the RSA formula:
m = c^d mod n - 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
| Step | Command / Action | Purpose | Key Result |
|---|---|---|---|
| 1 | Verify p and q (FactorDB optional) | Ensure modulus factors are correct | Correct factors obtained |
| 2 | Compute n, phi, and d | Prepare RSA private key parameters | Private key ready |
| 3 | Decrypt ciphertext c using pow(c, d, n) | Recover plaintext | Flag revealed |
💡 Beginner Tips
- 🔢 Always verify the provided primes and modulus first.
- 🧮 Use Python libraries like
Crypto.Util.numberfor large number operations. - 🔑 Understand the relationship:
n = p*q,phi = (p-1)*(q-1), andd = e^-1 mod phi. - 💻 Test your script with smaller RSA examples to understand the process.
🎓 What you learn (takeaways)
- Knowing the prime factors of
nmakes 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
emodulophi. - Why: Needed to decrypt RSA ciphertext.
- What: Computes modular inverse of
- 🔓 RSA decryption (
pow(c, d, n))- What: Calculates
c^d mod nefficiently. - Why: This is the core decryption step.
- What: Calculates
- 🐍
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.
Leave a Reply