1
$\begingroup$

I have just started studying cryptography and secp256k1. I just wonder that adding two points can be easily reversible when the generator point is publicly known.

I mean that if $Q=\operatorname{adding}(P, R)$ then we can calculate $P$ as $\operatorname{adding}(Q, R)$, am I right? Would this be considered a weakness? I am not sure if there exists a known reverse function for doubling as well, Something that could recover P with having Q from $Q=\operatorname{doubling}(P)$.

Anyways, what point is the major strength of secp256k1? Does that rely on the functions we choose for adding and doubling? Or maybe it relies on the nature of the $IF$ statement we use in the calculations?

Taking any arbitrary functions $Q =f(P)$ and $Q=g(P, R)$ and then performing the multiplication function as long as the multiplication function is Surjective and Injective over the field $F_p$, will we get the same level of security?

$\endgroup$
  • $\begingroup$ realated Subtracting a point in elliptic curve cryptography? $\endgroup$ – kelalaka Jan 2 at 13:11
  • $\begingroup$ Ae you asking whether $Q = P+G$ implies $P=Q+G$? Of course not, unless $G = \mathcal O$ or $G$ has order $2$. $\endgroup$ – fkraiem Jan 2 at 13:49
  • $\begingroup$ If a line intersects the elliptic curve in exactly 3 points why should not we conclude that if $Q=P+G$ then $P=Q+G$!? $\endgroup$ – PouJa Jan 2 at 14:07
3
$\begingroup$

If $Q=\operatorname{adding}(P,R)=P+R$, then $P$ can be computed from $Q$ and $R$ as $P=\operatorname{adding}(Q,-R)=Q+(-R)$ where $-R$ is easy to compute from $R$ (just change the $y$ coordinate of $R$ from $y_R$ to $p-y_R$ where $p$ is the order of the prime field). This property follows from $\operatorname{adding}$ being a group law.

If $Q=\operatorname{doubling}(P)=P+P=2\times P$, then we can efficiently compute $P$ from $Q$. One method is to use that $P=\displaystyle\frac{n+1}2\times Q$ (where $n$ is the order of the curve's group). This property follows from $n$ being odd.

Neither property is considered weakness, because it follows from having a group (of odd order), which is necessary for the applications thought, including ECDSA.

By definition of secp256k1, for that curve $p=2^{256}-2^{32}-977$ and $n=2^{256}-432420386565659656852420866394968145599$.


What is the major strength of secp256k1?

It forms with point addition a group of known 256-bit prime order $n$ with a generator $G$, such that we do not know an algorithm requiring much less than $\sqrt n$ steps to compute $a$ from $a\times G$, for random $a$ in $\Bbb Z_n^*$ (Discrete Logarithm Problem).
Note per comment: $G+G=2\times G$ in a group noted additively becomes $G*G=G^2$ in that same group noted multiplicatively. Similarly $Q=a\times G$ in a group noted additively becomes $Q=G^a$ in that same group noted multiplicatively. This is why solving either equation for $a$ is called the Discrete Logarithm Problem in the group considered.

More strongly, we know no algorithm requiring much less than $\sqrt n$ steps to tell sizably better than random if a triple what obtained as $(a\times G,b\times G,c\times G)$ or as $(a\times G,b\times G,ab\times G)$ for random $a$, $b$, $c$ in $\Bbb Z_n$ (Decisional Diffie-Hellman assumption).

secp256k1 is preferred over simpler groups with the same properties, notably Schnorr groups, because a point can be expressed much more compactly and the group law is much faster. secp256k1 is preferred over other groups with the same properties also built by point addition on an elliptic curve over a prime field, notably secp256r1, because the special form of $p$ for secp256k1 allows slightly faster calculation, with no known decisive drawback.


Does that rely on the functions we choose for adding and doubling?

Yes it has to do with the group and its law, that is the functions we choose for adding and doubling.

Taking any arbitrary functions $Q=f(P)$ and $Q=g(P,R)$ and then performing the multiplication function as long as the multiplication function is Surjective and Injective over the field $\Bbb F_p$, will we get the same level of security?

No, even with added constraints making the operation defined by $f$ and $g$ a finite group law. As a counterexample, take the group $(\Bbb Z_p,+)$ for some prime $p$: that defines point doubling $f$, point addition $g$, and we can take any non-zero element as $G$ with $n=p$. Point multiplication reduces to multiplication modulo $p$. That allows construction of the group as stated, yet the DLP is trivial, giving no security: given $Q=a\times G$ we can compute $a$ as $(G^{-1}\bmod p)\times Q$ where $G^{-1}\bmod p$ can be computed by the Extended Euclidean Algorithm.

Note: When restricted to point addition and doubling as in an axiomatic construction from $f$ and $g$, we can compute $-R$ as $(n-1)\times R$.

$\endgroup$
  • 2
    $\begingroup$ Minor correction: $(a \times G, b \times G, ab \times G)$ $\endgroup$ – poncho Jan 2 at 14:19
  • $\begingroup$ Would you please explain little more on how is this special multiplication is related to the discrete logarithm problem!? $\endgroup$ – PouJa Jan 2 at 14:22
  • $\begingroup$ If $Q=axG$ what discrete logarithm problem should I solve to recover $a$!? $\endgroup$ – PouJa Jan 2 at 14:39

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.