Duplicate y-coordinate scalars on secp256k1?

[rdenkye]

Are there two different known scalars on secp256k1 that give points with the same y-coordinate?

[stwenhao]

Of course.

Code:

d=0x1
Q=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

d=0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
Q=(0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

d=0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce
Q=(0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

And it works for every valid public key:

Code:

d=satoshi
Q=(0x678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb6,0x49f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f)

d=satoshi*0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
Q=(0x964fff1d306a0ea78660e00ec9468def965580d0c3aa892233a51da5c7a7dd0d,0x49f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f)

d=satoshi*0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce
Q=(0x02250331d140a93160372e4ac588bb000cd3d7065c1c6d3752f8016f18f6406c,0x49f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f)

[kTimesG]

Since all valid points on the curve are defined as

y**2 = x**3 + b (b = 7)

this solves as three x roots for every possible y**2.

Since y**2 has two solutions, we have 3*2 = six points sharing the same y**2.

Simplifying and getting rid of the squaring, this means all curve points can be split in sets of 6, every set having the same min(y, -y).

Now, let's assume you have some (x, y) of a point, without even knowing its scalar. You can directly compute all other 5 points, and their scalar multiples, without any expensive operations!

In the scalar domain, solve for lambda**3 = 1 as the post above uses. This allows playing around with the scalars and verifying that the below math checks out OK!

In the curve field (x, y) first solve for beta**3 = 1 like this:

Because of Fermat we have a**(p-1) = 1 mod p for eny integer a and prime p.

So beta**3 == 1 == a**(p-1) hence beta = a**((p-1)/3) (there are only ever two solutions for this no matter what value for a you pick).

Due to another theorem, because we have beta**3 = 1 we then have beta**0 + beta**1 + beta**2 = 0 which gives all roots for beta, which are:

beta**0 = 1
beta**1 = a**((p-1)/3)
beta**2 = -beta**0 - beta**1 = -1 - beta

So, fastest way to get all other 5 points from (x, y):

(x, -y)
(x * beta, y)
(x * beta, -y)
(x * beta**2, y) = (- (x + x*beta), y)
(x * beta**2, -y) = (- (x + x*beta), -y)

So, just one multiplication and a field additions / negations at most.

Note that my point is that the multiplication with a precomputed beta**2 can be simplified with a simple addition and negation.

[rdenkye]

If one of the 3 public keys with the same Y value is solved, can the other 2 also be solved?

[stwenhao]

If one of the 3 public keys with the same Y value is solved, can the other 2 also be solved?

If you have a single private key, then you will get all six.

Code:

key1=something
key2=(something*0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72)%n
key3=(something*0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd73)%n
key4=(something*0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce)%n
key5=(something*0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283cf)%n
key6=(something*0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140)%n