2
$\begingroup$

The Pohlig-Hellman algorithm is for computing discrete logarithms in a group whose order is a smooth integer.

This algorithm requires the factorization of the group order. However we know that factorization of big number is a hard problem. So how could Pohlig-Hellman be an effective algorithm?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Factorization of large numbers is a hard problem only if the factors are all very large. Not otherwise. $\endgroup$
    – user93353
    May 7, 2021 at 14:48
  • $\begingroup$ @user93353 Why is it easier to factorize a smooth number? $\endgroup$
    – Liang Chen
    May 8, 2021 at 2:14
  • $\begingroup$ The difficulty of factorising large numbers is true only if their factors are large. It prevents brute-forcing to find the factors. You start checking factors starting with 2, 3, etc. If say 2 is factor, then you have now only factor n/2 next - so the size of the number which is left to factor has already reduced. Likewise if you can find any factor (f) which is not so big as to make brute-forcing impossible, then you now only have to factor n/f which is smaller than n. So the security of the factor problem depends on how big the smallest factor of the number is. $\endgroup$
    – user93353
    May 8, 2021 at 2:39
  • $\begingroup$ @user93353: the reasoning you make leads to the conclusion that the security of the factoring problem against trial division depends essentially on the size of the second largest factor. And certainly not of the "smallest factor", which typically is almost immaterial when there's more than two factors, as considered in the question. For other factoring algorithms, the conclusion differs. If we don't specify the algorithm, things get even more hairy. $\endgroup$
    – fgrieu ♦
    Jun 7, 2021 at 8:49
  • $\begingroup$ @fgrieu - yes, of course you are right. By what I (mis)said in my last line a Sophie Germain prime would be bad. $\endgroup$
    – user93353
    Jun 8, 2021 at 11:24

1 Answer 1

Reset to default
1
$\begingroup$

I will mostly talk about the Elliptic Curve since here the field size is around $2^{255}, 2^{448},2^{512}$ for secure curves. With Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ the number of points is not too far away from the field size. With this, we can compare with the factoring records.

The current record achieved in 2020, CADO-NFS has factored an 828-bit $n$ with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)". For the history see this detailed answer

If you set up a curve that has no big prime order on the order of the safe curves, it is not hard to factor for a dedicated attacker then use the Pohlig-Hellman algorithm for the discrete logarithm. Don't set up such a curve.

Actually, the parameters are never meant to be hiding see in SafeCurves, no security by obscurity. This more about don't propose a curve that doesn't have a large factor.

Having one large and a few small is fine like Curve255 has 8 as cofactor. The cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The order of the subgroups is $2,4,8,n,2n,4n,8n$.

Small groups are also vulnerable to small-subgroup attacks ( Lim–Lee active small-subgroup attacks), so we don't want them for this reason, too. Curve255 has no problem with either the curve itself or its twist.

Multiplicative discrete logarithm, on the other hand, dead for characteristic 2 ($GF(2^m)$) and almost dead for characteristic 3, ($GF(3^m)$). To be secure you need to a big field that the Pohlig-Hellman is your least problem (see on the keylength.com). Anyway, there are not to be kept secret either.

Improve this answer
$\endgroup$
0

Your Answer

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

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