Pohlig-Hellman: why the group order must have a large prime factor (1978)

Pohlig and Hellman noticed that a discrete log in a group of order n = p1**e1 * p2**e2 * … splits into small problems, one per prime power, recombined with the Chinese Remainder Theorem. The cost depends on the largest prime factor of n, not on n. A huge group with a smooth order is weak.

What to look for

Two groups of about the same size: one whose order splits into small primes, one of prime order. Pohlig-Hellman breaks the first almost instantly and gains nothing on the second. This is why Diffie-Hellman and Schnorr use a subgroup of large prime order, like blockchainkit’s TEACHING_GROUP.

The history behind this experiment: Breakthroughs in Cryptography.

A smooth order falls apart

import matplotlib.pyplot as plt

import blockchainkit as bk
from blockchainkit.crypto.systems.discrete_log import factor_order

smooth_p = 8101  # 8100 = 2**2 * 3**4 * 5**2
print("order factors:", factor_order(smooth_p - 1))
secret = 4321
target = pow(6, secret, smooth_p)  # 6 generates the whole group modulo 8101.
ph = bk.crypto.pohlig_hellman(6, target, smooth_p, smooth_p - 1)
bsgs = bk.crypto.baby_step_giant_step(6, target, smooth_p, smooth_p - 1)
assert ph.exponent == bsgs.exponent == secret
print("Pohlig-Hellman:", ph.group_operations, "ops; baby-step giant-step:", bsgs.group_operations)

order factors: {2: 2, 3: 4, 5: 2}
Pohlig-Hellman: 27 ops; baby-step giant-step: 139

A prime order does not

prime_order = bk.crypto.DHGroup(8147, 4073, 4)  # 4073 is prime.
target = prime_order.public(1234)
ph_prime = bk.crypto.pohlig_hellman(4, target, prime_order.p, prime_order.q)
bsgs_prime = bk.crypto.baby_step_giant_step(4, target, prime_order.p, prime_order.q)
assert ph_prime.exponent == bsgs_prime.exponent == 1234
assert ph_prime.group_operations >= bsgs_prime.group_operations

fig, ax = plt.subplots(figsize=(7, 4))
labels = ["smooth order 8100", "prime order 4073"]
xs = range(2)
ax.bar(
    [x - 0.18 for x in xs],
    [bsgs.group_operations, bsgs_prime.group_operations],
    0.36,
    label="baby-step giant-step",
)
ax.bar(
    [x + 0.18 for x in xs],
    [ph.group_operations, ph_prime.group_operations],
    0.36,
    label="Pohlig-Hellman",
)
ax.set_xticks(list(xs), labels)
ax.set(ylabel="group operations", title="Only the largest prime factor matters")
ax.legend()
fig.tight_layout()

Exercise

The teaching group uses p = 2q + 1 with q prime (a “safe prime”). What is the largest prime factor of p - 1, and what would Pohlig-Hellman cost in the order-q subgroup? Why would working in the full group modulo p leak one bit of every exponent?