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$?
