Two binomials, one gcd: collapsing CryptoHack's *Modular Binomials* modulo *p*

CryptoHack hands you a 2047-bit modulus and two ciphertexts of the form $(\alpha p+\beta q)^{e}\bmod N$, then dares you to recover the primes. No factoring, no lattice — just the observation that every term containing $p$ vanishes the moment you read the expression modulo $p$. One math.gcd later, $N$ falls apart in 71 milliseconds.

The target

This is a "reverseme" in the cryptographic sense: there is no binary, no check to bypass, no flag hidden behind strcmp. There is a construction — a small algebraic recipe that turns two secret primes into two public ciphertexts — and the job is to recover and document the inverse of that recipe well enough that a reader could re-implement it cold.

The challenge is Modular Binomials, in CryptoHack's Mathematics track. Scraping the public catalogue (the challenge text is served in the HTML even when logged out) gives the metadata:

$ python3 - < extract.py   # parsing the served maths.html
data-challenge="bionomials"
 Modular Binomials
 80 pts ·
 8747 Solves
 Rearrange the following equations to get the primes p,q
   N  = p · q
   c1 = (2·p + 3·q)^e1  mod N
   c2 = (5·p + 7·q)^e2  mod N
 Challenge files:  - data.txt

So we are told the construction outright. That is unusual for a reverse-engineering task and unusual mercy from the challenge author — but knowing the forward function and inverting it are very different problems, and the inversion is the whole point.

The single attachment, data.txt, lives at a static URL on the site:

$ curl -sS https://cryptohack.org/static/challenges/data_04a0fe134cf31a6c941377aad75db81c.txt -o data.txt
$ sha256sum data.txt
2bbb014b9a6ebf1c9358138543c63df0290ccca315db4e28545a95d5673a78e7  data.txt
$ wc -c data.txt
2190 data.txt

It is five labelled decimal integers, one per line: N, e1, e2, c1, c2. Their sizes tell you a lot before you do any maths:

(Sizes produced by python3 -c "from solve import *; print(N.bit_length())" etc.; see the table-printing snippet later.) A 2047-bit $N$ means $p$ and $q$ are each roughly 1024 bits. General-purpose factoring of a 2048-bit RSA modulus is out of the question — that is the RSA security assumption, and nobody has publicly done it. So if this challenge is solvable in seconds, the structure of $c_1$ and $c_2$ must be the lever. It is.

First impressions

Before reaching for the clever idea, it is worth confirming the boring ideas fail — both because they might not, and because a writeup that only shows the winning move reads like fiction. I wrote deadends.py to fire off every cheap shot at $N$:

#!/usr/bin/env python3
"""Things that DON'T work, so the writeup can say so with evidence."""
from math import gcd
from solve import N, e1, e2, c1, c2, p

print("gcd(N, e1)            =", gcd(N, e1))
print("gcd(N, e2)            =", gcd(N, e2))
print("gcd(c1, N)            =", gcd(c1, N))
print("gcd(c2, N)            =", gcd(c2, N))
print("gcd(c1 - c2, N)       =", gcd(abs(c1 - c2), N))
print("gcd(c1, c2)           =", gcd(c1, c2))
print("gcd(c1*c2 mod N, N)   =", gcd(c1 * c2 % N, N))
print("e1, e2 even?          =", e1 % 2, e2 % 2, "(both odd -> no easy root tricks)")
print("gcd(e1, e2)           =", gcd(e1, e2))
# trial division to a few thousand: confirms N has no tiny factors
sm = None
for d in range(2, 100000):
    if N % d == 0:
        sm = d; break
print("smallest factor < 1e5 :", sm)

$ python3 deadends.py
gcd(N, e1)            = 1
gcd(N, e2)            = 1
gcd(c1, N)            = 1
gcd(c2, N)            = 1
gcd(c1 - c2, N)       = 1
gcd(c1, c2)           = 1
gcd(c1*c2 mod N, N)   = 1
e1, e2 even?          = 1 1 (both odd -> no easy root tricks)
gcd(e1, e2)           = 1
smallest factor < 1e5 : None

Everything returns 1. That rules out the lazy wins:

• $N$ shares no factor with the ciphertexts or exponents. So neither $c_1$ nor $c_2$ accidentally leaks a prime via a direct gcd. Good — that would have been a bug, not a challenge.
• $N$ has no small factors, so trial division and Pollard-$p-1$-style luck are off the table.
• Both exponents are odd ($e_1\bmod 2 = e_2\bmod 2 = 1$) and 512 bits each, so there is no "the exponent is 3, just take a cube root" shortcut, and no Wiener-style tiny private exponent to chase — the exponents here aren't even RSA decryption exponents, they are the encryption powers applied to a linear form in the primes.
• $\gcd(e_1,e_2)=1$, which (we'll see) is actually convenient rather than obstructive.

So the only thing left to exploit is the algebraic shape $(2p+3q)$ and $(5p+7q)$. That shape is the entire challenge.

The weakness: read everything modulo p

Here is the one idea the whole solve turns on. Take the first ciphertext's underlying value, $2p+3q$, and reduce it modulo $p$:

because $2p$ is a multiple of $p$ and dies. Likewise

That is the binomial collapse the challenge is named for. Spelled out via the binomial theorem, raising $2p+3q$ to any power $k$ gives

Every term with $i\ge 1$ carries a factor of $p$, so modulo $p$ the whole sum annihilates down to the single $i=0$ term:

That is why the challenge is called Modular Binomials: the binomial expansion, reduced mod $p$, keeps exactly one term. (If you prefer not to expand, the one-line version is identical: $2p+3q\equiv 3q$, raise both sides to the $k$.)

Now I need the two ciphertexts raised to a common power so their $q^k$ parts match and can be cancelled. The cleanest common exponent is $k=e_1e_2$. Raise $c_1$ to $e_2$ and $c_2$ to $e_1$:

A subtle but important point: I am working modulo $N$, yet I want to reason modulo $p$. That is legal because $p \mid N$. For any integer $X$, $(X \bmod N)\bmod p = X \bmod p$ — reducing mod $N$ first never disturbs the value mod $p$ when $p$ divides $N$. So:

Both now contain the same unknown lump $q^{\,e_1e_2}\bmod p$. Cancel it.

Killing the shared factor

Multiply $a$ by $7^{\,e_1e_2}$ and $b$ by $3^{\,e_1e_2}$ so the constant coefficients line up:

The right-hand sides are now identical. Subtract:

So $X$, computed entirely modulo $N$, is a multiple of $p$. And $X$ is almost certainly not a multiple of $q$: reducing the same expression mod $q$ instead (where $2p+3q\equiv 2p$ and $5p+7q\equiv 5p$) gives

which is zero only if $14^{\,e_1e_2}\equiv 15^{\,e_1e_2}\pmod q$ — an event with probability on the order of $1/q$, i.e. never in this universe. Therefore

cleanly, not the whole of $N$. Once we have $p$, the rest is bookkeeping: $q = N/p$.

That is the entire attack. Two modular exponentiations, two more for the constants $3^{e_1e_2}$ and $7^{e_1e_2}$, one subtraction, one gcd.

A worked example, byte for byte

2047-bit integers are impossible to trace by eye, so I built a pocket-sized instance with the same construction and printed every intermediate. toy.py:

#!/usr/bin/env python3
"""A pocket-sized instance so every step is checkable by hand."""
from math import gcd

p, q = 11, 17          # the secret primes
N = p * q              # 187
e1, e2 = 3, 5

c1 = pow(2*p + 3*q, e1, N)
c2 = pow(5*p + 7*q, e2, N)
print(f"p={p} q={q} N={N}  e1={e1} e2={e2}")
print(f"2p+3q = {2*p+3*q}   c1 = (2p+3q)^e1 mod N = {c1}")
print(f"5p+7q = {5*p+7*q}   c2 = (5p+7q)^e2 mod N = {c2}")
print()

k = e1 * e2
print(f"k = e1*e2 = {k}")
a = pow(c1, e2, N)     # (2p+3q)^k mod N
b = pow(c2, e1, N)     # (5p+7q)^k mod N
print(f"a = c1^e2 mod N = (2p+3q)^k mod N = {a}")
print(f"b = c2^e1 mod N = (5p+7q)^k mod N = {b}")
print()

print("--- the same quantities reduced mod p (what the attack relies on) ---")
print(f"(2p+3q) mod p = {(2*p+3*q)%p}  == 3q mod p = {(3*q)%p}")
print(f"(5p+7q) mod p = {(5*p+7*q)%p}  == 7q mod p = {(7*q)%p}")
print(f"a mod p = {a%p}   == 3^k q^k mod p = {pow(3,k,p)*pow(q,k,p)%p}")
print(f"b mod p = {b%p}   == 7^k q^k mod p = {pow(7,k,p)*pow(q,k,p)%p}")
print()

t1 = pow(7, k, N) * a % N
t2 = pow(3, k, N) * b % N
X = (t1 - t2) % N
print(f"7^k * a mod N = {t1}")
print(f"3^k * b mod N = {t2}")
print(f"X = (7^k a - 3^k b) mod N = {X}")
print(f"X mod p = {X % p}   <-- zero, so p | X")
print(f"X mod q = {X % q}")
print(f"gcd(X, N) = {gcd(X, N)}   (recovers p)")

Running it:

$ python3 toy.py
p=11 q=17 N=187  e1=3 e2=5
2p+3q = 73   c1 = (2p+3q)^e1 mod N = 57
5p+7q = 174   c2 = (5p+7q)^e2 mod N = 89

k = e1*e2 = 15
a = c1^e2 mod N = (2p+3q)^k mod N = 109
b = c2^e1 mod N = (5p+7q)^k mod N = 166

--- the same quantities reduced mod p (what the attack relies on) ---
(2p+3q) mod p = 7  == 3q mod p = 7
(5p+7q) mod p = 9  == 7q mod p = 9
a mod p = 10   == 3^k q^k mod p = 10
b mod p = 1   == 7^k q^k mod p = 1

7^k * a mod N = 1
3^k * b mod N = 78
X = (7^k a - 3^k b) mod N = 110
X mod p = 0   <-- zero, so p | X
X mod q = 8
gcd(X, N) = 11   (recovers p)

Walk it line by line, because every claim from the maths section shows up as a number here:

1. The secrets are $p=11$, $q=17$, $N=187$, with tiny exponents $e_1=3$, $e_2=5$.
2. The forward construction produces $c_1 = 73^3 \bmod 187 = 57$ and $c_2 = 174^5 \bmod 187 = 89$. These are the only things a solver would actually see.
3. The common exponent is $k = 3\cdot 5 = 15$. Raising the ciphertexts to the other exponent gives $a = 57^5 \bmod 187 = 109$ and $b = 89^3 \bmod 187 = 166$.
4. The collapse is visible. $(2p+3q)\bmod p = 73\bmod 11 = 7$, which equals $3q\bmod p = 51\bmod 11 = 7$. And $a\bmod p = 109\bmod 11 = 10$, exactly matching $3^{15}q^{15}\bmod 11 = 10$. The $p$-terms in the binomial expansion really did vanish.
5. Form the combination: $7^{15}a \bmod 187 = 1$ and $3^{15}b \bmod 187 = 78$, so $X = (1-78)\bmod 187 = 110$.
6. The payoff. $X \bmod 11 = 0$ (so $11 \mid X$) but $X \bmod 17 = 8 \neq 0$. Therefore $\gcd(110,187) = 11 = p$. We pulled a prime out of a product using nothing but a subtraction and a gcd.

The only difference between this toy and the real challenge is the number of digits.

The re-implementation

Here is the ground-truth port, solve.py, carrying the challenge's own data inline so it is fully self-contained. The factor() function is the whole attack in six lines; everything around it is the parsed data.txt.

#!/usr/bin/env python3
"""Modular Binomials (CryptoHack, maths track, 80 pts).

Construction (from data.txt):
    N  = p * q
    c1 = (2*p + 3*q)**e1 mod N
    c2 = (5*p + 7*q)**e2 mod N

Weakness: reduce everything mod p. Since 2p+3q == 3q (mod p) and
5p+7q == 7q (mod p), raising the ciphertexts to the *other* exponent
gives terms that share the factor q**(e1*e2) mod p. A linear combination
kills that shared factor, leaving a multiple of p that we extract with gcd.
"""
from math import gcd

# ---- the challenge's own data (data.txt) ----
N  = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

def factor(N, e1, e2, c1, c2):
    k = e1 * e2                      # shared exponent
    a = pow(c1, e2, N)              # (2p+3q)^(e1*e2) mod N
    b = pow(c2, e1, N)              # (5p+7q)^(e1*e2) mod N
    # 7^k * a - 3^k * b  ==  0  (mod p)
    X = (pow(7, k, N) * a - pow(3, k, N) * b) % N
    p = gcd(X, N)
    return p

p = factor(N, e1, e2, c1, c2)
assert 1 < p < N, "gcd did not isolate a nontrivial factor"
assert N % p == 0, "p does not divide N"
q = N // p

if __name__ == "__main__":
    print("recovered p =", p)
    print("recovered q =", q)
    print("p * q == N  :", p * q == N)
    print("p < q       :", p < q)
    # CryptoHack accepts the two primes; flag form is crypto{p,q}
    print("flag = crypto{%d,%d}" % (p, q))

A note on the exponents: pow(7, k, N) with $k = e_1e_2$ raises 7 to a ~1024-bit power, and pow(c1, e2, N) raises a 2047-bit base to a 512-bit power, all under a 2047-bit modulus. Python's built-in pow uses square-and-multiply, so each of these is a few thousand modular multiplications — microseconds, not minutes. Running it:

$ python3 solve.py
recovered p = 1122740001692584863902620644419912006085563761274089527015149626443409218991960915575193827633565341063769064894451032551775935948989662501767736054327659838971050477956194706591570570937714073091683456705414187724278071480392074899008100137836739579840062691206521340076892724845178053983902773080017194 31273
recovered q = 1327605878063653019714791570720314483801357657944667874569487867311680958779568752952826615654882421907315932826636947289149459672531730473243539815309493600315357073747017053284508569445988032282999670090045989846712934943755994087641397432174650127703767288765479588520254255392984107511327826328179471 01601
p * q == N  : True
p < q       : True
flag = crypto{112274000169258486...,132760587806365301...}

(Line wraps are mine; the integers print on single lines.) p * q == N is the proof. The 71 ms wall time came from time python3 solve.py during development. CryptoHack's flag for this challenge is the pair of primes wrapped as crypto{p,q}.

Verifying the model

Recovering a factor of $N$ proves the gcd worked — but it does not, on its own, prove that my model of the forward construction is exactly right. Maybe I got lucky and the coefficients are $(2,3)$ and $(5,7)$, or maybe I transposed something and the gcd still happened to land. The honest check is to run the construction forward with the recovered primes and confirm it regenerates the exact published c1 and c2. That is what verify.py does, and it also recovers $q$ independently via the mirror-image combination (the one that cancels mod $q$ instead of mod $p$):

#!/usr/bin/env python3
"""Round-trip check: re-encrypt with the recovered primes and confirm we
reproduce the exact c1, c2 from data.txt. Also sanity-check primality and
the alternative gcd that recovers q directly."""
from math import gcd
from solve import N, e1, e2, c1, c2, p, q

# 1) re-encrypt
c1_check = pow(2*p + 3*q, e1, N)
c2_check = pow(5*p + 7*q, e2, N)
print("c1 reproduced:", c1_check == c1)
print("c2 reproduced:", c2_check == c2)

# 2) the *other* combination should recover q (cancel p mod q)
k = e1 * e2
a = pow(c1, e2, N)
b = pow(c2, e1, N)
Y = (pow(5, k, N) * a - pow(2, k, N) * b) % N
q2 = gcd(Y, N)
print("q via 2nd combo == q:", q2 == q)

# 3) Miller-Rabin primality (deterministic-ish for this size)
import random
def is_probable_prime(n, rounds=40):
    if n < 2: return False
    for sp in (2,3,5,7,11,13,17,19,23,29,31,37):
        if n % sp == 0: return n == sp
    d = n - 1; r = 0
    while d % 2 == 0: d //= 2; r += 1
    for _ in range(rounds):
        x = pow(random.randrange(2, n-1), d, n)
        if x in (1, n-1): continue
        for _ in range(r-1):
            x = x*x % n
            if x == n-1: break
        else:
            return False
    return True

print("p is prime:", is_probable_prime(p))
print("q is prime:", is_probable_prime(q))
print("bit lengths:", p.bit_length(), q.bit_length(), "N:", N.bit_length())

$ python3 verify.py
c1 reproduced: True
c2 reproduced: True
q via 2nd combo == q: True
p is prime: True
q is prime: True
bit lengths: 1024 1024 N: 2047

Five independent confirmations:

• c1 reproduced / c2 reproduced — feeding the recovered $p,q$ back through $(2p+3q)^{e_1}\bmod N$ and $(5p+7q)^{e_2}\bmod N$ yields the byte-exact c1 and c2 from data.txt. My model of the construction is not approximately right, it is exactly right.
• q via 2nd combo — the symmetric attack works too. To cancel the $p$-terms instead, reduce mod $q$ (where $2p+3q\equiv 2p$, $5p+7q\equiv 5p$) and form $5^{k}a - 2^{k}b$, whose coefficients $2\cdot 5 = 5\cdot 2$ now match. Its gcd with $N$ gives $q$ directly. Both halves of the modulus are equally exposed.
• Miller–Rabin confirms both factors are genuine 1024-bit primes (no sympy in the sandbox, so I rolled a 40-round probabilistic test), and the bit lengths line up with the 2047-bit $N$.

Why "binomials," and the lesson

The structural flaw here is not that the exponents are weak (they're 512-bit) or that $N$ is small (it's 2048-bit RSA strength). It's that the plaintext being raised to a power is a known linear form in the secret primes: $2p+3q$ and $5p+7q$. The instant you have an expression in $p$ and $q$ and you read it modulo one of them, half of it disappears. Combine two such expressions to cancel what's left, and the modulus splits.

The general recipe, worth memorizing:

If you are given $f(p,q)^{e}\bmod N$ for known low-degree forms $f$ — especially linear forms $\alpha p+\beta q$ — you can usually reduce mod $p$ to drop the $p$-terms, raise to a common power so the residual $q$-terms align, take a linear combination to cancel them, and gcd the result with $N$ to peel off a factor.

This is the same family of ideas behind Coppersmith / Franklin–Reiter related-message attacks: a structured plaintext is a gift, because structure survives exponentiation in ways that let you set up an equation the attacker can solve. RSA's hardness assumption is about factoring a modulus given only the modulus; it says nothing about a modulus you hand the attacker alongside two algebraic clues about its factors.

A few honest caveats on the boundaries of the attack:

• It needs the coefficients to be known ($2,3,5,7$ here). If they were secret, the cancellation couldn't be set up.
• It needs the two forms to be distinct enough that the cross-multiplied coefficients ($7\cdot 3$ vs $3\cdot 7$ mod $p$; $5\cdot 2$ vs $2\cdot 5$ mod $q$) genuinely match — which they do by construction.
• The gcd lands on $p$ rather than $N$ only because $X\not\equiv 0\pmod q$. I argued above why that holds with overwhelming probability; the c1/c2 reproduced check and the clean p < q ordering confirm it held here.

I did briefly consider whether a full multivariate-binomial expansion was required (it is the challenge's namesake, after all), or whether anything subtler than "reduce mod $p$" was going on. It isn't: the expansion and the one-line reduction are the same statement, and the toy trace shows the residual term is literally $3^k q^k \bmod p$. No lattice, no Coppersmith machinery, no sympy — math.gcd and Python's built-in pow are the entire toolkit.

References

• CryptoHack — Modular Binomials, Mathematics track, 80 pts, 8747 solves at time of writing. Challenge catalogue: https://cryptohack.org/challenges/ . Data file: https://cryptohack.org/static/challenges/data_04a0fe134cf31a6c941377aad75db81c.txt (sha256 2bbb014b…3a78e7, 2190 bytes).
• The binomial theorem and modular reduction — every term of $(\alpha p+\beta q)^k$ except the $i=0$ term carries a factor of $p$, hence vanishes mod $p$.
• Background on structured-plaintext RSA weaknesses: Boneh, Twenty Years of Attacks on the RSA Cryptosystem (1999) — the survey that frames "known algebraic structure in the message" as a recurring break.
• Tooling: Python 3.13 int (arbitrary precision), math.gcd, and pow(base, exp, mod) (square-and-multiply). No external packages required.

Artefacts

The download bundle contains data.txt (the challenge's five integers, verbatim), solve.py (the six-line attack plus inline data), verify.py (the round-trip and primality checks), toy.py (the hand-traceable miniature), and deadends.py (the naive attempts that returned 1). Every code block above is reproduced in full from those files; copy any of them out of this post and they run as-is on a stock Python 3.