0
$\begingroup$

I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description includes?

For example here he is making the differentiation that in Elliptic Curves this group description makes it harder to solve the discrete log problem. Is it because for example in RSA the group elements are known beforeh and so their group description is just all numbers mod n while in the EC the group elements are not known and you are only given the EC parameters (i am not sure about the last one)?

$\endgroup$
4
$\begingroup$

My question is what does this description includes?

The information that describes what elements are in the group, and how to perform the group operation. In a $\mathbb{Z}_n^*$ group, the value $n$ may be sufficient, for an Elliptic Curve group, that'd include the curve equation (e.g. for Weierstrass curves, the values $a$, and $b$ in the equation $y^2 = x^3 + ax + b$), and the finite field the group is defined over. Actually, in practice, we typically don't generate curves on the fly; it is far more typical to say "I'm using P256" or "I'm using Curve25519".

Is it because for example in RSA the group elements are known before

No, it's because that the group $\mathbb{Z}_n^*$ has additional properties that generic groups don't have, and an attacker can exploit these properties to make solving the discrete log problem faster.

One such property is that fact that we can construct a modest-sized list of elements $p_0, p_1, ..., p_i \in \mathbb{Z}_n^*$ such that, given a random element of $x \in \mathbb{Z}_n$, we have a nontrivial probability of being able to quickly find the values $e_0, e_1, ..., e_i$ such that $x = p_0^{e_0} \cdot p_1^{e_1} \cdot ... \cdot p_n^{e_i}$; we don't know how to do that with a generic group, and it turns out to be useful in the discrete log problem.

And, in case you're wondering what that quick algorithm is, well, we set $p_0, p_1, ..., p_i$ to the first $i+1$ primes, and given $x$, we treat it as an integer (rather than an element of $\mathbb{Z}_n^*$) and do a quick factorization on it, using an algorithm that is designed to be find small factors (and if it fails because of a large factor, we can detect that quickly). A nontrivial fraction of $x$ turn out to be smooth, and hence this works sufficiently often.

$\endgroup$
  • 2
    $\begingroup$ I think you mean "the group $\mathbb{Z}_n^∗$ has additional properties that generic groups don't have, right? Namely a ring homomorphism to the unique factorisation domain $\mathbb{Z}$ - for @AntonisParagas , each number in $\mathbb{Z}$ we can try to factorise it because we understand factorisation of integers. There is no obvious map from elliptic curve points to something we can factorise - so for groups $\mathbb{Z_n^*}$ we must choose orders large enough to make index calculus (the algorithm above) impractical. $\endgroup$ – diagprov May 6 '17 at 21:38
  • $\begingroup$ It seems like the algorithm would be quicker if it used -1 rather than just primes. $\hspace{1.34 in}$ $\endgroup$ – user991 May 7 '17 at 17:34

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.