Chapter Overview
Modular 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\))
Modular 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.
Modular 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\))
Distributivity of Modular Operations
  • Distributivity over add/multiply:
    • (a + b)⋅c = a⋅c + b⋅c
    • This is illustrated by example (left).
    • Modulus can be performed anytime.
Modular Division
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.
  • To compute prime field division: \(\frac{1}{n} = n^{p-2} \left(\bmod p\:\right)\)
Prime 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}_{11} = \left\{0,1,2,3,...,9,10\right\}\)
    • \(\mathbb{F}_{127} = \left\{0,1,2,3,...,125,126\right\}\)
  • Prime field \(\mathbb{F}_{p}\) is simply a set of integers from \(0\) to \(p-1\), where p is prime.
  • Addition/Multplication and their inverse operations are defined over all field elements.
  • Addition/Multplication have commutativity & distributivity properties.
Chapter Overview
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 (\(g\))
      • \(g\circ g\circ g...g\circ g\circ g = g^{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=g \circ g \circ g...g \circ g \circ g = g^{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)
Additive Groups in Prime Fields
    • 1) Closed group operation (\(+\) over \(\mathbb{F}_{p}\))
      • Addition over \(\mathbb{F}_{p}\)
      • Group operation is Associative & Distributive
    • 2) Generator group element (\(g\))
      • \(g+g+g...g+g+g = k*g = \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 in \(\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 in Additive Prime Groups
  • Discrete Log Problem:
    • \(\beta=g+g+g...g+g+g = k*g\)
      • 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 in 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\))
      • \(g \times g \times g...g \times g \times g = g^{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 in \(\mathbb{Z}_{p}^*\)
  • Discrete Log Problem:
    • \(\beta=g \times g \times g... g \times g \times g = g^{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)
Index-Calculus Solution for DL over \(\mathbb{Z}_{p}^*\)
  • 1) Significant fraction of \(\mathbb{Z}_{p}^*\) can be expressed by products from subset.
  • 2) Construct small prime factorbase to express group elements.
    • \(s=\left\{a_{1}, a_{2},...,a_{t}\right\}\)
  • 3) For random \(z\), try to factorize:
    • \(g^{z}=a_1^{s_{1}} \cdot a_2^{s_{2}} ...a_t^{s_{t}}\)
    • \(z=s_{1}\cdot\log_ga_{1}+s_{2}\cdot\log_ga_{2}...s_{t}\cdot\log_ga_{t}\)
    • Results in linear relationships. Solve for \(log_ga_{t}\).
  • 4) For random \(s\), try to factorize:
    • \(g^{s} \cdot g^{x}=a_1^{b_1} \cdot a_2^{b_2} ... a_t^{b_t}\)
    • \(x=b_{1}\cdot \log_{g}a_{1} + b_{2}\cdot \log_{g}a_{2} ... b_{t}\cdot \log_{g}a_{t} - s\)
  • 5) Index-Calculus implies 1040bit (group order) / 80bit (security)
    • Subexponential Complexity
Square and Multiply
  • Computing \( \beta=g^{k}\) from known \( k \) must be efficient
    • \( g^{26}=g^{11010} \)
      • Bitscan from left to right.
      • Value of Bit0 is 1: \( g \)
      • Value of Bit1 is 1: \( g^{2} \times g = g^{3} \)
      • Value of Bit2 is 0: \( (g^{3})^{2} = g^{6} \)
      • Value of Bit3 is 1: \( (g^{6})^{2} \times g = g^{13} \)
      • Value of Bit4 is 0: \( (g^{13})^{2} = g^{26} \)
    • 25 Group operations reduced to 6
    • \(O(\log n)\) Complexity
Pollard Rho Solution for General DL
  • 1) Random walk \(i,j\), find collisions for:
    • \( g^{i_1} \cdot \beta^{j_1}=g^{i_2} \cdot \beta^{j_2} \)
  • 2) When collision is found:
    • \( i_1+x\cdot j_1 = i_2 + x\cdot j_2 \:\:mod(\vert G \vert ) \)
    • \( x=\frac{i_2-i_1}{j_1-j_2}\:\:mod(\vert G \vert) \)
  • 3) 160bit (group order) / 80bit (security)
    • Intuition: Birthday attack, \(O(\sqrt{n})\) complexity
Chapter Overview
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)
Chapter Overview
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 \)
      • 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    \(\:)\)
  • \(|G| =\) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • \(\:p =\) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • 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.

    Necessarily even/odd, because scalar field order is prime (odd). For given x, both +/-y values valid, which are complements in the odd field order.
Chapter Overview