Approximate GCD Explained: When Your Secret Prime Hides in Plain Arithmeti

🇺🇸EN🇸🇦AR
• 10 min read • #Approximate GCD, #Lattice Cryptanalysis, #LLL, #Cryptography, #Homomorphic Encryption, #CTF

Imagine hiding a house key by supergluing it inside a bowling ball, then leaving a thousand identical bowling balls in your driveway. Sounds secure, right? Except every ball is only "identical" if nobody bothers to weigh them. Weigh a few, notice they're all suspiciously close to the same number, and the key stops being hidden at all.

That's basically what happens when someone builds their own encryption scheme by multiplying a secret prime with a random number, tossing in a pinch of noise, and calling it a day. The math has a name: the Approximate GCD problem, and it's the load-bearing wall behind a whole family of "encrypt with plain integers" schemes. Get the noise budget wrong and the whole wall comes down with nothing but a laptop and a lattice reduction algorithm.

This article covers what Approximate GCD actually is, why people keep reinventing it badly, how to break it when they do, and how to not be the person whose secret prime ends up in someone else's writeup.

What Is Approximate GCD, Anyway?

Regular GCD (greatest common divisor) is old news: given two numbers, find the biggest number that divides both. Approximate GCD asks a sneakier question: given several numbers that are each close to a multiple of some secret value, can you recover that secret value?

Formally, you're handed a bunch of samples that look like this:

x_i = p * q_i + r_i

Here p is the secret you want to protect (think: a private key), q_i is a big random multiplier that's different every time, and r_i is a small "noise" term thrown in to blur things. If r_i were always zero, recovering p would just be gcd(x_1, x_2, ...), trivial. The noise is what's supposed to make this hard.

This exact structure is the backbone of integer-based homomorphic encryption (schemes that let you compute on encrypted data without decrypting it first). A single encrypted bit looks like:

c = p * q + 2 * r + b

p is the secret prime, q is noise-scale randomness, r is small random noise, and b is the actual bit you're hiding (0 or 1). Notice the 2 * r: it's there so that c mod 2 still equals the bit once you strip away everything tied to p. Cute idea. The security of the whole scheme rides entirely on r being small enough, and p being large enough, that nobody can pull them apart.

Why Should You Care?

You've probably never typed "Approximate GCD" into a job description, and that's fine, most people building "secure" custom encryption never heard of it either, which is exactly the problem. This bug class shows up whenever someone:

  • Builds custom encryption instead of using an audited library, and it "feels" clever because it uses big primes and randomness
  • Implements a homomorphic encryption scheme from a paper without matching the paper's actual parameter sizes
  • Adds "noise" to a value for obfuscation, assuming noise automatically means security
  • Picks noise and multiplier sizes based on vibes instead of actual security proofs

The consequences are blunt: full recovery of the secret key, and by extension, every single value ever "protected" by it. Not partial leakage. Total, silent, mathematically guaranteed collapse, and the attacker doesn't even need to know the algorithm in advance, just enough samples encrypted under the same secret.

Worked Example: Breaking a Homemade Bit Cipher

Let's build a synthetic version of a scheme I ran into and see exactly where it falls apart.

The Setup

A small side project encrypts each bit of a secret message individually. The "encryption" for one bit looks like this:

from Crypto.Util.number import getPrime
import random

class BitCipher:
    def __init__(self, prime_bits=1024):
        self.p = getPrime(prime_bits)

    def encrypt_bit(self, bit):
        q = random.randint(self.p, self.p**2)
        r = random.randint(2**256, 2**512)
        return self.p * q + 2 * r + bit

    def encrypt_message(self, message: str):
        bits = "".join(f"{ord(c):08b}" for c in message)
        return [self.encrypt_bit(int(b)) for b in bits]

At a glance this looks reasonable. Big prime, big random multiplier, chunky noise term. The comments in the original code even used flowery language about "noise rituals" and "entropy harvested from chaos." Poetic. Also irrelevant to the actual math.

The Reasoning

Here's the part that matters: p is 1024 bits. The noise term r tops out around 512 to 513 bits. That's half the bit length of the secret. For Approximate GCD to be genuinely hard, the noise needs to be tiny compared to the secret, ideally tied to an actual security parameter, not "half of it, because that sounded safe enough."

With hundreds of encrypted bits sitting around (one ciphertext per bit of the message), you don't need to guess p at all. You can find it.

The Attack, Step by Step

  1. Recognize the shape. c = p*q + 2r + b is the textbook Approximate GCD / integer-FHE encryption formula. The moment you see a "custom cipher" doing secret * big_random + small_random , you already know what family of attack applies.
  2. Build a kernel lattice. Take a handful of ciphertexts c_1, ..., c_d and construct a lattice designed to find integer vectors u such that u · c = 0 . This is done with a scaling trick: stack the identity matrix next to a heavily scaled copy of the c values, then run lattice reduction (LLL). Because the scaling factor is enormous, the reduced basis is forced to zero out the c -component, handing you a genuine basis for the "kernel" of the ciphertext vector.
  3. Let the noise expose itself. Every vector u in that kernel satisfies u · c = 0 , which means u · r is always an exact multiple of p . If u 's entries are small enough, u · r is smaller in magnitude than p itself, and the only multiple of p smaller than p is zero. So u · r = 0 , for free, no guessing involved.
  4. Solve for the noise vector. With enough of these "noise-orthogonal" relations, the actual noise vector r gets pinned down to a small residual lattice (usually just rank 2, thanks to the two directions that don't get killed off: the ciphertext direction and one leftover noise direction). A second, smaller lattice reduction, combined with the fact that every r_i has to be a small positive number, nails down the exact values.
  5. Recover the prime. Once r is known exactly, p = gcd(c_1 - r_1, c_2 - r_2, ...) . The random multipliers q_i are, well, random, so they essentially never share a common factor beyond p itself. The gcd comes out clean.
  6. Decrypt everything. With p in hand, every single ciphertext reduces to bit = (c mod p) mod 2 , because 2r is always even and r is always smaller than p . Run that over every encrypted bit and the entire message falls out.

None of this required brute force, guessing the prime, or any weakness in the prime generation itself. The prime was fine. The noise budget was the vulnerability, and lattice reduction turned "hidden" into "computed" in a few seconds of runtime.

Adjacent Ideas

  • Shrinking the noise even further makes the attack easier , not harder, since the margin between "small enough to force to zero" and "the actual secret size" only grows.
  • Reusing the same secret prime across many ciphertexts is what made this attack practical. A handful of samples is already enough; hundreds just made the lattice construction comfortable.
  • Swap the multiplication for an actual FHE library with parameters chosen by a security proof (not vibes) and this entire attack chain stops working, because the noise-to-secret ratio the proof enforces closes the gap the lattice needs.

Vulnerable Code Examples

Vulnerable: noise is a large fraction of the secret's bit length, and the same secret is reused across many independent encryptions.

# VULNERABLE: noise (up to 512 bits) is way too large relative to
# the 1024-bit secret, and the same secret is reused for every bit.
class BitCipher:
    def __init__(self, prime_bits=1024):
        self.p = getPrime(prime_bits)

    def encrypt_bit(self, bit):
        q = random.randint(self.p, self.p**2)
        r = random.randint(2**256, 2**512)      # <- noise is far too big
        return self.p * q + 2 * r + bit

Patched: don't build this yourself. Use a maintained, peer-reviewed cryptography library for anything that needs to be actually secure. If you're experimenting with homomorphic encryption specifically, use an audited library (Microsoft SEAL, OpenFHE, TFHE-rs) with parameters chosen for you by people who do this for a living, not a random noise range you picked because the numbers looked big enough.

# PATCHED: use audited primitives. If you need to hide a bit or a
# message, use authenticated symmetric encryption, full stop.
from cryptography.fernet import Fernet

key = Fernet.generate_key()
cipher = Fernet(key)
token = cipher.encrypt(b"the actual secret message")

Yes, that's a smaller, more boring block of code. That's the point.

Defense: How to Not Get Approximate-GCD'd

  1. Never invent your own encryption scheme for anything that matters. Not even a "small internal tool." It always ends up somewhere important.
  2. If you must implement a published cryptosystem, match its parameters exactly. A scheme's security proof only holds for the noise-to-secret ratio it was proven under. Change the ratio, and the proof (and your security) goes with it.
  3. Never reuse a single secret across many samples in a noise-based scheme. Every additional sample is another equation an attacker can feed into a lattice.
  4. Use secrets, not random, for anything security-relevant in Python. It wasn't the main hole here, but Python's default random module is a Mersenne Twister, not cryptographically secure, and state recovery from its output is its own entire attack category.
  5. Get it reviewed. A five-minute glance from someone who's seen an Approximate GCD writeup before would have caught this before it shipped.

Testing / Audit Points

If you're reviewing code and see any of the following, stop and ask hard questions:

  • A "secret" multiplied by a large random number, with a smaller random number added for "obfuscation"
  • Homebrew comments describing the scheme in metaphors ("noise," "chaos," "entropy rituals") instead of citing an actual paper or standard
  • No reference to a specific, named cryptographic scheme with a security proof
  • The same secret key used across dozens or hundreds of independently generated ciphertexts

Final Thoughts

Approximate GCD isn't some obscure academic curiosity, it's the actual security foundation of real integer-based homomorphic encryption research, and it's provably hard when the parameters are chosen correctly. The problem is never the math. The problem is someone skimming a paper, copying the formula, and eyeballing the noise size because "half the bit length" sounded conservative enough.

It wasn't. A lattice doesn't care how confident you were.

The safest custom cipher is the one you never write.

References