Draft:Elliptic Curves in Cryptography

1. Elliptic Curves in Cryptography

• • Elliptic curve cryptography** (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (such as RSA) to provide equivalent security.

Elliptic curves are applicable for key agreement, digital signatures, pseudo-random generators and other tasks. They are also used in several integer factorization algorithms that have applications in cryptography, such as Lenstra elliptic-curve factorization.

1. 1. Definition and Properties

1. 1. 1. Mathematical Definition

An elliptic curve \[E\] over a field \[K\] can be defined by the Weierstrass equation:

\[E: y^2 = x^3 + ax + b\]

where \[a, b \in K\] are constants such that \[\Delta = -16(4a^3 + 27b^2) \neq 0\] (this ensures that the curve is non-singular).

When the characteristic of \[K\] is neither 2 nor 3, the curve can be given by the simplified Weierstrass equation:

\[E: y^2 = x^3 + ax + b\]

with the discriminant condition \[\Delta = -16(4a^3 + 27b^2) \neq 0\].

1. 1. 1. Group Law

The set of points on an elliptic curve, together with a special point at infinity \[\mathcal{O}\], forms an abelian group with the following addition operation:

Given two points \[P = (x_1, y_1)\] and \[Q = (x_2, y_2)\] on an elliptic curve \[E\], their sum \[P + Q = (x_3, y_3)\] is determined as follows:

1. If \[x_1 = x_2\] and \[y_1 = -y_2\], then \[P + Q = \mathcal{O}\] 2. Otherwise:

  - If \[P \neq Q\], the slope of the line through \[P\] and \[Q\] is \[m = \frac{y_2 - y_1}{x_2 - x_1}\]
  - If \[P = Q\], the slope of the tangent line at \[P\] is \[m = \frac{3x_1^2 + a}{2y_1}\]

Then: \[x_3 = m^2 - x_1 - x_2\] \[y_3 = m(x_1 - x_3) - y_1\]

1. 1. 1. Elliptic Curves over Finite Fields

For cryptographic applications, elliptic curves are typically defined over finite fields. The two most common cases are:

1. **Prime fields** \[\mathbb{F}_p\], where \[p\] is a large prime 2. **Binary fields** \[\mathbb{F}_{2^m}\], which are extension fields of \[\mathbb{F}_2\]

The security of elliptic curve cryptography depends on the difficulty of the **Elliptic Curve Discrete Logarithm Problem (ECDLP)**: Given points \[P\] and \[Q = kP\] on an elliptic curve, find the integer \[k\].

1. 1. Cryptographic Applications

1. 1. 1. Key Generation

The process of generating a public-private key pair in ECC involves:

1. Select an elliptic curve \[E\] defined over a finite field and a base point \[G \in E\] of order \[n\] 2. Select a random integer \[d \in [1, n-1]\] as the private key 3. Compute \[Q = dG\] as the public key

1. 1. 1. Elliptic Curve Diffie-Hellman (ECDH)

ECDH is a key agreement protocol that allows two parties to establish a shared secret over an insecure channel:

1. Alice generates key pair \[(d_A, Q_A = d_A G)]\] 2. Bob generates key pair \[(d_B, Q_B = d_B G)]\] 3. Alice computes \[S = d_A Q_B = d_A d_B G\] 4. Bob computes \[S = d_B Q_A = d_B d_A G\] 5. Both arrive at the same point \[S\], which serves as the shared secret

1. 1. 1. Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA is a variant of the Digital Signature Algorithm (DSA) that uses elliptic curve cryptography:

• • Signing process**:

1. Select a cryptographically secure random integer \[k \in [1, n-1]\] 2. Compute \[R = kG\] and let \[r\] be the x-coordinate of \[R\] modulo \[n\] 3. Compute \[s = k^{-1}(z + rd) \mod n\], where \[z\] is the leftmost bits of the hash of the message 4. The signature is the pair \[(r,s)\]

• • Verification process**:

1. Compute \[u_1 = zs^{-1} \mod n\] and \[u_2 = rs^{-1} \mod n\] 2. Compute \[R' = u_1G + u_2Q_A\] 3. The signature is valid if the x-coordinate of \[R'\] modulo \[n\] equals \[r\]

1. 1. Standard Curves

Several standardized elliptic curves are commonly used in cryptographic applications:

1. 1. 1. NIST Curves

The National Institute of Standards and Technology (NIST) has standardized the following elliptic curves for use in cryptography:

| Curve | Field Size | Security Level (bits) | |-------|------------|----------------------| | P-256 | 256 | 128 | | P-384 | 384 | 192 | | P-521 | 521 | 256 |

1. 1. 1. Curve25519

Curve25519 is a Montgomery curve designed by Daniel J. Bernstein that offers: - 128-bit security level - Efficient implementation - Resistance against various side-channel attacks - Simple validation rules

The equation for Curve25519 is: \[y^2 = x^3 + 486662x^2 + x \mod 2^{255} - 19\]

1. 1. 1. Brainpool Curves

The Brainpool curves are a set of elliptic curves developed by the Brainpool consortium that provide: - Verifiably random parameters - Various security levels (160, 192, 224, 256, 320, 384, and 512 bits) - Resistance against special-purpose attacks

1. 1. Security Considerations

1. 1. 1. Curve Selection Criteria

When selecting an elliptic curve for cryptographic applications, several factors should be considered:

1. **Field size**: Larger fields provide higher security but require more computational resources 2. **Resistance to known attacks**: The curve should resist MOV/FR reduction, Smart's attack, etc. 3. **Efficient implementation**: The curve should allow for efficient point multiplication 4. **Domain parameters generation**: Verifiably random or rigid parameters may be preferred

1. 1. 1. Known Attacks

Several attacks against elliptic curve cryptosystems have been developed:

1. **Pohlig-Hellman algorithm**: Effective when the order of the base point has small factors 2. **Baby-step giant-step and Pollard's rho algorithms**: Generic discrete logarithm algorithms 3. **MOV/FR attack**: Reduces ECDLP to DLP in a finite field using Weil or Tate pairings 4. **Invalid curve attacks**: Exploits implementations that don't validate that points lie on the curve 5. **Side-channel attacks**: Exploits information leaked during computation (timing, power consumption, etc.)

1. 1. Implementation Aspects

1. 1. 1. Point Representation

Several forms exist for representing points on elliptic curves:

1. **Affine coordinates**: Points represented as \[(x,y)\] 2. **Projective coordinates**: Points represented as \[(X:Y:Z)\] where \[x=X/Z\] and \[y=Y/Z\] 3. **Jacobian coordinates**: Points represented as \[(X:Y:Z)\] where \[x=X/Z^2\] and \[y=Y/Z^3\] 4. **Montgomery form**: Enables efficient scalar multiplication using only the x-coordinate

1. 1. 1. Efficient Scalar Multiplication

Scalar multiplication \[kP\] is the core operation in ECC and can be optimized using:

1. **Double-and-add algorithm**: The basic method based on binary representation of \[k\] 2. **Montgomery ladder**: Provides resistance against simple power analysis attacks 3. **Window methods**: Process multiple bits of \[k\] at once 4. **Comb methods**: Precompute multiples of \[P\] for faster computation

1. 1. Applications in Modern Cryptography

Elliptic curve cryptography is widely used in various applications:

1. **TLS/SSL**: Securing web communications 2. **Bitcoin and other cryptocurrencies**: For digital signatures 3. **Secure messaging applications**: Signal, WhatsApp, etc. 4. **Smart cards and embedded systems**: Due to smaller key sizes and computational efficiency 5. **Internet of Things (IoT) devices**: Where computational resources are limited

1. 1. Historical Development

The use of elliptic curves in cryptography was independently proposed by Neal Koblitz and Victor S. Miller in 1985. However, ECC only gained widespread adoption in the early 2000s due to:

1. Increased computational power making RSA with large key sizes less practical 2. Resource constraints in mobile and embedded devices 3. Concerns about quantum computing threats to traditional public-key systems

1. 1. See Also

• Public-key cryptography
• RSA (cryptosystem)
• Discrete logarithm
• Finite field
• Quantum cryptography

1. 1. References

1. Koblitz, N. (1987). "Elliptic curve cryptosystems". Mathematics of Computation. 48 (177): 203–209. 2. Miller, V. S. (1985). "Use of elliptic curves in cryptography". CRYPTO. Lecture Notes in Computer Science. 218: 417–426. 3. Hankerson, D.; Menezes, A.; Vanstone, S. (2004). "Guide to Elliptic Curve Cryptography". Springer Professional Computing. 4. Bernstein, D. J.; Lange, T. (2007). "Faster addition and doubling on elliptic curves". ASIACRYPT. Lecture Notes in Computer Science. 4833: 29–50. 5. Johnson, D.; Menezes, A.; Vanstone, S. (2001). "The Elliptic Curve Digital Signature Algorithm (ECDSA)". International Journal of Information Security. 1 (1): 36–63. 6. Bernstein, D. J. (2006). "Curve25519: New Diffie-Hellman Speed Records". Public Key Cryptography. Lecture Notes in Computer Science. 3958: 207–228. 7. Certicom Research (2000). "SEC 2: Recommended Elliptic Curve Domain Parameters". Standards for Efficient Cryptography. 8. National Institute of Standards and Technology (2013). "Digital Signature Standard (DSS)". FIPS PUB 186-4.

1. 1. External Links

• [Certicom ECC Tutorial](https://www.certicom.com/content/certicom/en/ecc-tutorial.html)
• [SafeCurves: Choosing safe curves for elliptic-curve cryptography](https://safecurves.cr.yp.to/)
• [ECC on Cryptography Stack Exchange](https://crypto.stackexchange.com/questions/tagged/elliptic-curves)