# Smooth Criminal Writeup

## Challenge

We are given a standard finite-field discrete logarithm instance:

```text
h = g^x mod p
```

with

```text
p = 1363402168895933073124331075716158793413739602475544713040662303260999503992311247861095036060712607168809958344896622485452229880797791800555191761456659256252204001928525518751268009081850267001
g = 223
h = 1009660566883490917987475170194560289062628664411983200474597006489640893063715494610197294704009188265361176318190659133132869144519884282668828418392494875096149757008157476595873791868761173517
```

The flag is encoded as the secret exponent `x`, interpreted as bytes.

The hint says:

> Our cryptographer assured us that a 649-bit prime makes this completely unbreakable. He also said the order of the group "doesn't really matter that much."

That hint points directly at the structure of the multiplicative group modulo `p`.

## Key observation

For DLP in `F_p^*`, the relevant group order is `p - 1`, not just the bit length of `p`.

If `p - 1` has a large prime factor, generic discrete log attacks are still hard. But if `p - 1` is very smooth, then Pohlig-Hellman breaks the discrete log efficiently by reducing it to many tiny subgroup logs.

So the first thing to check is the factorization of `p - 1`.

## Factorization of `p - 1`

Factoring `p - 1` gives:

```text
2^3 * 3^3 * 5^3 * 7^2 * 11^3 * 13^3 * 17^3 * 19 * 23^2 * 29^2 * 31^3 *
37^2 * 41^2 * 43^2 * 47^3 * 53^3 * 59^3 * 61 * 67^3 * 71^2 * 73 * 79^3 *
83^2 * 89^3 * 97^4 * 101^2 * 103 * 107^2 * 109 * 113^2 * 127^7 * 131^2 *
137^3 * 139 * 149^5 * 151 * 157^3 * 163^3 * 167^2 * 173^3 * 179^3 * 181 *
191^5 * 193 * 197
```

The largest prime factor is only `197`. That is catastrophically smooth for a DLP group order.

We also check the order of `g = 223`. It has full order `p - 1`, so solving the discrete log modulo `p - 1` is enough to recover the exact exponent.

## Why Pohlig-Hellman works here

Suppose the group order is

```text
n = p - 1 = product(q_i^e_i)
```

Pohlig-Hellman computes `x mod q_i^e_i` for each prime power dividing `n`, then reconstructs `x mod n` using the Chinese Remainder Theorem.

For each prime power `q^e`, write:

```text
x = x_0 + x_1 q + x_2 q^2 + ... + x_(e-1) q^(e-1)
```

and solve for the base-`q` digits one at a time.

Let

```text
gamma = g^((p - 1) / q) mod p
```

Then `gamma` has order `q`. Since every `q` here is tiny, we can brute-force the discrete log in that subgroup.

At step `j`, if we have already recovered the lower digits of `x`, let `r` be the partial residue so far. Then:

```text
target = (h * g^(-r))^((p - 1) / q^(j+1)) mod p
```

This lands in a subgroup of order `q`, so the next digit is:

```text
x_j = log_gamma(target)
```

Because `q <= 197` for every factor, each subgroup log is trivial.

## Practical attack

The attack is:

1. Factor `p - 1`.
2. For each factor `q^e`, recover `x mod q^e` with Pohlig-Hellman digit lifting.
3. Combine the residues with CRT to recover `x mod p - 1`.
4. Verify that `g^x mod p == h`.
5. Convert `x` to bytes.

This works quickly because all subgroup logs are tiny brute-force searches.

## Solver

The repo now contains a complete solver in `solve.py`. The core idea is:

```python
def dlog_small_subgroup(base, target, order):
    value = 1
    for k in range(order):
        if value == target:
            return k
        value = (value * base) % p


def pohlig_hellman_prime_power(q, e):
    subgroup_generator = pow(g, (p - 1) // q, p)
    residue = 0
    for j in range(e):
        corrected = h * pow(g, -residue, p) % p
        target = pow(corrected, (p - 1) // (q ** (j + 1)), p)
        digit = dlog_small_subgroup(subgroup_generator, target, q)
        residue += digit * (q ** j)
    return residue
```

After computing all prime-power residues, the script recombines them with CRT and decodes the result as bytes.

## Recovering the flag

Running:

```bash
python solve.py
```

prints:

```text
utflag{sm00th_cr1m1nal_caught}
```

## Final flag

```text
utflag{sm00th_cr1m1nal_caught}
```

## Takeaway

The 649-bit prime was a distraction. The real security of finite-field DLP depends on the order of the subgroup generated by `g`. If `p - 1` is smooth and `g` lies in that smooth-order group, Pohlig-Hellman destroys the instance even when `p` itself is large.