Elliptic Curve Cryptosystems

Cyclic Groups

• Each group includes the point at infinity

Points vs Integers

• 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 (x,y)

Group Cardinality

• 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
• Might imagine that a curve would have $2p+1$ points, in reality it is fewer than this
• Hasse's theorem states that for a curve $E$ over a field $\Z_p$ the number of elements #E is bounded by....

#E

• Large #E is very important to prevent various attacks on ECDLP
• Calculating it exactly is hard, it can be done with Shoofs algorithm
• Various properties of #E enable or restrict certain attacks

How hard is ECDLP

• GA like Pollards Rho and Pohlig-Hellman that are applicable to any category of DLP
• These generic attacks mean curves and parameters should be chosen with care
• Most powerful attack on modular arithmetic based DLP is Index Calculus. Modern cryptosystems must use >2000 bit keys
• Index calculus does not work on Elliptic Curves, so they need to remain secure against generic attacks

Efficient Computation

• No natural way of calculating $a\times P$

EC Structure
ECDH/ECDSA
Scalar Multiplication
Point Addition/Doubling
GF(p)

Implementation

Point Compression

• Do not need to transport full (x,y) coords as know the formula
• Each point contains a unique $x$, and one of two $y$ values where ...
• 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 to point addition to use projective coordinates (x,y,z) rather than (x,y)
• Curve sits on the plane $z=1$
• Point at infinity O=(0,1,0)

Standard Curves

• Choice of curve parameters influence both security and efficiency of cryptosystems based around ECs
• Never use a randomly generated curve
• Standard curves exist in various forms
  • Varied equations
  • Different implementation methods
  • Different choices of prime