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

I guess that computation of M through discrete logarithm will also fail, because 'a' is computed with a wrong 'k' (a = g^k mod p). So I doubt that you will get anything useful for M.

Where there any solution for this crackme?

hi darkelf,

nope, there aren't any solution for this crackme. in addition i wrote to the coder and told him that he choosed a "wrong" k. so he changed the keygenme. now it works fine.

after your post i recalculated all numbers and found that i did a mistake in calculating M. i had a wrong intermediate result for a*x. with the new calculation i get:



so there are two solutions for the serial. maybe next time i will calc more than 5 times before i'll post such a request. but i'm still interested what will happen if i dont take a randomly k which isn't relative prime to p-1.

edit: imho i think with the dlp of M you will always get an usefull serial. because the value t is computed and g and p are given. so with dlp you get M with that g^M mod p would result the computed t. dunno if i'm wrong. short question: is there any condition for solving the discret logarithm?

What you describe isn't ElGamal signature.
http://en.wikipedia.org/wiki/ElGamal_signature_scheme

In classic ElGamal, gcd(k,p-1)=1 must hold, so there would exist k^-1.
In your case M = xa+kb mod p-1, you don't need k^-1.

Since Zp (integers modulo p) is cyclic (http://en.wikipedia.org/wiki/Cyclic_group), (http://planetmath.org/encyclopedia/ProofThatEveryGroupOfPrimeOrderIsCyclic.html) then every element of Zp is a discrete logarithm of some other element (there is no restriction).

hi _g_,

sorry, i have to disagree to your statement. what i've described is the el gamal signature scheme (look at verification). the only thing is, that the coder of this keygenme used a and b as hardcoded values (in case of a a hardcoded number and b as result of a "hash" and the aim is to get M. to get M you have to solve the dlp two times (for x and k). so if the gcd(k,p-1)=1 there is always a solution.

the other thing with Zp i know. but still thanks.

>
sorry, i have to disagree to your statement. what i've described is the el gamal signature scheme (look at verification). the only thing is, that the coder of this keygenme used a and b as hardcoded values (in case of a a hardcoded number and b as result of a "hash" and the aim is to get M. to get M you have to solve the dlp two times (for x and k). so if the gcd(k,p-1)=1 there is always a solution.
<

it's based on elgamal, but it's not elgamal, look at the signature generation -- if your argument is true ("look at verification", then mine is also true...

can you explain why do you need gcd(k,p-1)=1 in this crackme?

>the other thing with Zp i know. but still thanks.

then what did you mean by this:

"short question: is there any condition for solving the discret logarithm?"

note for first post: if you found one solution for y=g^x mod p, then others are x+phi(p)*n for n natural. phi(p)=p-1.