Ask Your Question
0

How to modify code to find (calculate) exact generator of curve?

asked 2020-08-08 14:01:14 -0600

Duglas gravatar image

updated 2020-08-09 07:25:51 -0600

slelievre gravatar image

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)
edit retag flag offensive close merge delete

Comments

This is ready to run source on pastebin https://pastebin.com/mCv0AHj7

Duglas gravatar imageDuglas ( 2020-08-08 14:26:15 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2020-08-10 09:38:58 -0600

dan_fulea gravatar image

updated 2020-08-10 09:40:17 -0600

This could not be a comment, so it is posted as an answer.

In such a case it is best to also explain mathematically what is expected and why. So let us digest together.

The code defines a curve $E$ with equation $y^2=x^3+ax+b$ defined over the field with $p$ elements $F$, where

  • $p$ is the prime 2**224 * (2**32 - 1) + 2**192 + 2**96 - 1

  • $a$ is 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC and

  • $b$ is 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B.

The code also gives the order $N$ of $E(F)$.

It is $N=$0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 .

The curve also comes with a generator, that i will denote by $G$. The $N=$ord below is maybe a prime, at any rate ord * G is E(0). So i would expect that $(E(F),+)$ is isomorphic with the simpler group $(\Bbb Z/N,+)$, a map in one direction being simple, $k\to k*G$.

The following code initializes the data in the above notations in a manner that i understand.

p = 2^224 * (2^32 - 1) + 2^192 + 2^96 - 1
a = ZZ(0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC)
b = ZZ(0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B)

F = GF(p)
E = EllipticCurve(F, [a, b])

ord = ZZ(0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551)

G = E.point( ( ZZ( 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 ),
               ZZ( 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 ) )
R = Zmod(ord)

Now the framework of the OP becomes even harder to understand (and thus also understanding where is the question), since there are some undefined points like Point1 and Point and some expressions that do not make sense like Point1-1 and Point-3. (Furthermore it is a bad idea to try to reproduce an error using sample code involving a randomizer.)

Note: If we have a point like G on the curve E, then in order to take some multiple of it, say k=2020 times, is is enough to compute k*G. It is no need for taking E( k*G ) to make the code even less readable.

The OP introduces now several (random) integers $k$, and the corresponding points $kG$. Unfortunately these integers have complicated variable names, i will use mine. (Just place yourself in an other place to see how complicated it is to use unexplained variable notations to figure out a simple point...)

# we use now a fixed private key, k0, instead of the privkey. 
k0 = 2020
Q0 = k0 * G

# i have no idea what is a malicious generator, so i will use some special k, k1, instead of kprime...
k1 = R(1234567890)
k2 = 1/k1
Q02 = ZZ(k2) * Q    # so it is k2 * Q = k2 * k0 * G

Now where is the problem?

Please define all variables and try to explain in both mathematical and programatical worlds the issue. (Since the error can be in both of them.)


A final note: Asking a question is both work and effective communication. It is work, since the question should come maximally digested. (For instance, just try to reproduce the situation with small values for $p,a,b,N$. If the problem remains, then post it for these values. Then one can also mention the real framework where the problems shows, but not just copy+paste code from a file written for other purposes.) Always consider that the answer will be longer, and try to already cover with the question a fair share of the effort. The question is always a plus for the community, so write it so that it really lasts longer. This applies also in the case of the other post:

https://math.stackexchange.com/questi...

edit flag offensive delete link more

Comments

Big thank you for your answer !!! Problem for me in understanding how to get k0 for f(k2)G=Q=True ? k0 - unknown for me. Because then I use not G as a generator I have invalid point what too mach different then original k. with In your notation I need calculate a k0. How I can calculate k0 with known Q,G and k2 i.e. *k0=f(Q,G,k2) ?? and k0 * G = Q ??? Help me pleeease.

Duglas gravatar imageDuglas ( 2020-08-10 11:35:43 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-08-08 14:01:14 -0600

Seen: 92 times

Last updated: Aug 10