ECC Encryption

Introduction

Elliptic Curve Cryptography (ECC) is a powerful public-key cryptosystem that offers the same level of security as RSA or ElGamal but with much smaller key sizes. Introduced independently by Neal Koblitz and Victor Miller in 1985, ECC is based on the algebraic structure of elliptic curves over finite fields.

Instead of relying on the difficulty of integer factorization (like RSA) or discrete logarithms in multiplicative groups (like ElGamal), ECC uses the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is significantly harder to solve for equivalent key sizes.

What is an Elliptic Curve?

An elliptic curve over a field \( \mathbb{F} \) is defined by the Weierstrass equation:

Where \( a, b \in \mathbb{F} \) and the discriminant \( \Delta = -16(4a^3 + 27b^2) \neq 0 \) (ensures the curve is smooth).

Types of Fields

• Prime fields \( \mathbb{F}_p \) (p large prime)
• Binary fields \( \mathbb{F}_{2^m} \) (less common now)

In practice, we work over finite fields: all arithmetic is done modulo \( p \).

Group Law: Point Addition

The set of points on the curve forms an abelian group under a special addition operation.

Key Operations

Mathematical Example (Small Curve)

Curve: \( y^2 = x^3 + 2x + 3 \mod 17 \)

Point \( P = (5, 1) \):

• \( 1^2 = 1 \)
• \( 5^3 + 2\cdot5 + 3 = 125 + 10 + 3 = 138 \mod 17 = 138 - 8\cdot17 = 138 - 136 = 2 \)
• \( 1^2 \equiv 2 \mod 17 \)? No → Try another.

Valid point: \( P = (1, 6) \)

• \( 6^2 = 36 \mod 17 = 2 \)
• \( 1^3 + 2\cdot1 + 3 = 1 + 2 + 3 = 6 \mod 17 = 6 \)
• \( 2 \neq 6 \)? Wait — let's use a known safe curve.

Standard Example (secp256k1):

Standard Curves (NIST, Brainpool, Curve25519)

Core ECC Algorithms

1. ECDH – Elliptic Curve Diffie-Hellman (Key Exchange)

1. Alice has private \( d_A \), public \( Q_A = d_A \cdot G \)
2. Bob has private \( d_B \), public \( Q_B = d_B \cdot G \)
3. Shared secret: \( K = d_A \cdot Q_B = d_B \cdot Q_A = d_A d_B \cdot G \)

2. ECDSA – Elliptic Curve Digital Signature Algorithm

Sign message \( m \):

1. Hash: \( e = H(m) \)
2. Pick random \( k \)
3. \( R = k \cdot G = (r, y) \), use \( r \)
4. \( s = k^{-1}(e + d \cdot r) \mod n \)
5. Signature: \( (r, s) \)

3. ECIES – Elliptic Curve Integrated Encryption Scheme

Hybrid encryption:

• Use ECDH to derive shared key
• Derive symmetric key via KDF
• Encrypt data with AES-GCM

Pseudocode: ECDH Key Exchange

# Parameters: Curve, base point G, order n
def ecdh_private_key():
    return random.randint(1, n-1)

def ecdh_public_key(d):
    return multiply(G, d)  # Scalar multiplication

# Alice
dA = ecdh_private_key()
QA = ecdh_public_key(dA)

# Bob
dB = ecdh_private_key()
QB = ecdh_public_key(dB)

# Shared secret
K_A = multiply(QB, dA)
K_B = multiply(QA, dB)

assert K_A == K_B

Security & Attacks

Performance Comparison

Applications

• TLS/HTTPS: ECDHE key exchange
• Bitcoin/Ethereum: ECDSA signatures
• Signal, WhatsApp: Curve25519 (X25519)
• SSH, VPNs: ECDH
• IoT: Lightweight ECC

Conclusion

Elliptic Curve Cryptography is the gold standard for modern public-key cryptography. Its efficiency, small key sizes, and strong security make it ideal for mobile devices, IoT, and high-performance systems.

While the math is complex, libraries like openssl, cryptography.io, and libsodium make ECC easy to use securely.

Best Practices:

• Use X25519 for key exchange
• Use Ed25519 for signatures
• Never roll your own crypto
• Always validate public keys

References

1. Koblitz, N. (1987). "Elliptic Curve Cryptosystems"
2. Miller, V. (1985). "Use of Elliptic Curves in Cryptography"
3. NIST FIPS 186-4: Digital Signature Standard
4. SafeCurves