1
$\begingroup$

I have the following data where all the inputs are Big Integers,

  1. group size $p$,
  2. group generator $g$
  3. public key of the receiver $y$
  4. $c_1$ and $c_2$
  5. Random Number as well

I am trying to execute an EL Gamal Attack (On a Weak Number Generator) without knowing the secret key $x$.

$$y = g^x \bmod p\quad \text{where } x \text{ is the secret key.}$$

As we know $y,g$ and $p$. I am trying to compute $x$.I tried as follows $m$ as,

$$m = c_2 \times (c_1^x )^{-1}$$

By converting $m$ as ByteArray, I am not getting the desired output!

  • What I am missing out? What's the advantage of having this random number as input?

Actually,I tried finding x by taking log on both sides,

log y = x log g mod p

Each y, g, and P are of 1024 bits. Java is not supporting this BigInteger computation. How can I solve this equation involving such a big number?

Or is there any other shortcut available to compute the secret key, if the public key and g are given? Also, how can I take advantage of the given random number?

$\endgroup$
  • $\begingroup$ Cool! The Edit is impressive! Thanks !! Yeah, this is part of my home work . I read and tried the implementation already. Just I want some help to evaluate if I am doing something wrong here! $\endgroup$ – arunprakashpj Jan 1 at 13:05
  • $\begingroup$ Each g, p, and y are of length 308. How can I compute x accurately from the equation, as Big Integers of length 308 are involved $\endgroup$ – arunprakashpj Jan 1 at 23:02
  • $\begingroup$ Probably best to remove the question from StackOverflow, or leave just the question about BigInteger there :) $\endgroup$ – Maarten Bodewes Jan 1 at 23:53
  • $\begingroup$ I gave a broad tag Cryptography in StackOverflow that should put my question in the eyes of many people. So looking forward for some quick attention. $\endgroup$ – arunprakashpj Jan 1 at 23:59
  • $\begingroup$ Finally Did it! I used the public key inverse and the random number to compute my shared secret key! However Thanks everyone for all your suggestions! $\endgroup$ – arunprakashpj Jan 2 at 14:43
1
$\begingroup$

$g$, $p$, and $y$ are of length 308 (decimal digits). How can I compute $x$ accurately from the equation?

Computations with integers this size (for example, verifying a guess of an integer $x$) are possible with Python's pow in its three-arguments form, Java's BigInteger modPow, GP/Pari, Sage, Mathematica…

I tried finding $x$ by taking log on both sides

That method can give you a real $x$, but here we want an integer. Given 1024-bit prime $p$, generator $g$, and $y=g^x\bmod p$, there is no general and easy way to find an integer $x$. That may be possible if the order of $g$ is appropriately smooth, but nothing in the context suggests that. That also may be possible if $x$ was generated by a weak RNG, but since the nature of the weakness is untold, it is hard to tell how to proceed.

  1. Random Number as well

Perhaps that mysterious given helps to determine the nature of the RNG weakness. Or/and perhaps this given is somewhat related to the random number generated during the encryption, which knowledge would trivially allow to decipher without the private key $x$.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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