Score:3

Problem with point addition about [n-1]+[2]G and [n-1]+G on on Secp256k1

cn flag

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$?

kelalaka avatar
in flag
Welcome to Cryptography.SE. Your question is not clear. Do you use [the point addition group laws](https://crypto.stackexchange.com/a/66296/18298)?
Franko avatar
cn flag
Yes, i suppose.
kelalaka avatar
in flag
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!
Franko avatar
cn flag
I used code from https://onyb.gitbook.io/secp256k1-python/point-addition-in-python. When i add coordinates for 15792089237316195423570985008687907852837564279074904382605163141518161494336 point 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 and add to this point 2 with coordinates c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee51ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a, i get coordinates of 1 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 as result.
kelalaka avatar
in flag
I really don't get it. What is $P=(Px,Py)$ and $Q=(Qx,Qy)$
Franko avatar
cn flag
Lets make it little simpler. What correct answer for point addition for two points:115792089237316195423570985008687907852837564279074904382605163141518161494336 and 2?
kelalaka avatar
in flag
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...
Franko avatar
cn flag
Im sorry. Point 115792089237316195423570985008687907852837564279074904382605163141518161494336 G with coordinates x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 y: b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 and point 2G x: c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 y :1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
kelalaka avatar
in flag
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](https://crypto.stackexchange.com/q/68593/18298) $[k]G$
PrincePolka avatar
cn flag
secp256k1 is a curve of prime order N = 115792089237316195423570985008687907852837564279074904382605163141518161494337 , you're adding (N-1)G + 2G and get G which is correct , same principle as if you're adding 2 hours to 11 a'clock you get 1'a clock
Franko avatar
cn flag
Thanks!!! This means all work correct. But it possible somehow to avoid this second round point adding? Fo rpoint adding results greater than n. After all, result of adding, which equal to n (115792089237316195423570985008687907852837564279074904382605163141518161494337) calculating correct as 0. May be it possible for other results, greater than n?
kelalaka avatar
in flag
I see. You are totally using incorrect terminology. You are executing scalar multiplication. In this case, you can use this identity. $[k]P = [ k \mod n]P$
Franko avatar
cn flag
Thanks, will try.
kelalaka avatar
in flag
And don't forget that the way of StackExchange, is upvoting an answer if it is useful to you and accepting it if it satisfies your question. Have fun.
Score:4
in flag

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)
kelalaka avatar
in flag
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).
Franko avatar
cn flag
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?
kelalaka avatar
in flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.