Огромные цифры (Huge Numbers)

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-02 | Status: Solved Techniques: Continued fraction expansion of e/n, Convergent enumeration to recover d, Verification via phi(n) factorization check, Wiener's Attack on RSA with small private exponent

Summary

Task: RSA with unusually large public exponent e (inverse of small d). Solution: Wiener's attack using continued fraction expansion of e/n to recover small private exponent d.

Огромные цифры (Huge Numbers) - hackerlab

Description

"Я слышал что небольшие значения публичного ключа могут быть потенциально уязвимыми, поэтому решил брать числа как можно больше"

Files:

• encrypt.py - RSA encryption script
• output.txt - contains n, e, c in hex format

Analysis

Encryption source code

 python read-only • copy allowed Copy
from random import getrandbits
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from math import gcd

def gen():
    p, q = getPrime(1024), getPrime(1024)
    n, phi = p * q, (p-1) * (q-1)
    while True:
        d = getrandbits(510)  # <-- VULNERABILITY: small d!
        if gcd(d, phi) == 1:
            e = inverse(d, phi)  # e is computed as inverse of d
            break
    return (n, e)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

m = bytes_to_long(b"CODEBY{???????????????????????????????}")
n, e = gen()
c = pow(m, e, n)

Key observation

Irony of the task name: The author thought that large e = security. But in reality:

• Large e means small d
• Small d makes the system vulnerable to Wiener's attack!

Wiener's attack condition

Wiener's attack works when:

d < (1/3) * n^(1/4)

For n = 2048 bits:

• n^(1/4) ≈ 2^512
• Boundary: d < 2^512 / 3 ≈ 2^510

In this task: d = getrandbits(510) - exactly at the attack boundary! ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Theory of Wiener's Attack

Mathematical basis

From RSA definition:

e * d ≡ 1 (mod φ(n))
e * d = k * φ(n) + 1

Dividing by d * φ(n):

e / φ(n) = k/d + 1/(d * φ(n))

Since φ(n) ≈ n for large primes:

e / n ≈ k/d

Continued Fractions

Expanding e/n as a continued fraction gives a sequence of convergents. One of them will equal k/d, allowing us to recover d.

Candidate verification

For each candidate (k, d):

1. Compute φ(n) = (e*d - 1) / k
2. Check: s = n - φ(n) + 1 (sum p + q)
3. Solve: x² - s*x + n = 0
4. If discriminant is a perfect square, we found d! ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
from Crypto.Util.number import long_to_bytes
import gmpy2

n = 0x6d550908a16fee2e3dcd0027dd62c0f74a9a6c8982080951129f6d3f855930529d4f8e2a6e9e064ca9939abb3c1b33c2c1195b61f06996a022becab4974314b9e7805fe6f8768b9aef2b412ae8947689341c645030c1267bd09e3297967c9dd928c2f5851f38657e107cda494eccb4c2c6994e9ba7d1c9a80f8284e8127f2cceab54fbd2a730a937ca3880a1553264091392c4783031c53998a2a711ce001d33acbe37c2831fde6d18ce36bcdc0244f504e89e75462ac702ae0f6cdc613a44467ff1ae2dc83972d81a7d3c762a50036106058ac0c1f8713164f6f54fb50a9d433e9568b3db45d54861468382dad34a7cc40d891e7e12a9e5cbe7bd28499cd547
e = 0x516d425872e6bbef46c09effb4af22b7a116c1f0ae2adfbcc017e8c9624769d8bbd88db70545d78eb04b02449d26517d569cb64ec48d68901229faed21430cf6760b40afd9b52f2c5e28f5cb60e380747bda72dc661309be6c6e4a95f487541054ea73c8dbe544694ee2a9059fd3397bc113696df738126f09734008be776f0cb95eaf1670ea1e08ebaa3d800d7539b8067a3b8cdd510ace0c6cf0c9ae07bce3f29fc39e718bf6c209d3dec1b174b36444e358134531a24a9fd4230d027cada0c2980a196a4900e5b743a7ca2cf6c4d27544a204387353b6f74aa18f12380bd218b5e33ff4f42523fdf87311e5e0d9d2d37bf3c09659825508e678a130153567
c = 0x6e72fa52825e51ed0c3bd245843e1d3cc1e22d139bbfe96ee36d3f31a4056057a68fe0c8f929cdb4972e7b3f009e06e70ed62276ec2c7606b0414203efe51904c74b37eaba832e84564b730b86742e6e789c5ff7e4130b3cf1010d3701408c79fdc082953819bb6f85f9d9d4a006d501f7e63dfdea027623187f6ae2a6dd4a45419fafeb265d6540227f576e41eb35673e2e3bf9f4452d863ee5d884e42a932091250d4140e6597be6467119dbe0fce2604241469c2a43ce76c156fe278b0a950d973bee4c8c14378978cf28ae2019adb83d7d985f91c29a61ddaafff4d940eea1ae52477197cb30721a065fc82091bc16fb16b054282ac8096150902f7c9eb
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def continued_fraction(num, den):
    """Expand num/den as a continued fraction"""
    cf = []
    while den:
        q = num // den
        cf.append(q)
        num, den = den, num - q * den
    return cf

def convergents(cf):
    """Generator for convergents"""
    n0, n1 = 0, 1
    d0, d1 = 1, 0
    for a in cf:
        n2 = a * n1 + n0
        d2 = a * d1 + d0
        yield n2, d2
        n0, n1 = n1, n2
        d0, d1 = d1, d2

def isqrt(n):
    """Integer square root"""
    return int(gmpy2.isqrt(n))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def is_perfect_square(n):
    """Check if n is a perfect square"""
    if n < 0:
        return False
    root = isqrt(n)
    return root * root == n

def wiener_attack(e, n):
    """Wiener's attack on RSA"""
    cf = continued_fraction(e, n)
    
    for k, d in convergents(cf):
        if k == 0:
            continue
        
        # Check: (e*d - 1) must be divisible by k
        if (e * d - 1) % k != 0:
            continue
        
        phi = (e * d - 1) // k
        
        # s = p + q = n - phi + 1
        s = n - phi + 1
        
        # Discriminant of quadratic equation x^2 - s*x + n = 0
        discriminant = s * s - 4 * n
        
        if discriminant < 0:
            continue
        
        # If discriminant is a perfect square, we found d!
        if is_perfect_square(discriminant):
            return d
    
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Execute the attack
d = wiener_attack(e, n)
print(f"Recovered d: {d}")
print(f"d bit length: {d.bit_length()}")

# Decrypt
m = pow(c, d, n)
flag = long_to_bytes(m)
print(f"Flag: {flag.decode()}")

Alternative Tools

• owiern - ready-made Wiener's attack implementation
• RsaCtfTool - automatically detects and applies the attack
• SageMath - continued_fraction(e/n).convergents()

Related Attacks

References

• Wiener's Attack - Wikipedia
• Cryptanalysis of Short RSA Secret Exponents ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍