1
$\begingroup$

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 \le x < q - 1$ such that $g^{x (p-1)/q} \pmod p = b^{(p-1)/q} \pmod p$ (assuming that such $x$ exists).

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

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't understand the following relation: 362274084216648467976382636880 = 142363323 mod (p-1)/q Can someone please elaborate how to get 362274084216648467976382636880 from 142363323? $\endgroup$
    – user15129
    Jun 25, 2014 at 12:24

1 Answer 1

Reset to default
5
$\begingroup$

$((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 $

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much, that answered my question. Is there a way to mark this as the answer? $\endgroup$
    – benmuell
    May 8, 2013 at 9:35
  • 1
    $\begingroup$ @benmuell Click the checkbox left of the answer (and upvote it :-)) $\endgroup$
    – Thomas
    May 8, 2013 at 12:54
  • $\begingroup$ How to get 362274084216648467976382636880 from 142363323 then? $\endgroup$
    – Smit Johnth
    Apr 30, 2014 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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