A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

1

If this is true, how would one solve this in practice? Actually, in practice, what we generally do is not use El Gamal at all, but instead use Integrated Encryption Scheme (IES), which solves the same problem based on the same hard problem, but where one doesn't worry about Quadratic Residues (or the homomorphic properties, or the need to compute inverses, ...

1

TL;DR: as pointed by DrLecter in comment¹, the question's formula is for exponential ElGamal encryption, with per-encryption random $r$ explicit. I'll first describe (straight) ElGamal encryption. It works in an arbitrary finite cyclic group of generator $g$ and order $q$ (with the internal law noted multiplicatively). That is, $q$ is the smallest strictly ...

1

In order to retrieve the message $M$ from the Discrete Log provided by the final step of ElGamal, knowing that $-l \le M \le l \text{ where } |\ l\ | \lt \lfloor p/2\rfloor$ works the same way as if $1 \le M \le p - 1$ that is, testing for all exponents. For negative values of $l$ we use modular division, e.g. 5^{-3} \equiv 125^{-1} \equiv 6^{-1} \equiv 6\...

0

A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe. We needn't be worried at all (unless we're concerned about the feasibility of the attack that recovered the first message). If a decryption of one message allows you to break an unrelated message, then El Gamal ...

1

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

Top 50 recent answers are included