SPAKE2 In Golang: Elliptic Curves Primer ######################################## :date: 2018-07-28 13:22 +0530 :slug: golang_spake2_2 :tags: go, golang, spake2, cryptography, ecc :author: copyninja :summary: Second post in series SPAKE2 in Golang, my notes on Elliptic curves and groups .. TLDR; this post is going to be too long and mostly theoretical. Actual Golang related posts will be may 2 or 3 posts later. In my `previous post `_ I talked about starting of my new adventure to write a cryptographic library and how I tried to brute force to solve problem without knowing basics. In this post I'll talk about my learning of *Elliptic Curves and their Groups*. This post is just my notes and I'm not trying to explain all basics or mathematics behind the Elliptic curves. Ramakrishnan gave me a good article to start with Elliptic curves. Its a series of posts by *Andrea Corbellini*, which starts with `Elliptic Curve Cryptography: A Gentle Introduction `_. These posts gave me a great deal of understanding about elliptic curves and how elliptic curve cryptography works, and why its faster. If you want to learn about elliptic curve I highly recommend you to go through the series. Elliptic Curves =============== Elliptic curves are set of points described by equation .. math:: y^2 = x^3 + ax + b where `a` and `b` are the coefficients which needs to satisfy :math:`4a^3 + 27b^2 \neq 0`. This form of equation is called *Weirstrass normal form of elliptic curves*. Along with normal point there is also point on curve which is considered ideal point and is *point at infinity*; it is denoted by symbol 0. So considering point at infinity we can define elliptic curve as .. math:: \{(x,y) \in \mathbb R ^2 | y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0 \} \cup \{0\} Groups ====== Before going to Elliptic curve groups we need to know what are groups. I now remembered my academics where I had studied about groups and number theory in general. That time never knew where exactly it was useful. And I should really say learning something without knowing its application is really difficult. Moving on to the groups, A group in mathematics is basically a set for which there is a binary operation which is called as *"addition"* and idicated with + symbol. In order for set :math:`\mathbb G` the binary operation must be defined so that it has following properties. 1. **closure**: if `a` and `b` are members of of :math:`\mathbb G` then :math:`a + b` is also member of :math:`\mathbb G`. 2. **associativity**: :math:`(a + b) + c = a + (b + c);` 3. there exists an **identity element** 0 such that :math:`a + 0 = 0 + a = a;` 4. Every element has a inverse, that is for every `a` there exists `b` such that :math:`a + b = 0` For a group to be Abelian there is a 5th rule. 5. **commutativity**: :math:`a + b = b + a` If a group satisfies we get some additional property such that **unique identity element** and **unique inverse element** which is very important for cryptography. Elliptic Curve Groups --------------------- Similar to number groups we defined above, its possible to have group over elliptic curves. Following are the property or rule for a Elliptic curve groups. 1. Elements of the groups are point on elliptic curve; 2. the **identity element** is the point at infinity; yes the one we described above while defining elliptic curves. 3. the **inverse** of a point :math:`\mathrm R` is the one symmetric on `x-axis`. i.e. if point is :math:`(x,y)` then inverse of the point is :math:`(x, -y)` 4. **adition** is given by the rules: **given three aligned, non-zero points,** :math:`\mathrm P,Q` **and** :math:`\mathrm R` **their sum is** :math:`P + Q + R = 0`. This means the line through the 3 point passes through the point at infinity. 5. For addition we want 3 points to be aligned and does not require any specific order which means :math:`P + (Q + R) = Q + (P + R) = R + (P + Q) = ... = 0` that is **our + operator is both associative and commutative** By point 5 we conclude that Elliptic curve groups are *Abelian*. Algebraic Addition ------------------ Since we know :math:`P + Q + R = 0` we can say :math:`P + Q = -R`. This means we draw a line on elliptic curve which passes through point `P` and `Q` it intersects the curve at 3rd point `R`. Inverse of point `R` is `-R` and is the result of addition of 2 points `P` and `Q`. This is easy geometrically but for computers we need to represent this with algebraic notation. This is where the *slope of line* comes to picture, another academic topic which I learnt without actually knowing its real world application. So considering point `P` as :math:`(x_P,y_P)` and `Q` as :math:`(x_Q, y_Q)` we can calculate slope of line going from `P` to `Q` as follows .. math:: m = \frac{y_P - y_Q}{x_P - x_Q} And in a special case where :math:`P = Q` formula is slightly different .. math:: m = \frac{3x_P^2 + a}{2y_P} Intersection of this line with curve is point `R` :math:`(x_R,y_R)` and point :math:`x_R` and :math:`y_R` are calculated using following formula. .. math:: x_R = m^2 - x_P - x_Q y_R = \begin{cases} y_P + m(x_R - x_P), & \text{or} \\ y_Q + m(x_R - x_Q) \end{cases} I've not mentioned about special cases of elliptic curve additions which is explained in `Andrea Corbellini `_ blog. Please refer for more mathematical oriented explanation. Scalar Multiplication --------------------- One more important operation we do with elliptic curve group is scalar multiplication. Let's say we want to calculate :math:`nP`. Scalar multiplication can be defined in terms of addition as shown below .. math:: nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}} This property is what makes elliptic curves attractive and faster than the normal integer groups where scalar multiplication is actually exponentiation operation. Given `n` and `P` we can easily cacluate :math:`Q = nP` but given `Q` and `P` there is no *easy* way to find `n` especially when numbers are big. This is the *"hard"* problem or the *discrete logarithm problem* which makes cryptography work.