Invalid curve attack: finding low order points
Is there an efficient algorithm for finding curves with small order points?


Yup, just choose a curve at random and you will find one soon enough. Example with P-256 in Pari/GP.

First create the curve and check that its order matches the expected one just to be sure:

(00:31) gp &gt; p = 115792089210356248762697446949407573530086143415290314195533631308867097853951;
(00:31) gp &gt; b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b;
(00:33) gp &gt; E = ellinit([Mod(-3,p),Mod(b,p)]);
(00:38) gp &gt; n = ellsea(E)
115792089210356248762697446949407573529996955224135760342422259061068512044369
(00:39) gp &gt; isprime(n)
1


Create the invalid curve $y^2 = x^3 - 3x + 2019$ and check its group structure:

(00:40) gp &gt; E2 = ellinit([Mod(-3,p),Mod(2019,p)]);
(00:41) gp &gt; ellgroup(E2)
[115792089210356248762697446949407573529765911662708030293191211169245686839810]
(00:41) gp &gt; n2 = ellsea(E2);
(00:42) gp &gt; factor(n2)

[                                                              2 1]

[                                                              3 1]

[                                                              5 1]

[                                                             13 1]

[                                                            941 1]

[                                                           3001 1]

[                                                         644899 1]

[163029786756926124665585146297685125210696471441070761964520581 1]


So the group is cyclic of highly composite order (unlike the real curve, where the goup has prime order). Just get a random point on it, and check its order:

(00:43) gp &gt; P = random(E2);
(00:43) gp &gt; o = ellorder(E2,P)
115792089210356248762697446949407573529765911662708030293191211169245686839810
(00:44) gp &gt; factor(o)

[                                                              2 1]

[                                                              3 1]

[                                                              5 1]

[                                                             13 1]

[                                                            941 1]

[                                                           3001 1]

[                                                         644899 1]

[163029786756926124665585146297685125210696471441070761964520581 1]


I got lucky; my point is a generator so I can easily generate points whose order is any factor of the group order, e.g.:

(00:46) gp &gt; P2 = ellmul(E2,P,o/2);
(00:47) gp &gt; ellorder(E2,P2)
2
(00:47) gp &gt; P3 = ellmul(E2,P,o/3);
(00:47) gp &gt; ellorder(E2,P3)
3
(00:47) gp &gt; P644899 = ellmul(E2,P,o/644899);
(00:48) gp &gt; ellorder(E2,P644899)
644899


But maybe I just got lucky; what if I try another random point? I'll leave it to you as an exercise to try other random points on the curve, as well as other curves.