Trouble detecting cyclic group order crossovers in SECP256K1

Question

There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary

For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars), one-way converted to points on the elliptic curve.

$n$ - is the order of the group. Private keys can range from $1$ (the generator point $G$) to $n - 1$.

$n - 1$ is the maximum size (integer value) of a private key, and it is also the number of all non-trivial points available on the curve.

The order $n$ itself produces the point at infinity $n*G = O$. Adding points further, just starts the curve over again.

As each public key has its own corresponding private key, that corresponding private key lies within certain ranges of powers of 2.

The order itself lies within: $2^{255} < n < 2^{256}$

Suppose that we have a public key $Pub$ that corresponds to the private key $Priv$ whose range is known. Like: $2^{a} < Priv < 2^{b}$

Before using a certain formula, we need to create 2 arrays

1. An array of 256 public keys. Each public key will represent a private key that will be powers of 2 ranging from $2^{0}=1$ (the generator point) to $2^{255}$:

$A[256] = [2^{0}=1 (G) => A[0]; 2^{1}=>A[1]; 2^{2}=>A[2];...; 2^{255}=>A[255]]$

2. Another array of 256 public keys, with each public key representing private key that contains: 1 + (1 over the power of 2 ranging from $2^{1}$ to $2^{255}$). Note: B[0] is going to be 1 + 1 = 2. Like:

$B[256] = [1+1=2 => B[0]; 1+{1\over 2^{1}}=>B[1]; 1+{1\over 2^{2}}=>B[2]; ... ; 1+{1\over 2^{255}}=>B[255]]$

The formula allows us to do this:

Imagine we have in addition:

$2^{a} < Pub < 2^{a+1}$

$2^{b} < A[b] < 2^{b+1}$

If a = b then:

${(Pub+A[b])\over 2^{a+1}} - {(Pub-2^{a})+(A[b]-2^{a})\over 2^{a+1}} = 1 (G)$

or

${(Pub+A[b])\over 2^{a}} - {(Pub-2^{a})+(A[b]-2^{a})\over 2^{a}} = 2$

If the $Pub+A[b]$ hasn’t crossed the n boundary, the result should be 1 or 2. Otherwise, it has crossed the n boundary

If a > b then:

${(Pub+A[b])\over 2^{a}} - {(Pub-2^{a})+(A[b]-2^{b})\over 2^{a}} = 1 + {1\over 2^{a-b}} = B[a-b]$

If the $Pub+A[b]$ hasn’t crossed the n boundary, the result should be $1 + {1\over 2^{a-b}}$ or $B[a-b]$ (the same). Otherwise, it has crossed the n boundary.

If a < b then:

${(Pub+A[b])\over 2^{b}} - {(Pub-2^{a})+(A[b]-2^{b})\over 2^{b}} = 1 + {1\over 2^{b-a}} = B[b-a]$

If the $Pub+A[b]$ hasn’t crossed the n boundary, the result should be $1 + {1\over 2^{b-a}}$ or $B[b-a]$ (the same). Otherwise, it has crossed the n boundary.

Let's review specific examples (Had to use links for images, as inserting them here directly would crash mathematical notation):

1. a = b (https://i.sstatic.net/b0EOb.jpg)

Let 567 be our unknown private key converted into the public key. $2^{9} < 567 < 2^{10}$

Let 637 be a public key that we add. $2^{9} < 637 < 2^{10}$

${(567+637)\over 2^{10}}-{((567-2^{9})+(637-2^{9}))\over 2^{10}} = 1$

or

${(567+637)\over 2^{9}}-{((567-2^{9})+(637-2^{9}))\over 2^{9}} = 2$

2. a > b (https://i.sstatic.net/ZupFE.jpg)

For example we could add the number that is 1 power of 2 less than our public key. Our public key corresponds to $2^{9} < 567 < 2^{10}$ and we add the public key of $2^{8}<325<2^{9}$

${(567+325)\over 2^{9}}-{((567-2^{9})+(325-2^{8}))\over 2^{9}} = 1+{1\over 2^{9-8}} = 1.5$

3. a < b (https://i.sstatic.net/rSHp8.jpg)

Let's add the number that is 1 power of 2 higher than our public key. Our public key corresponds to $2^{9} < 567 < 2^{10}$ and we add the public key of $2^{9}<1058<2^{10}$

${(567+1058)\over 2^{10}}-{((567-2^{9})+(1058-2^{10}))\over 2^{10}} = 1+{1\over 2^{10-9}} = 1.5$

Why is it important? (https://i.sstatic.net/UhZIF.jpg) (https://i.sstatic.net/xhX3e.jpg)

Imagine if we have a curve of order of n = 33 151. $2^{15}<33151<2^{16}$

We'd like to add 67. $2^{6}<67<2^{7}$. However, if the addition result of 2 public keys is bigger than the order of the elliptic curve, the count starts again. We could have our original private key to be $n-1=33150$. Hence, $33150+67 => 33217-33151=66$

Let's apply the formula. In other settings:

${(33150+67)\over 2^{15}}-{((33150-2^{15})+(67-2^{6}))\over 2^{15}} = 1+{1\over 2^{15-6}} = 1.001953125$

However, in settings of our elliptic curve, $33150+67$ becomes $66$

${(66)\over 2^{15}}-{((33150-2^{15})+(67-2^{6}))\over 2^{15}} \neq 1+{1\over 2^{15-6}} \neq -0.009735107422$

We didn't get an expected result, and hence we detected a cyclic group crossover.

But in practice it doesn't work. I've been experimenting with SECP256K1 additions. For example, if we take $n - 1$ as our original private key converted to public key then:

When $(n-1)+3$ we'd get a public key of $2G$.

${(n-1)+3\over 2^{255}} - {((n-1)-2^{255})+(3-2^{1})\over 2^{255}}$

In normal arithmetic, the expression is not equal to $1+{1\over 2^{255-1}}$ But in tests with SECP256K1 ECC additions, it is! Have no idea why.

In other words, why does the method work with decimal (normal) arithmetic, but with ECC additions, it doesn't? Is there any way to fix it?

Answer 1

This field only has one group so you haven't "crossed over". You are still in the same group. Addition is just a description. You went from N-1 to 2G. To go from 5G to 3G, do you "crossover"?

5 + (N-2) = 5 - 2 = 3

And your example... 3 - 1 = 2

Answer 2

I'm not really answering the question but I think the flaw in your reasoning is that there is no definition of crossing over, hence you won't be able to detect whether a point crossed over or not. It works in small examples because you know what $1G,2G,..$ are, but if you get as resulting point, e.g. $16253683426435476125348162351G$, you wouldn't be able to understand whether it crossed over or not without computing its discrete log. So at the end what you are proposing isn't easier than solving the discrete log of the initial point.