294 lines
8.8 KiB
Markdown
294 lines
8.8 KiB
Markdown
# Elliptic Curves
|
||
|
||
- We’d like to find another type of group and operation in which the discrete logarithm problem is hard
|
||
|
||
$$
|
||
ax^2+by^2=r^2
|
||
$$
|
||
|
||
- There are an infinite number of solutions to this equation
|
||
- However if we restrict to only integers ($\mathbb{Z}$) and use mod, we have a finite set
|
||
|
||
- We define an elliptic curve over points in $\mathbb{Z}_p, \space p>3$
|
||
- Set of all pairs where:
|
||
- $y^2 \equiv x^3 + ax + b \space (mod \space p)$
|
||
- The neutral element is 0
|
||
- One requirement is:
|
||
- $4a^3 + 27b^2 \neq 0 \space (mod \space p)$
|
||
|
||
This is $y^2 \equiv x^3 -3x +3$ over $\mathbb{R}$
|
||
|
||
|
||
|
||
Notice the symmetry about the x axis, this is because we have a $y^2$ term meaning we have two solutions
|
||
|
||
- For a DLP problem, we need a cyclic group
|
||
- Elements within the group
|
||
- A group operation
|
||
- For ECs the elements are points on the curve
|
||
- The operation is point addition
|
||
|
||
#### Point Addition
|
||
|
||
|
||
|
||
#### Point Doubling
|
||
|
||
$P + P = 2P$
|
||
|
||
- Here our line will be tangent to P
|
||
|
||
|
||
|
||
#### Group Laws
|
||
|
||
In elliptic curves, to get $4P$, we can either do $P+3P$ or $2P+2P$
|
||
|
||
##### Group Properties
|
||
|
||
- Closed
|
||
- Any closed addition operation will end up somewhere on the curve
|
||
- Associative
|
||
- The order of calculations doesn’t matter
|
||
|
||
##### Point Addition Equations
|
||
|
||
- We can derive equations for this based on the equation for a line that intersects the curve in three places
|
||
- Given $y^3=x^3+ax+b$ and points:
|
||
- $P=(x_1,y_1)$
|
||
- $Q=(x_2, y_2)$
|
||
- line $y=s\cdot x + m$
|
||
- $(sx+m)^2 = x^3 + ax + b$
|
||
- $s^2x^2 + 2sxm + m^2 = x^3+ax+b$
|
||
- Plugging in $x_1, y_1, x_2, y_2$
|
||
- $P+Q=(x_3, y_3)$
|
||
- $x_3 = s^2 - x_1 - x_2$
|
||
- $y_3 = s(x_1 - x_3) - y_1$
|
||
|
||
$$
|
||
s = \cases{\frac{y_2-y_1}{x_2-x_1} \quad (mod\space p); P\neq Q\\{\frac{3x_1^2+a}{2y_1}}\quad (mod\space p); P=Q}
|
||
$$
|
||
|
||
###### Example
|
||
|
||
$y^2\equiv x^3+2x+2\space (mod \space 17)$
|
||
|
||
$(3,1)+(9,16)$
|
||
|
||
$$
|
||
s=\frac{16-1}{9-3}=\frac{15}{6}=15\cdot 6^{-1} \\
|
||
= 15\cdot 3 \mod{17} \\
|
||
= 11
|
||
$$
|
||
|
||
$$
|
||
x_3=11^2-3-9 \\
|
||
109 \space \mod{17} = 7 \\\\
|
||
y_3 = 11\cdot(3-7)-1=11\cdot 13 \mod{17} = 6 \\
|
||
$$
|
||
|
||
#### Inverses
|
||
|
||
The point reflected in the x axis is the inverse
|
||
|
||
|
||
|
||
#### Neutral Element
|
||
|
||
$P-P=?$
|
||
|
||
$P+?=P$
|
||
|
||
|
||
|
||
These are a pain as they don’t intersect the curve, we say they cross the curve at $\infty$
|
||
|
||
|
||
|
||
#### The Point $\mathcal O$ at Infinity
|
||
|
||
- The point at infinity is the neutral element on an elliptic curve
|
||
- $P+(-P)=\mathcal O$
|
||
- $P+\mathcal O=P$
|
||
- In practice the point doesn’t have coordinates, and can’t be used within the normal formula
|
||
- $P=(x,y)$
|
||
- $-P=(x,-y)$
|
||
- When implementing, you have to detect when the x values are equal and y values are inverses $\mod p$
|
||
- e.g. $(7,6)+(7,11)$
|
||
- $\frac{y_2-y_1}{x_2-x_1}=\frac{-5}{0} = \mathcal O$
|
||
|
||
### Cyclic Groups
|
||
|
||
- The points on an elliptic curve including the neutral element $\mathcal O$ form a cyclic subgroup
|
||
- Under certain conditions all points form a cyclic group
|
||
|
||
|
||
|
||
- Given a curve $E$, a primitive root $P$, and a point $aP$, what is $a$?
|
||
- This is the elliptic curve discrete logarithm problem
|
||
|
||
$$
|
||
aP = \underbrace{P+P+...+P}_{a \space \mathrm {times}}
|
||
$$
|
||
|
||
|
||
|
||
This is the graph modulus $p$
|
||
|
||
- Given a generator point, points on elliptic curves generate cyclic groups
|
||
- $y^2 \equiv x^3+2x+2 \mod 17$
|
||
|
||
- 
|
||
|
||
- Here the next two points are the point at infinity ($\mathcal O$) and then it loops back round to $(5,1)$
|
||
- Each cyclic group includes the point at infinity
|
||
|
||
## Elliptic Curve Discrete Logarithm
|
||
|
||
- We can construct a DLP in a very similar way to the modular exponentiation equivalent
|
||
- $aP = \underbrace{P+P+...+P}_{a \space\textrm{ times}} = A$
|
||
- Given points $P$ and $A$, find scalar value $a$
|
||
- It's important to remember the distinction between points on the curve and integer values
|
||
- On elliptic curves, private keys such as $a$ are integers
|
||
- Generators and public keys are points
|
||
|
||
#### Group Cardinality
|
||
|
||
- The size of cyclic groups is very important to the security
|
||
- While easy to calculate for modular arithmetic, the number of points on a given elliptic curve is not so obvious
|
||
- You might imagine that a curve would have $2p+1$ points, in reality it is fewer than this
|
||
- This is closer to $p$
|
||
- Hasse’s theorem states that for a curve $E$ over a field $\mathbb{Z}_p$, the number of elements $\#E$ is bounded by:
|
||
- $\#E=p+1+\epsilon$
|
||
- where $|\epsilon| \leq 2\sqrt{p}$
|
||
|
||
##### #E
|
||
|
||
- A large #E is very important to prevent various attacks on ECDLP
|
||
- Calculating it exactly is hard; it can be done with Schoof’s algorithm
|
||
- Various properties of #E enable or restrict certain attacks
|
||
|
||
##### How Hard is ECDLP
|
||
|
||
- There are generic algorithms like **Pohlig-Hellman** that are applicable to any category of DLP
|
||
- Pohlig-Hellman requires $O(\sqrt{\#E})$ steps
|
||
- These generic attacks mean curves and parameters should be chosen with care
|
||
- The most powerful attack on modular arithmetic based DLP is **index calculus**
|
||
- It is this attack that forces modular arithmetic based crypto-systems to use >2000 bit keys
|
||
- Index calculus does not work on elliptic curves so they only need to remain secure against generic attacks
|
||
|
||
#### Efficient Computation
|
||
|
||
- There is no natural way of calculating $a\cdot P$
|
||
- Think back to binary exponentiation, square and multiply `->` double and add
|
||
|
||
| Decimal | Binary |
|
||
| ---------------- | ---------------- |
|
||
| $26_{10}\cdot P$ | $11010_2\cdot P$ |
|
||
| $1P$ | $1 \cdot P$ |
|
||
| $2P=1P+1P$ | $10\cdot P$ |
|
||
| $3P=2P+1P$ | $11\cdot P$ |
|
||
| $6P=3P+3P$ | $110\cdot P$ |
|
||
| $12P=6P+6P$ | $1100\cdot P$ |
|
||
| $12P+1P = 13P$ | $1101\cdot P$ |
|
||
| $26P = 13P+13P$ | $11010\cdot P$ |
|
||
|
||
### Elliptic Curve Diffie-Hellman (ECDH)
|
||
|
||
$$
|
||
E, \#E, G \\
|
||
\mathrm{Alice}: a\in \{1,2,...,\#E-1\} \\
|
||
\mathrm{Bob}: a\in \{1,2,...,\#E-1\} \\
|
||
$$
|
||
|
||
Alice takes point $G$ on the curve and adds it to $a$: $A = a\cdot G$
|
||
|
||
Bob does the same: $B=b\cdot G$
|
||
|
||
Alice takes Bob’s public key $k_{ab} = a\cdot B$
|
||
|
||
Bob does the same: $k_{ab}=b\cdot A$
|
||
|
||
$k_{ab} = a\cdot B = a \cdot (b \cdot G)=ab\cdot G$
|
||
|
||
$k_{ab} = b\cdot A = b \cdot (a \cdot G)=ab\cdot G$
|
||
|
||
|
||
|
||
#### EC Structure
|
||
|
||
|
||
|
||
Where each layer builds on the one beneath
|
||
|
||
## Implementation
|
||
|
||
#### Point Compression
|
||
|
||
- Since we know the formula for a given curve, we do not need to transport full $(x,y)$ coordinates
|
||
- Each point contains a unique $x$, and one or two $y$ where
|
||
- $y=\sqrt{x^3 + 2x + 2}\mod p$
|
||
- Most implementations will use the full $x$ value, and append a single bit representing a positive or negative y value
|
||
|
||
#### Projective Coordinates
|
||
|
||
- Some implementations adjust the formula for point addition to use projective coordinates $(x,y,z)$ rather than $(x,y)$
|
||
- The curve sits on the plane $z=1$
|
||
- Points at infinity $\mathcal O = (0,1,0)$
|
||
|
||
**Why?**
|
||
|
||
- Point addition in this system does not require a multiplicative inverse
|
||
|
||
#### Standard Curves
|
||
|
||
- The choice of curve parameters influences both security and efficiency of crypto-systems based around ECs
|
||
- Never use a randomly generated curve!
|
||
- The chances are the number of points we generate will have a subgroup susceptible to Pohlig-Hellman
|
||
- Standard curves exist in various forms
|
||
- Varied equations
|
||
- Different implementation methods
|
||
- Different choices of prime
|
||
|
||
##### P-256
|
||
|
||
- Weierstrass curve $y^2\equiv x^3+ax+b\mod p$
|
||
- Very widely used
|
||
- One of the few curves in `TLS1.3` and NSA Suite B
|
||
|
||
|
||
|
||
- $h$ is the cofactor, the size of the subgroup in $G$
|
||
- Because it's 1 it means all the points are being generated
|
||
- If it was 2, only half of the points are being generated
|
||
|
||
##### secp256k1
|
||
|
||
- Koblitz curve $y^2\equiv x^3+7\mod p$
|
||
- Underpins Bitcoin digital signatures
|
||
|
||
|
||
|
||
##### Curve25519
|
||
|
||
- Montgomery curve $y^2\equiv x^3 + 486662x^2+x\mod p$
|
||
- Primary alternative to `P-256`
|
||
- In `TLS1.3` and numerous other protocols
|
||
- The nature of this curve allows efficient multiplication using a Montgomery ladder, using only $X$ and $Z$
|
||
- This algorithm can compute numbers in constant time
|
||
|
||
|
||
|
||
##### Curve448-Goldilocks
|
||
|
||
- Untwisted Edwards Curve $y^2+x^2\equiv 1 - 39081x^2y^2\mod p$
|
||
- 448 bit curve
|
||
- Primarily used within digital signatures as part of `Ed448`
|
||
- Edwards curve arithmetic mod this “goldilocks” prime is very efficient
|
||
|
||
#### Primary Applications
|
||
|
||
- Elliptic Curve Diffie Hellman
|
||
- DSA signature scheme, based on Elgamal signatures
|
||
- Similar schemes involving the alternative curves such as `Ed25519` and `Ed448`
|