# DH Elliptic Curves: Why choose a fixed base point?

I am having a first look at the TLS key exchange using Diffie Hellman and try to understand the Elliptic Curve variant of it.

So if a client and a server agree on using ECDH for key exchange and they use the secp256r1 curve, it seems like the base point G is given and they take it from the standard (04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE33576B315ECE CBB64068 37BF51F5)

From my understanding, i could use an arbitrary base point G and obtain a group which i can use for my key-exchange. Whats the advantage of using a fixed one? Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

To me it seems more intuite that picking a new base point G every time would increase security. But as far as i understand it, it's not whats done in TLS. Can anyone tell why we pick a fixed base point instead of generating a new one for each key-exchange?

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

If you could create such a rainbow table that allows you to compute discrete logs of random values to a base $$G$$ with nontrivial probability $$p$$, then you can solve the discrete log to any base (with work that takes an expected $$O(1/p)$$ time.

Here's how it works:

• You're given the point $$H$$ and $$J$$, and want to compute the discrete log of $$J$$ to base have $$H$$, that is, the value $$x$$ s.t. $$xH = J$$

• First step, compute the discrete log of $$H$$ to the base $$G$$, that is, the value $$y$$ s.t. $$yG = H$$. What you do is pick random values $$r$$, compute $$rH$$, and use your rainbow table to find try to find the discrete log $$y'$$ of $$rH$$. This takes an expected $$1/p$$ attempts (because $$rH$$ is a random point), and one we stumble on an $$r$$ that works, we have $$y = r^{-1}y'$$

• Second step, use the same procedure to compute the discrete log $$z$$ of $$J$$ to the base $$G$$; again, this takes an expected $$1/p$$ attempts.

• Third step is easy; $$x = y^{-1}z$$; we're done; that works because $$yH=G$$ hence $$H = y^{-1}G$$, and $$J = zG$$, hence $$J = z(y^{-1})H$$

On the other hand, for any curve we believe is secure, creating such a rainbow table is infeasible; if the order of the curve is $$n$$, then the creation would take at least $$pn$$ point multiplications; for all practical purposes, the standard discrete log algorithms that take $$O(\sqrt{n})$$ time are more feasible.

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

In addition to having the same security, it turns out that, if we know $$G$$ in advance, we can compute $$rG$$ considerably faster; hence it makes the system faster for the honest parties, and just as secure.

• Just to be sure: are you alluding to pre-computation (NAF) in that final sentence, right? – Maarten Bodewes Sep 13 at 18:22
• @MaartenBodewes: there are a lot of various precomputation strategies – poncho Sep 14 at 6:28