Chapter Overview $$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 • (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)

• 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)...
• 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.    • 1) Form a line with P1 & P2
• 2) Intersect resulting line with EC
• 3) Reflect intersection point across X-axis for P3
• 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}$$. • 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)     (P1 + P2) + P3 = P1 + (P2 + P3)
• P1 + P2 = P2 + P1
• (Same intersection point)

• 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}$$
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}$$

• $$(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)
• 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 