IM Engineer Study Notes
← Back to list
Security & Privacy
#ECC#ECDSA#ECDH#Curve25519#공개키암호
Last updated · 2026-11-04

Elliptic Curve Cryptography (ECC)

1. Overview

Definition: Elliptic Curve Cryptography (ECC) is a public-key cryptosystem whose security rests on the computational hardness of the "Elliptic Curve Discrete Logarithm Problem (ECDLP)," built on the scalar multiplication operation of the abelian group formed by the points of an elliptic curve defined over a finite field.

Public-key cryptography became practical after Diffie and Hellman introduced the key-exchange concept in 1976 and RSA harnessed the integer factorization problem in 1977. However, RSA and finite-field discrete logarithms (DH, DSA) share a structural limitation: raising their security requires sharply increasing the key length. Because sub-exponential-time algorithms such as the Number Field Sieve exist, driving up attack cost means continually enlarging the modulus to 2048, 3072, or 4096 bits, which directly translates into heavier computation, bandwidth, and storage burdens.

ECC was proposed independently by Neal Koblitz and Victor Miller in 1985 precisely to resolve this "key-length versus performance dilemma." No sub-exponential-time algorithm is yet known for the discrete logarithm problem over the elliptic curve group (ECDLP), and general attacks remain fully exponential (about √n for a group of size n), as with Pollard's rho. As a result, the same security strength is achieved with a far shorter key — NIST SP 800-57, for example, recommends that 256-bit ECC provides the 128-bit security strength comparable to roughly 3072-bit RSA.

Thanks to this efficiency, ECC has become the de facto standard in constrained environments such as smart cards, IoT, and mobile, and sits at the core of modern security infrastructure including TLS 1.3, SSH, Bitcoin, and e-passport chips (ICAO). This answer discusses the mathematical foundation and group structure of ECC, its core primitives (ECDH and ECDSA) and operating procedures, a comparison with RSA and curve standards, and the latest trend of transitioning to post-quantum cryptography (PQC) together with considerations from a professional engineer's perspective.

2. Mathematical Foundation and Overall Structure

2.1 Elliptic Curves and the Group Structure of Points

The starting point of ECC is an elliptic curve defined over a finite field. Over a prime field GF(p), one generally uses the Weierstrass form y² = x³ + ax + b (mod p), which must satisfy the discriminant condition 4a³ + 27b² ≠ 0 so that it has no singular points. If a "point at infinity (O)" is added as an identity element to the set of all points on this curve, the set of points forms an abelian group that is closed under addition and satisfies associativity, an identity, and inverses.

A key intuition here is that the security of ECC comes not from the "curve itself" but from the "addition structure defined over this group." The geometric rule for adding two points P and Q (the third point where the line through them meets the curve, reflected across the x-axis) is replaced on a finite field by modular arithmetic, and this rule creates the asymmetry that separates the cryptographically "easy" direction from the "hard" one. That is, point addition and scalar multiplication are computed efficiently, but their inverse (the discrete logarithm) is practically unsolvable — this one-wayness is the basis of the cryptosystem.

2.2 ECC Overall Structure Diagram

flowchart TB
  subgraph MATH["Mathematical foundation"]
    FF["Finite field GF(p) or GF(2^m)"]
    EC["Elliptic curve y^2 = x^3 + ax + b"]
    GRP["Abelian group of points(addition·inverse·identity O)"]
  end
  subgraph PARAM["Domain parameters"]
    CURVE["Curve coefficients a,b / prime p"]
    BASE["Base point G(generator)"]
    ORDER["Order n·cofactor h"]
  end
  subgraph HARD["Hard problem"]
    ECDLP["ECDLP: recovering k from Q=kG is infeasible"]
  end
  subgraph PRIMS["Cryptographic primitives"]
    ECDH["ECDH key exchange"]
    ECDSA["ECDSA digital signature"]
    ECIES["ECIES public-key encryption"]
  end
  FF --> EC --> GRP
  GRP --> BASE
  CURVE --> BASE --> ORDER
  ORDER --> ECDLP
  ECDLP --> ECDH
  ECDLP --> ECDSA
  ECDLP --> ECIES

As the diagram shows, the ECC scheme consists of four layers: (1) the mathematical foundation of an elliptic curve group over a finite field, (2) the domain parameters shared by all participants (curve coefficients, prime p, base point G, order n), (3) the ECDLP hard problem, and (4) the primitives built on top of it such as ECDH, ECDSA, and ECIES. The quality of the domain parameters, in particular, governs security: the order n of the base point G must be a sufficiently large prime, the cofactor h must be small, and the parameters must be generated verifiably (verifiably random) to prove they were not tampered with, shutting out backdoor concerns.

2.3 Core Operation — Scalar Multiplication and ECDLP

Every ECC operation ultimately reduces to scalar multiplication Q = kG, that is, adding the base point G to itself k times. This operation is computed in O(log k) point additions using binary expansion and the "double-and-add" technique, so even a 256-bit k finishes in a few hundred group operations. Conversely, the problem of recovering the scalar k given only the public point Q and G is exactly the ECDLP, and even the best general attack requires on the order of √n ≈ 2^128 operations, making it practically infeasible.

Expressed numerically, this asymmetry is clearly convincing. A 256-bit curve has a group order of roughly 2^256, and the cost of Pollard's rho attack is about 2^128, a cosmic-scale amount of computation. By contrast, a legitimate user's scalar multiplication finishes within microseconds in around 256 double-and-add steps, so the ideal structure of public-key cryptography — "legitimate computation is cheap while attacks are astronomical" — holds.

3. Core Primitives and Operating Procedures

3.1 ECDH — Key Exchange

ECDH (Elliptic Curve Diffie-Hellman) is a protocol by which two parties safely agree on a shared secret over a public channel. Each creates a private key (scalar) a, b and a public key A=aG, B=bG, exchanges only the public keys, and then multiplies the peer's public key by its own private key to reach the same point, a·B = a(bG) = b(aG) = b·A = abG. An eavesdropper sees A, B, and G but would have to solve the ECDLP to compute abG, so cannot learn the shared secret.

sequenceDiagram
  participant A as Alice
  participant N as "Public channel(eavesdroppable)"
  participant B as Bob
  A->>A: choose private key a, compute public key A=aG
  B->>B: choose private key b, compute public key B=bG
  A->>N: send public key A
  N->>B: deliver A
  B->>N: send public key B
  N->>A: deliver B
  A->>A: shared point S=a*B=abG
  B->>B: shared point S=b*A=abG
  Note over A,B: derive session key from the same S via KDF

In practice, ECDHE — which uses an ephemeral key pair for each session — is the standard, in order to provide Forward Secrecy. That is, even if the server's long-term private key leaks later, the ephemeral keys of past sessions have already been discarded, so past traffic cannot be decrypted. A representative case is TLS 1.3, which removed static RSA and static DH key exchange and effectively mandated ECDHE; this is also a defense against the "Harvest Now, Decrypt Later" threat.

3.2 ECDSA — Digital Signatures

ECDSA (Elliptic Curve Digital Signature Algorithm) is a signature scheme that ports DSA to the elliptic curve group. The signer computes R=kG from the message hash e and an ephemeral random number k, takes its x-coordinate as r, computes s = k⁻¹(e + r·d) (mod n), and outputs (r, s) as the signature (d is the private key). The verifier reconstructs R from the public key Q=dG and (r, s) and checks whether the x-coordinate matches r.

The most fatal practical pitfall in ECDSA is the reuse or predictability of the ephemeral random number k. If the same k is used in two different signatures, the private key d is exposed directly via simultaneous equations; in fact, in 2010 the Sony PlayStation 3 used a fixed constant for k, which allowed the signing private key to be extracted and arbitrary code signing to become possible. For this reason, RFC 6979, which deterministically derives k from the message and private key, or EdDSA (Ed25519), which designs out the random-number vulnerability altogether, is now recommended.

3.3 Curve Standards and Parameters

The security and performance of ECC vary greatly depending on which curve is used. The representative standards are listed below, and not only raw performance but also "implementation safety (how easy constant-time operation is)" and "parameter trustworthiness (whether it is verifiably random)" become selection criteria.

Curve Security strength(approx.) Characteristics·use Considerations
NIST P-256(secp256r1) 128-bit TLS·PKI standard, abundant hardware support Controversy over parameter-generation transparency
secp256k1 128-bit Bitcoin·Ethereum signatures Non-standard structure, specific optimizations possible
Curve25519 128-bit X25519 key exchange, fast·safe implementation Constant-time·fault-resistant design
Ed25519 128-bit EdDSA signatures, random-number vulnerability designed out Spreading in SSH·modern protocols
P-384 / Curve448 192-bit or higher High security·long-term secrecy Increased performance cost

In this table, the contrast between NIST P-256 and Curve25519 is especially important. Both provide 128-bit security strength, but P-256 is criticized because its generation involves an unexplained constant (seed) that does not fully rule out the possibility of a backdoor, whereas Curve25519 and Ed25519 have transparent generation rationale and use the Montgomery/twisted Edwards form, making constant-time implementation and side-channel resistance easy and thus earning trust. As a result, modern protocols such as Signal, WireGuard, OpenSSH, and TLS 1.3 tend to adopt the Curve25519 family as the first choice.

4. Comparison with RSA and Application Cases

ECC and RSA are both public-key cryptosystems, but their security bases and efficiency characteristics are fundamentally different. RSA is based on the factorization problem and, as the key grows, is chased by sub-exponential attacks, whereas ECC is based on the exponentially hard ECDLP, so its security rises steeply relative to key growth.

Category RSA ECC Why the difference arises
Underlying problem Integer factorization(IFP) Elliptic curve discrete log(ECDLP) No sub-exponential algorithm for ECDLP
Key length for 128-bit security about 3072-bit about 256-bit Difference in attack-algorithm complexity
Signature generation speed Slow Fast Short key·few operations
Signature verification speed Fast Relatively slow RSA exponent e is small(65537)
Bandwidth·storage Large Small Small key·signature size
Implementation difficulty Relatively simple Complex(watch for side channels) Needs group ops·constant-time implementation

The practical implication of this comparison is that "the optimal point differs by use case." For instance, an API gateway where the server performs JWT verification in bulk may benefit from RSA with its fast verification, but an environment where many mobile devices each generate and exchange signatures overwhelmingly favors ECC with its fast generation and small transmission size. In fact, mobile security chips such as Apple Secure Enclave and Android StrongBox, active authentication in e-passports (ICAO Doc 9303), and Bitcoin transaction signing (secp256k1) adopted ECC because of their common ground of constrained environments and bulk transactions. TLS measurement cases also report that the ECDHE+ECDSA combination significantly lowers handshake latency and CPU usage compared to RSA key exchange (specific figures vary by environment).

5. (Deep Dive) Transition to Post-Quantum Cryptography and Latest Trends

The greatest structural threat to ECC is the quantum computer. Once a sufficiently large fault-tolerant quantum computer appears, Shor's algorithm will solve the ECDLP in polynomial time, so ECC, along with RSA, is fundamentally neutralized. There is even analysis suggesting that ECC, with its short keys, can be attacked with fewer qubits than RSA, so from the standpoint of the quantum threat ECC may break first.

Accordingly, NIST finalized the post-quantum cryptography (PQC) standards FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) in 2024, and its transition roadmap (NIST IR 8547 draft, etc.) proposes pushing quantum-vulnerable algorithms such as RSA and ECC out in stages — recommended-deprecated around 2030 and disallowed around 2035 (details subject to confirmation against the source). However, because of concerns that PQC is not yet sufficiently vetted, a hybrid approach is for now establishing itself as the realistic solution. For example, the X25519MLKEM768 key exchange in TLS, which combines X25519 and ML-KEM, is designed so that the whole remains secure as long as either one is secure, preparing for the quantum threat while maintaining compatibility with the existing ECC ecosystem — Google, Cloudflare, and others are already deploying it at large scale.

Another trend is strengthening the implementation safety of ECC itself. Because even mathematically secure ECC has repeatedly suffered private-key leakage from side-channel attacks (power/timing analysis) or random-number vulnerabilities, constant-time operation, deterministic random numbers (RFC 6979), adoption of EdDSA, and the choice of safe curves (Curve25519) have emerged as the core of "implementation governance." In other words, the recognition that "how it was implemented" governs actual security as much as algorithm choice is maturing.

6. Considerations and Implications (Professional Engineer's Perspective)

  • Transition strategy (crypto-agility): Since the quantum threat is all but certain, one should not hardcode ECC throughout the code but first establish crypto-agility that makes algorithms replaceable via policy and configuration. It is realistic to inventory ECC usage with a CBOM and apply hybrid key exchange in stages first.
  • Trade-offs: ECC has the advantages of short keys, low bandwidth, and fast signature generation, but its group operations are complex, making it vulnerable to implementation errors and side-channel attacks, and signature verification can be slower than RSA. A design that selectively combines RSA, ECC, and PQC by use case (bulk verification vs. constrained devices) is desirable.
  • Implementation·operational risk: Because reusing the ephemeral random number k in ECDSA leads directly to full private-key exposure, one should adopt deterministic signatures (RFC 6979) or EdDSA and isolate keys with a hardware security module (HSM) or Secure Enclave. When choosing a curve, evaluate not only performance but also parameter trustworthiness and ease of constant-time implementation (the Curve25519 family).
  • Standards·regulatory compliance: Comply with the approved curves of NIST SP 800-57·FIPS 186 and each country's regulations, but considering the PQC transition roadmap (2030/2035), hybrid transition should be brought forward for assets requiring long-term secrecy.
  • Outlook and related technologies: ECC will coexist in the short term as one axis of hybrid PQC and then be replaced by ML-KEM·ML-DSA over the medium-to-long term, but thanks to its short-key advantage it is expected to retain a core position for the time being in constrained environments such as IoT and blockchain. It is tightly linked to zero-trust workload authentication, DID (decentralized identity), and TLS 1.3.

References

In one line: ECC is a public-key cryptosystem that uses the scalar multiplication of a finite-field elliptic curve group and the ECDLP hard problem to achieve the same security strength with a far shorter key than RSA; it forms the backbone of TLS, mobile, and blockchain through ECDH and ECDSA, but a hybrid PQC transition is underway in response to the quantum-computer threat.