3
$\begingroup$

I apologize in advance for my question. I am trying to make my own simple Secp256k1 calculator, just addition and subtraction, and one thing keeps confusing me. When I add 2 points, and I know what result of addition should be a bigger number than $n$, and as far as I understand, the result should be 0, because it is the point at infinity.

However, my calculator shows a different result. For example, I add:

115792089237316195423570985008687907852837564279074904382605163141518161494336 + 2

and get 1 as result. The same thing happens with other points whose sum is greater than $n$.

But when I add

115792089237316195423570985008687907852837564279074904382605163141518161494336 + 1

calc shows me 0.

I can't understand, is it calculator work right, and it's my misunderstanding in ECC? Or its a mistake in my code? What result should be when I add two points with sum, greater than $n$?

$\endgroup$
14
  • 1
    $\begingroup$ Welcome to Cryptography.SE. Your question is not clear. Do you use the point addition group laws? $\endgroup$
    – kelalaka
    Commented Jun 21, 2021 at 18:55
  • 1
    $\begingroup$ Reading your question again, it seems that you have a problem in ECC point arithmetic. You may edit your question to show how do you add points? Mathematically or programmatically, in the later case that should be minimal! $\endgroup$
    – kelalaka
    Commented Jun 21, 2021 at 19:19
  • 1
    $\begingroup$ I really don't get it. What is $P=(Px,Py)$ and $Q=(Qx,Qy)$ $\endgroup$
    – kelalaka
    Commented Jun 21, 2021 at 20:30
  • 1
    $\begingroup$ A point in ECC in affine coordinates has two coordinates. Are you sure got this? There is a point $$(2, 69211104694897500952317515077652022726490027694212560352756646854116994689233)$$ with $x=2$ and y is calcualted... $\endgroup$
    – kelalaka
    Commented Jun 21, 2021 at 20:49
  • 1
    $\begingroup$ I think you are missing the concepts. The point you called should be the private key and you want to calculate the public key. The private key is an integer and the public key is a point via the scalar multiplication $[k]G$ $\endgroup$
    – kelalaka
    Commented Jun 21, 2021 at 20:55

1 Answer 1

5
$\begingroup$

There is confusion about the Elliptic curve terminology in this question. Let deal some of them;

Elliptic Curve

Algebraically an elliptic curve is

$$E(\mathbb{K}) := \{ (x, y) \in \mathbb{K}^2 \mid y^2+a_1xy+a_3y = x^3+a_2x^2+a_4x+a_6\} \cup \{\mathcal O\}$$

$\{\mathcal O\}$ is the point at infinity added as extra that has no representation in the geometric shape of the curve.

The points are the $(x,y)$ tuple that satisfies the curve equation so they are not integers!

Point addition

The point addition has a very well geometric meaning. In the below picture $P,Q,R$ represents the points on the curve and $\{\mathcal O\}$ is represented as $0$

Geometric interpretation of addition on a Weierstrass curve

and we extract the arithmertic equations from this ( tangent chord rule). For detail of the extraction look at Chapter 2 of Washington's book.

The points of a curve form an Abelian group under the point addition operator with the identity element $\{\mathcal O\}$.

Scalar multiplication

When we add a point $P$ to itself we say doubling some person write as $2P$, however, the common and better way to write it is $[2]P$. So $[2]P = P + P$.

Similarly, we can talk about adding three times, four times, or $t$ times.

$$[t]P : = \underbrace{P + P + \cdots + P}_{t-times}$$

This is what we call the scalar multiplication ( actually a Z-Module for Abelian groups)

Generator

A generator of a cyclic group is an element $G$ such that when $G$ added itself again and again it will generate all elements of the group (Sorry for the group theorist, the capital letters colliding here - an element $g$ of a group $G$ is generator if $\langle g \rangle = G$).

Order

The order has two usages in ECC

  1. Order of the Elliptic curve $|\#E(\mathbb{K})|$ means the number of elements of the curve

  2. Order of an element.

    When the curve has prime order as in Secp256k1 then every element has the same order as the curve order and this implies every element is a generator.

Back to your question

In Secp256k1, the base point

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
83121579216557378445487899878180864668798711284981320763518679672151497189239 )

and the order of the basepoint $n$ is

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

The order means that $[n]G = \mathcal{O}$ and we can uses this to derive the below equation

$$[k]P = [ k \bmod n]P$$

  • So what you do is with $+2$ is

    $$[n-1]G + [2]G = [n-1+2]G = [n+1]G = [1]G = G$$

  • So what you do is with $+1$ is

    $$[n-1]G + [1]G = [n-1]G = [n]G = \mathcal{O}$$


Let's finish with SageMath verification;

#secp256k1
p = Integer("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F")
a = Integer("0x0000000000000000000000000000000000000000000000000000000000000000")
b = Integer("0x0000000000000000000000000000000000000000000000000000000000000007")

K = GF(p)
E = EllipticCurve(K,[a,b])
print(E)

G = E(Integer("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
      Integer("0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"))
print("\nG =",G)

n = G.order()

print("\nG's order =",n)

G2 = 2*G
Q = (n-1)*G + 2*G
print("\n[n-1]G+[2]G =",Q)
assert(Q == G)

R = (n-1)*G +G
print("\n[n-1]G+G =",Q)
print(R)

and the output is

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

G's order = 115792089237316195423570985008687907852837564279074904382605163141518161494337

[n-1]G+[2]G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

[n-1]G+G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
(0 : 1 : 0)
$\endgroup$
3
  • 1
    $\begingroup$ Yes, you can talk about the point as an integer where the integer represents the scalar that needed to multiply with $G$. However, the reverse is the discrete logarithm, i.e. given $P$ find $t \in Z$ such that $P = [t]G$, and this is the core of the security of many ECC and a hard problem. It is common that we can keep the indexes ( the $t$'s for each $P$) to speed up, however, most of the time you are given $P$ without the index as in the Elliptic Curve Diffie-Hellman Key Excange (ECDH). $\endgroup$
    – kelalaka
    Commented Jun 22, 2021 at 17:53
  • $\begingroup$ Thank you very much for such detailed answer. Sorry for my wrong point description, i understand what point is x y coordinates, not integer, but for me it easier describe point as integer because it show number what lies behind this point. And thanks for calculation, now i see clearly what happens when i add this points. But I have a new question. Is there a possible way to track what result of point adding is bigger than n and result point lies in "second round"? Is it possible? $\endgroup$
    – Franko
    Commented Jun 22, 2021 at 18:15
  • 1
    $\begingroup$ If you give me $P$ and $Q$ with their coordinates then there is no way for me, as I mentioned in the previous comment, that is one need to solve the Discrete logarithm on Seckp256k1. Note that, there is no such rounding when you consider $P+Q$ since the addition formula doesn't need to use the index and base point. $\endgroup$
    – kelalaka
    Commented Jun 22, 2021 at 18:20

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.