Modular Arithmetic for CTF Crypto: The Math Behind RSA, DH, and ECC

Six ideas stand between you and every crypto challenge

People bounce off CTF cryptography because the writeups say things like "recover d by inverting e modulo phi(n)" and assume you already know what that sentence means. It is not deep mathematics. It is six concepts, all of which fit on this page, and all of which have a one-line Python implementation.

Those six are: congruence, the greatest common divisor, the modular inverse, Euler's totient, fast exponentiation, and the Chinese Remainder Theorem. Learn them once and RSA stops being magic, Diffie-Hellman becomes obvious, and elliptic curves become the same ideas in a different group.

You do not need number theory. You need six operations and the ability to notice which one a challenge has left unprotected.

This post is the prerequisite page for the RSA attacks guide, Diffie-Hellman, and elliptic curves. The cryptography roadmap places all of them in order.

Congruence: arithmetic on a clock

Working modulo n means keeping only the remainder after division by n. A twelve-hour clock is arithmetic modulo 12: four hours after ten o'clock is two o'clock, because 14 mod 12 is 2. Two numbers are congruent modulo n when they leave the same remainder, written a ≡ b (mod n).

The rule that makes this useful: addition, subtraction, and multiplication all survive the reduction. You may reduce at any point, as often as you like, and the answer does not change. That is why cryptography can multiply thousand-digit numbers without ever storing a million-digit intermediate.

>>> (17 * 23) % 5
1
>>> ((17 % 5) * (23 % 5)) % 5    # reduce first, same answer
1
>>> (-3) % 7                      # Python always returns non-negative
4

You have already used this without naming it. A Caesar cipher is addition modulo 26, and ROT13 is the special case where the shift is its own inverse. The classical ciphers guide is modular arithmetic on the alphabet.

GCD, and why it breaks real keys

The greatest common divisor of two numbers is the largest integer dividing both. Euclid's algorithm computes it in microseconds even for thousand-bit inputs, which is why it appears in attacks rather than only in theory. Lame's theorem, proved in 1844, bounds the number of division steps at five times the decimal digit count of the smaller input. A 2048-bit modulus has about 617 digits, so the worst case is roughly 3,000 iterations: the reason factoring a shared-prime key pair is instant while factoring one key is impossible.

That gap has cost real money. The ROCA vulnerability, CVE-2017-15361, was a flawed prime generator in an Infineon library that gave its RSA keys enough structure to be factored directly; Estonia suspended roughly 760,000 national ID cards over it in 2017. No lattice, no supercomputer, just primes that were not random enough.

from math import gcd
 
gcd(1071, 462)      # 21
 
# the attack: two RSA moduli that share a prime
p = gcd(n1, n2)
if p > 1:
    q1, q2 = n1 // p, n2 // p     # both keys are now broken

Two numbers are called coprime when their GCD is 1. That condition shows up constantly: it is exactly when a modular inverse exists, exactly when the Chinese Remainder Theorem applies, and exactly what e must be relative to phi(n) for RSA to work at all.

Modular inverses: the closest thing to division

The inverse of a modulo n is the number x with a * x ≡ 1 (mod n). It exists if and only if gcd(a, n) == 1. Once you have it, dividing by a means multiplying by x.

pow(3, -1, 7)        # 5, because 3*5 = 15 = 1 (mod 7). Python 3.8+
 
# the same thing by hand, if you need it in another language
def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y
 
def inv(a, n):
    g, x, _ = egcd(a % n, n)
    if g != 1:
        raise ValueError('no inverse: not coprime')
    return x % n

This is where the RSA private exponent comes from: d = pow(e, -1, phi). Every challenge that gives you the factorization of n is asking for exactly this line.

Fermat, Euler, and the totient function

Euler's totient phi(n) counts the integers below n that are coprime to it. For a prime p it is p - 1, because everything below a prime is coprime to it. For a product of two distinct primes, which is the RSA case, it is (p - 1) * (q - 1).

Euler's theorem says that for any a coprime to n, a^phi(n) ≡ 1 (mod n). Fermat's little theorem is the prime case: a^(p-1) ≡ 1 (mod p). Two consequences do all the work in CTF:

• Exponents live modulo phi. a^k mod n only depends on k mod phi(n). A gigantic exponent reduces to a small one the moment you know the totient.
• Encryption and decryption cancel. RSA works precisely because e and d are inverses modulo phi(n), so raising to e then to d returns the original message.

Fast exponentiation, and why the naive version hangs

Computing pow(m, e) % n for a 2048-bit modulus builds an integer with millions of digits before the reduction ever happens. Your script does not crash, it just never finishes. Square-and-multiply reduces at every step and finishes in milliseconds.

The difference is the difference between exponential and linear in the bit length. A 2048-bit exponent needs about 2,048 squarings plus at most 2,048 multiplications, each on numbers that never exceed the modulus, so a few thousand operations total. The naive form needs e multiplications, and e here is a number with 617 decimal digits. Python's three-argument pow implements the fast version natively, which is why every crypto script in this guide uses it and none of them import a library for it.

pow(m, e, n)         # correct: three-argument pow, always use this
pow(m, e) % n        # wrong: allocates a colossal integer first
 
# what the builtin is doing
def powmod(b, e, n):
    r = 1
    b %= n
    while e:
        if e & 1:
            r = r * b % n
        b = b * b % n
        e >>= 1
    return r

RSA is these ideas in three lines

With the pieces above, the entire cryptosystem is short enough to read in one screen. No step uses anything not already covered.

# key generation
n = p * q
phi = (p - 1) * (q - 1)
e = 65537                     # must be coprime to phi
d = pow(e, -1, phi)           # modular inverse
 
# use
c = pow(m, e, n)              # encrypt
m = pow(c, d, n)              # decrypt
 
# a full break, given the factors
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))

Read those lines against the failure modes and the standard CTF attacks explain themselves. If e is 3 and the message is short, m^3 never exceeds n, so no reduction happens and an integer cube root recovers the message. If p and q are close, Fermat factorization finds them. If two moduli share a prime, one GCD breaks both.

from gmpy2 import iroot
m, exact = iroot(c, 3)        # small-e attack when m^3 < n
 
from sympy import factorint
factorint(n)                  # works when n is small or has tiny factors

The Chinese Remainder Theorem: recombining partial answers

Given remainders of an unknown number modulo several pairwise coprime bases, CRT reconstructs the number modulo their product, uniquely. In CTF it appears in two recurring shapes.

It is also in the deployed standard. Section 3 of RFC 8017 defines a second representation for the RSA private key that stores five extra values (p, q, dP, dQ, qInv) so decryption can run two half-size exponentiations and recombine with CRT. Since modular exponentiation costs roughly the cube of the bit length, halving the modulus makes each operation about 8 times cheaper, and doing two of them nets a 4x speedup. That is why an OpenSSL private key file is far larger than (n, d) would require.

The optimisation carries its own attack. Boneh, DeMillo, and Lipton showed in 1997 that a single computational fault during one of the two CRT branches produces a signature that fails to verify, and a single GCD between that faulty signature and the correct one recovers p outright. One glitched bit, one gcd, whole key. If a challenge hands you a valid and an invalid signature over the same message, this is what it wants.

• Hastad broadcast. The same message encrypted with e = 3 under three different moduli. CRT recombines the three ciphertexts into m^3 modulo the product, which now exceeds m^3 itself, so a plain cube root finishes it.
• Pohlig-Hellman. A discrete log solved separately in each small prime subgroup, then reassembled with CRT. This is why a "smooth" group order destroys Diffie-Hellman, as covered in the Diffie-Hellman guide.

from sympy.ntheory.modular import crt
 
residues = [2, 3, 2]
moduli   = [3, 5, 7]
x, mod = crt(moduli, residues)   # x = 23 (mod 105)

Discrete logarithms: the hard direction

Given g, p, and y = g^x mod p, finding x is the discrete logarithm problem. Exponentiation is cheap and its inverse is not, which is the asymmetry Diffie-Hellman and elliptic-curve cryptography are built on.

It is only hard when the parameters are chosen well, and CTF parameters usually are not. The costs are known precisely, which is what lets you decide in advance whether an attack is worth starting. Shanks' baby-step giant-step runs in O(sqrt(n)) time and O(sqrt(n)) memory, so a 64-bit modulus needs about 4 billion stored entries and is out of reach on a laptop, while a 40-bit one needs about a million and finishes instantly. Pohlig-Hellman, published in 1978, reduces the problem to the largest prime factor of the group order, so a 2048-bit prime whose p-1 factors into small primes is as weak as its biggest factor. NIST SP 800-56A therefore requires safe primes and validated group parameters, which challenge authors reliably skip. Three shortcuts cover most challenges:

• Small modulus: brute force or baby-step giant-step, which trades memory for a square-root speedup.
• Smooth group order: Pohlig-Hellman solves it in each small subgroup and glues the answers with CRT.
• Small exponent: if x is a PIN, a year, or a timestamp, the keyspace is a few million and a loop wins. Weak parameter choice is covered in the insecure randomness guide.

from sympy.ntheory.residue_ntheory import discrete_log
discrete_log(p, y, g)         # fine for CTF-sized parameters

The Python toolkit

pip install pycryptodome sympy gmpy2
 
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse, isPrime
from sympy import factorint, isprime, totient, nextprime
from sympy.ntheory.modular import crt
from gmpy2 import iroot, mpz
 
bytes_to_long(b'picoCTF{x}')   # message as an integer
long_to_bytes(m)               # and back
pow(c, d, n)                   # the workhorse

Two habits save real time. Convert between bytes and integers only at the boundaries of your script, and print intermediate values in hex when they should be printable. The Python for CTF guide covers the conversion pitfalls, and XOR for CTF covers the other arithmetic primitive you will use just as often.

Where to practice

• picoCTF 2022 basic-mod1 and basic-mod2 are pure modular arithmetic, with the second requiring a modular inverse rather than a reduction. Start here.
• picoCTF 2019 john_pollard is factoring a small modulus, the direct link between factorization and key recovery.
• picoCTF 2021 Mind your Ps and Qs gives an n small enough to factor outright, then asks for the full decryption chain.
• picoCTF 2022 Sum-O-Primes hands you p + q and n, which is a quadratic away from both factors. Algebra, not cracking.
• picoCTF 2022 Very Smooth is smoothness made concrete: when p - 1 has only small prime factors, Pollard's p-1 algorithm finds the factor using nothing but Fermat's little theorem and a GCD.
• picoCTF 2025 Even RSA Can Be Broken is the extreme case of a badly chosen prime. Once one factor is guessable, the totient falls out and the private exponent is a single inverse away.
• picoCTF 2026 clusterRSA builds its modulus from many primes rather than two. More factors means each one is far smaller than the square root of n, so the factorization that should be infeasible finishes in seconds.

Quick reference

That is the whole mathematical toolkit for CTF cryptography below the research tier. With it, the RSA attacks guide reads as a list of symptoms rather than a wall of theorems, and elliptic curves becomes the same six operations performed on points instead of integers.

Sources and further reading

The maths here is centuries old, but the parameter choices that make it safe are recent and written down. Both halves are worth reading from the source.

• RFC 8017 specifies RSA including the five-value CRT private key form, and NIST SP 800-56B Rev. 2 covers key establishment with integer factorization.
• NIST SP 800-56A Rev. 3 explains the discrete-log parameter validation that Pohlig-Hellman punishes when it is skipped.
• CVE-2017-15361 (ROCA) for what happens when prime generation has structure.
• Implementations: Python three-argument pow, SymPy number theory, and gmpy2.