Some questions about small subgroup attack。

[qxzhou1010]

Hi, I am reading your article : Hacking private keys from unsafe primes using the Pohlig-Hellman discrete logarithm. I found that the final solution for 6^a = 2 % p does not seem to use the small subgroup. Just like 100000008359680 = 2^8 5 11^2 13 19 31 37 43 53. Instead, solve the DLP problem directly in the large group p = 100000008359681. I am confused about this, please help me understand, thanks

[mvaneerde]

That's correct! If p is unsafe, then ALL keys k are vulnerable to quick recovery using Pohlig-Hellman, even if the order of the generator g is large

[qxzhou1010]

Thank you for your quickly reply. I have a few other questions I want to ask.

1. I'm trying to implement a small subgroup attack, and I've been stuck in this for a few days. So, can you tell me how to implement a small subgroup attack with the small group defined by small prime factor?
2. In your article : Hacking private keys from unsafe primes using the Pohlig-Hellman discrete logarithm. I can not understan this step:

> .\find-generator.ps1 -p 100000008359681
2^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 2
3^((100000008359681 - 1)/5) mod 100000008359681 = 1, rejecting 3
4^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 4
5^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 5
6 passes all checks
> $g = [bigint]::Parse("6")
> $g
6

why 3^((100000008359681 - 1)/5) the divisor is 5 and other case the divisor is 2? And there are general method to find the generator?