Cryptography - Lecture 14 - Number Theory

Objectives

Preliminary Reading

Lecture Content

Number Theory cont

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

     This is the inverse problem to exponentiation. And here we see an example of a problem thats "easy" one way (raising a number to a power), but "hard" the other (finding what power a number is raised to giving the desired answer). Problems with this type of asymmetry are very rare, but are of critical usefulness in modern cryptography.

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

     Another common problem is to determine the "greatest common divisor", that is the largest number that divides into both a & b. Actually, a lot of the time we want to show that its 1, that is the two number a & b are relatively prime, with no factors in common.

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 
     

     Euclid's Algorithm is derived from the observation that if a & b have a common factor d (ie. a=m.d & b=n.d) then d is also a factor in any difference between them, vis: a-p.b = (m.d)-p.(n.d) = d.(m-p.n). Euclid's Algorithm keeps computing successive differences until it vanishes, at which point that divisor has been reached.

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

     Finding the multiplicative inverse is a common problem. Needed to do "division". An extension to Euclid's Algorithm can help us find it, by tracking gi = ui.n + vi.a. When have 1 = ui.n + vi.a, we have the inverse of a mod n as v_i.

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

     The reduced set of residues is important, because these are the values which are relatively prime to the modulus. The other values share some common factor with the modulus, which means that multiplying them by some values gives a multiple of the modulus, ie they are factors of zero, which is pretty nasty when multiplying. eg. 5.4 = 20 = 0 mod 10, so 5 & 4 are factors of zero. Knowing how many "non-zero" multipliers there are is important, when working out exponentiations for example.

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

      To work out ø(n), start with n-1 non-zero residues, then remove all factors of n, and all multiples of those factors. If n is prime, there are no factors, so ø(n)=n-1. If n=p.q, then remove all multiples of p les than n (ie q-1 of them), and all multiples of p (ie p-1 of) to get ø(n=p.q)=p.q-(q-1).p-(p-1).q-1=(p-1).(q-1). Can extend the same idea to get the general formula based on the prime factorisation of n. Hence need to know all factors to compute ø(n).

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

      These are a couple of important theorems concerning powers of an reduced residue. Its used both as one way to find inverses (see below), and also as the key theorem used in the RSA crypto system.

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

      Now have 3 ways to find inverses: search for it if n is (really) small. Use Euler's Theorem by writing it as a.b=1 mod n where b=aø(n)-1. Or use the Extended Euclid's Alg in the general case.

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

Summary

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

Exercises

1. 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
      

Additional References