0
$\begingroup$

I think I have an understanding of the Pohlig-Hellman attack on elliptic curves. From page 31 of Pairings for Beginners:

  • Find the group order $\#E(\mathbb{F}_q)$, call it $n$, and factor it. Example: $966 = 2 \cdot 3 \cdot 7 \cdot 23$
  • For each prime factor $p_i$, above: multiply the generator $P$ and target point (not sure what the term is), $Q$, by $n/p_i$ (the cofactor)
    • This particular example does not have any prime factors that are raised to powers, (e.g the factorization is not $2^3 \cdot 5^2$, but you multiply by the $n$ divided by the prime, not the prime raised to exponent)
  • Now we have $[\frac{n}{p_i}]P$ and $[\frac{n}{p_i}]Q$.
  • We know the order of $[\frac{n}{p_i}]P$ is $p_i$
  • Thus, $[\frac{n}{p_i}]Q = [k \text{ mod } p_i]P$ where $kP = Q$
  • We solve for $k\text{ mod } p_i$ and repeat for each $p_i$
  • Then, using Chinese Remainder Theorem, we can find $k\text{ mod } n$

This all roughly makes sense. It also matches up with other explanations of Pohlig-Hellman on this site: Pohlig-Hellman algorithm.

However, I'm confused b/c it seems like the "full" Pohlig-Hellman attack, involves representing $k_i$ as $z_0 + z_1p_i + z_2p_i^2 + ...$

Why are there multiple variations of the Pohlig-Hellman algorithim?

$\endgroup$

1 Answer 1

2
$\begingroup$

Actually, the method using the Chinese Remainder Theorem is the more general version. The one representing $k_i$ as $z_0 + z_1p_i + z_2p_i^2 + ...$ is only useful in the situation that the group order is a prime power (a power of $p_i$), so you solve in each of the smaller powers first and build up. You use the CRT (or a mixture of both) when the groups are not all powers of the same prime. In both cases, the idea is the same - solve the DLP in a smaller subgroup and use that information to reconstruct the solution in the full group.

$\endgroup$
2
  • $\begingroup$ To clarify, when you say the "group order" you mean the order of the sub-group $p_i^{n_i}$ right? $\endgroup$
    – Foobar
    Jan 28, 2022 at 16:13
  • $\begingroup$ The full order of the group you are computing the discrete log in. In the example in your question, the order was composite (966) so we use the CRT. If the order was, say, 3^5, we would first use the subgroup of order 3, then 3^2, then 3^3, etc. $\endgroup$ Jan 28, 2022 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.