Invalid curve attack: finding low order points Background
Here's a description of page 182 of &quot;Guide to Elliptic Curve Cryptography&quot; by Hankerson, Menezes and Vanstone. Here's a quote from that page:

The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve $E$ defined over $\mathbb F_q$ do not involve the coefficient $b$ (see §3.1.2). Thus, if $E'$ is any elliptic curve defined over $\mathbb F_q$ whose reduced Weierstrass equation differs from $E$’s only in the coefficient $b$, then the addition laws for $E'$ and $E$ are the same. Such an elliptic curve $E'$ is called an invalid curve relative to $E$.
Suppose now that $A$ does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker $B$ selects an invalid curve $E'$ such that $E'(\mathbb F_q)$ contains a point $R$ of small order $l$, and sends $R$ to $A$. $A$ computes $K=dR$ and $k = KDF(R)$. As with the small subgroup attack, when $A$ sends $B$ a message $m$ and its tag $t=MAC_k(m)$, $B$ can determine $d_l = d \bmod l$. By repeating the attack with points $R$ (on perhaps different invalid curves) of relatively prime orders, $B$ can eventually recover $d$.

Question
I am having a problem understanding one aspect of invalid-curve attacks: given some curve $E$, how does one finds an invalid curve $E'$ ($E$ and $E'$ have same parameters except for coefficient $b$) and a small-order point $R$ on $E'(\mathbb F_q)$? Is there an efficient algorithm for finding curves with small order points?
I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some &quot;popular&quot; $E$ (e.g. one of the NIST curves).
Related questions
Why do public keys need to be validated?
Attacks on schemes based on elliptic curves when the transmitted points are not on the curve
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.