0
$\begingroup$

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

  1. 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.stack.imgur.com/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$

  1. a > b (https://i.stack.imgur.com/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$

  1. a < b (https://i.stack.imgur.com/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.stack.imgur.com/UhZIF.jpg) (https://i.stack.imgur.com/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?

$\endgroup$
5
  • 1
    $\begingroup$ I'm not quite sure what you're asking (hence this is not an answer); however if you, given $aG, bG$, check whether $(a+b)G$ "crosses over", that is, whether $a+b \ge n$, then you can compute discrete logs (using binary search) $\endgroup$
    – poncho
    Jul 28, 2023 at 20:07
  • $\begingroup$ The question is about solving the misalignment of results applied to integer arithmetic and elliptic curve cryptographic arithmetic. Imagine, we have a public key whose private key we don't know, but we know in what range of powers on 2 it lies in For example: $2^{255} < Priv < n$. $Priv -> Pub$ We add to our $Pub$ other public keys whose private keys we know. The following method described in the question sort of proposes a method of checking whether such addition is bigger than $n$. While the method works in decimal (normal) arithmetic, with elliptic curves, it doesn't. Why? $\endgroup$ Jul 28, 2023 at 20:18
  • $\begingroup$ $2^b<A[b]$ compares integer $2^b$ with the elliptic curve point $A[b]$ which has no specified integer representation. What would that mean and why would it hold? Independently: $B[1]$ is supposed the be the public key corresponding to $1+\frac12$, that is to the fraction $\frac32$ which is not an integer. Is $B[1]$ the public key corresponding to the integer $\frac{n+3}2$? If not, what else is $B[1]$? Independently: from the definition given $C[i]=2^i$; is that correct? Independently: What is "The formula" that "allows us to do…"? $\endgroup$
    – fgrieu
    Jul 29, 2023 at 15:07
  • $\begingroup$ 1) By $A[b]$ in formula presentation just means any public key whose private key is within $2^{b} < A[b] < 2^{b+1}$. In my original algorithm from which this piece of detail was taken from, A[number from 0 to 255] just meant to be an array of public keys that correspond to keys being the powers of 2. 2) Yes, $B[1] = 1 + {1\over2^{1}} = {3\over2}$. However $C[i]$ is not $2^{i}$. Acctually, $C[i] = 2^{-i}\:mod\:n$. For example, $C[1] = 2^{-1}\:mod\:n = 57896044618658097711785492504343953926418782139537452191302581570759080747169$. Sorry, C array has no contextual meaning here. Will fix $\endgroup$ Jul 29, 2023 at 15:49
  • $\begingroup$ The formula had the purpose of checking whether the corresponding private key of 2 public keys added together is more than the cyclic order $n$, without knowing the private key of 1 of the public keys in the addition $\endgroup$ Jul 29, 2023 at 16:02

1 Answer 1

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yeah, that's what I've meant. We have $n-1$, and to get to $2$, we have to add and not subtract. This would be going "forward". During the addition process, we would be crossing the boundary, which is: $N$. After that, the count will start over, from 1, 2, 3 and forward.... $\endgroup$ Oct 27, 2023 at 8:51

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.