3
$\begingroup$

So, according to the elliptic curve discrete logarithm problem:

$$A=[r]B$$

In which $A$ and $B$ are points on the curve, and r is the scalar. It is trivial to compute $A=[r]B$ if $r$ is known, but it would be incredibly difficult to find $r$ if $r$ is unknown.

Now, take bitcoin's elliptic curve as an example - secp256k1. Are there any "special" point $B$s on this curve which would allow an attacker, with knowledge of $A$ and $B$, to trivially compute $r$, and thus render the elliptic curve insecure?

$\endgroup$
2
  • $\begingroup$ Not directly related to secp256k1, but a backdoor can be placed : Does the backdoor in Dual_EC_DRBG work like that? $\endgroup$
    – kelalaka
    May 27 '20 at 16:27
  • $\begingroup$ probably not. Take a look at random self-reducibility for dlog. If such a set of points exists, it should be negligibly small. One can precompute such set himself too. $\endgroup$ May 27 '20 at 16:53
3
$\begingroup$

Let's first consider your proposed secp256k1 curve. The order of the curve is prime, which means any (valid) point on the curve will generate the whole curve; for any choice of your base point $G$ except for the point at infinite $\mathcal O$, there are integers $r$ such that $[r]G$ reaches the whole curve. In other words, the only sub groups are the whole curve and the trivial group $\{\mathcal O\}$.

This is however is not true for all elliptic curves. In fact, many have a composite structure (order $n=r\cdot h$), consisting of a large subgroup of prime order $r$ and a "cofactor" $h$. This property can lead to a subgroup confinement attack. For more information about the cofactor, see this excellent answer. In order to avoid this, care has to be taken when these kinds of curves are used in protocols.


This is (of course) not the only attack we can think about, but it's the most evident from wording of your question. SafeCurves, a webpage by people with a lot more understanding of elliptic curve cryptography than me, lists up many curves with their flaws. Curves like secp256k1 may be safe from subgroup confinement, but have other flaws w.r.t. timing and side channels.

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