Understanding Elliptic Curve Cryptography: Implementation and Security

Introduction and Core Concepts

Elliptic curve cryptography (ECC) is a public-key cryptographic approach based on the algebraic structure of elliptic curves over finite fields. Unlike RSA, which relies on the difficulty of factoring large integers, elliptic curve cryptography derives its security from the elliptic curve discrete logarithm problem (ECDLP) — the computational infeasibility of determining a scalar multiplier given two points on a curve. This fundamental difference allows ECC to achieve equivalent security with dramatically smaller key sizes, making it indispensable for modern constrained environments.

At its core, an elliptic curve is defined by the Weierstrass equation y² = x³ + ax + b over a field, typically a prime field F_p or a binary field F_2^m. For cryptographic use, we require that the curve be non-singular, meaning 4a³ + 27b² ≠ 0 mod p, which ensures no cusps or self-intersections. The set of points (x, y) satisfying this equation, together with a distinguished point at infinity (denoted O) that serves as the identity element, forms an abelian group. This group structure is what enables cryptographic operations: we can add points together and multiply a point by a scalar integer.

The appeal of elliptic curve cryptography lies in its efficiency. A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. This 12x reduction in key size translates directly into faster computations, lower power consumption, reduced memory footprint, and smaller certificates and signatures. As the internet scales to billions of mobile devices, IoT sensors, and embedded systems, these advantages are not merely convenient — they are essential. Understanding elliptic curve cryptography is therefore critical for any engineer building secure systems today.

• Smaller keys, equivalent security: 256-bit ECC ≈ 3072-bit RSA for 128-bit security level.
• Faster operations: Key generation and signing are significantly faster than RSA at comparable security levels.
• Ideal for constrained devices: Low bandwidth, memory, and CPU requirements make ECC perfect for mobile, smart cards, and IoT.
• Forward-looking foundation: Underpins modern protocols like TLS 1.3, Signal, and blockchain systems.

How It Works

To understand elliptic curve cryptography, we must first understand the group law. Given two points P and Q on the curve, we define P + Q geometrically as the reflection across the x-axis of the third intersection point of the line through P and Q with the curve. If P = Q, we use the tangent line at P. Algebraically over a prime field F_p, this is computed with modular arithmetic. The point at infinity O acts as the identity: P + O = P, and for any point P = (x, y), its inverse is -P = (x, -y mod p). This group is finite, with its size (the number of points) denoted by #E(F_p) and bounded by Hasse's theorem: |#E(F_p) - (p+1)| ≤ 2√p.

The core one-way function in ECC is scalar multiplication: given a base point G (the generator) and a private integer k, compute Q = kG = G + G + ... + G (k times). Computing Q from k and G is efficient using repeated doubling and addition, requiring O(log k) group operations. However, reversing this — finding k given Q and G — is the elliptic curve discrete logarithm problem. For well-chosen curves over large prime fields, no known algorithm can solve the ECDLP in sub-exponential time. The best generic attacks, like Pollard's rho algorithm, run in O(√n) time where n is the subgroup order, which is exponential in the bit-length of n.

The Domain Parameters and Key Generation

An ECC system is defined by domain parameters: (p, a, b, G, n, h). Here p defines the field F_p, a and b define the curve, G is the base point (generator), n is the prime order of G (so nG = O), and h is the cofactor #E(F_p)/n, typically small (1, 2, or 4). Security requires that n be a large prime (> 2²⁵⁶ for 128-bit security) and that the curve not be anomalous or supersingular. Standard curves like NIST P-256 (secp256r1), Curve25519, and secp256k1 (used in Bitcoin) have been vetted to satisfy these constraints.

Key generation is straightforward: select a private key d uniformly at random from [1, n-1]. Compute the public key Q = dG. The private key remains secret, while Q and the domain parameters are public. Any party can use Q to encrypt or verify, but only the holder of d can decrypt or sign. The security relies entirely on the inability to derive d from Q.

From Group Operation to Cryptographic Protocol

This one-way scalar multiplication is then used to construct higher-level protocols. In Elliptic Curve Diffie-Hellman (ECDH), two parties Alice and Bob with private keys dA, dB and public keys QA = dA*G, QB = dB*G can derive a shared secret S = dA*QB = dB*QA = dA*dB*G without ever transmitting S. An eavesdropper seeing QA and QB cannot compute S without solving the ECDLP or the computational Diffie-Hellman problem. In the Elliptic Curve Digital Signature Algorithm (ECDSA), the private key is used to generate a pair (r, s) that can be verified with the public key, providing authenticity, integrity, and non-repudiation without revealing the private key.

Implementation

Implementing elliptic curve cryptography correctly requires careful finite field arithmetic, constant-time operations, and rigorous validation. The following Python examples are simplified for educational clarity and operate over a prime field. They are not production-ready and omit critical side-channel protections, but they illustrate the core mathematics faithfully. In production, use vetted libraries such as cryptography, libsodium, or OpenSSL.

First, we define the fundamental point addition and doubling operations over F_p. These are the building blocks for all higher-level operations. Note the handling of the point at infinity and the use of modular inverses via Fermat's Little Theorem.

# ECC Point Operations over prime field y^2 = x^3 + ax + b mod p
# Educational implementation - NOT constant-time or production-safe

# None represents the point at infinity (identity element)
Point = tuple  # (x, y) or None

def inv_mod(k, p):
    """Modular inverse via Fermat: k^(p-2) mod p, p must be prime."""
    if k % p == 0:
        raise ZeroDivisionError("division by zero")
    return pow(k, p - 2, p)

def point_add(P, Q, a, p):
    """Add two points P and Q on curve y^2 = x^3 + a*x + b mod p."""
    # Identity cases
    if P is None:
        return Q
    if Q is None:
        return P

    x1, y1 = P
    x2, y2 = Q

    # P + (-P) = O (point at infinity)
    if x1 == x2 and (y1 + y2) % p == 0:
        return None

    if P == Q:
        # Point doubling: s = (3*x1^2 + a) / (2*y1) mod p
        if y1 % p == 0:
            return None  # tangent is vertical
        s = (3 * x1 * x1 + a) * inv_mod(2 * y1, p) % p
    else:
        # Point addition: s = (y2 - y1) / (x2 - x1) mod p
        if x1 == x2:
            return None
        s = (y2 - y1) * inv_mod(x2 - x1, p) % p

    x3 = (s * s - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return (x3, y3)

def is_on_curve(P, a, b, p):
    """Validate that point P satisfies curve equation."""
    if P is None:
        return True
    x, y = P
    return (y * y - x * x * x - a * x - b) % p == 0

With point addition defined, we can implement scalar multiplication using the double-and-add algorithm, analogous to square-and-multiply for modular exponentiation. This algorithm processes the binary representation of the scalar k from most significant bit to least, doubling the accumulator at each step and adding the base point when the bit is 1.

def scalar_mult(k, P, a, p):
    """Compute k*P using double-and-add method. k >= 0."""
    if k == 0 or P is None:
        return None
    if k < 0:
        # k*P = -k * (-P)
        return scalar_mult(-k, (P[0], (-P[1]) % p), a, p)

    # Result initialized to point at infinity
    result = None
    addend = P

    # Binary method: iterate bits of k
    while k > 0:
        if k & 1 == 1:
            result = point_add(result, addend, a, p)
        addend = point_add(addend, addend, a, p)
        k >>= 1

    return result

def scalar_mult_double_and_add(k, G, a, p):
    """Alternative left-to-right double-and-add (more common)."""
    if k == 0 or G is None:
        return None
    result = None
    # Process bits from MSB to LSB
    # Find highest bit
    bits = bin(k)[2:]  # binary string without '0b'
    for bit in bits:
        # Double
        result = point_add(result, result, a, p) if result is not None else None
        # Add if bit is 1
        if bit == '1':
            result = point_add(result, G, a, p)
    return result

Next, we build the Elliptic Curve Diffie-Hellman (ECDH) key exchange. This demonstrates how two parties derive a shared secret without transmitting it. The security depends on using a validated, high-order generator point and ensuring private keys are uniformly random and never reused with different schemes.

import secrets

def generate_keypair(G, a, p, n):
    """Generate ECC private/public keypair."""
    # Private key d in [1, n-1], use cryptographically secure RNG
    d = secrets.randbelow(n - 1) + 1
    Q = scalar_mult(d, G, a, p)
    return d, Q

def ecdh_shared_secret(private_key, peer_public_key, a, p):
    """Compute ECDH shared secret: S = d * Q_peer."""
    if peer_public_key is None:
        raise ValueError("Invalid peer public key: point at infinity")
    # Optional: validate peer_public_key is on curve and has order n
    S = scalar_mult(private_key, peer_public_key, a, p)
    if S is None:
        raise ValueError("Shared secret is point at infinity - invalid keys")
    # Typically, x-coordinate is hashed with KDF to derive symmetric key
    return S  # S = (x_s, y_s), use x_s as secret

# Example domain parameters: tiny curve for testing (NOT SECURE)
# y^2 = x^3 + 2x + 2 mod 17, G = (5,1), n = 19
p_small = 17
a_small = 2
b_small = 2
G_small = (5, 1)
n_small = 19

# Alice and Bob generate keys
dA, QA = generate_keypair(G_small, a_small, p_small, n_small)
dB, QB = generate_keypair(G_small, a_small, p_small, n_small)

# Shared secret computed independently
S_A = ecdh_shared_secret(dA, QB, a_small, p_small)
S_B = ecdh_shared_secret(dB, QA, a_small, p_small)
assert S_A == S_B  # Should be equal: dA*dB*G
print(f"Alice secret: {S_A}, Bob secret: {S_B}")

Finally, we illustrate a simplified ECDSA signing and verification flow. Real ECDSA requires a cryptographic hash function (e.g., SHA-256), deterministic nonce generation per RFC 6979, and careful handling of the random nonce k — reuse or bias in k immediately leaks the private key.

import hashlib

def ecdsa_sign(msg, d, G, a, p, n):
    """Simplified ECDSA sign. msg is bytes. Returns (r, s)."""
    # Hash message and convert to integer
    h = int.from_bytes(hashlib.sha256(msg).digest(), 'big') % n
    if h == 0:
        h = 1

    while True:
        # k must be random in [1, n-1] and NEVER reused
        k = secrets.randbelow(n - 1) + 1
        R = scalar_mult(k, G, a, p)
        if R is None:
            continue
        r = R[0] % n
        if r == 0:
            continue
        s = (inv_mod(k, n) * (h + r * d)) % n
        if s == 0:
            continue
        # For malleability protection, ensure s <= n//2 (low-S)
        if s > n // 2:
            s = n - s
        return (r, s)

def ecdsa_verify(msg, signature, Q, G, a, p, n):
    """Simplified ECDSA verify. Returns True if valid."""
    r, s = signature
    if not (1 <= r < n and 1 <= s < n):
        return False
    h = int.from_bytes(hashlib.sha256(msg).digest(), 'big') % n
    if h == 0:
        h = 1
    s_inv = inv_mod(s, n)
    u1 = (h * s_inv) % n
    u2 = (r * s_inv) % n
    # Compute u1*G + u2*Q
    P1 = scalar_mult(u1, G, a, p)
    P2 = scalar_mult(u2, Q, a, p)
    P = point_add(P1, P2, a, p)
    if P is None:
        return False
    return (P[0] % n) == r

# Demo with small curve
msg = b"hello ecc"
d, Q = generate_keypair(G_small, a_small, p_small, n_small)
sig = ecdsa_sign(msg, d, G_small, a_small, p_small, n_small)
print(f"Signature: {sig}, Valid: {ecdsa_verify(msg, sig, Q, G_small, a_small, p_small, n_small)}")

Step-by-Step Example

Let us walk through a concrete, small-number example to make the group law tangible. We will use the toy curve E: y² = x³ + 2x + 2 mod 17. This curve is not secure, but its small field allows manual computation. First, we verify the curve is non-singular: 4a³ + 27b² = 4*8 + 27*4 = 32 + 108 = 140 mod 17 = 4 ≠ 0, so it is valid. The points on this curve can be enumerated; one of them is G = (5, 1), since 1² = 1 and 5³ + 2*5 + 2 = 125 + 10 + 2 = 137 mod 17 = 1. The order of G is n = 19, meaning 19G = O and the subgroup generated by G has prime order.

Suppose Alice's private key is dA = 7 and Bob's is dB = 12. Alice computes her public key QA = 7G. We compute this via double-and-add: 7 = 0b111, so 7G = 2*(2*G) + G + 2*G? Let's compute stepwise. First, 2G = G + G. Slope s = (3*5² + 2) / (2*1) = (75+2)/2 = 77/2 mod 17. 77 mod 17 = 9, 2^-1 mod 17 = 9 (since 2*9=18=1). So s = 9*9 =81 mod17=13. Then x_2G = 13² -5 -5 =169-10=159 mod17=6 (since 17*9=153). y_2G=13*(5-6)-1=13*(-1)-1=-14 mod17=3. So 2G=(6,3). Next, 4G=2*(2G): s=(3*36+2)/(2*3)= (108+2)/6=110/6 mod17. 110 mod17=8, 6^-1 mod17=3 (6*3=18=1). s=8*3=24 mod17=7. x_4G=49-6-6=37 mod17=3, y_4G=7*(6-3)-3=21-3=18 mod17=1. So 4G=(3,1). Next, 3G=2G+G: s=(3-1)/(6-5)=2/1=2, x=4-6-5=-7 mod17=10, y=2*(5-10)-1=-11 mod17=6 => 3G=(10,6). Then 7G=4G+3G: s=(6-1)/(10-3)=5/7 mod17. 7^-1 mod17=5 (7*5=35=1). s=5*5=25 mod17=8. x=64-3-10=51 mod17=0, y=8*(3-0)-1=24-1=23 mod17=6. So QA=(0,6). Similarly, Bob's QB=12G can be computed as 8G+4G, yielding QB=(5,16) after similar arithmetic.

Now for ECDH: Alice computes S = dA*QB =7*(5,16). Bob computes S = dB*QA =12*(0,6). Both should arrive at the same point S =84G. Since 84 mod19 = 84-76=8, S=8G. Computing 8G =2*4G: 4G=(3,1), doubling gives s=(3*9+2)/(2*1)=29/2 mod17. 29 mod17=12, *9=108 mod17=6. x=36-3-3=30 mod17=13, y=6*(3-13)-1=6*(-10)-1=-61 mod17=7 (since -61+68=7). So S=(13,7). The x-coordinate 13 would be fed into a key derivation function (e.g., HKDF-SHA256) to produce an AES-256 key. An attacker seeing G, QA=(0,6), QB=(5,16) would need to solve 7G or 12G to recover the secret, which is easy for p=17 but infeasible for p≈2²⁵⁶.

This example highlights why validation matters: if an attacker sends a point not on the curve or of small order, they can force the shared secret into a small subgroup and brute-force it (invalid curve attack). Production implementations must validate that received points are on the curve and that n*Q = O.

Complexity Analysis

The performance of elliptic curve cryptography is dominated by finite field operations — modular multiplication, squaring, and inversion — and by the number of such operations required for scalar multiplication. Unlike RSA's modular exponentiation with 3000-bit numbers, ECC operates on 256-bit numbers but requires more intricate point operations. Understanding the asymptotic and concrete costs is essential for selecting curves and optimizing implementations for servers versus microcontrollers.

Point addition and doubling each require a constant number of field operations: one modular inversion, a few multiplications, and additions. Inversion is the most expensive, typically 10-100x more costly than multiplication, which is why projective coordinate systems (Jacobian, Edwards) are used to defer inversions. Scalar multiplication via double-and-add requires O(log n) point operations, where n is the scalar size. For a 256-bit scalar, this is about 256 doublings and on average 128 additions (if using binary method), or fewer with windowed methods.

Space complexity is modest: O(1) for point operations (a few field elements) and O(log n) for scalar storage. The overall memory footprint is dominated by the field size, not by large auxiliary structures, which is why ECC is ideal for embedded systems with kilobytes of RAM.

Here n denotes the bit-length of p (e.g., n=256). While the asymptotic O(n³) may look worse than RSA's O(n³) with larger n, the constant factors and smaller n make ECC faster in practice for equivalent security. With optimizations like fixed-base comb methods, ECDSA verification can be accelerated by precomputation, and ECDH can use Montgomery ladders for constant-time execution. For 128-bit security, typical timings on a modern x86-64 CPU are: P-256 scalar multiplication ~0.05 ms, RSA-3072 private operation ~1.5 ms — a 30x speedup for ECC signing.

Variations and Optimizations

Not all elliptic curves are created equal. The choice of curve shape and coordinate system has profound implications for performance and security. The classic Weierstrass form y² = x³ + ax + b is used by NIST curves (P-256, P-384), but it requires careful handling of the point at infinity and has incomplete addition formulas that can leak timing information if not implemented carefully.

Montgomery curves, defined by By² = x³ + Ax² + x, enable the Montgomery ladder — a constant-time scalar multiplication algorithm that performs the same sequence of operations regardless of the scalar bits, thwarting simple timing and power analysis. Curve25519 (y² = x³ + 486662x² + x over F_2²⁵⁵-19) is the most famous example, designed by Daniel Bernstein for high speed and inherent side-channel resistance. It uses only the x-coordinate for ECDH (X25519), simplifying implementations.

Twisted Edwards curves, given by ax² + y² = 1 + dx²y², offer complete addition formulas — they work for all pairs of inputs without exceptions — and the fastest known point addition. Ed25519, the signature scheme using the Edwards form of Curve25519, provides deterministic signatures, small 64-byte signatures, and very fast verification. This is why Ed25519 is preferred in OpenSSH, Signal, and many blockchain systems.

Coordinate Systems and Scalar Multiplication Tricks

To avoid expensive modular inversions, implementations use projective coordinates. In Jacobian coordinates, a point (x, y) is represented as (X, Y, Z) where x = X/Z², y = Y/Z³. Point addition then requires only multiplications, with a single inversion at the end to convert back to affine. This reduces the cost of scalar multiplication by ~80%. Other optimizations include windowed methods (precomputing multiples like 3G, 5G, 7G to process 3-4 bits at once), Non-Adjacent Form (NAF) which reduces the Hamming weight of the scalar, and endomorphisms like GLV/GLS for curves with efficiently computable endomorphisms (e.g., secp256k1), which can halve the number of doublings.

For fixed-base scalar multiplication (e.g., generating a public key from a private key where G is constant), comb methods with precomputed tables can achieve 2-3x speedups. For variable-base (ECDH with peer's point), Montgomery ladder or constant-time windowed methods are preferred to avoid secret-dependent branches.

Real-World Applications

Elliptic curve cryptography is not a theoretical curiosity; it secures the majority of modern encrypted traffic. Its compactness and speed make it the default choice wherever bandwidth, compute, or power is limited, and its adoption is mandated by major standards bodies.

In web security, TLS 1.3 — the protocol securing HTTPS — has removed RSA key exchange entirely in favor of (EC)DHE. When you connect to a website, your browser and server perform an ECDHE handshake using X25519 or P-256 to establish ephemeral session keys, providing perfect forward secrecy. Certificates themselves use ECDSA or EdDSA signatures, reducing handshake size by ~50% compared to RSA-2048 certificates, which directly improves page load times on mobile networks.

Beyond the web, ECC is foundational to secure messaging (Signal Protocol uses X25519 + Ed25519 for X3DH and Double Ratchet), cryptocurrencies (Bitcoin and Ethereum use secp256k1 for ECDSA signatures to authorize transactions), secure enclaves and smart cards (Apple Secure Enclave, TPMs use P-256 for attestation), and government standards (NSA Suite B and CNSA 2.0 require P-384 and are transitioning to post-quantum hybrids with ECC).

Databases and networks also benefit: encrypted replication in PostgreSQL and MySQL can use ECC certificates for mutual TLS, and VPNs like WireGuard rely exclusively on Curve25519 for key exchange and ChaCha20-Poly1305 for transport, achieving kernel-level performance with minimal code. The trend is clear: as performance and privacy demands grow, elliptic curve cryptography displaces RSA everywhere except legacy compatibility.

Comparison with Alternatives

Choosing a public-key system involves trade-offs among security, performance, key size, and ecosystem support. While RSA dominated for decades, finite-field Diffie-Hellman (FFDH) and DSA offered alternatives, but all suffer from larger parameters for equivalent security compared to ECC. The table below provides a head-to-head comparison for a 128-bit security level — the current baseline for protecting data beyond 2030.

Security levels are measured in bits: a 128-bit security level means an attacker must perform ~2¹²⁸ operations to break the system. For RSA and FFDH, this requires 3072-bit keys due to sub-exponential factoring and discrete log algorithms (General Number Field Sieve). For ECC, a 256-bit key suffices because only exponential attacks (Pollard's rho) are known. This exponential vs sub-exponential gap widens as security levels increase: for 256-bit security, RSA needs 15360-bit keys while ECC needs only 512-bit keys.

In short, elliptic curve cryptography wins on size and speed for new systems, while RSA retains an edge in legacy verification speed (due to small public exponent e=65537) and ubiquitous library support. However, both are threatened by large-scale quantum computers running Shor's algorithm, which can solve factoring and discrete logs in polynomial time. The industry is therefore moving toward hybrid deployments (ECC + post-quantum KEMs like Kyber) and ultimately post-quantum cryptography, but ECC will remain critical during this transition period.

Common Mistakes and Best Practices

Implementing elliptic curve cryptography incorrectly can completely nullify its security, even if the underlying mathematics is sound. The most catastrophic failures have come from implementation flaws, not from breaking the ECDLP. Awareness of these pitfalls is essential for both developers and auditors.

The single most dangerous mistake is nonce reuse or bias in ECDSA. The signing equation s = k^-1(h + r*d) mod n reveals the private key d if k is ever reused for two different messages: given (r, s1) and (r, s2) for hashes h1, h2, an attacker computes k = (h1 - h2)/(s1 - s2) mod n and then d = (s1*k - h1)/r mod n. The Sony PlayStation 3 hack famously exploited this by using a static k. Similarly, biased or predictable k (e.g., using a weak PRNG) leaks bits of d via lattice attacks (Howgrave-Graham–Smart). Best practice is to use deterministic nonce generation per RFC 6979, which derives k = HMAC(d, h) and eliminates randomness failures, as done in Ed25519.

Other critical pitfalls include failing to validate peer public keys, using insecure curves, and leaking secrets through side channels. An invalid curve attack sends a point on a different, weak curve where the discrete log is easy; if the victim does not check that the point satisfies the curve equation and has order n, the shared secret can be brute-forced. Small-subgroup attacks exploit points of low order when the cofactor h > 1 and the implementation does not multiply by h or check n*Q = O. Timing attacks exploit non-constant-time scalar multiplication where the duration depends on the private key bits. Best practices mandate: always validate that received points are on the curve and not at infinity, use twist-secure curves like Curve25519, implement constant-time ladders, and use vetted libraries.

• Never roll your own curve or RNG: Use standardized curves (P-256, Curve25519, Ed25519) and a CSPRNG (secrets module, /dev/urandom). Custom curves often have hidden weaknesses.
• Validate all inputs: Check 0 < r, s < n for signatures, verify points are on curve, and reject weak keys (d=0, Q=O).
• Use constant-time code: Avoid branches on secret data, use Montgomery ladder or complete formulas, and enable compiler mitigations.
• Apply low-S and malleability checks: Enforce s ≤ n/2 and unique encodings to prevent signature malleability in blockchain contexts.
• Prefer Ed25519/X25519 for new designs: They are designed to be misuse-resistant, deterministic, and fast without requiring extensive validation.
• Plan for hybrid post-quantum: For long-lived data, combine ECC with a post-quantum KEM to hedge against future quantum attacks.

Interview Questions

Interviewers frequently probe elliptic curve cryptography to assess depth beyond buzzwords. Expect questions that test mathematical intuition, security reasoning, and practical trade-offs. Below are common questions with concise, interview-ready answers.

1. Why does a 256-bit ECC key offer similar security to a 3072-bit RSA key?

Answer: Security depends on the best known attack. RSA's security relies on integer factorization, for which the General Number Field Sieve runs in sub-exponential time O(exp((64/9)^1/3 (ln N)^1/3 (ln ln N)^2/3)), so key sizes must grow quickly to maintain security. ECC's security relies on the elliptic curve discrete logarithm problem, for which the best generic attack is Pollard's rho with fully exponential complexity O(√n) = O(2¹²⁸) for n≈2²⁵⁶. Because no sub-exponential algorithm is known for well-chosen curves, ECC achieves 128-bit security with 256-bit keys, while RSA needs 3072 bits to force the sub-exponential attack to 2¹²⁸ work. This gap widens at higher security levels.

2. What happens if you reuse the same k (nonce) when signing two different messages with ECDSA?

Answer: Private key recovery is immediate. ECDSA signatures are (r, s) where r = (kG)_x mod n and s = k^-1(h + r*d) mod n. If k is reused, r repeats. Given two signatures (r, s1), (r, s2) on hashes h1, h2, an attacker solves s1 - s2 = k^-1(h1 - h2) mod n ⇒ k = (h1 - h2)/(s1 - s2) mod n, then d = (s*k - h)/r mod n. This is why RFC 6979 deterministic k generation is critical and why EdDSA derives its nonce deterministically from the private key and message.

3. Explain point addition on an elliptic curve and the role of the point at infinity.

Answer: The point at infinity O is the identity element of the elliptic curve group. Geometrically, adding P and Q involves drawing the line through P and Q, finding its third intersection R with the curve, and reflecting R across the x-axis to get P+Q. Algebraically over F_p, if P≠Q, slope s=(y2-y1)/(x2-x1) mod p; if P=Q, s=(3x1²+a)/(2y1) mod p; then x3=s²-x1-x2 mod p, y3=s(x1-x3)-y1 mod p. If P=(x,y) and Q=(x,-y), the line is vertical and intersects at O, so P+(-P)=O. O ensures every point has an inverse and the group axioms hold, enabling scalar multiplication kP.

4. What is the difference between Weierstrass, Montgomery, and Edwards curves?

Answer: They are different equation forms birationally equivalent but with different performance/security properties. Weierstrass y²=x³+ax+b is the general form used by NIST P-curves; its addition formulas are incomplete (exceptions for doubling, point at infinity) and can be tricky to implement constant-time. Montgomery curves By²=x³+Ax²+x enable the Montgomery ladder for constant-time, x-only ECDH (Curve25519) and are very fast for key exchange. Twisted Edwards curves ax²+y²=1+dx²y² have complete, unified addition formulas (no exceptions), fastest addition, and are ideal for signatures (Ed25519). In practice, use Montgomery for ECDH and Edwards for signatures.

5. How would you validate an untrusted ECC public key received from a peer?

Answer: Perform three checks: 1) Q ≠ O (not point at infinity), 2) coordinates are in range 0 ≤ x,y < p and satisfy the curve equation y² ≡ x³+ax+b mod p, and 3) nQ = O (Q has correct prime order, preventing small-subgroup attacks). For curves with cofactor h=1 (like P-256), check 3 can be omitted if check 2 passes and the implementation multiplies by h, but for cofactor >1 curves (Curve25519 h=8), you must either clear the cofactor (multiply by h) or verify subgroup membership. Libraries should also reject weak keys and use constant-time validation to avoid oracles.