How to modify code to find (calculate) exact generator of curve?
I am doing elliptic curve cryptography with the curve "nist256r1".
Here is the code I am using, also available at pastebin: https://pastebin.com/mCv0AHj7.
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
privkey = CG.random_element()
Q = curve(ZZ(privkey) * curve_gen)
### We generate the necessary malicious generator
kprime = CG.random_element()
kprimeinv = kprime.inverse_of_unit()
Gprime = ZZ(kprimeinv) * Q
### We can now verify that the we knows a private key corresponding
### to the public key under their generator
newpoint = curve(ZZ(kprime) * curve_gen)
Qprime = curve(ZZ(kprime) * Gprime)
When I multiply kprime
to Gprime
, result: Point1=Point1-1
.
But, when I multiply kprime
to curve_gen
, I get false result: Point1<>Point-3
.
But, when I multiply kprime * Gprime
I get true result.
How to get result Point1
after multiplying kprime
to curve_gen
?
How to modify code and what needed to add to code for finding exact Point1
after multiplying kprime
to curve_gen
? Maybe Chinese Remainder needed??
When I multiply kprime
to curve gen
, I get another point - I get not point Point-1-(29071217121488582521608171944263315625701615497932907218591416908586258568965, 59574170696980719976515868978945602886682382595455160870729457813974828581902),
and get this point Point3=(17926030768548235702442204134974018188929283587000768925853022445872051613924 : 31678060064977392800194523884536612241566631842713190224565644256881729064814 : 1).
Result:
sage: print("Q==Q'", Qprime == Q)
Q==Q' True
sage: print(Qprime.xy())
(29071217121488582521608171944263315625701615497932907218591416908586258568965,
59574170696980719976515868978945602886682382595455160870729457813974828581902)
sage: print(Q.xy())
(29071217121488582521608171944263315625701615497932907218591416908586258568965,
59574170696980719976515868978945602886682382595455160870729457813974828581902)
sage: print(newpoint)
(17926030768548235702442204134974018188929283587000768925853022445872051613924
: 31678060064977392800194523884536612241566631842713190224565644256881729064814
: 1)
This is ready to run source on pastebin https://pastebin.com/mCv0AHj7