1
$\begingroup$

In this answer by fkraiem he proves a property that:

$a^{(p-1)/2} = 1$ if and only if $x$ is even

But this doesn't seem to work in my test with the secp256k1 Elliptic Curve. Here is my Python 2 code:

ECLib.py:

P = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (int(Gx),int(Gy))
Acurve = 0

def legendreSymbol(a,p=P): #Legendre Symbol Calculation
    ls = pow(a, (p - 1) / 2, p)
    if ls == p - 1: return -1
    else: return ls

def modinv(a,n): # Extended Euclidean Algorithm
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm = hm - lm * ratio
        new = high - low * ratio
        hm = lm
        high = low
        lm = nm
        low = new
    return lm % n

def ECadd(xp,yp,xq=Gx,yq=Gy): # EC point addition
    m = ((yq-yp) * modinv(xq-xp,P))%P
    xr = (m*m-xp-xq)%P
    yr = (m*(xp-xr)-yp)%P
    return (xr,yr)

def ECdouble(xp,yp): # EC point doubling
    LamNumer = 3*xp*xp+Acurve
    LamDenom = 2*yp
    Lam = (LamNumer * modinv(LamDenom,P)) % P
    xr = (Lam*Lam-2*xp) % P
    yr = (Lam*(xp-xr)-yp) % P
    return (xr,yr)

Test.py:

import ECLib

Point = (ECLib.Gx, ECLib.Gy)
Deg = 1

print 'Degree of G \t\t\t Legendre Symbol'

for i in range(8):
  Point = ECLib.ECdouble(Point[0], Point[1])
  Deg = Deg * 2
  print '\t' + str(Deg) + '\t\t\t\t' + str(ECLib.legendreSymbol(Point[0]))

Output:

Degree of G                      Legendre Symbol
        2                               1
        4                               -1
        8                               -1
        16                              1
        32                              -1
        64                              -1
        128                             1
        256                             1

As I am doubling, the power of G is always even, so Legendre Symbol should always be 1 but that is not the case. Why is that?

$\endgroup$
4
  • $\begingroup$ You are testing the Legendre symbol on x coordinates of elliptic curve points. Legendre symbol shouldn't be used like that. You can't imply the "degree of G" by looking at x-coordinates. What are you trying to achieve ? $\endgroup$
    – Ruggero
    Feb 6 at 10:26
  • $\begingroup$ @kelalaka but do you know if the same properties apply to elliptic curves? $\endgroup$ Feb 6 at 16:32
  • 1
    $\begingroup$ No, the same properties do not apply to the elliptic curves themselves (at least, if we're working with a curve with an odd number of points, or a subgroup with odd order - we almost always do). $\endgroup$
    – poncho
    Feb 7 at 13:55
  • $\begingroup$ @Ruggero I was trying to find the parity of x by legendre symbol but finding the right legendre symbol is not possible for this elliptic curve $\endgroup$ Feb 8 at 8:29

1 Answer 1

1
$\begingroup$

This answer extends @poncho's comment.

The property “ $a^{(p-1)/2}=1\text{ if and only if }x\text{ is even}$ ” stated in the answer linked in the question is for the multiplicative group modulo an odd prime $p$, and assumes $a=g^x$ with $g$ a generator of that group. The group, thus generator $g$, has even order $p-1$ (the $-1$ is because $0$ is not a member of the group). That even order of $g$ is essential for proving the property.

The present question is for an elliptic curve group over prime field $\mathbb F_\mathtt{P}$ of prime order $\mathtt{N}$, and a generator $\mathtt{G}$ (all given numerically). That happens to be secp256k1. Customarily, elliptic curve groups are noted additively rather than multiplicatively. Indeed $A=x\,\mathtt{G}$ in the elliptic curve group parallels $a=g^x$ in multiplicative group modulo $p$. The point at infinity $\mathcal O$ parallels $1$. $G$ parallels $g$. $N$ parallels $p-1$.

The property “ $((N-1)/2)\,\mathtt{A}=\mathcal O\text{ if and only if }x\text{ is even}$ ” would parallel $a^{(p-1)/2}=1$ if $N$ was even. But it's not! That would require a different elliptic curve (and then, for a curve used in ECDSA, $G$ would be chosen of prime order, thus not a generator of the whole curve).

And there's no substitute. Using ${(\mathtt{A}_X)}^{(\mathtt{P}-1)/2}=1$ comes out of nowhere, and does not work, as the test in the question illustrates (and @poncho generalizes in another comment).

For the parameters of secp256k1, there is no known computationally feasible method to guess the parity of $x$ from $x\,\mathtt{G}$ alone for random $x\in[1,\mathtt{N})$. Argument: If there was a practical method for this consistently working significantly better than a random guess, that method could demonstrably be leveraged to compute the private key matching any public key.

$\endgroup$
4
  • 2
    $\begingroup$ "And there's no substitute. Using $({\mathtt{A}_X})^{(\mathtt{P}-1)/2}$ comes out of nowhere, and does not work, as the test in the question illustrates."; actually, it cannot work. A valid $\mathtt{A}_X$ value corresponds to two elliptic curve points, and for sec256k1, one has even $x$ and the other has odd $x$ - that test has no way to determine which. Hence, there is no possible test to determine the lsbit of $x$ which examines only $\mathtt{A}_X$ $\endgroup$
    – poncho
    Feb 7 at 17:04
  • $\begingroup$ Don't get me wrong but how can the legendre symbol still be so precise to always give 1 or p-1 in my example in the question? That's the natural outputs expected from the calculation of legendre symbol. $\endgroup$ Feb 7 at 20:04
  • $\begingroup$ @DevanshuLinux: your legendreSymbol has result $r$ such that $r≡a^{(\mathtt{P}-1)/2}\pmod{\mathtt{P}}$. Thus $r^2≡{\left(a^{(\mathtt{P}-1)/2}\right)}^2≡a^{\mathtt{P}-1}\pmod{\mathtt{P}}$. By Fermat's Little Theorem, since $\mathtt{P}$ of secp256k1 is prime, and since $a\not\equiv0\pmod{\mathtt{P}}$ for your inputs $a$ that are X coordinates on secp256k1, it holds $r^2≡1\pmod{\mathtt{P}}$. That's a second degree equation, thus it has only two solutions in the output set $[-1,p-1)$ of your legendreSymbol, and these are $-1$ and $1$. That's why your $r$ is always one of these. $\endgroup$
    – fgrieu
    Feb 7 at 20:17
  • $\begingroup$ ohhh! @fgrieu thanks a lot, mate! $\endgroup$ Feb 7 at 20:20

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.