scarebyte

November 25th, 2008, 12:47

i found a crackme which use the elgamal signature, but the one who codes it, didn't notice that the randomly choosen k have to be relatively prime to (p-1).

in short description the elgamal signatur:

following numbers are given by the crackme:

a, g, y, p

b = hash(name)

=> need to compute x, k, M

=> M = serial number

so i computed x and k. then i noticed that gcd(p-1,k) is 117 and not 1.

so i cannot compute M with the function above.

thats the reason why i need to calculate M with the discrete logarithm:

M = dlp (y^a * a^b, base g, modulo p)

now, my question is .. is it possible to calculate M without runtime discrete logarithm?

greets, sb

in short description the elgamal signatur:

Quote:

y = g^x mod pp is a prime number, x and g are less than p, where x is the private key then choose a random number k, such that k is relative prime to p-1. then compute: a = g^k mod p M = (x*a + k*b) mod (p-1) verification: (y^a * a^b) mod p == g^M mod p |

following numbers are given by the crackme:

a, g, y, p

b = hash(name)

=> need to compute x, k, M

=> M = serial number

so i computed x and k. then i noticed that gcd(p-1,k) is 117 and not 1.

so i cannot compute M with the function above.

thats the reason why i need to calculate M with the discrete logarithm:

M = dlp (y^a * a^b, base g, modulo p)

now, my question is .. is it possible to calculate M without runtime discrete logarithm?

greets, sb