RSA 1000

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-04-04 | Status: Solved Techniques: block_cipher_ecb_mode_decryption, known_plaintext_attack, rsa_small_key_factorization

Summary

Task: 1000 RSA public keys (128-bit), flag encrypted with unknown key, known plaintext+ciphertext pair provided. Solution: identify correct key via known plaintext attack on first block, factor small modulus, decrypt flag block-by-block.

RSA 1000 — Hackerlab

Description

Всегда возникают трудности достать нужный ключ из связки

English summary: We are given 1000 RSA public keys (128-bit each), a flag encrypted with one of them, and a known plaintext-ciphertext pair encrypted with the same key. The goal is to identify which key was used, factor its small modulus, and decrypt the flag.

Given files:

• keys/ — directory with 1000 RSA public keys (public_key_0.pem through public_key_999.pem), each 128-bit
• chall.py — encryption script
• flag_ciphertext.txt — encrypted flag (144 bytes = 9 blocks × 16 bytes)
• known_ciphertext.txt — encrypted known plaintext (64 bytes = 4 blocks × 16 bytes)
• known_plaintext.txt — contains CODEBY{FAKE-FLAG}\n (18 bytes) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Encryption scheme (chall.py)

The encryption script works as follows:

1. Key generation: Generates 1000 RSA keypairs with 128-bit modulus using rsa.newkeys(128), saves only public keys
2. Key selection: Picks a random key index (0-999)
3. Block encryption: Plaintext is split into 5-byte blocks (padded with \x00), each block is encrypted as raw/textbook RSA: c = m^e mod n, producing 16-byte ciphertext blocks
4. Same key: Both the flag and the known plaintext are encrypted with the same randomly chosen key ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key observations

1. Known plaintext attack is possible: We have CODEBY{FAKE-FLAG}\n and its ciphertext. Since encryption is block-based with no randomized padding (textbook RSA), we can compute pow(bytes_to_long(block), e, n) for each key and compare against the known ciphertext to identify the correct key.

2. 128-bit RSA is trivially factorable: Once we identify the key, factoring a 128-bit modulus takes milliseconds with any factoring tool (sympy, yafu, factordb, etc.).

3. ECB-like mode: Each 5-byte block is encrypted independently (no chaining, no IV), making it a deterministic block cipher in ECB mode. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Step 1: Identify the correct key (Known Plaintext Attack)

The first 5-byte block of the known plaintext is "CODEB". We compute pow(bytes_to_long(b"CODEB"), 65537, n) for each of the 1000 public keys and compare with the first 16-byte block of the known ciphertext (4fa3f704dbdb89cc0666b2c331c6005a).

Match found at public_key_223.pem with:

• n = 194520310904499582152797771866794860103
• e = 65537

Step 2: Factor the 128-bit modulus

Using sympy.factorint():

• p = 719815216019429701
• q = 270236453155567871003 ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 3: Compute private key

phi = (p - 1) * (q - 1) = 194520310904499581432561302691797559400
d = pow(65537, -1, phi) = 31218466363939859960529303046562905073

Step 4: Decrypt flag ciphertext

Split the 144-byte flag ciphertext into 9 blocks of 16 bytes each. Decrypt each block as pow(c, d, n), convert back to 5-byte plaintext blocks, concatenate, and strip null padding.

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import rsa
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sympy import factorint
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Step 1: Load known plaintext and ciphertext
with open("known_plaintext.txt", "rb") as f:
    known_pt = f.read()

with open("known_ciphertext.txt", "rb") as f:
    known_ct = f.read()

with open("flag_ciphertext.txt", "rb") as f:
    flag_ct = f.read()

# Block size parameters
BLOCK_SIZE = 5  # plaintext block size
# key size = 128 bits = 16 bytes

# First plaintext block
first_block = known_pt[:5].ljust(5, b"\x00")
first_ct_block = known_ct[:16]

# Step 2: Find the right key by known plaintext attack
m = bytes_to_long(first_block)
target_c = bytes_to_long(first_ct_block)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

found_key = None
for i in range(1000):
    fn = f"keys/public_key_{i}.pem"
    with open(fn, "rb") as f:
        pubkey = rsa.PublicKey.load_pkcs1(f.read())
    c = pow(m, pubkey.e, pubkey.n)
    if c == target_c:
        found_key = pubkey
        print(f"[+] FOUND KEY: public_key_{i}.pem")
        print(f"    n = {pubkey.n}")
        print(f"    e = {pubkey.e}")
        break

if found_key is None:
    print("[-] Key not found!")
    exit(1)

# Step 3: Factor the 128-bit modulus
factors = factorint(found_key.n)
primes = list(factors.keys())
p, q = primes[0], primes[1]
print(f"    p = {p}")
print(f"    q = {q}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Step 4: Compute private key
phi = (p - 1) * (q - 1)
d = pow(found_key.e, -1, phi)
print(f"    d = {d}")

# Step 5: Decrypt flag ciphertext block by block
k = 16  # bytes per ciphertext block (128 bit)
ct_blocks = [flag_ct[i : i + k] for i in range(0, len(flag_ct), k)]

plaintext = b""
for idx, block in enumerate(ct_blocks):
    c = bytes_to_long(block)
    m_dec = pow(c, d, found_key.n)
    pt_block = long_to_bytes(m_dec, BLOCK_SIZE)
    plaintext += pt_block

# Strip padding
plaintext = plaintext.rstrip(b"\x00")
print(f"\n[+] FLAG: {plaintext.decode()}")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍