y coordinate calculation (PUBLIC KEY BITCOIN)

[bytcoin]

I would like to understand the math behind this...

Simply and objectively!In decimal for ease.

All calculations:
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
-------------------------------------------------------------------------------------------------------------------------------------------------------
Private key : 1

Public key :

x = 55066263022277343669578718895168534326250603453777594175500187360389116729240

55066263022277343669578718895168534326250603453777594175500187360389116729240**3 + 7 =

32748224938747404814623910738487752935528512903530129802856995983256684603122**28948022309329048855892746252171976963317496166410141009864396001977208667916=

y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

OKAY
---------------------------------------------------------------------------------------------------------------------------------------------------

Private key : 2

Public key :

x = 89565891926547004231252920425935692360644145829622209833684329913297188986597

89565891926547004231252920425935692360644145829622209833684329913297188986597**3 + 7 =

57199941671890039290383617934355424684258807805258215939368959893591666662646**28948022309329048855892746252171976963317496166410141009864396001977208667916=

y = 12158399299693830322967808612713398636155367887041628176798871954788371653930

OKAY
-------------------------------------------------------------------------------------------------------------------------------------------------

Private key : 3

Public key :

x = 112711660439710606056748659173929673102114977341539408544630613555209775888121

112711660439710606056748659173929673102114977341539408544630613555209775888121**3 + 7 =

104193826873522593991639737736096919049125888873761064059040146529970392609905**28948022309329048855892746252171976963317496166410141009864396001977208667916=

y = 90209061256745311731914079131285931446821116410824268969537695047367247992253

NO OKAY
------------------------------------------------------------------------------------------------------------------------------------------------
Why did the y value of private key 3 need to be inverted?

What math or method is used to know whether or not I will need to invert the y value?

[_Counselor]

Each x coordinate corresponds to two y coordinates, because of square root.

To convert between Ys, you have to calculate y2 = (y1 - secp256k1.p) * -1. One of Y is even and another is odd.

To indicate which coordinate is needed, the compressed keys starts with 02 for even Y and 03 for odd Y.

[bytcoin]

Each x coordinate corresponds to two y coordinates, because of square root.

To convert between Ys, you have to calculate y2 = (y1 - secp256k1.p) * -1. One of Y is even and another is odd.

To indicate which coordinate is needed, the compressed keys starts with 02 for even Y and 03 for odd Y.

Yes...but what I would really like to understand is why private key 3 needed to invert the y value and private keys 1 and 2 didn't need to invert the y value.

Why do there have y values that need to be inverted and other values that don't need to be inverted?

What math or method is used to know whether or not I will need to invert the y value?

[_Counselor]

Yes...but what I would really like to understand is why private key 3 needed to invert the y value and private keys 1 and 2 didn't need to invert the y value.

Why do there have y values that need to be inverted and other values that don't need to be inverted?

What math or method is used to know whether or not I will need to invert the y value?

If you're using standard EC math, there no need to invert anything.
The point on the elliptic curve is generator point G multiplied by the private key. The EC multiplication formula calculates both X and correct Y and does not require additional inversion.
Looks like you're trying to calculate only X and then trying to calculate Y from that X with simple equation, which leads to two possible solutions of that equation. And without using the multiplication formula, there is no way to know whether the right Y will be even or odd.

[bytcoin]

@_Counselor Thanks for the answers... yes, I'm calculating using only x. Maybe with some more advanced equation or other methods it is possible to define exactly the value of y with only x?

[BlackHatCoiner]

32748224938747404814623910738487752935528512903530129802856995983256684603122**28948022309329048855892746252171976963317496166410141009864396001977208667916

What exactly are you trying to do here? It doesn't seem okay to me.

@_Counselor Thanks for the answers... yes, I'm calculating using only x. Maybe with some more advanced equation or other methods it is possible to define exactly the value of y with only x?

But, the only thing you need to define the value of y is x. @interiawp added you a code in which you can get one of the two values by knowing the other. If you wanted to know x, but having only y, then it's: x^3 = y^2 - 7.

To convert between Ys, you have to calculate y2 = (y1 - secp256k1.p) * -1. One of Y is even and another is odd.

Excuse me for the noob question:  Let's assume x³=1, which means y²=8. What's y? Will it be square root of 8?

[_Counselor]

Excuse me for the noob question:  Let's assume x³=1, which means y²=8. What's y? Will it be square root of 8?

It will be square root modulo prime of 8
to be precise, it will be 29896722852569046015560700294576055776214335159245303116488692907525646231534

(29896722852569046015560700294576055776214335159245303116488692907525646231534 * 29896722852569046015560700294576055776214335159245303116488692907525646231534) mod secp256k1.p = 8

[bytcoin]

@BlackHatCoiner Or it could be like this...
 
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

32748224938747404814623910738487752935528512903530129802856995983256684603122^
28948022309329048855892746252171976963317496166410141009864396001977208667916=
32670510020758816978083085130507043184471273380659243275938904335757337482424

[bytcoin]

script : x from y

Code:

## Input
y = 0x3199555CE45C38B856C9F64AC6DB27000AB6CEA10CAD76B2B6E246C9A020E707

## Field parameters
# Field modulus
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
# Cube root of 1
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

## Actual code
xcubed = (y*y - 7) % p
print ("xcubed = 0x%x" % xcubed)

x = pow(xcubed, (p + 2) / 9, p)
print ("x1 = 0x%x" % x)
print ("x2 = 0x%x" % (x * beta % p))
print ("x3 = 0x%x" % (x * beta * beta % p))

script: y from x

Code:

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x33709eb11e0d4439a729f21c2c443dedb727528229713f0065721ba8fa46f00e
ysquared = ((x*x*x+7) % p)    
print ("ysquared= %s ",  hex(ysquared) )   
y = pow(ysquared, (p+1)/4, p)
print ("y1 =  ",hex(y))
print ("y2 =  ", hex(y * -1 % p))
y1 = y
y2 = (y * -1) % p
print(" ")
print("value x = ",hex(x))
print("value x = ",x)
print("         ")

if Integer(y1) % 2 == 0:
    
    print("value 02 to y = ",hex(y1))
    print("value 02 to y =",y1)
    print(" ")
    print("value 03 to y = ",hex(y2))
    print("value 03 to y =",y2)
    

if Integer(y2) % 2 == 0:
    print("value 02 to y = ",hex(y2))
    print("value 02 to y =",y2)
    print(" ")
    print("value 03 to y = ",hex(y1))
    print("value 03 to y =",y1)
    

#test
print (hex((x**3 + 7 - y1**2) % p) )  

print (hex((x**3 + 7 - y2**2) % p))  

Thanks for the script ... but I already have the first and the second I already knew
What I would really like is some method that would give me the correct y value... without having to invert or choose between y or -y (I THINK IT'S IMPOSSIBLE)

[BlackHatCoiner]

It will be square root modulo prime of 8

But, the square root of 8 is not an interval. Specifically, it is around 2.82. If you mod this with a prime number, such as 11, won't you get the same 2.82? (2.82 = (11 * 0) + 2.82)

Please guide me I've messed things up again.

32748224938747404814623910738487752935528512903530129802856995983256684603122^
28948022309329048855892746252171976963317496166410141009864396001977208667916=
32670510020758816978083085130507043184471273380659243275938904335757337482424

The symbol that I colored red means power. The result from your process would give a much greater number, considered infinity. It doesn't give the blue one.

[garlonicon]

Specifically, it is around 2.82.

In finite field, all numbers are integers. There is no dot. Minus one is fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140, 0.5 is 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1, everything can be expressed as integers, even square roots and numbers like e, pi, logarithms, just everything.

The result from your process would give a much greater number, considered infinity.

No, because if you have a^b mod n, then you can check if b is even or odd. If b is odd, then you can calculate a*a^(b-1) mod n, in this way you have b-1 that is even. If b is even, you can calculate (a*a)^(b/2) mod n. If during multiplication you would get something bigger than n, then you take the result modulo n and proceed. Finally, you will always have a number modulo n, so it will always be in the correct range.

[BlackHatCoiner]

Minus one is fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

How? Don't I just convert the hexadecimal into decimal?

Code:

hex: fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
dec: 115792089237316195423570985008687907852837564279074904382605163141518161494336

You got me unprepared on this one. Still, I haven't learnt how they work. I know I shouldn't feel ridicule, but I do. 

everything can be expressed as integers, even square roots and numbers like e, pi, logarithms, just everything.

If you don't mind could you explain it a little bit more? Or share me a link with useful content, if you're out of time.

No, because if you have a^b mod n

Is the mod supposed to be implied? Because, OP didn't write it.

[bytcoin]

It will be square root modulo prime of 8

But, the square root of 8 is not an interval. Specifically, it is around 2.82. If you mod this with a prime number, such as 11, won't you get the same 2.82? (2.82 = (11 * 0) + 2.82)

Please guide me I've messed things up again.

32748224938747404814623910738487752935528512903530129802856995983256684603122^
28948022309329048855892746252171976963317496166410141009864396001977208667916=
32670510020758816978083085130507043184471273380659243275938904335757337482424

The symbol that I colored red means power. The result from your process would give a much greater number, considered infinity. It doesn't give the blue one.

Public key equations are always modular... you forgot to include:
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

[bytcoin]

firstly everything is possible.

second:
"What I would really like is some method that would give me the correct y value... without having to invert or choose between y or -y (I THINK IT'S IMPOSSIBLE)" ---> if you do that means you break ecdsa. You trying solve problem that pubkey is in d<n/2 or d> n/2

third -> you can check how many times is fliped (y) (as 02 to 03 and 03 to 02) depends on subgroup during adding point . but it is not possoble, you can't check   n/2 subgrups -> hundreds years.. you know ... or you are immortal:D

Technically it's the second option

[NotATether]

Minus one is fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

How? Don't I just convert the hexadecimal into decimal?

It's because -1 is outside of the range of remainders 0 to N-1, so it has to be shifted into this range, by repeatedly adding or subtracting N, until it becomes one of the numbers in that range (in this case, N-1).

everything can be expressed as integers, even square roots and numbers like e, pi, logarithms, just everything.

If you don't mind could you explain it a little bit more? Or share me a link with useful content, if you're out of time.

[Almost] all decimal numbers can be written as a fraction, with a numerator and denominator (Pi and some other math constants actually can't be expressed like this unless you truncate it to some digits).

So the decimal number is actually equivalent to: modinv(denominator) * numerator.

Where modinv is the modular inverse of the number with respect to N.

Is the mod supposed to be implied? Because, OP didn't write it.

Yes.


@OP, have you tried using Legendre numbers mod n to classify the private keys by their polarity? priv=1 gives an odd key (afaik), priv=2 gives an even key, so possibly odd keys have Legendre numbers of -1 and even numbers have them at 1.

I don't remember the polarity of the next few numbers from my head so it's worth a shot if you want to calculate them.

[_Counselor]

If you don't mind could you explain it a little bit more? Or share me a link with useful content, if you're out of time.

Simple explanation.

Let's take a number like 0.5
What is 0.5? It is half of 1, so this number, then multiplied by two, will give 1.
Now we will find a number that satisfies this in the conditions of a finite field.
It will be "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1" - if you double that number in secp256k1, you will get 1. So this enormous number also works just like 0.5.
You may try it yourself with some EC calculator, just get a point from this privkey, then double it, you will get point from key "1".

Some way we can explain "-1" as "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140"
-1 + 1 = 0. If you add "1" and "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140" you will get point at infinity, that is works on EC like zero.

[garlonicon]

Pi and some other math constants actually can't be expressed like this unless you truncate it to some digits

In finite field, everything is truncated to the prime modulo. You have one and you have prime modulo plus one and that two values have exactly the same value in finite field. You can take a square root of something and it will be equal to some integer, because if you multiply that value by itself, you will get back the value you started with. The same with pi, e, and other constants. If you have some equation, for example that pi is a circumference divided by a diameter, then you can calculate better and better approximation, and finally you will end up with a number that cannot be better approximated, because by taking modulo you will lose precision. You can have pi defined as an infinite sum, where after some point, you will get all zeroes, because numbers will be too small to be expressed in this finite field.

Finite fields are beautiful, because they are finite. You have well-defined precision set to 256-bit values and you will never need more precision than that if you stay in that field. Some values are undefined, for example there is no public key where x=5, so there is no value for the square root of 132 (y^2=x^3+7, x=5, y^2=132, y=sqrt(132) does not exist). But if it is possible to calculate some value (for example sqrt(2) exists), then it can be expressed as an integer.

[BlackHatCoiner]

It's because -1 is outside of the range of remainders 0 to N-1, so it has to be shifted into this range, by repeatedly adding or subtracting N, until it becomes one of the numbers in that range (in this case, N-1).

So let me get this straight. If we want to represent -1 in a finite field [1, 47) whose acres are prime numbers, we'll have to deform it and include it into that range. In order to do so, we'll take -1 and add 47 to it, until it's included. In this case, -1 + 47 = 46. The result will never be 47, that's why I added parenthesis instead above.

Now let's go on @_Counselor's example; if we take 0.5 and double it, we'll get 1. This means that we must find a number whose doubling will result in 1 in the finite field of secp256k1. In that case, it's - “7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1”. I'm trying to understand, though, how will you get 0.5 by having that hex and 1.

Sorry, but that's a bunch of new things introduced to my maths' knowledge. I'll try learnmeabitcoin.com's example with the modular inverse to possibly understand it better.

We take 8 in the finite field of 47. We'll multiply 8 by 13 times => 8*13 = 104, 104 mod 47 = 10. Now let's find the multiplication inverse of 10 in that field:

10 * x = 8

How exactly can I solve this besides trying a different value each time? In the article, it tries 1, 2, 3... until it finds 29 which is suitable.

You may try it yourself with some EC calculator, just get a point from this privkey, then double it, you will get point from key "1".

I tried it with a secp256k1 calculator and verified it. So, what we're describing is called scalar multiplication? Shouldn't there be an inverse, where you can get -1 by only having - "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140" - and 1?

[j2002ba2]

We take 8 in the finite field of 47. We'll multiply 8 by 13 times => 8*13 = 104, 104 mod 47 = 10. Now let's find the multiplication inverse of 10 in that field:

10 * x = 8

How exactly can I solve this besides trying a different value each time? In the article, it tries 1, 2, 3... until it finds 29 which is suitable.

Let's consider a * x ≡ b (mod p), which means x ≡ b/a (mod p) for a ≠ 0.
There are two ways to find x.

First through Fermat's little theorem:
a^p ≡ a (mod p)
a^p-2 ≡ a^-1 ≡ 1/a (mod p)
x ≡ b * a^p-2 (mod p)

Second through Extended Euclidean algorithm:
x ≡ b * inverse(a, p) (mod p)

[NotATether]

Now let's go on @_Counselor's example; if we take 0.5 and double it, we'll get 1. This means that we must find a number whose doubling will result in 1 in the finite field of secp256k1. In that case, it's - “7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1”. I'm trying to understand, though, how will you get 0.5 by having that hex and 1.

Once you move the 0.5 into the secp256k1 finite field, it is indistinguishable from that large number you quoted above. They are functionally equivalent.