Основы RSA 1 (RSA Basics 1)

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: RSA decryption with known prime factor, Modular inverse calculation for private exponent, Integer to bytes conversion

Summary

Walkthrough of the CUSTOM Crypto Основы RSA 1 (RSA Basics 1). Detailed walkthrough.

Description

Your friend recently learned RSA asymmetric encryption and encrypted a message with his public key and sent it to you, then disappeared forever. You want to know what he sent, so you went to obtain the private key. To your surprise, you found extra data... Perhaps it will help you.

Ваш друг недавно изучил асимметричное шифрование RSA и зашифровал сообщение своим открытым ключом и отправил его вам, а затем исчез навсегда. Вы хотите узнать, что он отправил, поэтому отправились за закрытым ключом. К вашему удивлению, вы нашли дополнительные данные... Возможно, они вам помогут. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Files

• data.txt - RSA parameters: n, e=65537, and p (one of the prime factors - "extra data")
• flag.txt - Encrypted flag (256 bytes binary ciphertext)

Analysis

Classic RSA challenge with a known prime factor. If one of the factors p is known, then:

1. Calculate the second factor: q = n // p
2. Calculate Euler's totient: phi(n) = (p-1) * (q-1)
3. Calculate the private exponent: d = e^(-1) mod phi(n)
4. Decrypt: m = c^d mod n

Data

n = 17327286385030297619055609812547395532303350738357039187271762800476355565047902196480182952525970808148340374159153211958450440378498794350454268441698198116395593570968780817193848386119467551056846736050217957904655068683306568686860949952622952069871723551854065721708810178405245808610636319206090568675639505989380448963390500784981938837344148741951935352345831138854398944969527820495720840504098981923332332034403797978425789401021243205986351856289983707620600473774106442080605714538190714676992843800728968866308968923652890236623555171107158471771943494381582012510740446793672404982545209615196896091487
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

e = 65537

p = 2087539982355952095352940591481182316534226033893916513431522538203193520762524106594022783007866775889494900254987221649795202213419228734556286567814291577680141913972513242659019754608685871868492014601186827830818090245390932534369400308423585229696958659515265119460457285099551187329600050104076864250940595905060827485529

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""RSA Basics 1 - Decrypt using known prime factor p"""

n = 17327286385030297619055609812547395532303350738357039187271762800476355565047902196480182952525970808148340374159153211958450440378498794350454268441698198116395593570968780817193848386119467551056846736050217957904655068683306568686860949952622952069871723551854065721708810178405245808610636319206090568675639505989380448963390500784981938837344148741951935352345831138854398944969527820495720840504098981923332332034403797978425789401021243205986351856289983707620600473774106442080605714538190714676992843800728968866308968923652890236623555171107158471771943494381582012510740446793672404982545209615196896091487
e = 65537
p = 2087539982355952095352940591481182316534226033893916513431522538203193520762524106594022783007866775889494900254987221649795202213419228734556286567814291577680141913972513242659019754608685871868492014601186827830818090245390932534369400308423585229696958659515265119460457285099551187329600050104076864250940595905060827485529
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Calculate q from n and p
q = n // p
assert p * q == n, "p * q != n, factorization error"

# Calculate private exponent d
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# Read ciphertext
with open('flag.txt', 'rb') as f:
    c = int.from_bytes(f.read(), 'big')

# Decrypt: m = c^d mod n
m = pow(c, d, n)

# Convert to bytes
decrypted = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(decrypted.decode('utf-8', errors='replace'))

Output

CODEBY{REDACTED}

Flag Meaning

The flag "REDACTED" is leetspeak for "asymmetric decryption", referring to RSA as an asymmetric encryption algorithm. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

RSA Theory

RSA is based on the difficulty of factoring large numbers:

• Key generation: two large prime numbers p and q are chosen, n = p*q is calculated
• Public key: (n, e), where e is usually 65537
• Private key: d, such that e*d ≡ 1 (mod phi(n))
• Encryption: c = m^e mod n
• Decryption: m = c^d mod n

If one of the factors is known, the entire cryptosystem is compromised. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering RSA decryption with known prime factor, Modular inverse calculation for private exponent, Integer to bytes conversion was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2025-12-30 • CUSTOM • Основы RSA 1 (RSA Basics 1) • Difficulty: Easy