Elliptic Curve Math Subtopics
  • Generalised Discrete Log
  • Generalised Cyclic Groups
  • Generalised DL Problem
  • Generalised DL security
  • Prime Fields \(\mathbb{F}_{p}\)
  • Operations over \(\mathbb{F}_{p}\)
  • Cyclic Groups over \(\mathbb{F}_{p}\)
  • Discrete Log over \(\mathbb{Z}_p^*\)
  • Discrete Log security
  • Elliptic Curve Discrete Log
  • EC operations over \(\mathbb{R}\)
  • EC operations over \(\mathbb{F}_{p}\)
  • Cyclic Point Groups
  • Elliptic Curve DL problem
  • Elliptic Curve DL security

Cyclic Groups

    • 1) Closed group operation ( \(\circ\) )
      • \( a \circ b = c \:,\:\: (a,b,c \in \mathbb{G}) \)
      • Group operation is Associative & Commutative
        • \( (a \circ b)\circ c=a\circ (b\circ c) \)
        • \(a\circ b=b\circ a\)

    • 2) Generator group element (\(\alpha\))
      • \(a\circ\alpha\circ\alpha...\alpha\circ\alpha\circ\alpha = \alpha^{k} = b \in \mathbb{G}\)
      • Finite \( \lvert \mathbb{G} \rvert \) number of elements in group \(\mathbb{G}\)

    • 3) Neutral group element (\(n\))
      • \(a\circ n=a\)

    • 4) Each group element has an inverse
      • \(a\circ a^{-1}=1, \: b\circ b^{-1}=1, \: c\circ c^{-1}=1\)
      • \(a^{-1}, \: b^{-1}, \: c^{-1}, ... \in \mathbb{G}\)
Generalised Discrete Log Problem
  • Discrete Log Problem for Cyclic Groups:

    • \(\beta=\alpha\circ\alpha\circ\alpha...\alpha\circ\alpha\circ\alpha = \alpha^{k} \)
      • Given \(\beta\), solve for \(k\)
      • Problem must be hard for large \( \lvert\mathbb{G}\rvert \)

    • General discrete log solutions apply:
      • Pollard Rho, \(O(\sqrt{ \lvert\mathbb{G}\rvert })\)
        • 160bit (group order) / 80bit (security)
        • 256bit (group order) / 128bit (security)
Elliptic Curve Math Subtopics
  • Generalised Discrete Log
  • Generalised Cyclic Groups
  • Generalised DL Problem
  • Generalised DL security
  • Prime Fields \(\mathbb{F}_{p}\)
  • Operations over \(\mathbb{F}_{p}\)
  • Cyclic Groups over \(\mathbb{F}_{p}\)
  • Discrete Log over \(\mathbb{Z}_p^*\)
  • Discrete Log security
  • Elliptic Curve Discrete Log
  • EC operations over \(\mathbb{R}\)
  • EC operations over \(\mathbb{F}_{p}\)
  • Cyclic Point Groups
  • Elliptic Curve DL problem
  • Elliptic Curve DL security

Introduction to Finite Fields
  • \(\mathbb{F}_{p} = \left\{0,1,2,...,p-1\right\}\)

  • Examples:
    • \(\mathbb{F}_{7} = \left\{0,1,2,3,4,5,6\right\}\)
    • \(\mathbb{F}_{21} = \left\{0,1,2,3,...,19,20\right\}\)
    • \(\mathbb{F}_{127} = \left\{0,1,2,3,...,125,126\right\}\)
  • Finite field \(\mathbb{F}_{p}\) is simply a set of integers from \(0\) to \(p-1\).
Finite Field Addition
\(5+8=1\:\left(\bmod 12\:\right)\)
  • Imagine all numbers of finite field \(\mathbb{F}_{12}\) wrapped around a circle, like a clock.
  • For every addition operation, move the needle n steps clockwise.
  • This is equivalent to taking the remainder if the division: (5 + 8)/12 = 13/12 = 1 Remainder 1
  • Commutivity (\(a + b = b + a\)) and Associativity ( \((a+b)+c = (a+b)+c\) )
Finite Field Subtraction
\(4 - 19 = 2 \:\left(\bmod 17\:\right)\)
  • For a subtractive operation, simply move the needle n steps counter-clockwise.
  • In our example above, we first move 4 ticks clockwise (positive) then 19 ticks counter-clockwise (negative) to arrive at 2.
Finite Field Multiplication
\(4 \cdot 5 = 3 \:\left(\bmod 17\:\right)\)
  • \(4 \cdot 5 = +20\), so we simply move the needle by +20 ticks clockwise and arrive at 3.
  • Commutivity (\(a \times b = b \times a\)) and Associativity ( \((a \times b)\times c = a\times (b\times c) \) )
Distributivity of Finite Field Operations
  • Distributivity over add/multiply:
    • (a + b)⋅c = a⋅c + b⋅c
    • This is illustrated by example (left).
    • Modulus can be performed anytime.

Finite Field Exponentiation
\(2^{5}=15\:\left(\bmod 17\:\right)\)
  • \(2^{5}=32\), so we move the needle by +32 ticks clockwise and arrive at 15.
  • Associativity: \( (a^{b})^{c} = (a^{c})^{b}\), no proof provided.
Finite Field Division
Division
Multiplication Table
  • \(2/4=2\:\left(\bmod 6\:\right)\)
  • \(3/5=4\:\left(\bmod 17\:\right)\)
  • \(2=4 \cdot 2\:\left(\bmod 6\:\right)\)
  • \(3=5 \cdot 4\:\left(\bmod 17\:\right)\)
Division over \(\mathbb{F}_{p}\) could (theoretically) be performed by maintaining
a multiplication table for all pairs of \(\mathbb{F}_{p}\).
  • Division can simply be defined as the inverse of multiplication (multiplication tables).
  • However, for prime field \(\mathbb{F}_{p}\), where P is prime, there is an easy way to compute division ...
  • The Extended Euclidean algorithm is a standard method for modular division, but is more involved.
Division over over Prime Fields
Fermat's little theorem
For prime field \(\mathbb{F}_{p}\)
  • Where p is prime:
  • \(n^{p-1} = 1\left(\bmod p\:\right)\)
  • \(\frac{1}{n} = n^{-1}\left(\bmod p\:\right)\)
  • \(\frac{1}{n} = n^{-1}\cdot n^{p-1} = n^{p-2} \left(\bmod p\:\right)\)
Since this is equal to one, we can apply to the division equation:                                           
  • Fermat’s little theorem is valid for all prime fields \(\mathbb{F}_{p}\), where p is prime.
  • We use Fermat’s little theorem to derive division for prime fields.
  • To compute prime field division: \(\frac{1}{n} = n^{p-2} \left(\bmod p\:\right)\)
Additive Groups over Prime Fields

    • 1) Closed group operation (\(+\) over \(\mathbb{F}_{p}\))
      • Addition over \(\mathbb{F}_{p}\)
      • Group operation is Associative & Distributive

    • 2) Generator group element (\(\alpha\))
      • \(\alpha+\alpha+\alpha...\alpha+\alpha+\alpha = k*\alpha = \beta \in \mathbb{G}\)
      • Finite elements in cyclical \(\mathbb{G}\)

    • 3) Neutral group element (0)
      • \(\alpha+0 = \alpha\)

    • 4) Group element inverse (\(-\beta)\)
      • \(\beta+(-\beta) = 0\)
Additive Group over \(\mathbb{F}_{11}\)

    • 1) Closed group operation (\(+\) over \(\mathbb{F}_{11}\))
      • Addition over \(\mathbb{F}_{11}\)
      • Group operation is Associative & Distributive

    • 2) Generator group element (2)
      • \(2+2+2...2+2+2 = k*2 = \beta \in \mathbb{G}\)
      • Group order \(\lvert\mathbb{G}\rvert\)= 11
      • \(\mathbb{G}=\left\{2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 0\right\}\)

    • 3) Neutral group element (0)
      • \(0\in\mathbb{G}\)

    • 4) Group element inverse (\(-\beta)\)
      • (+2/-2), (+4/-4), (+6/-6)...
      • (+2/+9), (+4/+7), (+6/+5)...
Disrete Log over Additive Prime Groups
  • Discrete Log Problem:

    • \(\beta=\alpha+\alpha+\alpha...\alpha+\alpha+\alpha = k*\alpha\)
      • Given \(\beta\), solve for \(k\)
      • However, for addititive prime groups, the solution is trivial.
        • \(k=\frac{\beta}{\alpha} \:(mod\:p)\)
        • \(k=\beta\cdot\alpha^{p-2} \:(mod\:p) \)
Multiplicative Groups over Prime Fields \( \mathbb{Z}_p^* \)

    • 1) Closed group operation (\(\times\) over \(\mathbb{F}_{p}\))
      • Multiplication over \(\mathbb{F}_{p}\)
      • Multiplication is Associative & Commutative

    • 2) Generator group element (\(\alpha\))
      • \(\alpha\times\alpha\times\alpha...\alpha\times\alpha\times\alpha = \alpha^{k} = \beta \in \mathbb{Z}_p^* \)
      • Finite elements in cyclical \( \mathbb{Z}_p^* \)

    • 3) Neutral group element (1)
      • \(\beta\times1=\beta\)

    • 4) Group element inverse \(\beta^{-1}\)
      • \(\beta\times\beta^{-1}=1\)
Multiplicative Group \( \mathbb{Z}_{11}^* \)

    • 1) Closed group operation (\(\times\) over \(\ \mathbb{Z}_{11}^* \))
      • Multiplication over \(\mathbb{F}_{p}\)
      • Multiplication is Associative & Commutative

    • 2) Generator group element (2)
      • \(2\times2\times2...2\times2\times2 = 2^{k} = \beta \in \mathbb{Z}_11^* \)
      • Group order \(\lvert\mathbb{Z}_{11}^*\rvert\)= 10
      • \(\mathbb{Z}_{11}^*=\left\{2, 4, 8, 5, 10, 9, 7, 3, 6, 1\right\}\)

    • 3) Neutral group element (1)
      • \(1\in\mathbb{Z}_{11}^*\)

    • 4) Group element inverse \(\beta^{-1}\)
      • \((2, 2^{9}), (4, 2^8), (8, 2^7)...\)
Disrete Log over \(\mathbb{Z}_{p}^*\)
  • Discrete Log Problem:

    • \(\beta=\alpha\times\alpha\times\alpha...\alpha\times\alpha\times\alpha = \alpha^{k} \)
      • Given \(\beta\), solve for \(k\)
      • \(k=\log_{\alpha}\beta \:(mod\:p) \)

      • Hard for large \( \lvert\mathbb{Z}_{p}^*\rvert \)
      • General discrete log solutions apply \(O(\sqrt{ \lvert\mathbb{Z}_{11}^*\rvert })\)

    • However, faster solutions are known for multiplicative groups \(\mathbb{Z}_{p}^*\):
      • Index-Calculus method
        • 1040bit (group order) / 80bit (security)
      • Comparison: General discrete log method
        • 160bit (group order) / 80bit (security)
Square and Multiply
  • Computing \( \beta=\alpha^{k}\) from known \( k \) must be efficient

    • \( \alpha^{26}=\alpha^{11010} \)
      • Bitscan from left to right.
      • Value of Bit0 is 1: \( \alpha \)
      • Value of Bit1 is 1: \( \alpha^{2} \times \alpha = \alpha^{3} \)
      • Value of Bit2 is 0: \( (\alpha^{3})^{2} = \alpha^{6} \)
      • Value of Bit3 is 1: \( (\alpha^{6})^{2} \times \alpha = \alpha^{13} \)
      • Value of Bit4 is 0: \( (\alpha^{13})^{2} = \alpha^{26} \)

    • 25 Group operations reduced to 6
    • \(O(\log n)\) Complexity
Elliptic Curve Math Subtopics
  • Generalised Discrete Log
  • Generalised Cyclic Groups
  • Generalised DL Problem
  • Generalised DL security
  • Prime Fields \(\mathbb{F}_{p}\)
  • Operations over \(\mathbb{F}_{p}\)
  • Cyclic Groups over \(\mathbb{F}_{p}\)
  • Discrete Log over \(\mathbb{Z}_p^*\)
  • Discrete Log security
  • Elliptic Curve Discrete Log
  • EC operations over \(\mathbb{R}\)
  • EC operations over \(\mathbb{F}_{p}\)
  • Cyclic Point Groups
  • Elliptic Curve DL problem
  • Elliptic Curve DL security

Ellipic Curves over Real Numbers
Curve shown: \(y^{2}=x^{3}+7\)
  • Elliptic curve general form:
  • \(y^{2}=ax^{3}+bx+c\)

  • The secp256k1 curve form:
  • \(y^{2}=x^{3}+7\)

  • Elliptic curve points:
  • EC-Point P(x,y)on the elliptic curve fulfills the its curve equation.

EC-Point Addition over Real Numbers
  • 1) Form a line with P1 & P2
  • 2) Intersect resulting line with EC
  • 3) Reflect intersection point across X-axis for P3
EC-Point Addition (Computation)
  • For an elliptic curve of form:
    • \(y^{2}=ax^{3}+bx+c\)

  • Computation of \(P_{3} = P_{1} + P_{2}\)
    • \(P_{3}(x_{3},y_{3}) = P_{1}(x_{1},y_{1}) + P_{2}(x_{2},y_{2})\)
      • \(s = \frac{y_{2}-y_{1}}{x_{2}-x_{1}}\) for \(x_{1} \neq x_{2}\)
      • \(x_{3} = s^{2}-x_{1}-x_{2}\)
      • \(y_{3}=s(x_{1}-x_{3})-y_{1}\)
  • The equations shown describe EC-point addition where \(x_{1} \neq x_{2}\).
EC Point Addition with Infinity
  • The Infinity Point:
  • The (Inf/Inf) point is defined as a point which is infinitely far away in the direction of the y-axis.

  • Therefore, we can add a point P1 to the infinity point simply by connecting a vertical line through P1.

  • \( P_{1}(x_{1},y_{1}) + (Inf/Inf) = P_{1}(x_{1},y_{1}) \)
  • \( P_{1}(x_{1},y_{1}) + P_{2}(x_{1},-y_{1}) = (Inf/Inf) \)
Scalar x EC Point
\(P_{3} = P_{1} + P_{1} = 2 \cdot P_{1}\)
  • Scalar multiplication of an EC point P
    • s ⋅ P equals adding P to itself s times.

  • Point(x,y) + Point(x,y)
    • Consider Line L'(P1,P2).
    • Converges to tangent of P1, as P1 = P2.
    • Computation of P3 = P1 + P1:
      • \(P_{3}(x_{3},y_{3}) = 2 \cdot P_{1}(x_{1},y_{1})\)
      • \(s =\frac{(3x_{1}^{2}+a)}{2y_{1}}\)
      • \(x_{3} =s^{2}-2x_{1}\)
      • \(y_{3} =s(x_{1}-x_{3})-y_{1}\)

  • Distributivity:
    • (a + b)⋅C = a⋅C + b⋅C
    • (Can be proved algebraically)
Commutivity/Associativity of Point Addition

(P1 + P2) + P3 = P1 + (P2 + P3)
  • EC point addition commutivity
    • P1 + P2 = P2 + P1
    • (Same intersection point)

  • EC point addition associativity
    • Order of addition doesn't change result.
    • Associativity proof is rather involved.
      • (P1 + P2) + P3 = P1 + (P2 + P3)
      • (Associativity can be observed in example)

Elliptic Curve Math Subtopics
  • Prime Fields \(\mathbb{F}_{p}\)
  • a + b over \(\mathbb{F}_{p}\)
  • a - b over \(\mathbb{F}_{p}\)
  • a ⋅ b over \(\mathbb{F}_{p}\)
  • (a+b)⋅c = a⋅c + b⋅c
  • a^b over \(\mathbb{F}_{p}\)
  • a/b over \(\mathbb{F}_{p}\)
  • Elliptic Curves (EC) over \(\mathbb{R}\)
  • EC-Point P over \(\mathbb{R}\)
  • A + B over \(\mathbb{R}\)
  • a ⋅ B over \(\mathbb{R}\)
  • (a+b)⋅C = a⋅C + b⋅C
  • EC over Prime Fields \(\mathbb{F}_{p}\)
  • EC-Point P over \(\mathbb{F}_{p}\)
  • A + B over \(\mathbb{F}_{p}\)
  • a ⋅ B over \(\mathbb{F}_{p}\)
  • (a+b)⋅C = a⋅C + b⋅C

  • Bitcoin Keys:
  • s ⋅ G over secp256k1
Elliptic Curves over \( \mathbb{F}_{p} \)

\( y^{2}=x^{3}+7\) over \( \mathbb{F}_{29} \)
  • Point on elliptic curve over \( \mathbb{F}_{p} \)
    • Point coordinates fulfill following equation:
    • \( y^{2}=ax^{3}+bx^{2}+c\:(mod\:P)\)

  • Example EC points:
    • \( y^{2}=x^{3}+7\) over \( \mathbb{F}_{29} \)
    • \( P_{1}\left(3,18\right) \):
      • \(18^{2} = 3^{3}+7\:(mod\:29) =5 \>\> \) ✓
    • \( P_{2}\left(23,20\right) \):
      • \(20^{2} = 23^{3}+7\:(mod\:29) =23 \>\> \) ✓
    • Note: Elliptic curve plots are a set of non-continuous points since finite fields themselves are non-continuous.
EC-Point Addition over \( \mathbb{F}_{p} \)
  • EC-Point Addition over
    Reals \(\mathbb{R}\):

  • Addition where x1 != x2:
  • \( s = \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \)
  • \( x_{3} = s^{2}-x_{1}-x_{2} \)
  • \( y_{3} = s\:(x_{1}-x_{3})-y_{1} \)

  • Addition where P1 = P2:
  • \( s =\frac{(3x_{1}^{2}+a)}{2y_{1}} \)
  • \( x_{3} =s^{2}-2x_{1} \)
  • \( y_{3} =s(x_{1}-x_{3})-y_{1} \)

  • Addition with infinity:
  • \( (x_{1},y_{1}) + (\infty , \infty) = (x_{1},-y_{1}) \)
  • EC-Point Addition over Prime \( \mathbb{F}_{p} \) :
  • ← EC-point addition equations over \( \mathbb{R} \) apply to EC point addition over prime \( \mathbb{F}_{p} \).

  • Example:

  • \(P_{3}\left(x_{3},y_{3}\right)=P_{1}\left(3,18\right)+P_{2}\left(23,20\right)\)

  • \(s = \frac{20-18}{23-3} =2\cdot20^{29-2} \>(mod\:29) = 3\)
  • \(x_{3} = 3^{2}-23-3\:(mod\:29) = 12\)
  • \(y_{3} = 3\cdot(3-12)-18\:(mod\:29)=13\)

\(y^{2}=x^{3}+7\) over \(\mathbb{F}_{29}\)

Elliptic Curve Point Groups (I)
\( y^{2}=x^{3}+7\) over \( \mathbb{F}_{29} \)
  • Symmetry: Each point P(x,y) has an inverse P(x,-y)
    • \(P(x,y)+P(x,-y)=(Inf/Inf)\)
    • Same relationship as over \(\mathbb{R}\)

  • Points form a cyclic point group
    • \(1 \circ G\)
    • \(2 \circ G\)
    • \(3 \circ G\)
    • \(...\)
    • \( \lvert \mathbb{G} \rvert \circ G = (Inf,Inf) \)
    • (Proof of cyclic behaviour omitted)
Elliptic Curve Point Groups (II)

    • 1) Closed group operation (Point addition)
      • EC point addition over \(\mathbb{F}_p\)
      • EC point addition is Associative & Commutative

    • 2) Generator group element (\( G \))
      • \(G+G+G...G+G+G = s \circ G = P \in \mathbb{G}\)
      • Finite number \(\lvert\mathbb{G}\rvert\) of elements in cyclical group \(\mathbb{G}\)

    • 3) Neutral group element (inf/inf)
      • \(P + (inf,inf)=P\)

    • 4) Group element inverse
      • \(P(x,y)+P(x,-y)=(inf,inf)\)
Disrete Log over Elliptic Curves
  • Discrete Log Problem:

    • \( P=G+G+G...G+G+G = k \circ G \)
      • Given \(P\), solve for \(k\)
      • \( \lvert\mathbb{G}\rvert \) is governed by Hasse's bound (approx. range of prime p)
      • Only general discrete log solutions are known for Elliptic Curves \(O(\sqrt{ \lvert\mathbb{G}\rvert })\)
        • 160bit (group order) / 80bit (security)
        • 256bit (group order) / 128bit (security)
        • 512bit (group order) / 256bit (security)

      • In Comparison: Index-calculus(DH, DSA, Elgamal), Factorization(RSA)
        • 1040bit (group order) / 80bit (security)
        • 3072bit (group order) / 128bit (security)
        • 15360bit (group order) / 256bit (security)
Double and Add
  • Computing \( P=k \circ G \) from known \( k \) must be efficient

    • \( 26 \circ G = {11010} \circ G \)
      • Bitscan from left to right.
      • Value of Bit0 is 1: \( \:\: G \)
      • Value of Bit1 is 1: \( \:\:2 \circ G + G = 3 \circ G \)
      • Value of Bit2 is 0: \( \:\:2 \circ 3G = 6 \circ G \)
      • Value of Bit3 is 1: \( \:\:2 \circ 6G + G = 13 \circ G \)
      • Value of Bit4 is 0: \( \:\:2 \circ 13G = 26 \circ G \)

    • 25 Group operations reduced to 6
    • \(O(\log n)\) Complexity
Bitcoin Private & Public Keys
  • The secp256k1 EC point group:
  • \(y^{2}=x^{3}+7\) over \(\mathbb{F}_{p}\) where \(p = 2^{256} - 2^{32} - 977\)
  • \(G = \:(\) 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798,
    \(\:\:\:\:\:\:\:\:\:\:\:\:\) 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
    \(\:)\)
  • \(n =\) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • Bitcoin private & public keys:
  • \(P = k \circ G\)
  • (Private key scalar \(s\) is chosen, secp256k1-point \(P\) is the public key)
  • The secp256k1 EC-Point Group is used to generate Bitcoin private/public keys.
Bitcoin Public Key Point Serialisation
  • ➊ Uncompressed Public Key Point
  • The uncompressed public key point directly represents both x and y-coordinates.

  • ➋ Compressed Public Key Point
  • The compressed public key point implies its y-coordinate from its x coordinate.

    A compressed public key begins with 0x02/0x03 to imply an even/odd y-coordinate.
Elliptic Curve Math Subtopics
  • Generalised Discrete Log
  • Generalised Cyclic Groups
  • Generalised DL Problem
  • Generalised DL security
  • Prime Fields \(\mathbb{F}_{p}\)
  • Operations over \(\mathbb{F}_{p}\)
  • Cyclic Groups over \(\mathbb{F}_{p}\)
  • Discrete Log over \(\mathbb{Z}_p^*\)
  • Discrete Log security
  • Elliptic Curve Discrete Log
  • EC operations over \(\mathbb{R}\)
  • EC operations over \(\mathbb{F}_{p}\)
  • Cyclic Point Groups
  • Elliptic Curve DL problem
  • Elliptic Curve DL security