Mod p vs. Mod q in Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) powers almost everything from HTTPS to cryptocurrencies. There is a distinction between mod p and mod q operations and I always forget, so I’ve written this post.

1. Core Mathematical Framework

ECC’s security rests upon two distinct mathematical structures:

1. The elliptic curve group E(F_p), defined over a finite field (mod p)
2. A cyclic subgroup of prime order q, where cryptographic operations take place

Consider mod p as defining our mathematical workspace (the field where points exist), while mod q governs our cryptographic operations (how we generate and use keys).

2. The Field of Definition (mod p)

Mathematical Foundation

• p is a large prime defining our finite field F_p
• E(F_p) is given by the Weierstrass equation: $$y^2 ≡ x^3 + ax + b (mod p)$$ where:
  • a, b ∈ F_p
  • 4a^3 + 27b^2 ≢ 0 (mod p) (ensuring non-singularity)
  • Points P = (x, y) have coordinates in F_p
  • O denotes the point at infinity (group identity)

Primality Requirement

• Prime fields F_p are essential because they:
  1. Provide optimal arithmetic performance
  2. Ensure F_p* is cyclic (crucial for point multiplication)
  3. Minimize potential cryptanalytic attacks
  4. Avoid the additional structure present in extension fields

3. The Cryptographic Subgroup (mod q)

Group Order and Structure

• By Hasse’s theorem: |#E(F_p) - (p + 1)| ≤ 2√p
• The curve order factors as: #E(F_p) = h × q where:
  • q is prime (the cryptographic subgroup order)
  • h is the cofactor (ideally 1 or small)

Security Requirements

• q must be:
  1. Large (≥ 256 bits for modern security)
  2. Prime (preventing Pohlig-Hellman attacks)
  3. Not equal to p (avoiding anomalous curves)
  4. Not a special form number (resisting specialized ECDLP attacks)

4. Operational Domain Mapping

5. Implementation Security

Critical Vulnerabilities

1. Invalid Point Validation

   • Always verify: $P \in E(F_p)$
   • Confirm: $[q]P = O$
   • Check: $P \neq O$

2. Timing Attack Prevention

   • Use constant-time algorithms
   • Prefer Montgomery ladder over double-and-add
   • Implement blinding techniques

3. Modular Arithmetic Pitfalls

   # INCORRECT - potential bias
   private_key = random_bytes(32)  # [0, 2^256-1]
    
   # CORRECT - uniform distribution
   private_key = random_int_modq()  # [1, q-1]

6. Real-World Parameters

Bitcoin (secp256k1)

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Curve25519

p = 2^255 - 19
q = 2^252 + 27742317777372353535851937790883648493

7. Historical Context

The distinction between mod p and mod q emerged from:

• Lenstra’s ECM work (1987)
• Koblitz and Miller’s concurrent ECC proposals (1985)
• Early implementation vulnerabilities in SSL/TLS

Further Reading

Further Reading

• NIST FIPS 186-5  for ECC standards.
• SafeCurves  for analyzing curve security.