The Koblitz elliptic curves specified in the SEC2 document https://docs.google.com/viewer?url=http%3A%2F%2Fwww.secg.org%2Fcollateral%2Fsec2_final.pdf all have the nice feature that the parameters are highly non-arbitrary; the modulus is simply a few powers of two put together, and the a and b parameters are 0 and 7. The group order can be forgiven; that's just a number that you get given the other parameters of the curve. However, the choice of generator seems to be very arbitrary. Why did the SEC not choose simpler parameters for the generator (eg. x = 1000, y is even) instead?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Well, I'm not privy to how Certicom selected these parameters, however I can tell you that it doesn't really matter; if the generator they selected is weak, then all generators on that curve are weak.
In particular (and assuming that the curve has a prime number of points on it; this is true for the Certicom curves):
If you can solve the discrete log to a specific generator $G$, you can solve it to any base (by solving two instances of the generator $G$ problem)
If you can solve the computational Diffie Hellman problem with a specific generator $G$, you can solve it to any base (by solving $\log p$ instances of the generator $G$ problem).
Hence, if there is a weakness with their generator, then their curve is weak (except possibly against the decisional Diffie-Hellman problem; I don't know of a similar reduction there).
Demonstrating the first reduction is quite straight-forward; suppose thatwe are given an Oracle, that, given $aG$, recovers $a$ (with $G$ being our distinguished generator). Then, given an instance which consists of $H$, and $aH$, with $H$ being an arbitrary point, we call the Oracle twice, once with $H=bG$, and once with $aH = cG$, recovering $b$ and $c$. Then we can compute $a = b^{-1}c \bmod q$ (where $q$ is the order of the curve); this is our answer.
The computational Diffie-Hellman case is somewhat more complex. For that, we suppose that we have an Oracle that, given $aG$ and $bG$, computes the value $abG$. Then, the problem we are trying to solve is, given $H$, $aH$ and $bH$, compute the value $abH$.
To see how to we proceed, let us designate $c$ as the value $H = cG$. Now, we don't know the value of $c$, however we can compute the point $c^2G$ (by using our Diffie-Hellman Oracle, with the inputs $cG$ and $cG$). Extending this observation, we can compute $c^kG$ with $\log{k}$ calls to the Oracle. So, we compute $c^{q-2}G = c^{-1}G$ (with $\log{q}$ Oracle calls, and $q$ is the curve order). Then, with $aH = acG$ and $bH = bcG$, we can compute $abH = abcG$ with two more Oracle calls.
