Cryptography
ECC Mathematics
A 256-bit elliptic curve key matches the security of a 3072-bit RSA key. TLS 1.3 uses X25519 for key exchange, P-256 for certificates. Signal uses Curve25519 for every message. ECC efficiency makes secure mobile and IoT cryptography feasible.
- **TLS 1.3**: X25519 ECDH mandatory. Every modern HTTPS connection uses ECC key exchange.
- **Signal/WhatsApp**: Curve25519 for X3DH and Double Ratchet. 2+ billion users protected daily.
- **Bitcoin**: secp256k1 (y^2 = x^3 + 7) for all key pairs. Private key is a 256-bit scalar.
- **Apple Secure Enclave**: P-256 for biometric key derivation, hardware-protected.
Elliptic Curve: Definition
An elliptic curve over a prime field Fp is the set of points (x,y) satisfying y^2 = x^3 + ax + b (mod p), plus a point at infinity O. The discriminant 4a^3 + 27b^2 must be non-zero to avoid singular points where the group law breaks down.
Curve25519 uses nothing-up-my-sleeve constants with published justifications. NIST P-256 derives parameters from a SHA-1 hash of an undisclosed seed, prompting debate about potential backdoors.
Why must the elliptic curve discriminant 4a^3 + 27b^2 be non-zero?
Point Addition on Elliptic Curves
Adding two curve points P and Q: draw a line through them, find the third curve intersection, reflect over the x-axis. The point at infinity O is the identity element. Point doubling uses the tangent line at P.
Montgomery curves support the Montgomery ladder: constant-time scalar multiplication using only x-coordinates. Twisted Edwards curves (Ed25519) have the simplest known addition formulas.
What is the role of the point at infinity O in elliptic curve groups?
Scalar Multiplication: Foundation of ECC
Scalar multiplication kP means adding P to itself k times. The double-and-add algorithm (analogous to square-and-multiply) computes kP in O(log k) steps, making 256-bit scalars feasible.
Constant-time scalar multiplication is critical: variable-time double-and-add leaks the scalar k via timing. Montgomery ladder and windowed NAF are used in production libraries (OpenSSL, libsodium).
Why is double-and-add scalar multiplication essential for ECC?
ECDLP: Discrete Logarithm on Curves
ECDLP: given G and Q=kG, find k. The best known algorithms (Pollard rho, BSGS) run in O(sqrt(n)) - fully exponential in the curve order bit length. Unlike DLP in Z_p, no subexponential attacks exist for ECDLP in general.
MOV and anomalous curve attacks reduce ECDLP to DLP for weak curves. P-256 and Curve25519 are specifically designed to resist these reductions.
ECDLP is easier than DLP in Z_p because elliptic curves use smaller parameters
ECDLP has no known subexponential attack unlike DLP in Z_p - this is exactly why ECC achieves higher security per bit
The absence of index calculus for ECDLP makes ECC more efficient - smaller parameters for the same security level.
Why does a 256-bit elliptic curve provide ~128-bit security?
Summary
- **Elliptic curve**: y^2 = x^3 + ax + b over Fp. Non-singular (discriminant != 0). Group of points under geometric addition.
- **Point addition**: geometric construction. O = identity. Every P has inverse -P.
- **Scalar multiplication**: double-and-add runs in O(log k). Foundation of ECDH and ECDSA.
- **ECDLP**: O(sqrt(n)) = 2^128 for 256-bit curves. No subexponential attack unlike Z_p DLP.
Related Topics
ECC mathematics underpins modern public key cryptography:
- ECC in Practice — ECDH, ECDSA, Ed25519 - practical applications of ECC math.
- Key Exchange — ECDH computes shared secret via scalar multiplication.
- Post-Quantum Cryptography — Shor algorithm solves ECDLP on a quantum computer.
Вопросы для размышления
- If an attacker sees Q=kG on a 256-bit curve, how long would Pollard rho take classically?
- Why does Bitcoin secp256k1 (a=0, b=7) differ from P-256, and does this affect security?
- What constant-time advantage does Curve25519 Montgomery form provide over short Weierstrass?