Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to calculate an $x$, such that $t = g^x \pmod p$ in order to crack a weak ElGamal encryption for university.

I found GDlog, but I cant figure out how I can use the input to calculate my $x$.

Here is what we got (from gdlogs example code):

p:1000000000000000000000000000057 //prime number, modulus
q:290240017                       //(p-1)/2
g:5                               //generator
t:519335238006017621936447751736  //member of the group

GDlogs result: Logarithm of the 519335238006017621936447751736 to the 5 is 142363323. My question is: What is the number that GDlog outputs (142363323)?

This is what is written in the README:

Find 0 <= x < q - 1 such that g^(x*(p-1)/q) mod p = b^((p-1)/q) mod p (assuming that such x exists).

But I still can't figure out how to do it.

share|improve this question
add comment

1 Answer

$((g \mod p)^{(p-1)/q})^{142363323} = (t \mod p)^{(p-1)/q}$

Equivalently,

$(g \mod p)^{362274084216648467976382636880} = (t \mod p)$

That is,

$362274084216648467976382636880 = 142363323 \mod \frac {p-1}q $

share|improve this answer
    
Thank you very much, that answered my question. Is there a way to mark this as the answer? –  benmuell May 8 '13 at 9:35
    
@benmuell Click the checkbox left of the answer (and upvote it :-)) –  Thomas May 8 '13 at 12:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.