1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
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 <https://copyninja.info/blog/golang_spake2_1.html>`_ 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
<http://andrea.corbellini.name/2015/05/17/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
<http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/>`_
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.
|
