Lecture 17: Elliptic Curve Cryptography and ECDH Key Exchange

Added:

Post-Quantum Cryptography (PQC) and the Quantum Threat to ECC

While Elliptic Curve Cryptography (ECC) and the ECDH key exchange currently offer robust security with smaller key sizes compared to RSA, their foundational security is entirely compromised by the advent of quantum computing. The Elliptic Curve Discrete Logarithm Problem (ECDLP), which secures ECC, can be solved in polynomial time using Shor’s algorithm on a sufficiently powerful quantum computer. Consequently, researchers and standards organizations like NIST are actively transitioning away from ECC toward Post-Quantum Cryptography (PQC). PQC relies on alternative mathematical problems, such as lattice-based, code-based, or hash-based cryptography, which are believed to be secure against both classical and quantum attacks. Studying ECC in isolation overlooks this critical, impending paradigm shift in global cryptographic standards.

Fundamental concepts of asymmetric (public-key) cryptography and the classical Diffie-Hellman key exchange protocol.
Basic abstract algebra, specifically group theory concepts such as abelian groups, cyclic groups, group operations, and generator elements.
Modular arithmetic and arithmetic within finite fields (such as prime fields F_p), including finding modular multiplicative inverses.
The classical Discrete Logarithm Problem (DLP) and its role in cryptographic security hardness assumptions.
Elliptic Curve Digital Signature Algorithm (ECDSA) and Edwards-curve Digital Signature Algorithm (EdDSA) for message authentication and non-repudiation.
Real-world cryptographic implementations and protocols that utilize ECC, such as TLS 1.3, SSH, and blockchain/cryptocurrency networks.
Cryptanalysis of elliptic curves, including attacks like Pollard's rho algorithm, and the criteria for selecting cryptographically secure curves (e.g., secp256k1 vs. Curve25519).
Pairing-based cryptography (using bilinear pairings on elliptic curves) which enables advanced protocols like Identity-Based Encryption (IBE) and Zero-Knowledge Proofs (ZKPs).
Post-Quantum Cryptography (PQC) and the study of quantum-resistant alternatives, since ECC is vulnerable to Shor's algorithm on a quantum computer.
81K views925likes1:26:31@introductiontocryptography4223Original Release: 2014-01-30

Elliptic curve cryptography leverages the elliptic curve discrete logarithm problem (ECDLP), where given a generator point P and a point T = dP on an elliptic curve, determining the integer d (the number of hops or additions needed to reach T from P) is computationally infeasible for large primes, providing strong security foundations for protocols like Diffie-Hellman key exchange, which allows two parties to securely establish a shared secret key over an insecure channel by exchanging public keys derived from their private keys through point multiplication.