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: 2255 < n < 2256
Suppose that we have a public key Pub that corresponds to the private key Priv whose range is known. Like: 2a < Priv < 2b
Before using a certain formula, we need to create 3 arrays
An array of 256 public keys. Each public key will represent a private key that will be powers of 2 ranging from 20 = 1 (the generator point) to 2255
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
- Another array of 256 public keys, with each public key representing private key that contains: 1 + (1 over the power of 2 ranging from 21 to 2255 ). Note: B[0] is going to be 1 + 1 = 2. Like:
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
- Array of 256 integers used for public key division
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
The formula allows us to do this:
Imagine we have in addition:
2a < Pub < 2a+1
2b < A[b] < 2b+1
If a = b then:
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
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:
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
If a < b then:
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
Let's review specific examples (Had to use links for images, as inserting them here directly would crash mathematical notation):
a = b (
)
Let 567 be our unknown private key converted into the public key. 29 < 567 < 210
Let 637 be a public key that we add. 29 < 637 < 210
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
- a > b (
)
For example, we could add the number that is 1 power of 2 less than our public key. Our public key corresponds to 29 < 567 < 210, and we add the public key of 28 < 325 < 29
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
- a < b (
)
Let's add the number that is 1 power of 2 higher than our public key. Our public key corresponds to 29 < 567 < 210, and we add the public key of 29 < 1058 < 210
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
Why is it important? (
) (
)
Imagine if we have a curve of order of n = 33 151. 215 < 33151 < 216We'd like to add 67. 26 < 67 < 27. 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:
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
However, in settings of our elliptic curve, 33150 + 67 becomes 66
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
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.
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
r/crypto - Trouble detecting cyclic group order crossovers in SECP256K1
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?