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

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-02 | Status: Solved Techniques: FactorDB modulus lookup, RSA decryption with factored modulus, Modular inverse calculation

Summary

Files: - data.txt — RSA parameters (n, e) - flag.txt — encrypted flag (binary data)

Основы RSA 2 — hackerlab

Description

Ваш старый знакомый тоже заметил свою оплошность и теперь исправил её. Докажите ему, что его ключ все равно отстой!

Files:

• data.txt — RSA parameters (n, e)
• flag.txt — encrypted flag (binary data)

Analysis

This is a continuation of the "Основы RSA 1" task. The author "fixed" their mistake (no longer gives p directly), but the key is still vulnerable.

RSA Parameters

n = 77618389780872619108052391179631102978288227827824071424012583606448571920761598730011050177486760785953979614075623444045518158274430580410744750813014734653181658420048158940571431510518957904714952617144773205232087142841664493972345738354705943859723243440097854736900578174502761971428893984243694343532390220216554015483627102650201665799940337765981388386628828806975765561963938364541618351852425936524659751776685389624346053921775245296854017285710301604248541811367878925093598437056148959304493974246679560400044921434479435615455237937042681637295805936795427223704790058415752241567158899964450554840575943798833091511319363794793947112807403136160849505131868858399027899044107538914639514404723496978994918940588151074011828580652618262508937747274504321362514540496197921392915928738773761998687893055236900162754142084615760760318500057649840451331396536464495864400327008809842016568514416323955918770209134914181633760720431
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

e = 65537

The modulus n is 3136 bits — an unusually large size. Standard factorization methods (Fermat, Pollard rho) don't work.

FactorDB Lookup

A query to the FactorDB API showed that n is already factored:

n = p × q
p = 14140603756509138613  (64 bits — very small!)
q = [huge 3072-bit prime number]

Vulnerability: One of the prime factors is too small (only 64 bits), making factorization trivial through public databases or even trial division.

Solution

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

# RSA parameters from data.txt
n = 77618389780872619108052391179631102978288227827824071424012583606448571920761598730011050177486760785953979614075623444045518158274430580410744750813014734653181658420048158940571431510518957904714952617144773205232087142841664493972345738354705943859723243440097854736900578174502761971428893984243694343532390220216554015483627102650201665799940337765981388386628828806975765561963938364541618351852425936524659751776685389624346053921775245296854017285710301604248541811367878925093598437056148959304493974246679560400044921434479435615455237937042681637295805936795427223704790058415752241567158899964450554840575943798833091511319363794793947112807403136160849505131868858399027899044107538914639514404723496978994918940588151074011828580652618262508937747274504321362514540496197921392915928738773761998687893055236900162754142084615760760318500057649840451331396536464495864400327008809842016568514416323955918770209134914181633760720431
e = 65537
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Factors from FactorDB
p = 14140603756509138613
q = n // p

# Verification
assert p * q == n, "Factorization error!"

# Calculate private key
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

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

m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag.decode())

Lessons

1. Always check FactorDB — many moduli are already factored
2. Asymmetric primes — if p and q differ significantly in size, the smaller one can be found by brute force
3. Large modulus ≠ security — 3136 bits are useless if one factor is only 64 bits
4. The flag "REDACTED" (very large numbers scare everyone) — irony about how large numbers scare but don't protect ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Related Tasks

• Основы RSA 1 — previous task in the series (p given directly)
• Ничего особенного — FactorDB lookup on standard 2048-bit modulus ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍