Results 1 to 6 of 6

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

  1. #1
    scarebyte
    Guest

    Question 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
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #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. #3
    scarebyte
    Guest
    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?
    Last edited by scarebyte; December 15th, 2008 at 07:44.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  4. #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).
    Last edited by _g_; December 29th, 2008 at 17:41.

  5. #5
    scarebyte
    Guest
    Quote Originally Posted by _g_ View Post
    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.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  6. #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.
    Last edited by _g_; December 30th, 2008 at 07:14.

Similar Threads

  1. Replies: 0
    Last Post: July 14th, 2009, 22:22
  2. ElGamal Signature
    By AdamA in forum RCE Cryptographics
    Replies: 22
    Last Post: January 9th, 2003, 05:44
  3. prime number properties
    By dion in forum RCE Cryptographics
    Replies: 10
    Last Post: April 23rd, 2002, 09:54
  4. RNG and relative primes
    By goatass in forum RCE Cryptographics
    Replies: 6
    Last Post: December 24th, 2001, 09:42

Bookmarks

Posting Permissions

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