notes/docs/lectures/cryptography/09_public_key_maths.md

Public Key Mathematics

• Recap: in rings and fields, multiplicative inverse might exist such that

a\cdot a^{-1} \equiv 1 \space (mod \space p)

• Modular inverse exists when gcd(a,p)=1
• For prime fields, gcd(a,p)=1, \forall a \neq 0 \in GF(p)

Euclidean Algorithm

• The Euclidean algorithm calculates the greatest common divisor of two numbers gcd(r_0, r_1)
  • This is the largest number that divides both r_0 and r_1
• If gcd(x,y)=1 then x and y are coprime (sometimes called relatively prime)
• The Euclidean algorithm is based around the fact:
  • gcd(r_0, r_1) = gcd(r_1, r_0 - r_1)

• Computing (x-y)\cdot gcd(r_0, r_1) is easier as it's a smaller number
• Doing this repeatedly is slow, we can use gcd(r_0,r_1) = gcd(r_1, r_0\space mod \space r_1)

Example

$r_0 = 57 \ r_1 = 12$

• At each step we convert r_0 and r_1 into the form r_0=q\cdot r_1 + r_2

r_0=q\cdot r_1 + r_2 \\57=4\cdot 12 + 9\\ r_1=q\cdot r_2 + r_3 \\ 12=1\cdot 9 + 3 \\ 9 = 3\cdot 3 + 0

• When the algorithm gets to 0, it is finished, therefore gcd(57,12)=3

Bézout’s Identity

• Bézout’s identity tells us that the greatest common divisor of two numbers can be expressed as the sum of multiples of these numbers
• gcd(r_0,r_1) = s\cdot r_0 + t\cdot r_1
  • e.g. gcd(99,20)=-1\cdot 99+5\cdot 20=1
  • gcd(141,50)=11\cdot 141+-31\cdot 50=1

Extended Euclidean Algorithm

• The extended Euclidean algorithm calculates the gcd(r_0,r_1) as normal, and in addition calculates s and t.

Euclidean Algorithm	Extended Euclidean Algorithm
r_0=q_1\cdot r_1+r_2	r_2=r_0-q_1\cdot r_1 \quad \rightarrow \quad r_2=s_2\cdot r_0-t_2\cdot r_1
r_1=q_2\cdot r_2+r_3	r_3=r_1-q_2\cdot r_2 \quad \rightarrow \quad r_3=s_3\cdot r_0-t_3\cdot r_1
r_2=q_3\cdot r_3+r_4	r_4=r_2-q_3\cdot r_3 \quad \rightarrow \quad r_4=s_4\cdot r_0-t_4\cdot r_1
…	…
r_{l-2}=q_{l-1}\cdot r_{l-1}+r_l	r_l=r_{l-2}-q_{l-1}\cdot r_{l-1} \quad \rightarrow \quad r_l=s_l\cdot r_0-t_l\cdot r_1
r_{l-1}=q_{l}\cdot r_{l}+0

Example

Formula

Modular Inverses

\begin{split}
& a\cdot a^{-1} \equiv 1 \mod n \\
& gcd(n,a) = s\cdot n + t\cdot a = 1 \\
& s\cdot n + t\cdot a = 1 \\
& s\cdot 0 + t\cdot a \equiv 1 \space mod \space n \\
& t\cdot a \equiv 1 \space mod \space n \\
& t \equiv a^{-1} \space mod \space n
\end{split}

Where t is our multiplicative inverse