Elliptic Curve Cryptography¶

Overview¶

Elliptic Curve Cryptography (ECC) is a public-key encryption algorithm based on elliptic curve mathematics. Unlike traditional cryptographic systems such as RSA that rely on integer factorization, ECC's security is based on the computational difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

ECC's core advantage lies in using shorter key lengths while providing the same level of security, thereby reducing computational cost, storage requirements, and bandwidth consumption. A 256-bit ECDSA signature provides the same security strength as a 3072-bit RSA signature, making ECC particularly valuable in resource-constrained environments (such as mobile devices and IoT) and blockchain applications.

Core Principles¶

Elliptic Curve Equation

An elliptic curve is defined mathematically by the following equation (Weierstrass form):

y² = x³ + ax + b

Over a finite field, the elliptic curve forms a finite set of points satisfying the above equation, plus a point at infinity O (serving as the identity element of the group).

Point Operations

Two basic operations are defined on elliptic curves: 1. Point Addition: Given two points P and Q on the curve, a third point R = P + Q can be defined 2. Scalar Multiplication: Given a point P and an integer k, kP = P + P + ... + P (k times) can be computed

Discrete Logarithm Problem (ECDLP)

This problem is the discrete logarithm problem on elliptic curves, and it is considered extremely difficult. Given two points G (base point) and Q on an elliptic curve, finding an integer k such that Q = kG is computationally infeasible. This is the mathematical foundation of ECC's security.

One-Way Trapdoor Function

Forward computation is simple: computing kG can be done in polynomial time using fast exponentiation algorithms
Reverse computation is difficult: given G and kG, solving for k requires exponential time complexity
Whether RSA, discrete logarithm encryption, or elliptic curve encryption, public-key encryption algorithms all rely on this type of mathematical problem that is easy in one direction and difficult in reverse

Main Algorithms¶

ECDH (Elliptic Curve Diffie-Hellman)

The Elliptic Curve Diffie-Hellman key exchange protocol is used to create a shared key between two parties.

How it works: 1. Alice chooses private key a, computes public key A = aG 2. Bob chooses private key b, computes public key B = bG 3. Alice computes shared key K = aB = a(bG) 4. Bob computes shared key K = bA = b(aG) 5. Since a(bG) = b(aG) = (ab)G, both parties obtain the same shared key

ECDSA (Elliptic Curve Digital Signature Algorithm)

The Elliptic Curve Digital Signature Algorithm is used for digitally signing and verifying data.

Signing Process: 1. Compute hash h = Hash(m) for message m 2. Choose random number k, compute R = kG, take r = R.x (x-coordinate of R) 3. Compute s = k^(-1)(h + r * private_key) mod n 4. Signature is (r, s)

Verification Process: 1. Compute u1 = h * s^(-1) mod n, u2 = r * s^(-1) mod n 2. Compute R' = u1*G + u2 * public_key 3. Verify R'.x = r (mod n)

Common Curves¶

secp256k1

The elliptic curve used by Bitcoin and Ethereum, with equation y² = x³ + 7.

Characteristics: - Due to its special construction, optimized implementations can achieve 30% better performance than other curves - Requires very little bandwidth and storage; key length is very short - Satoshi Nakamoto chose secp256k1 over NIST-defined curves, avoiding potential backdoor risks - Allows all users to perform field operations using the same procedures

Applications: - Bitcoin is the first and most well-known cryptocurrency to adopt secp256k1 - Ethereum adopted secp256k1 for interoperability with Bitcoin - Litecoin and many other cryptocurrencies

secp256r1 (P-256 / prime256v1)

A NIST-standardized curve, also known as P-256.

Controversy: - Questions about NSA having a backdoor in the SECP256r1 curve - Many people question the close relationship between NIST and the NSA - This is one of the reasons for community concerns about this curve

Differences between secp256k1 and secp256r1: - The only difference between SECP256K1 and SECP256R1 is the curve parameters of their respective elliptic curves - All computations are completely the same, only with different input parameters - secp256k1 has better performance, approximately 30% faster than secp256r1

Curve25519 / Ed25519

A modern elliptic curve designed by Daniel J. Bernstein.

Characteristics: - Curve25519 provides 128-bit security (256-bit key size) - Faster and more secure than secp256k1 and NIST curves - X25519 is used for ECDH key exchange, Ed25519 is used for EdDSA signatures - Curve25519 and Edwards25519 (Ed25519) curves are birationally equivalent (twists of each other)

Applications: - OpenSSH default signature scheme - Signal end-to-end encrypted messaging - DNSSEC - Git repository signing - TLS protocols and VPN tunnels

Other Common Curves: - P-384 / secp384r1: Higher security level (192-bit security) - P-521 / secp521r1: Highest security level (260-bit security) - brainpoolP256r1: European standard

Security Analysis¶

ECC Security

The security of secp256k1 originates from the Elliptic Curve Discrete Logarithm Problem (ECDLP). For well-chosen curves and sufficiently large key sizes, the ECDLP is considered computationally infeasible. The 256-bit key used in secp256k1 provides a high level of security, making it resistant to known attacks.

Key Length Comparison (Same Security Level):

Security Level	ECC Key Length	RSA Key Length	Symmetric Equivalent
80-bit	160 bits	1024 bits	DES-80
112-bit	224 bits	2048 bits	3DES
128-bit	256 bits	3072 bits	AES-128
192-bit	384 bits	7680 bits	AES-192
256-bit	521 bits	15360 bits	AES-256

Quantum Threat

Similar to RSA, ECC is also vulnerable to Shor's quantum algorithm. Quantum computers can solve the elliptic curve discrete logarithm problem in polynomial time. Migration to post-quantum cryptographic algorithms will be necessary.

Applications in Blockchain¶

Bitcoin

Bitcoin's core uses ECDSA (Elliptic Curve Digital Signature Algorithm), enabling transaction verification through public identifiers.

Uses the secp256k1 curve
Private key -> Public key (via elliptic curve point multiplication)
Public key -> Address (via hashing)
Transaction signing uses ECDSA

Ethereum

All Ethereum libraries default to supporting only SECP256K1, as this is the signature algorithm used on the public Ethereum network.

Adopted secp256k1 for interoperability with Bitcoin
Addresses are the last 20 bytes of the Keccak-256 hash of the public key
The smart contract ecrecover function is used for signature verification

Next-Generation Blockchains

Solana: Uses Ed25519 signatures for higher performance
Cardano: Uses Ed25519
Polkadot: Uses Ed25519 (Schnorrkel/Ristretto)
Algorand: Uses Ed25519

Performance Advantages¶

Computational Efficiency

ECC's key generation, signing, and verification are all faster than RSA
At the same security level, ECC is 10-40x faster than RSA

Storage and Bandwidth

256-bit ECC key vs 3072-bit RSA key
Signature size: ECDSA 64 bytes vs RSA 384 bytes
Saves over 85% of storage space

Mobile and Embedded Devices

Less memory usage
Faster computation
Lower power consumption

Implementations and Libraries¶

Common Libraries: - OpenSSL: C library supporting multiple elliptic curves - libsecp256k1: Optimized library used by Bitcoin Core - elliptic.js: JavaScript implementation - py_ecc: Python implementation - Bouncy Castle: Java/C# implementation

Security Protocol Applications¶

TLS/SSL

Transport Layer Security protocol uses ECDH for key exchange and ECDSA for authentication. Modern TLS 1.3 prioritizes elliptic curve algorithms.

SSH

Secure Shell protocol supports ECDSA and Ed25519 keys. Ed25519 is now the recommended default for OpenSSH.

VPN

Many VPN protocols (such as WireGuard) use Curve25519 for key exchange.