Intuition, Vocabulary and Foundations
An elliptic curve over a prime field is a finite set of points satisfying $y^2 \equiv x^3+ax+b \pmod p$, together with a special identity point $\mathcal O$. Picture the points as stops on a circular route: the group law combines two stops to reach a third, while scalar multiplication repeats that operation efficiently. For example, on $E: y^2 \equiv x^3+2x+3 \pmod{97}$, the point $P=(3,6)$ lies on the curve because both sides are congruent to $36$.
The discriminant condition $4a^3+27b^2 \not\equiv 0 \pmod p$ rules out singular curves, where the addition formulas cease to define the intended group. RSA instead works in arithmetic modulo a composite, finite-field Diffie–Hellman works in a multiplicative subgroup, and Rabin uses modular squaring; their shared lesson is that security claims depend on the exact algebraic domain and threat model, not merely on using large numbers.
An elliptic-curve cryptosystem is built on a finite abelian group: validate the field, nonsingularity, point membership, subgroup, and identity behavior before trusting any group operation. The examples here teach the mathematics only; production cryptography requires standardized parameters and audited, constant-time libraries.
| Concept | Definition or notation | Concrete example | Non-example or boundary | Question answered |
|---|---|---|---|---|
| Prime-field curve | $E: y^2 \equiv x^3+ax+b \pmod p$ with prime $p$ | $y^2 \equiv x^3+2x+3 \pmod{97}$ | Composite modulus without a specified ring or field model | Which coordinate pairs are curve points? |
| Nonsingularity | $4a^3+27b^2 \not\equiv 0 \pmod p$ | For $a=2,b=3,p=97$, the value is nonzero | A zero discriminant produces a singular cubic | Does the chord-and-tangent law form the intended group? |
| Identity and inverse | $P+\mathcal O=P$ and $-(x,y)=(x,-y\bmod p)$ | $-(3,6)=(3,91)$ modulo $97$ | Treating $(0,0)$ as a universal identity | How do cancellation and zero scalar work? |
| Scalar multiplication | $kP=P+\cdots+P$ for $k\ge 0$ | $2P=(80,10)$ for $P=(3,6)$ | Multiplying coordinates by $k$ | How is a public point derived from a secret scalar? |
| ECDH | Parties compare $a(bG)$ and $b(aG)$ | Both equal $(ab)G$ | Accepting an unvalidated peer point | How can two parties derive the same group element? |
| RSA | Exponentiation modulo $N=pq$ | $c\equiv m^e\pmod N$ | Textbook RSA without padding | Which trapdoor operation relies on factoring? |
| Rabin | Squaring modulo a composite | $c\equiv m^2\pmod N$ | Assuming decryption has one root | Why must encoding disambiguate multiple square roots? |
| Threat model | Capabilities and secrets an attacker may possess | Chosen inputs plus timing observations | “The formula is correct, so the system is secure” | What failures must an implementation resist? |
Step-by-Step Derivations and Algorithms
For distinct points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ with $x_1\ne x_2$, compute $\lambda=(y_2-y_1)(x_2-x_1)^{-1}\pmod p$; for doubling, use $\lambda=(3x_1^2+a)(2y_1)^{-1}\pmod p$. Then $x_3\equiv\lambda^2-x_1-x_2$ and $y_3\equiv\lambda(x_1-x_3)-y_1\pmod p$. Vertical pairs add to $\mathcal O$, and doubling a point with $y=0$ also yields $\mathcal O$.
Double-and-add scans the bits of $k$, maintaining an accumulated result and a repeatedly doubled point, so it uses $O(\log k)$ additions instead of $k-1$. A ladder maintains two related multiples and performs one addition and one doubling per bit; its regular structure is useful for side-channel-resistant implementations, although constant operation counts alone do not make arbitrary high-level code constant-time.
flowchart TD
A["Validate field and curve"] --> B{"Input point valid?"}
B -->|No| X["Reject input"]
B -->|Yes| C{"Operation"}
C -->|Add or double| D["Apply group-law cases"]
C -->|Scalar multiply| E["Double-and-add or ladder"]
D --> F["Verify result on curve"]
E --> F
F --> G{"Protocol use?"}
G -->|Key exchange| H["Validate subgroup and derive key"]
G -->|Signature| I["Use nonce-safe audited scheme"]
After processing any prefix of the scalar bits, scalar multiplication must preserve that its working points are known multiples of the original point; induction over the bit updates proves the result is $[k]P$. Both double-and-add and the ladder take $O(\log k)$ group operations and $O(1)$ auxiliary point storage, assuming field operations are unit cost.
Implementation, Complexity and Engineering
The reference implementation below uses affine coordinates because they expose the mathematics clearly. It validates the prime-field curve and every input and output point, but its modular inversions, branches, and Python integers are not constant-time. Real systems normally use projective coordinates, strict encodings, subgroup checks, secure randomness, approved protocols, and a maintained cryptographic library.
| Choice | Cost model | Numeric or security boundary | Likely failure | Mitigation |
|---|---|---|---|---|
| Affine point addition | One inversion plus field multiplications | Inversion is expensive and input dependent | Slow or variable-time behavior | Use it for teaching; use vetted projective formulas in production |
| Double-and-add | $O(\log k)$ group operations | Branch pattern depends on scalar bits | Timing or power leakage | Use an audited constant-time scalar-multiplication routine |
| Montgomery-style ladder | One add and one double per bit | Regular control flow is not sufficient by itself | Compiler, memory, or field-operation leakage | Use constant-time field arithmetic and verified implementations |
| RSA exponentiation | Roughly $O(\log e)$ modular multiplications for a public exponent | Security also depends on padding and key generation | Textbook-RSA and fault attacks | Use standardized authenticated padding and hardened libraries |
| ECDH key exchange | One public and one secret scalar multiplication per party | Peer point and subgroup must be valid | Invalid-curve or small-subgroup attack | Decode strictly, validate, clear cofactors as the standard requires, and use a KDF |
| Random nonces | Entropy must match the scheme requirements | Reuse or bias can reveal a signing key | Catastrophic key recovery | Use deterministic standardized signing or a secure system RNG |
| Property testing | Many random identities plus fixed vectors | Tests do not prove constant-time behavior | Arithmetic corner cases survive examples | Compare with a trusted oracle and run specialized side-channel analysis |
Applications, Case Studies and Exercises
Begin with the toy curve to see the group law directly, then contrast it with a protocol review where validation, encoding, entropy, side channels, authentication, and key derivation are part of correctness. The same mathematical operation can therefore be correct in a notebook and unsafe in a deployed service.
Apply Elliptic Curves & Cryptographic Foundations
Case study 1 — trace a tiny group. Use $E: y^2\equiv x^3+2x+3\pmod{97}$ and $P=(3,6)$. Verify membership, calculate $[2]P$, $[3]P$, $[4]P$, and $[5]P$, and compare each result with the code. Checkpoint: the sequence is $(80,10)$, $(80,87)$, $(3,91)$, then $\mathcal O$; success means every nonidentity result satisfies the curve equation.
Case study 2 — review a toy ECDH exchange. Let Alice choose $a=2$ and Bob choose $b=3$ using base point $P$. Compute $A=aP$, $B=bP$, and both shared values $aB$ and $bA$. Because $P$ has order $5$, both parties obtain $6P=P=(3,6)$. Then list why a real protocol must add parameter and point validation, subgroup handling, authenticated public keys, a KDF, secure randomness, transcript binding, and constant-time code.
Hands-on exercise. Add tests for $[0]P=\mathcal O$, $P+(-P)=\mathcal O$, $[m+n]P=[m]P+[n]P$, and ladder agreement for every $0\le m,n\le 20$. Next, deliberately pass an off-curve point and confirm rejection. Success means all identities pass, all produced points validate, and invalid input cannot reach scalar multiplication.
Tiered follow-up. Recall: define nonsingularity and the identity. Derive: prove the vertical-pair case. Implement: add strict point serialization and parsing. Debug: find why reducing coordinates silently can accept a noncanonical encoding. Extend: compare affine operation counts with Jacobian-coordinate counts, without treating the toy code as production cryptography.
Choose the group and algorithm only after defining the domain, validation rules, threat model, and workload; never equate mathematical correctness with protocol security. A useful next step is to connect these finite-field operations to standardized curve encodings, subgroup structure, authenticated key exchange, and formally tested constant-time implementations.
Next in the Series
In Number-Theoretic Data Structures & Problem Patterns, we'll explore Combine arithmetic invariants with query and dynamic-programming structures..