# Thread: ElGamal with non relative prime k to p-1 ?

1. ## ElGamal with non relative prime k to p-1 ?

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:

y = g^x mod p
p 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

2. 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?

3. 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:

y=104CD5256C36A4E2 // given
g=15B224DC17BE9B96 // given
p=EB8C340BBDF95BC3 // given
x=53795FE19DB89F3 // y=g^x mod p => dlp

a=3A01C4D1DBBA3897 // given
k=111111111 // a=g^k mod p => dlp
b=796104B9 // hash(name)

M=Serial
M=(a*x + b*k) mod (p-1)
u = a*x mod (p-1) = 584E650DA1961415
v = b*k mod (p-1) = 81788D921A0A9949
M = v+w mod (p-1) = D9C6F29FBBA0AD5E

verification:
(y^a * a^b) mod p == g^M mod p
r = y^a mod p = 1967B57CA867BE7F
s = a^b mod p = 169FCB3130F49782
t = r*s mod p = 3F825B3333337FEC
z = g^M mod p = 3F825B3333337FEC
=> t == z

and with dlp of: t = g^M mod p
M = 3CBECFED3CFA7032
proof: z = g^M mod p = 3F825B3333337FEC
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?

4. 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).

5. Originally Posted by _g_
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.
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.

6. >
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•