--- title: "From Coils to Curves - A Primer on Elliptic Curve Cryptography" url: "https://www.bekk.christmas/post/2020/05/from-coils-to-curves-a-primer-on-elliptic-curve-cryptography" authors: ["Tjerand Silde", "Martin Strand"] published: "2020-12-05" updated: "2024-11-07T13:05:28Z" language: "en-US" type: "article" tags: ["Sikkerhet"] --- # From Coils to Curves - A Primer on Elliptic Curve Cryptography Elliptic curves are seemingly ubiquitous in modern cryptographic protocols, and may turn up again later this December. Let’s take this opportunity to gain insight on what they are and why they are used. ## In short Elliptic curve cryptography builds on arithmetic over finite fields and on the geometric point-addition law on curves to create a group where repeated operations are easy to perform but hard to reverse. The article shows how this powers Diffie-Hellman key exchange, why ECC achieves similar security with much smaller key sizes than prime-field methods, and why signatures are needed to prevent man-in-the-middle attacks. - **For:** Developers and security engineers interested in modern cryptography - **Good to know beforehand:** Basic number theory and modular arithmetic _AI-generated_ It is well known that prime numbers are important for cryptography, although it has not always been true. The advent of primes came with several groundbreaking papers almost 50 years ago. Pioneers in introducing asymmetric cryptography, Whit Diffie, Martin Hellman, Ron Rivest, Adi Shamir and Leonard Adleman, used results from number theory to build key agreement, encryption, and signatures. Prime numbers hold a very special position in number theory, and this carried over to cryptography. ## From Primes to Crypto Cryptographic protocols are typically working _modulo_ some prime _p_. This can be likened to turning the number line into a coil, such that 0, _p_, 2_p_, etc. all join at the same place. From then on, whenever we add or multiply the number such that we go beyond _p_, we can simply remove as many multiples of _p_ as necessary until we come between 0 and _p_ again. Now, imagine that we used a composite number instead, for example 12. Then 0 and 12 are "the same" in this situation, but that also means that 3 multiplied by 4 is ... 0! One of the intuitions when working with normal numbers is that if _ab_ = 0, then either _a_ or _b_ would have to be 0. Hence, when using composite numbers, there is simply stuff that no longer works the way we’re used to. Fortunately, this is not the case when using the primes — for instance 7 — as our so-called modulus. ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/336884b909473e311de88e6394517134bac9165f-1600x1091.png) Let’s make a rule, and let’s call it _m_. We take the coil we just made from the number line, and since we can always reduce numbers to below _p_, we label our points on this circle from 0 to _p_-1. Given two points _a_ and _b_ on the circle, we decided that the output of the rule _m_(_a_, _b_) should be the point which is represented by the product _ab_, possibly after reducing modulo _p_. It may look like a very natural rule, but it is nonetheless a rule we just agreed on. If you play around with this rule a bit, you will notice some properties: - If _a_ = 1, then _m_(_a_, _b_) = _b_ (and the other way around). - For any _a_, _b_ not equal to 0, _m_(_a_, _b_) is never zero. So, if we removed 0 from the circle entirely, no harm would happen — the rule would still be well-defined. - For any nonzero _a_, there is always some _b_ such that _m_(_a_, _b_) = 1. These nice properties — together with a property called associativity — are the properties we need to be able to do cryptographic computations. Now focus on a particular number on the circle, and let’s call it _g_. If we take _m_(_g_, _g_), or — to return to the more usual notation — _g²_, we will reach a new point on the circle. We can continue this process and compute _g_³, _g_⁴, etc. At some point, we will reach 1. ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/4cf6e8e3f3d1a12c953d5b7a0bf4cafe3d57f360-986x1029.gif) All the points we have visited in this process are members of the set of numbers _generated_ by _g_, and if the number of points on the coil is a large prime, then we have a very good candidate for doing cryptography, for example Diffie-Hellman key exchange. Let _h_ be some number in this set generated by _g_. That means that _h_ = _g_ᵉ for some exponent _e_. If it is easy to find this _e_ from _g_ and _h_, we would have trouble. Fortunately, it turns out that if we use _large enough_ primes, then this _e_ appears to be very difficult to find. ## From Coils to Curves Coiling up the number line is not the only way of finding suitable primitives for cryptography. Let’s make a new rule. Instead of using a circle like we did in the previous section, we consider the following equation: _y_² = _x_³ + _ax_ + _b_, where _a_ and _b_ are fixed constants. If we graph this in our usual coordinate system, it may look like this curve: ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/889c4158cbb7633ab631a1c33866338ae6cb1311-1600x1091.png) We will now make a rule on how to combine two distinct points _P_ and _Q_ on this curve. The agreed upon notation is to call this rule addition, but we will have to define what we mean by that. Programming languages often include this mental concept as operation overloading. Draw the straight line between _P_ and _Q_. It will intersect at a third point, say, _R_. This could have been a nice candidate for _P_ + _Q_, but since we are making the rules, let’s make this a bit more interesting. Draw a vertical line through _R_. It will intersect the curve on the opposite side of the _x_-axis, and we define this point as _P_ + _Q_. Just as before, this is a rule we’re deciding here and now. However, this also turns out to be a very useful rule, with the same properties as before: - Instead of having the point 1 on the circle, we imagine a point infinitely far up. (Remember what you see when looking at railway tracks: parallel lines actually meet beyond the horizon, at infinity.) So, now the line intersecting _R_ and _P_ + _Q_ is indeed also intersecting a third point: the point at infinity. This can be made precise, but requires maths from algebraic geometry, which is far beyond the scope of this blog post. This point at infinity has all the same properties as 1 had above. - For any point _S_ on the curve, there is always a point _T_ such that we get a line intersecting _S_, _T_ and the point at infinity. This means that for any point _S_, we can find a point we can call -_S_. You can test this rule interactively in a simple [GeoGebra demonstration](https://www.geogebra.org/m/ukhajwzs). ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/cbe159de7cc0e46fef3f388b88702d862852060a-793x653.gif) In this case we assumed that _P_ and _Q_ were distinct. If _P_ = _Q_, then we simply use the tangent to the curve at point _P_ instead, and proceed as before. In particular, take a point _G_, and compute 2_G_ = _G_ + _G_, 3_G_, 4_G_, etc, that is, we add _G_ to itself many times. Eventually, we reach the point at infinity, and then back to _G_, see illustration below. We have now spent about 1000 words of this blog post getting here, just to do the same as we did above (where some fixed number _g_ was multiplied by itself over and over again until we reached 1 modulo _p_), and what was the point? Above, we said that computing exponents are secure if the primes were large enough. It turns out that "large enough" is currently about 3072 bits, or a number with approximately 925 digits. That is somewhat strenuous even for a computer, but the elliptic curve version only requires us to work on numbers of size 256 bits, or 77 digits, which is far more efficient. ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/2ff962169ea652af814d2627f511742c1fb4e7e0-986x1056.gif) ## Elliptic Curve Diffie-Hellman Key-Exchange The Diffie-Hellman key-exchange protocol is widely used today, and its instantiation using elliptic curves is ranked as the best choice in modern cryptographic protocols like TLS and SSH. The protocol is fairly simple. The public information is an elliptic curve _E_ and a generator _G_ for the points on this curve. One party, Alice, samples a random integer _a_ and computes a point _A_ = _a__G_. Another party, Bob, samples a random integer _b_ and computes _B_ = _b__G_. Then they exchange the values _A_ and _B_, and compute the shared key _K_ = _b__A_ = _a__B_ = _a__b__G_. As long as both _a_ and _b_ stay secret, even when an attacker knows _G_, _A_ and _B_, then the key is secure. ![](https://cdn.sanity.io/images/ah2n1vfr/bekk-blogg-prod/3b642f2612ab62dec86a128f9db34652dd85e4c2-1600x970.png) _Reference:_ [_https://asecuritysite.com/encryption/go_x3dh_](https://asecuritysite.com/encryption/go_x3dh)_. Used with permission._ To achieve long-term security, to protect previous messages in the case where someone’s secret keys are leaked after the fact, Alice and Bob can do an ephemeral key-exchange every time they communicate. If _a_ and _A_ is Alice’s long term key pair where _A_ is public to everyone, and similar for Bob, they can run the following protocol to agree upon a one-time session-key. Alice samples a random integer _c_ and computes _C_ = _c__G_, and Bob samples a random integer _d_ and computes _D_ = _d__G_. Then they exchange _C_ and _D_, and compute the shared key as (_a__b_ + _c__d_ )_G_. The interested reader can check out this [simple example written in Go](https://play.golang.org/p/qJBI0_2lsGP). Are you able to extend the basic protocol to the ephemeral key-exchange on behalf of Alice and Bob? We finally point out that this protocol is vulnerable to a man-in-the-middle attack, and we need to also send signatures computed on the messages to ensure that the communication is authentic. Are you able to attack the protocol as described above, when signatures are not used? If you found these problems interesting, we encourage you to check out similar challenges at [cryptohack.org](https://cryptohack.org/challenges/ecc/). ## Common Curves Not all elliptic curves are suitable for cryptography. There could also be power in choosing a curve and the distinguished base point(s). Hence, implementations tend to choose among a small number of well-known curves. The US National Institute of Standards and Technology [maintains a list](https://csrc.nist.gov/publications/detail/fips/186/4/final) of recommended curves; P-256 is perhaps the most popular among these. Among others, there is also the [SafeCurves](https://safecurves.cr.yp.to) collection proposed by Dan Bernstein and Tanja Lange. In particular, their Curve25519 has proven to be a popular choice. Elliptic curve libraries will typically have tailored support for certain curves. ## Relevant resources recommended by the author - [X3DH (Extended Triple Diffie-Hellman) in Go](https://asecuritysite.com/encryption/go_x3dh) - [A Look Into Elliptic Curve Cryptography (ECC) GIF](https://gfycat.com/immaterialcompetentcanine) - [Elliptic Curves challenges on cryptohack.org](https://cryptohack.org/challenges/ecc/) - [Modular Arithmetic: Driven by Inherent Beauty and Human Curiosity](https://www.ias.edu/ideas/2012/taylor-modular-arithmetic) - [What is the math behind elliptic curve cryptography?](https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3) - [Digital Signature Standard (DSS)](https://csrc.nist.gov/publications/detail/fips/186/4/final)