View page as slide show

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<n
    (a*1)\: mod\: n=a\: mod\: n=a\:\,;\, if\,\: a<n
  • 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+3q_{1}=4 \\13=4*3+1q_{2}=4\\3=3*1+0q_{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})=1when 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\,42e.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=1thus 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) ?
Last modified: 2013/07/01 14:42