Cryptography - Lecture 14 - Number Theory

1. Discrete Logarithms in GF(p)

• inverse problem to exponentiation is to find the discrete logarithm of a number modulo p
• find x where ax = b mod p
• eg. x = log₃ 4 mod 13 (ie x st. 3^x = 4 mod 13) has no answer
• eg. x = log ₂ 3 mod 13 = 4 by trying successive powers
• whilst exponentiation is relatively easy, finding discrete logarithms is generally a hard problem
• can show that if p is prime, then there always exists some a for which there is always a discrete logarithm for any b!=0
• successive powers of a "generate" the group mod p
• such an a is called a primitive root
• these are also relatively hard to find

2. Greatest Common Divisor

• a common problem in number theory is to determine the greatest common divisor(GCD)
• the GCD (a,b) of a and b is the largest number that divides evenly into both a and b
• often want this to prove that there are no common factors (except 1) and that the numbers are relatively prime

3. Euclid's GCD Algorithm

• Euclid's Algorithm is an efficient way to find the GCD (GCD) of two numbers a and n, given a<n
• uses fact that if a and b have divisor d then so does a-b, a-2b, ...
• Euclid's Algorithm is:

  GCD (a,n) is given by:
     let g0=n
         g1=a
         gi+1 = gi-1 mod gi  
     when gi=0 then (a,n) = gi-1 
  

4. GCD Example

• eg find (56,98)

     g0=98
     g1=56
     g2 = 98 mod 56 = 42
     g3 = 56 mod 42 = 14 
     g4 = 42 mod 14 = 0 
  hence
  (56,98)=14
  

• see Seberry & Pieprzyk 1/e Fig 2.2 p11 code for GCD alg

5. Inverses and Euclid's Extended GCD Routine

• another common problem is to find the inverse of a number
• ie in order to "divide" by it
• unlike normal integer arithmetic, sometimes an integer in modular arithmetic has a unique inverse
• a-1 is inverse of a mod n if a.a-1 = 1 mod n, where a,x in {0,n-1}
• eg 3.7 = 1 mod 10
• if GCD(a,n)=1 then the inverse always exists
• can extend Euclid's GCD Algorithm to find Inverses by keeping track of gi = ui.n + vi.a
• since GCD(a,n)=1 will find 1 = ui.n + vi.a giving us the inverse

6. Extended Euclid's Algorithm to find Inverses

• find inverse of a number a mod n (where (a,n)=1)

    Inverse(a,n) is given by:
      g0=n  u0=1  v0=0
      g1=a  u1=0  v1=1
    loop computing
      y = gi-1 div gi
      gi+1 = gi-1 - y.gi = gi-1 mod gi
      ui+1 = ui-1 - y.ui 
      vi+1 = vi-1 - y.vi 
   until gi=0
   at end Inverse(a,n) = vi-1 
  

7. Inverse Calculation Example

• to find Inverse(3,460):

  i          y          g          u          v          
  0          -          460        1          0          
  1          -          3          0          1          
  2          153        1          1          -153       
  3          3          0          -3         460        
  
  hence Inverse(3,460) = -153 = 307 mod 460
  

• see Seberry & Pieprzyk 1/e y Fig 2.3 p14 code for Inverse alg

8. Inverse Calculation Example

• to find Inverse(299,323):

  i     y     g     u     v       Difference Equation tracked
  0     -   323     1     0       323 = 1.323 + 0.299
  1     -   299     0     1       299 = 0.323 + 1.299
  2     1    24     1    -1        24 = 1.323 + -1.299
  3    12    11   -12    13        11 = -12.323 + 13.299
  4     2     2    25   -27         2 = 25.323 + -27.299
  5     5     1  -137   148         1 = -137.323 + 148.299   *** answer ***
  
  ie 148.299 = 137.323 + 1 = 1 mod 323
  gives 148 as inverse of 299 mod 323
  

9. Euler Totient Function ø(n)

• when doing arithmetic modulo n
• the complete set of residues is all numbers from 0..n-1
• the reduced set of residues is those which are relatively prime to n
  • eg for n=10,
  • the complete set of residues is {0,1,2,3,4,5,6,7,8,9}
  • the reduced set of residues is {1,3,7,9}
• the number of elements in the reduced set of residues is called the Euler Totient Function ø(n)
• there is no single formula for ø(n)
• but for various cases can count how many elements are excluded

10. Formulae for the Euler Totient Function ø(n)

• know have n-1 non-zero residues mod n
• remove all multiples of all factors of n to get ø(n)
• need to know all factors to compute ø(n)
• the following cases are simple:

  p (p prime)	ø(p) = p-1
  pr (p prime)	ø(p) = pr-1(p-1)
  p.q (p,q prime)	ø(p.q) = (p-1)(q-1)
  

• see Seberry & Pieprzyk 1/e y Table 2.1 p13

11. Fermat's and Euler's Theorems

• Fermat's Theorem
  • let p be a prime and gcd(a,p)=1 then
  • ap-1 mod p = 1
• several important theorems are based on ø(n)
• Euler's Theorem
  • a generalisation of Fermat's Theorem
  • for any number n and gcd(a,n)=1 then
  • aø(n) mod n = 1

12. Ways of Computing Inverses

• can now state several wyas to compute an inverses a-1 mod n
  1. if n is small simply search 1,...,n-1 until an a-1 is found with a.a-1 = 1 mod n
  2. if ø(n) is known, then from Euler's Theorem have
     • a-1 = aø(n)-1 mod n
  3. otherwise use Extended Euclid's algorithm for inverse

13. Primality Testing

• often need to find some very large prime numbers
• classic way of finding primes is to sieve for them by trial division
• ie. divide by all numbers (primes) in turn less than the sqrt of the number
• only works for small numbers
• hence because of the size of numbers used, must find primes by trial and error
• these primality tests use properties of primes eg:
  • an-1 = 1 mod n where GCD(a,n)=1
  • all primes numbers 'n' will satisfy this equation
  • some composite numbers will also satisfy the equation
  • such composites are called pseudo-primes
• these tests:
  • guess at a prime number 'n'
  • then take a large number (eg 100) of numbers 'a'
  • apply this test to each
  • if it fails the number is composite, otherwise it is is probably prime

14. Primality Testing

• There are a number of stronger tests which will accept fewer composites as prime than the above test. eg using the Jacobi function:

  (a)
  (-) (mod n) = a (n-1)/2 (mod n)
  (n)
  
  where
  
  (a)
  (-)	is the Jacobi function of a,n
  (n)
  

• whichever test is used, its repeated until are "virtually certain" the number is prime
• still a probabalistic test
• if then want to be absolutely sure, can do a slower "proof of primality"

15. Chinese Remainder Theorem

• can be used to speed up modulo computations
• when working modulo a product of numbers
• eg. mod N = p.q, p,q prime
• the Chinese Remainder theorem lets us work modulo p and q separately
• since computational cost is proportional to size, we speed up
• have several ways to do this
• essentially if want to compute M mod N
• then separately compute M1 mod p and M2 mod q and combine results to get answer

  M = [((M2 +q - M1)u mod q] p + M1
  	where
  p.u mod q = 1
  

• will see this later when doing RSA

16. Summary

• how to compute discrete logs, GCD, Inverses and ø(n)
• how large prime numbers are found

17. Exercises

1. Find the discrete log of:

   2x = 3 mod 5
   4x = 3 mod 7
   4x = 2 mod 13
   5x = 3 mod 7
   6x = 10 mod 11
   7x = 3 mod 13
   8x = 3 mod 11
   9x = 6 mod 11
   

2. Find the Greatest Common Divisor:

   GCD(65,91)
   GCD(102,238)
   GCD(110,154)
   GCD(171,285)
   GCD(185,259)
   

3. Find the Euler Totient Function ø(n) of:

   57
   61
   65
   79
   83
   85
   

4. Compute the Inverse of the following using any of (as appropriate):
   • exhaustive search
   • Euler's Theorem
   • Extended Euclid's Algorithm

   2 mod 11
   2 mod 15
   5 mod 7
   5 mod 17
   12 mod 35
   13 mod 45
   17 mod 199
   19 mod 193
   21 mod 197
   22 mod 199