//bolt_fast

Author: lime_for_snake

Category: Crypto - RSA

>Summary

In this challenge, we are given the RSA modulus N = pq, the public exponent e, and a ciphertext c = m^e mod N. The source file (chall.py) indicates a subtle leak: dp_smart = getPrime(16) (a 16-bit prime) was used when computing e as the inverse of dp_smart (mod p-1) — i.e. e was set so that edp ≡ 1 (mod p-1), with dp ≈ 16 bits. That means we have an extremely small d_p (the private exponent modulo p-1) which can be exploited to factor N.

The flag format is flag{...} and the encrypted message decrypts to this flag once the private key is recovered.

>Observations

p and q are large 1024-bit primes, N is about 2048 bits.
dp is explicitly set to a 16-bit prime (in code: dp_smart= getPrime(16)). So dp is small.
The relationship: e * dp ≡ 1 (mod p-1), equivalently, there exists integer k such that

e*dp = 1 + k(p - 1) (Equation 1)

Rearranged: p = (e*dp - 1)/k + 1.

Since dp is small (16 bits), k is less than dp and therefore also small (< 2^16). This allows a search over small k values to reconstruct p.

>Attack idea

We leverage the equation above: for small k, we can test whether a candidate dp derived from dp ≡ e^{-1} (mod k) gives an integer p that divides N.

Steps:

For each k in [1, 2^16):

Compute r = e^{-1} (mod k), if it exists. The actual dp satisfies dp ≡ r (mod k).
The actual dp is dp = r + t*k for some integer t ≥ 0. Since dp < 2^16, we can enumerate all such dp values less than 2^16.
We test whether dp is a prime (because dp was generated as a small prime in the challenge code).
If dp is a plausible candidate, compute M = e*dp - 1. If M % k == 0, we can compute p' = M // k + 1. If p' divides N (N % p' == 0), we have recovered p. Then q = N // p'.

With p, q recovered, compute phi = (p-1)*(q-1) and d = e^{-1} (mod phi). Decrypt the ciphertext with m = c^d mod N and convert to bytes.

This method is fast because k (and dp) are small (less than 2^16), so the loops are cheap and we quickly find the required values.

>Why Wiener doesn't apply

Wiener’s attack recovers d directly when the private exponent is small (d < N^0.25) using continued fractions. Here however, the private exponent d is not small; instead dp (d mod p-1) is small — a different leakage. The challenge text explicitly jokes about Wiener's attack being irrelevant.

>Implementation and code

I wrote a solver solve.py to execute the attack and print the flag. Key points:

I used pycryptodome for the number-theory helpers (inverse and isPrime).
The script loops over k up to 2^16; for each k, it attempts to compute a base congruence dp ≡ e^{-1} (mod k). Then it enumerates all dp that fit that congruence and are less than 2^16.
For candidate dp (and matching k), it computes p = (e*dp - 1) // k + 1. If p divides N, we have a factor and can derive the private key and decrypt the ciphertext.

Solver code (full):

python


#!/usr/bin/env python3

from Crypto.Util.number import inverse, long_to_bytes, isPrime

N = 22061149554706951873851465765917042279909309233484615798640186468876401527123242297915465375459511054772541825273007749026648641620485458471351811298443479262277231839408201654282927999029324652496830649919637863202844794784443579336735415046336390091671003022244732389217910334465895328371360158510046347031294125509649474722535171601096998732929497780870057433634214228116293166963101489644680801538837005001377764416442380530464289453201654394144682138927826247301956954884930328147978637795259346321547054237005318172528896865428457293207571804464061990459958593520373578234234490804585522859401957032395007142007

E = 9648003423571638489624579625383119603270189664714210175737275695548206153582516635644990660189908448510652756058045483763071850222529184219333877863638216254054444012130393864033392161426815671725858723096432660521038315432183692553568344247916320931122090436770154203149432285380142051084178668290839858171

C = 18817014323644102879407569381912044887671193778381872592373573382139976320220125847317309926920208859012582031032930373240219755720268543444729983316326640661427616841700761054678137741340093140586895094016730198447552611014038632666821117758006775144046000049080406858764900680265384743839472653817299383323869146152251839342236631780818396088131196202767951301023089053662813175083035336272981588533957561537975684034210166185396046071368061264321959248372783262788158418696375783427276741258526067168910326630496339287237940444426277757582174810909733937257258767407189452212391936958267819666424558678534741723930

# Limit where dp < 2^16

LIMIT = 1 << 16

for k in range(1, LIMIT):

    if E % k == 0:

        continue

    try:

        dp0 = pow(E, -1, k)

    except ValueError:

        continue

    dp = dp0

    while dp < LIMIT:

        if dp >= (1 << 15) and isPrime(dp):

            M = E * dp - 1

            if M % k == 0:

                p = M // k + 1

                if p > 1 and N % p == 0:

                    q = N // p

                    phi = (p - 1) * (q - 1)

                    d = inverse(E, phi)

                    m = pow(C, d, N)

                    print('FOUND')

                    print('k =', k)

                    print('dp =', dp)

                    print('p =', p)

                    print('q =', q)

                    print('flag =', long_to_bytes(m))

                    raise SystemExit

        dp += k

print('Not found')

>Running the solver

Prerequisites:

bash


pip install pycryptodome

Run:

bash


python3 solve.py

During my run this produced:

Found k = 2418
dp = 34171
p and q were found, and the flag decrypted to:

flag{w31n3r_d1dn7_73ll_y0u_70_b3_6r33dy}

>Why this works so fast

Because dp < 2^16 and k < dp, the search space has only about 2^16 possibilities for k and at most about 16 checks per k on average. This is trivially computable on a modern machine in seconds.
The congruence relation e*dp = 1 (mod p-1) collapses p to a simple linear expression given k and dp, allowing a deterministic check if p divides N

>Final flag

flag{w31n3r_d1dn7_73ll_y0u_70_b3_6r33dy}