Join Log in
Score:0
Foobar avatar Crypto

Why are there different versions of the Pohlig-Hellman attack?

fr flag
Foobar

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?

49
0 + 0
Score:2
meshcollider avatar Crypto
gb flag
meshcollider

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.

0 + 0
Foobar avatar
fr flag
Foobar
To clarify, when you say the "group order" you mean the order of the sub-group $p_i^{n_i}$ right?
0
Reply
meshcollider avatar
gb flag
meshcollider
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.