4
$\begingroup$

The question is somewhat complex and directed to clearing things out.

Suppose that $n$ is the order of the cyclic group. It $n - 1$ is the number of all private keys possible

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

We also know that every private and public key has its modular inverse. To get a modular inverse of a private key, we need to subtract the private key from $n$.

$$n - privKey$$

To get a modular inverse of a public key, we'll have to multiply its $y$ coordinate by $-1$ and modulo by the $p$ - order of the finite field. $$x,y = x, -y \bmod p$$

A modular inversed public key has the same $x$ coordinate as the original public key, but a different $y$ coordinate, and the $y$ coordinate is always different in its polarity. If the original $y$ was odd, in a modular inversed key it will be even, and vice versa.

The question is, if the $y$ coordinate of a public key is even, does it mean that the corresponding private key is less than $n/2$ by its value? If the $y$ is odd, the private key is more than $n/2$?

Is there any relationship between the evenness/oddness of the $y$ (or $x$) coordinate and the value of the corresponding private key?

Is there any way to know that the private key is more or less than $n/2$ while not knowing the private key itself?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

A little test with Sagemath for the first 10 integers as the private key;

#secp256k1
p = Integer("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F")

a = Integer("0x0000000000000000000000000000000000000000000000000000000000000000")
b = Integer("0x0000000000000000000000000000000000000000000000000000000000000007")

K = GF(p)
E = EllipticCurve(K,[a,b])

Gx = Integer(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
Gy = Integer(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
G = E(Gx, Gy)

# Check the point

#prime curve
n = E.order()


for i in range(1,10):
    A = i* G
    print(A[0],A[1])

The below is the output $(x,y)$;

55066263022277343669578718895168534326250603453777594175500187360389116729240 32670510020758816978083085130507043184471273380659243275938904335757337482424
89565891926547004231252920425935692360644145829622209833684329913297188986597 12158399299693830322967808612713398636155367887041628176798871954788371653930
112711660439710606056748659173929673102114977341539408544630613555209775888121 25583027980570883691656905877401976406448868254816295069919888960541586679410
103388573995635080359749164254216598308788835304023601477803095234286494993683 37057141145242123013015316630864329550140216928701153669873286428255828810018
21505829891763648114329055987619236494102133314575206970830385799158076338148 98003708678762621233683240503080860129026887322874138805529884920309963580118
115780575977492633039504758427830329241728645270042306223540962614150928364886 78735063515800386211891312544505775871260717697865196436804966483607426560663
41948375291644419605210209193538855353224492619856392092318293986323063962044 48361766907851246668144012348516735800090617714386977531302791340517493990618
21262057306151627953595685090280431278183829487175876377991189246716355947009 41749993296225487051377864631615517161996906063147759678534462689479575333124
78173298682877769088723994436027545680738210601369041078747105985693655485630 92362876758821804597230797234617159328445543067760556585160674174871431781431

As we can see there are both even and odd cases for $X$ and $Y$ coordinates in this range. This concludes that there is no %100 relation.

Is it really indistinguishable, I think so, however, I can neither prove it nor calculate it!


For a run for the first 1 million private keys we have;

Number of odd X'es 499822
Number of odd Y'es 499944

As we can see, quite close to the half.


As a special note: the coordinate of the point should not be used for randomness since they are not uniform.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.