Invalid point attack on quadratic twist of Elliptic Curve when -1 is a quadratic residue

Question

I'm replicating an invalid point attack on ECC using Short Weierstrass curves. For this I have written a "dumb" implementation that does not validate points are on the curve before going into the scalar multiplication. For the outline of the attack, I'm heavily borrowing from Samuel Neves' excellent descrption which he gave here: Understanding Twist Security with respect to short Weierstrass curves

I can replicate this without any issue when $d = -1$ is a quadratic non-residue in $\mathbb{F}_p$, then everything works out-of-the-box. However, when $p$ is so that $-1$ is a quadratic residue and therefore I need to choose a different value for $d$, everything falls apart.

For simplicity, in the first run I am not using curves in $\mathbb{F}_{p^2}$ because for small $p$ exhaustive enumeration to find low-order points is not an issue.

As an example, say my curve is defined over $\mathbb{F}_{101}$; here, $-1$ is a quadratic residue mod $p$, since $10 \cdot 10 = -1 \mod 101$. My curve is given by

$E: y^2 = x^3 + 13x + 29$

And with $d = 2$, a quadratic non-residue mod 101,

$E^d: y^2 = x^3 + 52x + 30$

The order of $E^d$ is $111 = 3 \cdot 37$. I have chosen two points on $E^d$ which have orders 3 and 37, respectively:

$P_1 = (28, 62)$

$P_2 = (8, 7)$

When I run these values through my scalar multiplication without point validation (for private key $d = 58$, I get the following output:

$S_1 = (94, 53)$

$S_2 = (32, 14)$

Neither $S_1$ nor $S_2$ is a point on the quadratic twist $E^d$. I can lift either X coordinate in $E^d$, but then the orders of the points are wrong.

Here's my example code:

Fp = GF(101)
D = Fp(2)
    
print(D, "is square?", D.is_square())
(a, b) = (13, 29)

E = EllipticCurve(Fp, [a, b])
Et = EllipticCurve(Fp, [ a*D^2, b*D^3 ])

print("Et.order()", factor(Et.order()))

attack_points = [
    Et(28, 62),
    Et(8, 7),
]
print(E)
print(Et)
for P in attack_points:
    print(P, P.order())

# private key d = 58
mul_results = [ 
    Et(94, 53), 
    Et(32, 14), 
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())

Which outputs:

2 is square? False
Et.order() 3 * 37
Elliptic Curve defined by y^2 = x^3 + 13*x + 29 over Finite Field of size 101
Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
TypeError: Coordinates [94, 53, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101

How can I perform this attack for a quadratic twist where $d \neq -1$?

Answer 1

This is not a problem of d being a QNR that is not -1.

Instead, it is a problem of small moduli. I can demonstrate this reliably using a modified script of Samuel Neves: Invalid point attack yields wrong results for low order points

This does not answer at all why it does not work, but at least this demonstrates that $d \neq -1$ is not the root cause of my issue.