PDA

View Full Version : ElGamal with non relative prime k to p-1 ?

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:

Quote:
 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

Darkelf
December 13th, 2008, 20:00
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?

scarebyte
December 15th, 2008, 07:32
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:

Quote:
 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?

_g_
December 29th, 2008, 16:35
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).

scarebyte
December 30th, 2008, 05:36
Quote:
 [Originally Posted by _g_;78410]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.

_g_
December 30th, 2008, 06:57
>
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.