name: elliptic-curves description: This skill should be used when working with elliptic curve cryptography, implementing or debugging secp256k1 operations, understanding modular arithmetic and finite fields, or implementing signature schemes like ECDSA and Schnorr. Provides comprehensive knowledge of group theory foundations, curve mathematics, point multiplication algorithms, and cryptographic optimizations.
This skill provides deep knowledge of elliptic curve cryptography (ECC), with particular focus on the secp256k1 curve used in Bitcoin and Nostr, including the mathematical foundations and implementation considerations.
A group is a set G with a binary operation (often denoted · or +) satisfying:
A cyclic group is generated by repeatedly applying the operation to a single element (the generator). The order of a group is the number of elements.
Why groups matter in cryptography: The discrete logarithm problem—given g and gⁿ, find n—is computationally hard in certain groups, forming the security basis for ECC.
Modular arithmetic constrains calculations to a finite range [0, p-1] for some modulus p:
a ≡ b (mod p) means p divides (a - b)
Operations:
- Addition: (a + b) mod p
- Subtraction: (a - b + p) mod p
- Multiplication: (a × b) mod p
- Inverse: a⁻¹ where (a × a⁻¹) ≡ 1 (mod p)
Computing modular inverse:
A finite field GF(p) or 𝔽ₚ is a field with a finite number of elements where:
For cryptographic curves like secp256k1, the field is 𝔽ₚ where p is a 256-bit prime.
Key property: The non-zero elements of a finite field form a cyclic group under multiplication.
An elliptic curve over a finite field 𝔽ₚ is defined by the Weierstrass equation:
y² = x³ + ax + b (mod p)
The curve must satisfy the non-singularity condition: 4a³ + 27b² ≠ 0
A point P = (x, y) is on the curve if it satisfies the equation. The set of all points, plus a special "point at infinity" O (the identity element), forms an abelian group.
Point Addition (P + Q where P ≠ Q):
λ = (y₂ - y₁) / (x₂ - x₁) (mod p)
x₃ = λ² - x₁ - x₂ (mod p)
y₃ = λ(x₁ - x₃) - y₁ (mod p)
Point Doubling (P + P = 2P):
λ = (3x₁² + a) / (2y₁) (mod p)
x₃ = λ² - 2x₁ (mod p)
y₃ = λ(x₁ - x₃) - y₁ (mod p)
Point at Infinity: Acts as the identity element; P + O = P for all P.
Point Negation: -P = (x, -y) = (x, p - y)
secp256k1 is defined by SECG (Standards for Efficient Cryptography Group):
Curve equation: y² = x³ + 7 (a = 0, b = 7)
Prime modulus p:
0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2²⁵⁶ - 2³² - 977
Group order n:
0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
Generator point G:
Gx = 0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Cofactor h = 1
The special form of p enables fast reduction without general division:
For p = 2²⁵⁶ - 2³² - 977:
To reduce a 512-bit number c = c_high × 2²⁵⁶ + c_low:
c ≡ c_low + c_high × 2³² + c_high × 977 (mod p)
Scalar multiplication kP (computing P + P + ... + P, k times) is the core operation.
Input: k (scalar), P (point)
Output: kP
R = O (point at infinity)
for i from bit_length(k)-1 down to 0:
R = 2R # Point doubling
if bit i of k is 1:
R = R + P # Point addition
return R
Complexity: O(log k) point operations Vulnerability: Timing side-channels (different branches for 0/1 bits)
Constant-time algorithm that performs the same operations regardless of bit values:
Input: k (scalar), P (point)
Output: kP
R0 = O
R1 = P
for i from bit_length(k)-1 down to 0:
if bit i of k is 0:
R1 = R0 + R1
R0 = 2R0
else:
R0 = R0 + R1
R1 = 2R1
return R0
Advantage: Resistant to simple power analysis and timing attacks.
Precompute small multiples of P, then process w bits at a time:
w-NAF representation reduces additions by ~1/3 compared to binary
Precomputation table: [P, 3P, 5P, 7P, ...] for w=4
secp256k1 has an efficiently computable endomorphism φ where:
φ(x, y) = (βx, y) where β³ ≡ 1 (mod p)
φ(P) = λP where λ³ ≡ 1 (mod n)
This allows splitting scalar k into k₁ + k₂λ with smaller k₁, k₂, reducing operations by ~33-50%.
For computing k₁P₁ + k₂P₂ (common in signature verification):
Process both scalars simultaneously, combining operations
Reduces work compared to separate multiplications
Standard (x, y) representation. Requires modular inversion for each operation.
Represent (X:Y:Z) where x = X/Z, y = Y/Z:
Represent (X:Y:Z) where x = X/Z², y = Y/Z³:
For curves over GF(2ⁿ), optimized for binary field arithmetic.
Key Generation:
Private key: d (random integer in [1, n-1])
Public key: Q = dG
Signing message m:
1. Hash: e = H(m) truncated to curve order bit length
2. Random: k ∈ [1, n-1]
3. Compute: (x, y) = kG
4. Calculate: r = x mod n (if r = 0, restart with new k)
5. Calculate: s = k⁻¹(e + rd) mod n (if s = 0, restart)
6. Signature: (r, s)
Verification of signature (r, s) on message m:
1. Check: r, s ∈ [1, n-1]
2. Hash: e = H(m)
3. Compute: w = s⁻¹ mod n
4. Compute: u₁ = ew mod n, u₂ = rw mod n
5. Compute: (x, y) = u₁G + u₂Q
6. Valid if: r ≡ x (mod n)
Security considerations:
Simpler, more efficient, with provable security.
Signing message m:
1. Random: k ∈ [1, n-1]
2. Compute: R = kG
3. Challenge: e = H(R || Q || m)
4. Response: s = k + ed mod n
5. Signature: (R, s) or (r_x, s) where r_x is x-coordinate of R
Verification:
1. Compute: e = H(R || Q || m)
2. Check: sG = R + eQ
Advantages over ECDSA:
To prevent timing attacks:
// BAD: Timing leak
if secretBit == 1 {
doOperation()
}
// GOOD: Constant-time conditional
result = conditionalSelect(secretBit, value1, value0)
The Bitcoin Core library includes:
Given P and Q = kP, finding k is computationally infeasible.
Best known attacks:
For detailed implementations, see:
references/secp256k1-parameters.md - Full curve parametersreferences/algorithms.md - Detailed algorithm pseudocodereferences/security.md - Security analysis and attack vectors