UDCTF 2023 - Strong Primes

Published October 29, 2023 • more posts

I've written a diffie hellman server. I made sure not to let people select their parameters, and I use only strong primes. Those are safe, right?

We're given five files: alice.py, server.py, auth.log, strong_primes.txt, and gen_agreed_primes.py. alice.py performs a Diffie–Hellman key exchange, which consists of the following steps:

For each exchange, server.py logs the ciphertext, AA, BB, and pp to auth.log. However, normally this information is not enough to compute the shared secret. The security of DH relies on the fact that it is generally difficult to determine xx given the value of gxg^x for cyclic groups. This is called the discrete logarithm problem.

gen_agreed_primes.py contains the code used to generate the primes used for the exchanges. We see that the primes were generated using pycrypto's Crypto.Util.number.getStrongPrime() function, "strong" meaning that p1p - 1 has at least one large prime factor.

The factorization of p1p - 1 matters, because for prime values of pp the order of the multiplicative group of integers mod pp is equal to p1p - 1. If the order of a cyclic group has prime factor rr, we can compute the value of xmodrx \bmod r in r\sqrt{r} time.

To identify factors of p1p - 1, we can simply try dividing it against a list of primes. In my case I used a list of primes up to 10710^7. This revealed that for many of the primes used in the authentication, p1p - 1 contains "small" prime factors.

Suppose we are able to calculate xmodrx \bmod r for values r1,r2,rnr_1, r_2, \dots\, r_n. The Chinese remainder theorem states that from these values we can compute the value of xmod(r1×r2××rn)x \bmod (r_1 \times r_2 \times \dots \times r_n). If we are able to do this for enough values of rr, we can leak Alice's entire secret value, whic allows us to compute the shared secret and decrypt the ciphertexts. (The server uses a different secret value each time, so we can't apply the same strategy there.)

We have to be careful, since 22 may only generate a subgroup of the full group. However, we know that the order of the full group divisible by the order of the subgroup (Lagrange's theorem), so we can easily determine whether a factor of p1p - 1 is also a factor of the subgroup's order:

let order = p - 1n;
const subgroupFactors = [];
for(const factor of factorize(order)) {
    // if order/factor is equal to or a multiple of the subgroup's order, 2^order/factor will be equal to 1
    if(powMod(2n, order / factor, p) == 1n) {
        order /= factor;
    } else {

To determine xmodrx \bmod r, we start by transforming our gg and y=gxy = g^x to elements of a cyclic group of order rr:

g=gp1rg' = g^\frac{p - 1}{r} y=yp1ry' = y^\frac{p - 1}{r}

Then, we just need to solve (g)x=y(g')^{x'} = y' for xx'. For this I made a small implementation of the baby-step giant-step algorithm since there wasn't one for JS, but you can easily accomplish this using tools like SageMath. Because rr is small, this process is fast.

const discreteLog = (g, y, p, order) => {

    if(y==1n) return order;

    const m = sqrt(order);

    const arr = new Array(m);
    for(let j = 0n; j < m; j++) {
        arr[powMod(g, j, p)] = j; 

    const c = powMod(g, m * (order - 1n), p);
    let gamma = y;
    for(let i = 0n; i < m; i++) {
        if(gamma in arr) {
            return i * m + arr[gamma];
        gamma = (gamma * c) % p;


So at this point, we have a list of values for rr and xmodrx \bmod r. We just need to solve this system of congruences and check if gxg^x matches Alice's public value (meaning we have retrieved the full key):

const factors = Object.keys(map).map(BigInt);
let N = factors.reduce((a,c) => a*c, 1n);
let ans = 0n;
for(const factor of factors) {
    ans += map[factor] * (N / factor) * inverse(N / factor, factor);
ans %= N;

// test if we have the full secret
if(powMod(g, ans, p) == y) {

Once we have Alice's secret, we can use it to compute the encryption key and decrypt any ciphertext of your choosing from auth.log.

import hashlib
from Crypto.Cipher import AES
from Crypto.Util import Padding

# fill in parameters from auth.log
# p = ...
# B = ...
# iv = bytes.fromhex('...')
# ct = bytes.fromhex('...')

g = 2
aliceSecret = ...
ss = pow(B,aliceSecret,p)
key = hashlib.sha256(ss.to_bytes(2048//8,'big')).digest()[:16]
cipher = AES.new(key,AES.MODE_CBC,iv)




Resources §

Full solution code

Diffie-Hellman key exchange

Chinese remainder theorem

Baby-step giant-step

Pohlig–Hellman algorithm