# CT30A8800 Secured communications

## Mathematics

• Some Cryptographic primitives are based on mathematics
• Mathematics is needed to understand how the primitives work
• Data is represented in numerical form rather than binary form
• Binary data is handled as positivive integers (mathematical integer, not datatype)
• The manipulation of data is conducted by mathematical functions
• Encrypted data = f(plain data)
• Modulus is used to keep the results of calculation in proper size
• $f(x)=g(x) mod 4$ guarantees that result of f(x) is 2 bits long

## Basics of number theory

• Number theory deals with the properties of integers
• Important features are divisibility and residue
• div function returns the integer part of division, mod function returns residue
• $\frac{5}{2}=2\frac{1}{2}$ $\mapsto$ 5 div 2 = 2 , 5 mod 2 = 1
• If b mod a = 0, then a divides b i.e. b is divisible with a
• i.e. there exists such integer k so that $b =a*k$
• denoted $a \mid b$

## Number theory: Prime numbers

• Number p (>0) is a prime number if it is divisible only with itself and 1
• Prime numbers are useded in various cryptographic primitives.
• Number that is not prime number is composite.
• composites can be represented as a product of prime numbers
• Dividing composite to product of primenumbers is called factorization
• Factorization is unique
• 54=2*27=2*3*9=2*3*3*3 = $2*3^{3}$

## Relatively prime

• two numbers are relatively prime (or coprime) if their common positive integer factor is 1 e.g. their greatest common divisor is 1
• gcd (p,q) = 1
• gcd = greatest common divisor (in finnish: syt = suurin yhteinen tekijä)
• Biggest integer number that is factor for both a and b
• if p is prime and $p>q$ then $gcd(p,q)=1$

∗ p and q are relatively prime to each other

• Can be calculated by using Euclidean algorithm.

## Euclidean algorithm

• Euclidean algorithm
• gcd (a,b)
• set a=q*b+r , where a>b, $q=a\: div\: b$ and r=a\: mod\: b
• repeat formula: $b=q'*r+r'$ , where $q'=b\: div\: r$ and $r'=b\: mod\: r$
• Until r'=0. Then value r in formula is the gcd for a and b

## Extended Euclidean algorithm

• For integers a and b, There exists integers s and t such that $a*s+b*t=gcd(a,b)$
• These values are needed often in modulus algebra
• s and t can be found by using extended euclidean algorithm
• Extended Euclidean algorithm
• solving s and t from formula: $as+bt=gcd(a,b)$
• Divide a with b → $a=q_{1}b+r_{1}$and continue as with Euclidean algorithm increasing the indexes
• form sequences $s_{0}=0,s_{1}=1,s_{j}=-q_{j-1}s_{j-1}+s_{j-2}$ and $t_{0}=1,t_{1}=0,t_{j}=-q_{j-1}t_{j-1}+t_{j-2}$
• The difference between s and t is just that initial values are reversed.
• The values s and t are the values from the sequences which have same index as the last quotient q (i.e last quotient value is not used)
• the last values that can be calculated for s and t will provide the value of a and b divided with the gcd.
• Algorithm is used to find congruences

## Number Theory: Modulus algebra

• “Clock arithmetics”: 5 hours after 9 it is 2 o'clock
• $9+5\equiv2\:(mod\:12)$ or $9+5\equiv_{12}2$
• congruence ($\equiv$) : $a\equiv b\:(mod\: n)$ a is congruent to b mod n
• same as: $a=b+kn$ ,where k is any integer
• Equivalency: x is equivalent to y : $x\equiv_{n}y$ , if $(x\: mod\: n)=(y\: mod\: n)\Longrightarrow x\equiv_{n}y$ if $(x-y)=k*n$ with any k
• Congruence behaves mostly like equality ($=$)

## Properties of congruence

• Associativity
$[a+(b+c)]\: mod\: n=[(a+b)+c]\: mod\: n$
$[a*(b*c)\: mod\: n]=[(a*b)*c]\: mod\: n$
• Commutativity $(a+b)\: mod\: n=(b+a)\: mod\: n$
$(a*b)\: mod\: n=(b*a)\: mod\: n$
• Distributivity $a*(b+c)]\: mod\: n=[(a*b)+(a*c)]\: mod\: n$
• Existence of identities $(a+0)\: mod\: n=a\: mod\: n=a\:\,\,\,\, if\,\: a
$(a*1)\: mod\: n=a\: mod\: n=a\:\,;\, if\,\: a
• Reducibility $(a+b)\: mod\: n=((a\: mod\: n)+(b\: mod\: n))\: mod\: n$
$(a*b)\: mod\: n=((a\: mod\: n)*(b\: mod\: n))\: mod\: n$
• Existence of inverse $a+(-a)\! mod\: n=0$
$a*(a^{-1})\: mod\: n=1\:\,\, iff\: a\neq0$
• addition, multiplication and subraction of modulus works normally
• if $a\equiv_{n}b$ and $c\equiv_{n}d$ then
$a+c\equiv_{n}b+d\rightarrow a\equiv_{n}b+d-c$
$a-c\equiv_{n}b-d$
$a*c\equiv_{n}b*d$

## Division in modulus n

• a can be divisor in mod n when gcd(a,n) = 1
• $2x\equiv_{5}4\rightarrow x\equiv2$(division can be done since gcd (2,5)=1)
• Fractions can be dealt as modulo inverses
$a^{-1}=\frac{1}{a}$
thus $\frac{a}{b}\, mod\, n$ is same as $\frac{a}{b}\, mod\, n$
• division if gcd(a,n) > 1
• let's try to solve x from $a*x\equiv_{n}b$ and gcd (a,n) =d, d >1
• if d does not divide b, then there is no solution!
• if $d\mid b$ you can try changing the formula to$(\frac{a}{d})*x\equiv\frac{b}{d}\, mod\,\frac{n}{d}$ , solve this new formula to obtain $x$
• solutions for x are $x_{0},x_{0}+\frac{n}{d},x_{0}2*(\frac{n}{d})$

## Inverse of modulo

• Inverse of a value is a value with which it is multiplied results 1
• $a^{-1}*a=1\Longrightarrow a*b\: mod\: m=1\Rightarrow a^{-1}mod\: m=b$
• Example: $13^{-1}mod\:55=17\Rightarrow13*17\: mod\:55=1$
• Finding inverse of modulo
• $a^{-1}\equiv s\:(mod\: n)\rightarrow\frac{1}{a}\equiv s\:(mod\: n)$thus gcd(a,n) should be 1 (a is divisor)
• since $a^{-1}*a=1\rightarrow a^{-1}*a\equiv1\, mod\, n$ if we denote $a^{-1}=s$ then we state that there exists value t such that $as+nt=1$,
• Use extended euclidean algorithm to solve the value s from the formula
• inverse is the value of s with same index as the last index of quotient q in extended euclidean
• Example: $13^{-1}mod\:55\rightarrow13*s+55*t=1$\\$55=4*13+3$$q_{1}=4$ \\$13=4*3+1$$q_{2}=4$\\$3=3*1+0$$q_{3}=3$
• last index of quotient q is 3
• sequences for s are: $s_{0}=0,s_{1}=1,s_{2}=-4_{q1}1_{s1}+0_{so}=-4,s_{3}=-4_{q2}-4_{s2}+1=17$
• $s_{3}=17$ and thus inverse of 13 mod (55) is 17
• sequences for t would be: $t_{0}=1,t_{1}=0,t_{2}=-4_{q1}0_{t1}+1_{to}=1,t_{3}=-4_{q2}1_{t2}+0_{t1}=-4$
• resulting 13*17+55(-4)=1 –> gcd (13,17) = 1

## Modular exponentation

• Exponentation can be divided to multiplication and then use multiplication rules to avoid using huge numbers
• example: $3^{5}mod\,5=(3^{3}*3^{2})\, mod\,5$
• $3\, mod\,5=3$
• $3^{2}mod\,5=9\, mod\,5=4$
• $3^{3}mod\,5=(3^{2}mod\,5*3\, mod\,5)\, mod\,5=4*3\, mod\,5=12\, mod\,5=2$
• $3^{5}mod\,5\,=(3^{2}mod\,5*3^{3}mod\,5)\, mod\,5\,=4*2\, mod\,5=3$
• Never have to work with number bigger than $n^{2}$,
• Useful as cryptography uses very big numbers which storage requires memory

## Chinese remainder theorem

• for $x\equiv a_{1}mod\, n_{1}$,$x\equiv a_{2}mod\, n_{2}$ ,$x\equiv a_{3}mod\, n_{3}$$x\equiv a_{k}mod\,$, with gcd$(n_{i},n_{j})=1$when $i\neq j$ There is a common unique solution for x in [0, n-1], where $n=n_{1}*n_{2}*...*n_{k}$
• the moduluses n are pairwise relatively prime
• Simple example: $x\equiv4\, mod\,7,x\equiv1\, mod\,6$
• $x=7k+4$ use this as value of x for $x\equiv1\, mod\,6$
• $7k+4\equiv1\, mod\,6\rightarrow7k\equiv-3\, mod\,6$
• $7mod\,6=1\rightarrow k\equiv3\, mod\,6\rightarrow k=6s+3$
• use value of k to first equation
• $x=7*(6s+3)+4=42s+25$ $\rightarrow x\equiv25\, mod\,42$e.g. x=25,67,109…
• $6*7=42$

## Euler's totient function

• $\phi(n)$ function (Euler's $\phi$ -function, totient function, Euler's totient function)
• returns the amount of numbers smaller than n that are relatively prime with n i.e. amount of integers smaller than n that has no common divisor with n
• $\phi(10)=4$ → 1,3,7,9 (2,4,6 and 8 has 2 as gcd with 10. gcd(5,10)=5)
• For prime p: $\phi(p)=p-1$
• Furthermore :$\phi(pq)=(p-1)(q-1)$ if p and q are primes
• $10=5*2$ (factorize 10) so p=5 and q= 2
$\phi(10)=\phi(5*2)=(5-1)(2-1)=4$
• $\phi(p^{r})=(1-\frac{1}{p})p^{r}$
• $\phi(3^{2})=(1-\frac{1}{3})*9=\frac{2}{3}*9=6$ (1,2,4,5,7,8)
• More generally$\phi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$ , where p are distinct primes dividing n i.e factorize n
• Example: $1000=2^{3}*5^{3}$$\rightarrow\phi(1000)=1000(1-\frac{1}{2})(1-\frac{1}{5})=40$

## Fermat's little and Euler's Theorem

• Fermat Little Theorem: $a^{p-1}\: mod\: p=1$ when p is prime and p does not divide a
$a^{p}\: mod\: p=a$ division with a gives: $a^{p-1}\: mod\: p=1$
• Euler's theorem: $a^{\phi(p)}\equiv_{p}1$ if gcd (a,p) = 1 e.g. a and p are relatively prime
• if p is prime then, euler's totient function for prime is p-1 $\phi(p)=p-1$
• When we combine this we see that Euler's theorem is actually generalisation of Fermat's theorem
• $a^{\phi(p)}\equiv_{p}1$ for prime is $a^{p-1}\equiv_{p}$

## Use of Fermat (or Euler) to find inverse on mod p

• x is inverse of a in mod p when: $ax\: mod\: p=1$
• Fermat theorem states $a^{p-1}\: mod\: p=1$ thus $ax\: mod\: p=a^{p-1}mod\: p$
• Divide both sides with a
$\rightarrow x=a^{p-2}\: mod\: p$

## Use of Fermat to help in big number modulus

• Example: Calculate $2^{3434309}mod\,101$
• $2^{3434309}\equiv_{101}(2^{100})^{34343}*2^{09}$
• From fermat theorem we get $\rightarrow2^{100}mod\,101=1$thus $1^{34343}*2^{9}\equiv_{101}2^{9}\rightarrow512\equiv_{101}=7$
• If you work with mod n, try to get $\phi(n)$ in exponent to ease calculations

## Discrete logarithm

• The discrete logarithm problem is to find i such that $g^{i}\equiv_{p}b$
• This is harder problem than factoring integer with same amount of digits.
• if $g^{i}\equiv_{p}b$ it can be said that i is the index of b (mod p), this can be stated as $i=ind_{g,p}(b)$
• Index calculus is similar to logarithmic calculus, thus indexes are also called as discrete logarithms.
• $ind\:(x*y)=ind\:(x)+ind\:(y)$
• $ind\:(x^{k})=k*ind\:(x)$

## Primitive root

• $f(x)=g^{x}mod\: p$, where p is prime and g is primitive root
• g is primitive root of p if $g,g^{2},g^{3},\ldots g^{p-1}\:(mod\: p)$ produce all the values between $1\ldots(p-1$
• if none of the power $i$ that are smaller than $\phi(p)$ do not produce $g^{i}\equiv_{p}1$ it means that g is primitive root of p
• Primitive root for prime p can be thus calculated by calculating factors of $\phi(p)$ and raising the potential root to all powers (mod p). Result may not be 1 except with value p-1.
• Is 5 primitive root mod (17) ?