Elliptic Curve Arithmetic

Elliptic curve representations:

• Short Weierstrass: $E:y^2-x^3-Ax-B=0$
• Montgomery: $E:y^2-x^3-A{x}^2-x=0$
• Edward:
• Twisted Edwards:

Elliptic curve

• Affine point: $P:(x,y)$
• Projective point: $P:(x,y,z)$
• Jacobian point:

Negation

Inverse of a point by inverting on x-axis, including the case when $x_1=x_2=0$:

$$-P:(-x,y)$$

Addition

Addition: $P,Q\in E:R=P+Q$ where $x_1\ne x_2$. Using algebraic formula,

Using chord method,

$$\begin{array}{rl}\lambda & =\frac{y_2-y_1}{x_2-x_1}\\ x_3& ={\lambda }^2-x_1-x_2\\ y_3& =\lambda (x_1-x_3)-y_1=\lambda (2x_1+x_2)-{\lambda }^3-y_1\\ R& =(x_3,y_3)\end{array}$$

Cost: $6A+2M+1I$

as human species, we have arrived to the unanimous conclusion that we hate divisions, and will do anything to avoid them.

Doubling

Case where, $P=Q$

Using tangent method, slope of the curve comes out to be:

$$\begin{array}{rl}\lambda & =\frac{3x_1^2+a}{2y_1}\\ x_3& ={\lambda }^2-2x_1\\ y_3& =\lambda (x_1-x_3)-y_1=\lambda (3x_1)-{\lambda }^3-y_1\\ R& =(x_3,y_3)\end{array}$$

Cost: $4A+2M+1I$

Scalar Multiplication

scalar multiplication for elliptic curve refers to multiplication of a scalar value $k\in {\mathbb{F}}_r$ with a point $P\in E$. Three different kinds of scalar mult exists:

• Fixed base: where the point is fixed
• Variable base: where the point can be different
• Double base: multiple points with multiple scalars

Montgomery curve formulae

montgomery curves

List of things and resources to learn

• all different point representations and their advantages/disadvantages.
  • affine
  • projective
  • Jacobian
  • extended jacobian
• different curve representations
  • short weierstrass
  • montgomery
  • edwards
  • twisted edwards
• hash to curve
• constant time operations
• pairings

resources

• axioms’ halo2curves
• pse’s halo2curves
• dalek-cryptography’s ed25519
• martin klepmann’s paper
• lamdaworks’ ec module
• arkworks’ ec modulehttps://github.com/arkworks-rs/algebra/tree/master/ec
• twisted edwards curve
• twisted edwards curve revisted
• montgomery ladder
• pairing friendly ec curves of prime order
• Hyperelliptic database
• ristretto group
• Constant-Time Arithmetic for Safer Cryptography
• constant time montgomery ladder
• Hardware Aspects of Montgomery Modular Multiplication
• Montgomery Multiplication Using Vector Instructions
• Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis
• Faster addition and doubling on elliptic curves
• Montgomery curves and the Montgomery ladder