El Gamal: solve "a" for "h = g^a (mod p)"

Question

Currently trying to understand cryptography by myself. There is a task of forging El Gamal signature p=541, g=2, h=419 and are public keys. I need to find a, which is a private key.

The only info I found so far is that the whole task is somehow related to the discrete logarithms.

Answer 1

If p-1 has a decent number of prime divisors, it can be done relatively fast, using the chinese remainder theorm and a bit of tricks. I ran a program that hunted down these sorts of numbers for every prime under two million.

In essence, we note that 540 = 2*2*3*3*3*5, and proceed from there.

Find 2^270 and h^270.  as 540 and 1
Find 2^135 and h^135.  as  52 and 540.  Thus a = 2, mod 4

Find 2^180, h^180  as 129, 1   Thus a = 0, mod 3
Find 2^60, h^60  as  15, 129   Thus a = 3, mod 9
Find 2^20, (64*h)^20 as 411

We've added 2^6 to h, and found that the nineth power of this is 411 = 129^2. This means that h+6 = 18, mod 27, and thus h = 12, mod 27

Find 2^108, 419^108. = 48, 48.  

We scroll through the powers of 48 until we get a match, but h mod 5 = 1.

So, modulo(4, 27, 5), we seek (2,12,1).

We have 108 = (0,0,3), so 216 = (0,0,1)   add 216
We have 20  = (0,20,0), so 80 = (0,-1,0)  add -960
We have 135 = (3,0,0) so 405 = (1,0,0)   add 810

216-960+810 = 66

This particular algorim is considerably fast when p-1 has a large number of small divisors.

Answer 2

For these small values use Pollard's rho. My implementation found $a=66$ in $22$ iterations.

For more info see the Wikipedia entry for Discrete logarithms and especially the algorithm section.