Here is a sage script that implements the described attack. I have scripts that implement curve parameters separately (so I can load them into other scripts as needed) so this might look a little redundant in places:
#!/usr/bin/env sage
nistp256r1_order = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
nistp256r1_modulus = 2**224 * (2**32 - 1) + 2**192 + 2**96 - 1
nistp256r1_a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
nistp256r1_b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
nistp256r1_field = GF(nistp256r1_modulus)
nistp256r1 = EllipticCurve(nistp256r1_field, [0,0,0,nistp256r1_a,nistp256r1_b])
nistp256r1_base_x = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
nistp256r1_base_y = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
nistp256r1_gen = nistp256r1(nistp256r1_base_x, nistp256r1_base_y, 1)
curve = nistp256r1
curve_order = nistp256r1_order
curve_gen = nistp256r1_gen
CG = Zmod(curve_order)
### these are "inputs" to the system. Only pubkey is known to an attacker
privkey = CG.random_element()
Q = curve(ZZ(privkey) * curve_gen)
### The attacker generates the necessary malicious generator
kprime = CG.random_element()
kprimeinv = kprime.inverse_of_unit()
Gprime = ZZ(kprimeinv) * Q
### We can now verify that the attacker knows a private key corresponding
### to the public key under their generator
Qprime = curve(ZZ(kprime) * Gprime)
print("Q==Q'", Qprime == Q)
print(Qprime.xy())
print(Q.xy())
### So if the attacker believes Gprime is a correct generator,
### this is bad news.
### you can implement something relying on it, with Gprime as your generator, here.
This is using real secp256r1, i.e. NIST P256, parameters. You can try this in sagemath's online tools and see that it works very efficiently. inverse_of_unit is a nice function that computes the inverse of kprime in the multiplicative group modulo the prime order of the curve. You can do exactly the same thing with the XGCD algorithm from sage.arith.misc. ZZ is required simply for type conversion: sage doesn't understand how to multiply a point by a Zmod element. We help it out by converting to an integer. .xy() is not required, it simply prints affine, instead of projective, coordinates. I wrote this with sage 9, which is based on python 3. The 0,0,0 are not necessary for the elliptic curve constructor (two parameters = short weierstrass) but I'm in the habit...
As a corollary to Lagrange's theorem, any prime order group is cyclic, which means any randomly chosen point is a generator and since the group of curve points under elliptic curve point addition is of prime order, any randomly chosen point on the curve necessarily generates the whole group. However, we need to choose a random secret key to relate the old generator to the new, because solving G' = k'Q is a discrete logarithm problem and we can't solve those.
P256 is obviously quite difficult for humans to deal with in their minds, so if you want to play with a more human-sized curve, try:
E=EllipticCurve(GF(17),[3,5])
which is of prime order and has 23 points (and so cofactor 1 like P256).
As a corollary to Lagrange's theorem, any prime order group is cyclic, which means any randomly chosen point is a generator and since the group of curve points under elliptic curve point addition is of prime order, any randomly chosen point on the curve necessarily generates the whole group. However, we need to choose a random secret key to relate the old generator to the new, because solving G' = k'Q is a discrete logarithm problem and we can't solve those.
P256 is obviously quite difficult for humans to deal with in their minds, so if you want to play with a more human-sized curve, try:
which is of prime order and has 23 points (and so cofactor 1 like P256).