4
$\begingroup$

I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system. I am using the terms as defined in Wikipedia.

Alice publishes $g$ and $g^x$. Theoretically an attacker could calculate $g^i$ for all $i$ from 0 to $n$. At some point the attacker will get the value which is the public key $g^x$. However big a number $n$ is, surely it might be computationally feasible to try to get the value $g^x$ in this way, and thus $x$, especially if the pre-computations are done for using repeated squaring.

I am sure I am missing something obvious :-) I am guessing it could be the size of the group $G$ is much larger than I am assuming.

Why wouldn't the above method work?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ $x$ is selected at random in $(\mathbb{Z}/q\mathbb{Z})^*$. Typically, $q$ is several hundred bits long. You cannot feasibly iterate through such a large search space in a brute force attempt to locate $x$. $\endgroup$
    – Thomas
    Commented Jan 6, 2013 at 7:46
  • 2
    $\begingroup$ I think your confusion comes from the illusion that repeated squaring would help find $x$. It does help, to some extent - instead of $O(q^2)$ operations (go over each possible $x$, and naively raise $g$ to that power), you get $O(q \log_2 {q})$ with repeated squaring, which, while better, still doesn't make this possible. $\endgroup$
    – Thomas
    Commented Jan 6, 2013 at 10:10
  • $\begingroup$ Are there any ballpark figures for the time required? a few years or not till the end of the universe? I understood your comment, just wanted some figures $\endgroup$
    – bobby
    Commented Jan 7, 2013 at 6:59
  • 1
    $\begingroup$ In cryptography, we don't generally offer figures, after all we don't know the attacker's capabilities. But when we say "infeasible", we generally mean "beyond the reach of any realistic adversary". But, for all intents and purposes, "not till the end of the universe" is a good approximation. $\endgroup$
    – Thomas
    Commented Jan 7, 2013 at 7:13
  • 1
    $\begingroup$ Actually, repeated squaring doesn't really help compared to the naive approach $g^{i+1} = g^i · g$, if you want to calculate all of them anyways in sequence. (It might help when you want to work in parallel.) $\endgroup$
    – Paŭlo Ebermann
    Commented Jan 9, 2013 at 21:02

1 Answer 1

Reset to default
5
$\begingroup$

For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable. You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); hence for ElGamal to be secure, the size of the subgroup $n$ must be big enough.

If the security assumption of the adversary is that he cannot possibly perform $2^{128}$ computations, this immediately means that we need a group with at least $2^{128}$ elements or so.

That means that, in practice, this attack will not be practical, because (as you guessed) we'll pick ElGamal groups that are too large for the attack.

Two comments:

  • When I talk about the size of the group, what's actually important is the size of the subgroup generated by $g$; that is, the number of distinct values in $g^1, g^2, g^3, ...$. When we're in a multiplicative group modulo a prime, the size of this subgroup can be considerably smaller than the size of the modulus.

  • It turns out that there are cleverer generic ways to attack the discrete log problem; because of these ways, it turns out that if our assumption is that the attacker can't do more than $2^{128}$ operations, the size of the subgroup needs to be at least $2^{256}$ elements large.

Improve this answer
$\endgroup$

Your Answer

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

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