InfoSec 3001 — Information Security from the Offensive Perspective

Step 236. A Taste of ECC: Addition on an Elliptic Curve — Adding Points to Build a Cipher

Step 236. A Taste of ECC: Addition on an Elliptic Curve — Adding Points to Build a Cipher

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★★☆ | Estimated time: 4 hours

Prerequisites: Step 227 (modular inverses — pow(x, -1, p) is the denominator in today’s slope formula), Step 235 (DH’s discrete logarithm problem).

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

  • What you need: Python 3 (measured: 3.12.14). Standard library only, nothing to install.
  • Caution: at first you’ll think "it’s addition, why is it so complicated?" That’s normal — today’s addition is addition over coordinates.

If RSA and DH are ciphers built from "exponentiation in the mod world," elliptic-curve cryptography (ECC) is a cipher built from "point addition on a curve." The grammar changes, but the trapdoor-function structure is the same — Q, the result of adding point P k times, is fast to compute, while finding k given only P and Q (ECDLP) is hard. And for this version of the discrete logarithm problem, no attack better than exponential time is known, so a much shorter key (256 bits ≈ RSA 3072 bits) delivers the same strength. Bitcoin signatures and modern TLS key exchange (ECDHE) are both this. Today you’ll implement point addition yourself and actually break a small curve.

1. Learning Objectives

By the end of this chapter, you will be able to:

  • Enumerate every point of an elliptic curve y² = x³ + ax + b (mod p) over a finite field
  • Connect the geometric meaning of point addition (secant/tangent) to the algebraic formulas
  • Implement a point-addition function using modular inverses and a double-and-add scalar multiplication
  • Confirm the cyclic structure of scalar multiplication (a point’s order) in output
  • Solve ECDLP by exhaustive search on a small curve, and explain why real curves are safe

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

Category Details
Language/environment Python 3 (measured: 3.12.14) — standard library only, nothing to install
Today’s commands pow(x, -1, p) (modular inverse), hand-built add() / mul()
Concepts needed Elliptic curves over finite fields, point addition, the point at infinity O, doubling, scalar multiplication, ECDLP
Today’s deliverable A point list + point-operation implementation + successful ECDLP exhaustive-search output

2-1. Elliptic Curves over Finite Fields — Not a Continuous Curve but a Set of Points

The elliptic curve y² = x³ + ax + b you saw in school is a smooth curve over the reals. What ECC uses is that equation moved into the mod p world (a finite field) — since x and y are sought only in 0~p-1, the curve becomes "a finite set of scattered points." Today’s curve is y² = x³ + 2x + 2 (mod 17). With only 18 points, you can see all of them by eye.

2-2. Point Addition — The Moment Geometry Becomes Rules

The addition rule on a real curve: find the third point where the line through P and Q meets the curve, and reflect it across the x-axis — that’s P + Q. For P + P (doubling), use the tangent at P. Moved to algebra, this geometric rule becomes the slope formulas:

P ≠ Q: s = (y2 - y1) / (x2 - x1)     (slope of the secant)
P = Q: s = (3x1² + a) / (2y1)        (slope of the tangent)
x3 = s² - x1 - x2,   y3 = s(x1 - x3) - y1

In the mod p world, every division is a modular inverse — the denominator gets a pow(denominator, -1, p). Add the special point the point at infinity O (the identity of addition, playing the role of 0), and the points form a structure closed under addition (a group).

2-3. ECDLP — ECC’s Trapdoor Function

Q = kP, the point P added k times, computes fast via double-and-add (even a 256-bit k takes under 256 internal operations). Conversely, finding k given P and Q is the ECDLP (elliptic-curve discrete logarithm problem). The mod-p discrete log (DH) has sub-exponential attacks (index calculus), but no such general attack is known for ECDLP — so the same security level comes from far smaller numbers. That is the entire reason for "ECC = short keys."

2-4. Real Curves Exist

Today’s mod-17 curve is a toy. Production uses standard curves — Bitcoin’s secp256k1, TLS’s P-256. With about 2²⁵⁶ points, exhaustive search is meaningless (even efficient attacks cost 2¹²⁸ operations), and the parameters are vetted public standards. Nobody designs their own curve — you use standard curves through libraries.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14. The curve is y² = x³ + 2x + 2 (mod 17).

3-1. Enumerating Every Point on the Curve

Plug x = 0~16 into the right-hand side and find the y values where it’s a perfect square (mod 17):

p, a, b = 17, 2, 2
points = []
for x in range(p):
    rhs = (x**3 + a * x + b) % p
    for y in range(p):
        if (y * y) % p == rhs:
            points.append((x, y))
print(f"point count: {len(points)} + the point at infinity O")
print(points)

point count: 18 + the point at infinity O
[(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13)]

How to read the output: three observations. ① Only 18 points — finite. ② Each x carries two y values ((5,1) and (5,16) — 16 ≡ -1 mod 17, i.e., reflections across the x-axis). ③ Some x values (1, 2, 4, …) have no points — cases where the right-hand side isn’t a square mod 17.

3-2. Implementing Point Addition

def add(P, Q, a=2, p=17):
    if P is None: return Q          # O + Q = Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None                  # P + (-P) = O
    if P == Q:                       # doubling: tangent slope
        s = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:                            # secant slope
        s = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (s * s - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return (x3, y3)

P, Q = (5, 1), (6, 3)
print("P + Q =", add(P, Q))
print("P + P =", add(P, P))          # doubling
print("P + O =", add(P, None))       # identity

P + Q = (10, 6)
P + P = (6, 3)
P + O = (5, 1)

How to read the output: both (10, 6) and (6, 3) are on 3-1’s list — addition results land back on the curve (it’s closed). pow(2 * y1, -1, p) is the denominator’s inverse — every division in the mod world is this one line (Step 227’s inverse, in use here).

3-3. Scalar Multiplication — Double-and-Add

Computing k·P as "add P k times" doesn’t scale for large k. Use binary expansion — 13P = 8P + 4P + P, doublings and additions only:

def mul(k, P, a=2, p=17):
    R = None
    while k:
        if k & 1:
            R = add(R, P, a, p)
        P = add(P, P, a, p)
        k >>= 1
    return R

for k in range(1, 20):
    print(f"{k:2d}*P =", mul(k, (5, 1)))

 1*P = (5, 1)
 2*P = (6, 3)
 3*P = (10, 6)
 4*P = (3, 1)
 5*P = (9, 16)
 6*P = (16, 13)
 7*P = (0, 6)
 8*P = (13, 7)
 9*P = (7, 6)
10*P = (7, 11)
11*P = (13, 10)
12*P = (0, 11)
13*P = (16, 4)
14*P = (9, 1)
15*P = (3, 16)
16*P = (10, 11)
17*P = (6, 14)
18*P = (5, 16)
19*P = None

How to read the output: 19·P is O (the point at infinity, here None) — meaning P’s order is 19, and from 20·P it cycles back to (5, 1). Addition over finitely many points must cycle. This cyclic structure is the ECC backbone, exactly parallel to "the cycle of exponentiation" (Step 227’s Euler’s theorem).

3-4. Breaking ECDLP — The Tragedy of a Small Curve

Say Q = 13P = (16, 4) is given and k is unknown. With only 18 points, exhaustive search:

Q_target = mul(13, (5, 1))         # = (16, 4)
for k in range(1, 20):
    if mul(k, (5, 1)) == Q_target:
        print("exhaustive search succeeded: k =", k)
        break

exhaustive search succeeded: k = 13

How to read it: solved instantly. Same structure as DH’s small p — a trapdoor function is a trap only "when the space is large enough." The real curve secp256k1 has about 2²⁵⁶ points, and the best general attack costs about 2¹²⁸ operations — to get the same 2¹²⁸ security from RSA you’d need roughly a 3072-bit key. 256 versus 3072: that is ECC’s reason to exist.

4. Missions & Exercises

Mission — A Mini ECC Key Exchange

  1. Complete an ECC version of DH on today’s curve (mod 17, P = (5, 1)) — Alice picks secret a, Bob picks secret b, they exchange public values aP and bP, and each computes abP to confirm the match (reuse 3-3’s mul)
  2. Attacker scenario: given only the public values aP and bP, recover a and b by exhaustive search and recompute the shared secret
  3. Include output confirming that doubling (the P == Q branch) actually executed at least once during the computation (hint: k’s binary expansion)

Exercises

Exercise 1. Explain why the point-addition formulas apply pow(denominator, -1, p) to the denominators 2y1 or x2 - x1, from the perspective of "division in the mod world."

Exercise 2. In 3-1’s list, what is the "opposite point" (additive inverse) of (5, 1)? And what point do the two add up to?

Exercise 3. How does the fact that P = (5, 1) has order 19 show up in 3-3’s output? Also answer why a large-order point is advantageous for cryptography.

Exercise 4. Explain why ECC achieves the same security as RSA with a shorter key, in terms of "differences in known attacks."

5. Model Answers & Completion Criteria

Mission Model Answer

P = (5, 1)
a_sec, b_sec = 7, 11               # Alice's and Bob's secrets
A_pub = mul(a_sec, P)              # (0, 6)
B_pub = mul(b_sec, P)              # (13, 10)
shared_A = mul(a_sec, B_pub)       # a(bP) = abP
shared_B = mul(b_sec, A_pub)       # b(aP) = abP
print("public values:", A_pub, B_pub)
print("shared secret:", shared_A, shared_B, "match:", shared_A == shared_B)

Measured result: public values (0, 6), (13, 10) — the shared secret for both is the value at the 77·P position in 3-3’s table, i.e., the same as mul(77, P) (77 = 7×11, and with order 19, 77 mod 19 = 1, so the result is (5, 1) — the cycle even enables cross-checks like this).

Attacker part: recover a = 7 with for k in range(1, 19): if mul(k, P) == A_pub: ..., then get the shared secret via mul(7, B_pub). To confirm doubling executed, attach a counter to add(P, P) inside mul, or point out that k = 13 (binary 1101) causes 3 doublings.

How to verify: ① the shared-secret match output. ② the successful exhaustive-search recovery output. ③ evidence that the doubling branch actually ran (a count or a binary-expansion explanation).

Exercise Answers

Answer 1. The mod p world has no division — "division" is multiplying by the pair that multiplies to 1 (the modular inverse). The slope’s denominator must be converted to its inverse and multiplied for the result to stay closed as point coordinates within 0~p-1. pow(denominator, -1, p) computes that inverse.

Answer 2. (5, 16) — 16 ≡ -1 (mod 17); the point with the same x and negated y is the additive inverse. Adding the two gives the point at infinity O (the x1 == x2 and (y1+y2) % p == 0 branch).

Answer 3. It shows in 19·P = O (None) with 1~18·P all listed distinctly. The larger the order, the larger the candidate space for k, making ECDLP exhaustive search harder — so base points P are chosen with large order (real curves use points whose order is a large near-prime).

Answer 4. RSA’s foundation (integer factorization) and DH’s foundation (finite-field discrete log) have known sub-exponential attacks (sieve methods, index calculus), so keys must be grown large. ECDLP has no such general attack — the best is square-root level (about 2¹²⁸) — so far smaller parameters (256 bits) reach the same security.

Completion Criteria Checklist

  • [ ] I wrote code that enumerates every point of an elliptic curve over a finite field
  • [ ] I can explain the secant/tangent formulas of point addition and the role of modular inverses
  • [ ] I implemented add() and double-and-add mul() myself
  • [ ] I confirmed the cycle (order) of scalar multiplication in output
  • [ ] I solved a small curve’s ECDLP by exhaustive search
  • [ ] I can explain ECC’s key-length advantage as a "difference in attack difficulty"
  • [ ] Mission: mini ECC key exchange + attacker recovery complete

6. Common Pitfalls & Fixes

Wall 1. ValueError: base is not invertible for the given modulus

Symptom: this error from pow(2 * y1, -1, p).
Cause: the denominator isn’t coprime with p — either p isn’t prime, or you tried to double a special point where 2 * y1 is 0 (mod p) (y1 = 0, a vertical tangent).
Fix: on today’s curve p = 17 is prime, so the denominator just needs to be nonzero. Doubling a point with y1 = 0 correctly yields O — add that branch to your implementation.

Wall 2. The addition result isn’t on the curve

Symptom: add(P, Q) returns coordinates not in 3-1’s list.
Cause: nine times out of ten, a missing mod — you skipped % p on s * s - x1 - x2, or left a negative number without % p (Python’s % on negatives returns a positive, so just add it).
Fix: check % p at every step (slope, x3, y3), and validate each result against the list — that list is today’s best test code.

Wall 3. Swapped the doubling and general-addition branches

Symptom: computing P + P with the secant formula and hitting pow(0, -1, p).
Cause: when P == Q, the denominator x2 - x1 is 0 and has no inverse — which is exactly why the tangent formula exists separately.
Fix: fix the branch order: ① O handling ② P + (-P) = O ③ P == Q (doubling) ④ general addition.

Wall 4. The order is 19, but why are there 18 points?

Symptom: 3-1’s 18 points and 3-3’s order 19 seem to disagree.
Cause: they don’t — including O, the total is 19 points (18 + the point at infinity), and on this curve a single P generates all 19.
Fix: don’t forget O when counting points. "Points of an elliptic curve over a finite field" always includes the point at infinity.

Wall 5. mul seems slower than k repeated additions

Symptom: with k = 13, you wonder why bother with binary expansion.
Cause: true within today’s range. The difference appears when k is 256 bits — repeated addition takes 2²⁵⁶ operations (impossible), double-and-add takes 256.
Fix: for now, verify correctness with small k (compare against repeated addition), and understand "why this method" in the worldview of large k.

7. Summary

Today’s Concepts

Concept One-line explanation
Elliptic curve over a finite field The finite set of points satisfying y² = x³ + ax + b (mod p)
Point addition Reflect the line’s (secant/tangent) intersection with the curve across the x-axis — computed with modular inverses
Point at infinity O The identity of addition (the role of 0) — always included in the point list
Doubling P + P — uses the tangent formula, branch required
Scalar multiplication k·P — double-and-add handles even 256-bit k in 256 operations
Order The minimal k with k·P = O — larger means a larger ECDLP candidate space
ECDLP Finding k from Q = kP — no general fast attack, so short keys are allowed

Today’s Commands & Code

Command What it does
pow(x, -1, p) Modular inverse — handles the slope formulas’ denominators
add(P, Q) (hand-built) Point addition — 4 branches: O / inverse / doubling / general
mul(k, P) (hand-built) Scalar multiplication — double-and-add
Point-enumeration double loop Collects every point on the curve — a validation list

An Instinct More Important Than Commands

ECC’s formulas look complicated, but the backbone is the same as Step 235 — one "easy to go, hard to come back" operation and a key exchange on top. All that changed is the stage, from modular multiplication to addition on a curve — and thanks to that, keys got ten-plus times shorter. Today’s experience of listing all 18 points and breaking them is your ground for trusting the vast point-ocean of secp256k1 — the structure is what you saw today; only the size differs.

Once every box is checked, Step 236 is complete.

← 이전 스텝
다음 스텝 →