# Pohlig-Hellman Algorithm December 2014

I'm reading through A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgoup which is a **Small subgroup confinement attack**.

It deals with stuff I had no knowledge of, like **Schnorr's Signature** that I talk about in a previous post, or like what I'm going to talk about now:

The Pohlig-Hellman Algorithm is a method to compute a **Discrete Logarithm** (which is a difficult problem) on a multiplicative group whose order is a smooth number (also called *friable*). Meaning its order can be factorized into small primes.

```
y = g^x mod p
ord_p(g) = p - 1
p - 1 = q_1^(i_1) * ... * q_j^(i_j)
```

Here y is the public key,

`x`

is the secret key we're trying to compute.

The order of`g`

, our generator, is`p - 1`

since p is prime.

p - 1 is smooth so it can be factorized into something like 2^2 * 3 * 7 (extremely convenient example!)

Following is an **overview** of the method, if you read an equation and feel like it comes from nowhere (and it should feel like that), I posted a very short paper containing the simple proofs of those bellow.

## Overview

The idea that should come to your mind, if you're used to seeing that kind of problem, is that there might be a way to use the **Chinese Remainder Theorem** (abbreviated CRT) to our advantage. What if we could write `x`

modulo the factors of `p - 1`

and then **reconstruct** the real `x`

with the CRT? Well, let's do just that!

To write `x`

modulo a factor `q`

of `p - 1`

we can write `y^((p-1) / q)`

which we know and can compute, and is also equal to `g^(x_q * (p-1) / q)`

(If you have a factor that appears multiple times in the prime decomposition of `p - 1`

(for example `p - 1 = 2^5`

, then there is also a way to ease the computations by finding multiple unknowns (5 unknowns in our example))

We then have a discrete logarithm to compute, but a small one, that we can compute efficiently thanks to Shanks' method (baby-step giant-step) or Pollard's rho algorithm.

Then we have multiple ways of writing our `x`

(modulo the factors of `p - 1`

) and we find out what is `x`

with CRT (I explained this step in my airbus write-up here).

## Proofs + Video

You can read through the Algorithm (or watch the video bellow), but I don't really like to do that since I'm not really good at memorizing something if I don't understand the nut and bolts of it. So here's a really good paper written by **D. R. Stinson** that demonstrate where the equations of the algorithm come from. And here's an explanation + example of the algorithm: