Square roots and cube roots in secp224k1

j2002ba2

full member

Activity: 206

Merit: 450

Quote from: stwenhao on January 02, 2025, 07:46:57 PM

However, the same method won't work for p-value in secp224k1 for some reason:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
n=0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
p%4=1 (failed, expected 3)
p%9=1 (failed, expected 7)

If all of those curves were generated together, then why p-value for secp224k1 was picked differently, than for three other curves? And how to efficiently compute square roots and cube roots for this curve? Also, how to proceed with all n-values? I heard there are some algorithms, to compute those results for any values, but if those curves were selected specifically, to make operations like that "fast", then everything should be solvable by simple equations like "(p+x)/y", similar to "(p+1)/4" and "(p+2)/9", right?

There are "complex" algorithms: A remark on the computation of cube roots in finite fields

One could solve the square and cube root in this case by "simple equation" too. To my knowledge this is not published anywhere.

The smallest pair x & y for square root is (p+3)/8; and for cube root is (p+8)/27.

r4 and r9 are non-trivial 4th and 9th roots of 1 mod p more info

r4 = 11913830147633844989339888812832642491211314989669855304438134084459 r9 = 452128346974922831777605865588626403245808317223927710376180600773 b² = a (mod p) if a^(p-1)/2 = 1 ; if square root exists b = a^(p+3)/8 if b² != a b = b * r4 b³ = a (mod p) if a^(p-1)/3 = 1 ; if cube root exists b = a^(p+8)/27 if b³ != a b = b * r9 if b³ != a b = b * r9

stwenhao

member

Activity: 77

Merit: 89

Quote

Modular sqrt if p % 4 != 3: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

If that's the case, then why someone generated some curves, where those operations are fast, and then picked secp224k1, to make it more complex, than the rest?

Quote

Note that the modular square root may not always exist.

Yes, but when it exists, then it can be usually checked in simple ways, for example by using "(p+1)/4". And when you create a curve, then you can pick any p-value. So, why p-value for secp224k1 was picked in a different way, than in three other curves? It would make much more sense, to use exactly the same algorithm for all four curves, so if that's not the case, then why it was done differently?

Edit: Also, I wonder why "b=5" is used for secp224k1, where "b=2" would work as well. If someone started from "b=1", and just incremented it, to find some prime n-value, then why it landed on "b=5", and not "b=2"? Even the same x-value for half of the generator would work in that case!

kTimesG

member

Activity: 165

Merit: 26

Quote from: NotATether on January 02, 2025, 10:17:22 PM

Just to be clear, this formula only calculates the square root and cube root for the"p" scalar, right?

What would be the use of that?

For obvious reasons, square root doesn't make sense for points, so that means that this is only for the numbers. But p is outside the range of allowed scalars which is from 1 to n.

I'm just curious to see how all of this works.

I think you confused group scalar (k % n) with field values (x % p).

For field elements x can be 0, and you get two totally valid points on the curve (as long as there's a valid square root to solve for y).

y = 0 would also produce valid points as long as you can compute an x that satisfies the curve equation, and AFAIK this is mathematically impossible if the equation parameters forbid it, e.g no solution for (x1, x2, x3) = cuberoot(y**2 - d) = cuberoot(p - d).

Modular sqrt if p % 4 != 3: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Note that the modular square root may not always exist.

dexizer7799

newbie

Activity: 30

Merit: 0

Quote from: stwenhao on January 03, 2025, 04:00:02 AM

Quote

What would be the use of that?

You have the curve equation in all cases: "y^2=x^3+b". So, to calculate x-value or y-value, you have that:

Code:

y^2=x^3+b
y=sqrt(x^3+b)
x^3=y^2-b
x=cbrt(y^2-b)

So, the most basic use case, is just to get a valid point on a curve. You pick x-value, and want to calculate y-value, or the other way around: for a given y-value, you want to get a valid x-value. And that means, when you generate a curve, you want to make those operations "easy". And I wonder, why it is the case in all three other curves, but doesn't work in case of secp224k1 specifically.

Quote

But p is outside the range of allowed scalars which is from 1 to n.

All point coordinates are in range from 1 to (p-1). And then, private keys are in range from 1 to (n-1), but n-value is calculated later, when you already know p-value.

What do you think can it be used for compute private key for public key I mean can it be used for break Ecdsa?

stwenhao

member

Activity: 77

Merit: 89

Quote

What would be the use of that?

You have the curve equation in all cases: "y^2=x^3+b". So, to calculate x-value or y-value, you have that:

Code:

y^2=x^3+b
y=sqrt(x^3+b)
x^3=y^2-b
x=cbrt(y^2-b)

So, the most basic use case, is just to get a valid point on a curve. You pick x-value, and want to calculate y-value, or the other way around: for a given y-value, you want to get a valid x-value. And that means, when you generate a curve, you want to make those operations "easy". And I wonder, why it is the case in all three other curves, but doesn't work in case of secp224k1 specifically.

Quote

But p is outside the range of allowed scalars which is from 1 to n.

All point coordinates are in range from 1 to (p-1). And then, private keys are in range from 1 to (n-1), but n-value is calculated later, when you already know p-value.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Just to be clear, this formula only calculates the square root and cube root for the"p" scalar, right?

What would be the use of that?

For obvious reasons, square root doesn't make sense for points, so that means that this is only for the numbers. But p is outside the range of allowed scalars which is from 1 to n.

I'm just curious to see how all of this works.

stwenhao

member

Activity: 77

Merit: 89

We start with four elliptic curves, which were constructed together (because of how the half of the generator is set in all of them). We have secp160k1, secp192k1, secp224k1, and secp256k1. When we want to compute square roots and cube roots, then for three of them, it works fine for their p-values:

secp160k1:

Code:

p=0xfffffffffffffffffffffffffffffffeffffac73
n=0x0100000000000000000001b8fa16dfab9aca16b6b3
(p+1)/4=0x3fffffffffffffffffffffffffffffffbfffeb1d
(p+2)/9=0x1c71c71c71c71c71c71c71c71c71c71c55554c0d
0x1000000000^0x3fffffffffffffffffffffffffffffffbfffeb1d^0x1c71c71c71c71c71c71c71c71c71c71c55554c0d=0x40 (mod p)

secp192k1:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffeffffee37
n=0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d
(p+1)/4=0x3fffffffffffffffffffffffffffffffffffffffbffffb8e
(p+2)/9=0x1c71c71c71c71c71c71c71c71c71c71c71c71c71aaaaa8b1
0x1000000000^0x3fffffffffffffffffffffffffffffffffffffffbffffb8e^0x1c71c71c71c71c71c71c71c71c71c71c71c71c71aaaaa8b1=0x40 (mod p)

secp256k1:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
(p+1)/4=0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c
(p+2)/9=0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c555554e9
0x1000000000^0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c^0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c555554e9=0x40 (mod p)

However, the same method won't work for p-value in secp224k1 for some reason:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
n=0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
p%4=1 (failed, expected 3)
p%9=1 (failed, expected 7)

If all of those curves were generated together, then why p-value for secp224k1 was picked differently, than for three other curves? And how to efficiently compute square roots and cube roots for this curve? Also, how to proceed with all n-values? I heard there are some algorithms, to compute those results for any values, but if those curves were selected specifically, to make operations like that "fast", then everything should be solvable by simple equations like "(p+x)/y", similar to "(p+1)/4" and "(p+2)/9", right?

Topic: Square roots and cube roots in secp224k1 (Read 115 times)