After completing this tutorial, you should be able to:
Elliptic Curve Cryptography (ECC) is a modern public-key cryptographic system that provides the same security as traditional systems (like RSA and classical Diffie-Hellman) but with significantly smaller key sizes. This efficiency makes ECC particularly attractive for constrained environments such as mobile devices, embedded systems, IoT devices, and smart cards, where computational power, memory, and bandwidth are limited.
ECC was independently proposed by Neal Koblitz and Victor S. Miller in 1985. It leverages the algebraic structure of elliptic curves over finite fields. The security of ECC is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is believed to be computationally harder than the integer factorization problem (used by RSA) or the finite field discrete logarithm problem (used by classical DH).
In this tutorial, we explore the mathematics and cryptographic applications of elliptic curves. We begin by defining elliptic curves and their group law (point addition and doubling). We then extend these concepts to finite fields and discuss scalar multiplication. We introduce the ECDLP and explain why it underpins ECC security. We then examine the major ECC protocols: ECDH (key exchange), ECDSA (digital signatures), and ECIES (encryption).
We compare ECC with RSA and classical DH, demonstrating the advantages of smaller key sizes and improved performance. We review standardized curves, including NIST P-256, Curve25519, and secp256k1, and discuss their use in real-world protocols such as TLS 1.3, SSH, Bitcoin, and WireGuard. Finally, we consider implementation considerations and security pitfalls.
In Tutorial 2.11, we introduced public-key cryptography. Tutorial 2.12 covered RSA, and Tutorial 2.13 covered Diffie-Hellman. This tutorial introduces ECC, which provides the same services (key exchange, signatures, encryption) as RSA and DH but with better efficiency. Tutorial 2.15 will cover digital signatures and PKI in more detail, building on the ECDSA foundation established here.
Elliptic curves have been studied in number theory for over a century, but their application to cryptography is relatively recent:
Today, ECC is the preferred public-key cryptography for many applications due to its efficiency and strong security properties.
y² = x³ + a·x + b
where a, b ∈ K and the discriminant Δ = −16(4a³ + 27b²) ≠ 0 (to ensure the curve has no singular points).For real numbers, an elliptic curve is a smooth, cubic curve. The graph of y² = x³ + a·x + b has a characteristic shape:
Figure 1: An elliptic curve over the real numbers (y² = x³ + ax + b).
The set of points on an elliptic curve, together with the point at infinity O, forms an abelian group with:
For cryptography, elliptic curves are defined over finite fields rather than real numbers. This ensures that the points form a finite set, making the discrete logarithm problem computationally hard.
Two types of finite fields are commonly used:
Where p is a large prime. The curve equation is:
y² ≡ x³ + a·x + b (mod p)
with a, b ∈ GF(p) and discriminant ≠ 0 mod p. The points are pairs (x, y) ∈ GF(p) × GF(p) that satisfy the equation, plus the point at infinity O.
Where m is a positive integer. The curve equation is:
y² + x·y = x³ + a·x² + b
Binary fields are less common in modern applications due to security concerns and performance issues on many platforms. Prime fields are preferred.
Example: Consider the curve y² = x³ + 2x + 3 over GF(5). The points are:
Total points: (1,1), (1,4), (2,0), (3,1), (3,4), (4,0), plus O = 7 points.
The group operation on elliptic curves can be defined geometrically or algebraically. For cryptographic implementations, we use algebraic formulas.
For P = (x₁, y₁) and Q = (x₂, y₂) with P ≠ Q and P ≠ −Q:
λ = (y₂ − y₁) / (x₂ − x₁) x₃ = λ² − x₁ − x₂ y₃ = λ·(x₁ − x₃) − y₁
P + Q = (x₃, y₃)
For P = (x₁, y₁) with y₁ ≠ 0:
λ = (3x₁² + a) / (2y₁) x₃ = λ² − 2x₁ y₃ = λ·(x₁ − x₃) − y₁
2P = (x₃, y₃)
Scalar multiplication is the operation of adding a point P to itself k times:
[k]P = P + P + ... + P (k times)
This is the ECC analog of modular exponentiation in RSA/DH. Efficient scalar multiplication is critical for ECC performance. The standard method is the double-and-add algorithm (similar to square-and-multiply).
The complexity of scalar multiplication is O(log k) point operations, making it efficient even for large k.
The ECDLP is believed to be computationally hard for carefully chosen curves. The best known algorithms (Pollard's rho, baby-step giant-step) have exponential complexity, O(√n) group operations. For a 256-bit curve (n ≈ 2²⁵⁶), this is approximately 2¹²⁸ operations, which is infeasible with current technology.
Why ECDLP is harder than DLP in finite fields: The finite field DLP has subexponential algorithms (index calculus), while the ECDLP has no known subexponential algorithm for well-chosen curves. This allows ECC to use much smaller key sizes for the same security level.
ECC key generation is simple and efficient:
The security of ECC relies on the fact that given Q and P, it is infeasible to find d (the ECDLP).
ECDH is the elliptic curve version of Diffie-Hellman. It allows two parties to establish a shared secret over an insecure channel.
The shared secret S is a point on the curve. The x-coordinate (or the full point) is passed through a key derivation function to produce a symmetric key.
When ephemeral keys are used for each session, ECDH provides perfect forward secrecy (PFS). This is the standard in TLS 1.3 and other modern protocols.
ECDSA is the elliptic curve version of the Digital Signature Algorithm (DSA). It provides authentication and non-repudiation.
ECIES (Elliptic Curve Integrated Encryption Scheme) is a hybrid encryption scheme that uses ECC for key exchange and a symmetric cipher for confidentiality.
ECIES is secure and efficient, but it is less commonly used than ECDH (for key exchange) and ECDSA (for signatures).
| Security Level (bits) | RSA Key Size | ECC Key Size | Ratio |
|---|---|---|---|
| 80 | 1024 | 160 | 6.4x |
| 112 | 2048 | 224 | 9.1x |
| 128 | 3072 | 256 | 12x |
| 192 | 7680 | 384 | 20x |
| 256 | 15360 | 512 | 30x |
| Curve | Field | Key Size (bits) | Security (bits) | Applications |
|---|---|---|---|---|
| NIST P-256 | GF(p) | 256 | 128 | TLS, SSH, U.S. government |
| NIST P-384 | GF(p) | 384 | 192 | High-security applications |
| NIST P-521 | GF(p) | 521 | 256 | Very high security |
| Curve25519 | GF(p) | 255 | 128 | TLS 1.3, SSH, WireGuard |
| Ed25519 | GF(p) | 255 | 128 | Signatures (EdDSA) |
| secp256k1 | GF(p) | 256 | 128 | Bitcoin, Ethereum |
| Curve448 | GF(p) | 448 | 224 | High-security TLS |
NIST standardized 15 elliptic curves (P-192, P-224, P-256, P-384, P-521, and binary curves). P-256 is the most commonly used prime-field curve.
Designed by Daniel J. Bernstein, Curve25519 and Ed25519 are modern, highly secure curves optimized for performance. They avoid many of the pitfalls of older curves (e.g., they are designed to be resistant to side-channel attacks and have simple, constant-time implementations).
The Standards for Efficient Cryptography Group (SECG) defined the secp* and sect* curves. secp256k1 is the curve used in Bitcoin.
When receiving a point, always verify that it is on the curve (i.e., satisfies y² = x³ + ax + b) and that it is not the point at infinity unless expected. This prevents invalid curve attacks.
ECC operations must be constant-time to prevent timing and power analysis attacks. All scalar multiplication, point addition, and field operations should run in constant time.
Private keys and ephemeral nonces must be generated using a cryptographically secure random number generator. In ECDSA, nonce reuse is catastrophic.
Use RFC 6979 (Deterministic ECDSA) to generate k from the message and the private key using a KDF. This avoids the need for a random number generator for signatures.
Private keys must be stored securely, preferably in a hardware security module (HSM) or secure enclave.
TLS 1.3 mandates ECDHE for key exchange (with P-256, P-384, X25519). It also uses Ed25519 signatures for some certificate types.
SSH supports ECDH (with NIST curves and Curve25519) and ECDSA for host and user authentication.
Bitcoin uses secp256k1 with ECDSA for transaction signing. Ethereum also uses secp256k1.
WireGuard uses Curve25519 (X25519) for key exchange and BLAKE2 for hashing.
ECDSA and EdDSA are used for code signing, document signing, and certificate signing.
ECC's small key sizes and low power consumption make it ideal for constrained devices.
GPG supports ECDH and ECDSA for email encryption and signing.
In 2010, hackers recovered the ECDSA private key used by Sony to sign PlayStation 3 software. The attack exploited the reuse of the ephemeral nonce k in ECDSA signatures. By having two signatures with the same k, the private key could be recovered using basic algebra. This allowed unauthorized software to run on the PS3.
Lesson: Nonce reuse in ECDSA is catastrophic. Use deterministic ECDSA (RFC 6979) or ensure perfect randomness for each signature.
Bitcoin uses the secp256k1 curve for ECDSA signatures. The curve was chosen for its efficiency and security properties. However, in 2013, a vulnerability was discovered in Android's random number generator that caused nonce reuse, leading to the theft of Bitcoin. This highlighted the importance of secure randomness in ECDSA.
The NSA adopted ECC (Suite B) for U.S. government classified communications. Suite B mandated ECDH for key exchange and ECDSA for signatures, with P-256 and P-384 curves. This endorsement helped drive ECC adoption in industry.
TLS 1.3's mandate for ECDHE with forward secrecy, and the inclusion of X25519 and Ed25519, has made ECC the dominant public-key cryptography in modern web communications. Over 90% of TLS 1.3 connections use ECC.
Consider E: y² = x³ + x + 1 over GF(7). P = (0, 1), Q = (1, 4). Compute P + Q and 2P.
P = (0, 1), Q = (1, 4).
λ = (4 − 1) / (1 − 0) = 3 / 1 = 3 mod 7.
x₃ = 3² − 0 − 1 = 9 − 1 = 8 ≡ 1 mod 7.
y₃ = 3·(0 − 1) − 1 = 3·(−1) − 1 = −3 − 1 = −4 ≡ 3 mod 7.
P + Q = (1, 3).
2P: λ = (3·0² + 1) / (2·1) = 1 / 2 = 1 · 4 = 4 mod 7.
x₃ = 4² − 2·0 = 16 ≡ 2 mod 7.
y₃ = 4·(0 − 2) − 1 = 4·(−2) − 1 = −8 − 1 = −9 ≡ 5 mod 7.
2P = (2, 5).
Using the curve from Exercise 1, compute [3]P where P = (0, 1).
From Exercise 1, 2P = (2, 5).
3P = 2P + P = (2, 5) + (0, 1).
λ = (1 − 5) / (0 − 2) = (−4) / (−2) = 4 / 2 = 4 · 4 = 16 ≡ 2 mod 7.
x₃ = 2² − 2 − 0 = 4 − 2 = 2 mod 7.
y₃ = 2·(2 − 2) − 5 = 0 − 5 = −5 ≡ 2 mod 7.
[3]P = (2, 2).
Using E: y² = x³ + 2x + 3 over GF(5) with P = (1, 1). Alice's private key is dA = 2, Bob's private key is dB = 4. Compute the public keys and the shared secret.
QA = [2]P = (3, 4) (from earlier example).
QB = [4]P = [2](2P) = [2](3, 4) = (2, 0) (from earlier).
Shared secret S = [dA]QB = [2](2, 0) = (3, 4).
Alternatively, S = [dB]QA = [4](3, 4) = (3, 4).
Shared secret: (3, 4).
What is the ratio of RSA key size to ECC key size for 128-bit security? (RSA: 3072 bits, ECC: 256 bits)
Ratio = 3072 / 256 = 12. ECC keys are 12× smaller than RSA keys for the same security level.
If an attacker obtains two ECDSA signatures (r, s₁) and (r, s₂) with the same ephemeral key k, show how the private key d can be recovered. (Assume hash values h₁ and h₂ are known.)
Given s₁ = k⁻¹(h₁ + d·r) mod n and s₂ = k⁻¹(h₂ + d·r) mod n.
Subtract: s₁ − s₂ = k⁻¹(h₁ − h₂) mod n.
Thus k = (h₁ − h₂) / (s₁ − s₂) mod n.
Then d = (s₁·k − h₁) / r mod n.
This shows how nonce reuse allows recovery of the private key.
Write a 500-word report on the ECDLP. Include:
Complete answer would define the ECDLP, describe Pollard's rho (O(√n) complexity) and baby-step giant-step, explain that no subexponential algorithm is known for well-chosen curves, and discuss how curves with anomalies, small subgroups, or weak fields are vulnerable.
Research and compare the performance of ECC and RSA in a real-world application. Address:
Complete answer would include benchmarks showing ECC is faster for key generation and signing, while RSA is often faster for signature verification. ECC consumes less memory and bandwidth. ECC is preferred in constrained environments; RSA is still used in many legacy systems.
Research how ECC is implemented in a specific library (e.g., OpenSSL, libsodium, Bouncy Castle). Write a report addressing:
Complete answer would discuss OpenSSL's support for NIST curves, Curve25519, and Ed25519; its use of Montgomery ladder for constant-time scalar multiplication; blinding; and past vulnerabilities like the cache timing attack on ECDSA.
Design a secure communication protocol using ECDH and a symmetric cipher. Specify:
Complete answer would describe a protocol similar to TLS with ECDHE: parties exchange ephemeral public keys, sign them with their long-term keys (certificates), compute the shared secret, derive keys using a KDF, and use a symmetric cipher (e.g., AES-GCM) for encryption.
Implement point addition, point doubling, and scalar multiplication for a small elliptic curve over GF(p) (e.g., p = 17 or 23). Test with sample points. Report on:
Complete answer would include source code for the field operations, point addition, and double-and-add scalar multiplication. It would show test results verifying correctness and discuss the complexity of handling modular arithmetic and edge cases (e.g., point at infinity).
This tutorial has provided a comprehensive examination of Elliptic Curve Cryptography (ECC). We began by defining elliptic curves and their algebraic structure, extending the concept to finite fields to make cryptography practical. We explored the group operation—point addition and point doubling—and the core operation of scalar multiplication, which is the workhorse of ECC protocols.
We introduced the Elliptic Curve Discrete Logarithm Problem (ECDLP), the foundation of ECC security, and explained why it is believed to be harder than the discrete logarithm problem in finite fields, enabling smaller key sizes. We covered the three main ECC protocols:
We compared ECC with RSA and classical DH, demonstrating the significant efficiency advantages of ECC in terms of key sizes, performance, and resource consumption. We reviewed standardized curves, including NIST P-256, Curve25519, Ed25519, and secp256k1, and discussed their applications in TLS, SSH, Bitcoin, and other protocols.
We discussed implementation considerations, emphasizing point validation, constant-time operations, secure randomness, and side-channel resistance. The case studies illustrated the real-world impact of ECC vulnerabilities (e.g., the PS3 hack) and the importance of careful implementation.
With this knowledge, you are now equipped to understand, implement, and evaluate ECC in cryptographic systems, and to appreciate its advantages over traditional public-key algorithms.
In Tutorial 2.15: Digital Signatures and Public Key Infrastructure, we will explore digital signatures in depth, including RSA signatures, DSA, and ECDSA, and we will discuss how Public-Key Infrastructure (PKI) binds public keys to identities, enabling secure authentication on the Internet.