Cryptography - Lecture 15 - Number Theory, Complexity Theory

1. Computing with Polynomials in GF(qⁿ)

• have seen arithmetic modulo a prime number GF(p)
• can also do arithmetic modulo q over polynomials of degree n
• this means for each term compute values mod q
• and also limit size of polynomials to degree n
• by reducing modulo some irreducible polynomial of degree n+1
• these also form a Galois Field GF(qⁿ)
• its elements are polynomials of degree (n-1) or lower
• a(x)=an-1xn-1+an-2xn-2+...+ax+a0
• most typically work in GF(2ⁿ), ie all coeffs are 0 or 1

2. Modulo Arithmetic with Polynomials

• can have residues for polynomials just as for integers
  • p(x)=q(x)d(x)+r(x)
  • and this is unique if deg[r(x)]<deg[d(x)]
• if r(x)=0, then d(x) divides p(x), or is a factor of p(x)
• usually chose d(x) to be an irreducible polynomial
• an irreducible polynomial d(x) is a 'prime' polynomial, it has no polynomial divisors other than itself and 1
• modulo reduction of p(x) consists of finding some r(x) st: p(x)=q(x)d(x)+r(x)
• ie. find how many times d(x) goes into p(x) and then work out the remainder r(x) which is the residue we want
• since this effectively means multiplying highest term by q(x) to equal highest term in p(x), and then "fixing up" the rest
• shortcut is to simply replace highest term by rest of the irreducible polynomial

3. Example GF(2³)

• in GF(2³) there are 8 elements:
• 0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1
• to compute remainder when d(x)=x3+x+1 can simply replace x3 with x+1
• see addition and multiplication tables below.

4. Polynomial Addition

• addition in GF(qⁿ) just involves summing equivalent terms in the polynomial modulo q
• this is simply XOR if q=2 (as it does for our purposes)
  • a(x)+b(x)=(an-1+bn-1)xn-1+...+(a11)x+(a0+b0)

• +	000	001	010	011	100	101	110	111
  0 = 000	000	001	010	011	100	101	110	111
  1 = 001	001	000	011	010	101	100	111	110
  x = 010	010	011	000	001	110	111	100	101
  x+1 = 011	011	010	001	000	111	110	101	100
  x2 = 100	100	101	110	111	000	001	010	011
  x2+1 = 101	101	100	111	110	001	000	011	010
  x2+x = 110	110	111	100	101	010	011	000	001
  x2+x+1 = 111	111	110	101	100	011	010	001	000

  Addition Table for GF(2³)
  Reproduced with permission from Seberry & Pieprzyk, Table 2.2, p26

5. Polynomial Addition Examples

• in GF(2³)

  (x+1) + (x2) = x2+x+1
   011 XOR 100 = 111
  
  (x+1) + (x2+1) = x2+x+2 = x2+x
   011 XOR 101   = 110
  

6. Polynomial Multiplication

• multiplication in GF(qⁿ) involves
  • multiplying the two polynomials together
  • cf longhand multiplication; here use shifts & XORs if q=2)
  • then finding the residue modulo a given irreducible polynomial of degree n

• ×	001	010	011	100	101	110	111
  1 = 001	001	010	011	100	101	110	111
  x = 010	010	100	110	011	001	111	110
  x+1 = 011	011	110	101	111	100	001	010
  x2 = 100	100	011	111	110	010	101	001
  x2+1 = 101	101	001	100	010	111	011	110
  x2+x = 110	110	111	001	101	011	010	100
  x2+x+1 = 111	111	101	010	001	110	100	011

  Multiplication Table for GF(2³) modulo x3+x+1
  Reproduced with permission from Seberry & Pieprzyk, Table 2.2, p26

7. Polynomial Multiplication Example

• in GF(2³) mod x3+x+1 in GF(2³)

  (x+1).(x+1) = x.(x+1) + 1.(x+1) = x2+x+x+1 = x2+2x+1 = x2+1
   011.011 = 011<1 XOR 011<0 = 110 XOR 011 = 101
  
  (x2+1).(x2+x) mod x3+x+1
       = x2.(x2+x) + 1.(x2+x) = x4+x3+x2+x
       = x.(x3+x+1) + 1.(x3+x+1) + (x+1)
       = x+1
   101.110 = 110<2 XOR 110<0 = 11000 XOR 110
       = 11110 mod 1011 = 11110 XOR 1011<1
       = 1000 mod 1011 = 1000 XOR 1011
       = 011
  

8. Working with Polynomials

• can adapt exponentiation, GCD, Inverse, and CRT algorithms for GF(qⁿ)
  • ø(p(x)) = 2n-1 since every poly except 0 is relatively prime to p(x)
• arithmetic in GF(qⁿ) can be much faster than integer arithmetic, especially if the irreducible polynomial is carefully chosen
• eg a fast implementation of GF(2¹²⁷) exists
• has both advantages and disadvantages for cryptography, calculations are faster, as are methods for breaking

9. Binary Representation of Polynomials in GF(2ⁿ)

• can write polynomials in GF(2ⁿ) as a sequence of bits
• each being a coefficient in it, vis a(x)=an-1an-2...a1a0
• eg. in GF(2³): x²+1 is 101; x²+x+1 is 111
• addition then becomes XOR of the binary representations
• eg. (x²+1) + (x²+x+1) = x; 101 XOR 111 = 010
• multiplication becomes shift & XOR (ie long multiplication)
• eg. (x+1).(x²+1) = x.(x²+1) + 1.(x²+1) = x³+x+x²+1 = x³+x²+x+1
  011.101 = (101)<1 XOR (101)<0 = 1010 XOR 101 = 1111
• polynomial modulo reduction by replacing highest power also comes down to shift & XOR
• eg. (x³+x²+x+1) mod (x³+x+1) = 1.(x³+x+1) + (x²) = x²
  1111 mod 1011 = 1111 XOR 1011 = 0100

10. Complexity Theory - A Potted Intro

• Complexity theory - study of how hard a problem is to solve in general
• allows classification of types of problems
• some problems intrinsically harder than others, eg
  • multiplying numbers O(n^(2))
  • multiplying matrices O(n^(2)(2n-1))
  • solving crossword O(26^(n))
  • recognizing primes O(n^(log log n))
• deal with worst case complexity
  • may on average be easier

11. Complexity Theory in Pictures

• can show the various types as complexity as follows:
  Complexity Classes

12. Complexity Theory - Some Terminolgy

• an instance of a problem is a particular case of a general problem
• the input length of a problem is the number n of symbols used to characterize a particular instance of it
• the order of a function f(n) - is some O(g(n)) of some function g(n) s.t.
  • f(n)<=c.|g(n)|, for all n>=0, for some c
• a polynomial time algorithm (P) is one which solves any instance of a particular problem in a length of time O(p(n)), where p is some polynomial on input length
• an exponential time algorithm (E) - is one whose solution time is not so bounded
• a non-deterministic polynomial time algorithm (NP) - is one for which any guess at the solution of an instance of the problem may be checked for validity in polynomial time
• NP-complete problems - are a subclass of NP problems for which it is known that if any such problem has a polynomial time solution, then all NP problems have polynomial solutions. These are thus the hardest NP problems
• Co-NP problems - are the complements of NP problems, to prove a guess at a solution of a Co-NP problem may well require an exhaustive search of the solution space

13. Complexity Theory and Cryptography

• for cryptography to work: en/decryption must be easy when you know the key, but hard when you dont
• basically by definition this makes cryptography an NP class problem
• that is: easy to check the answer when you know it (the P bit)
• hard to find it when you don't (the N bit)
• which suggests that NP problems could well be of interest in the design of cryptographic systems
• which leads into the concept of public key systems

14. Summary

• computing with polynomials
• some complexity theory basics

15. Exercises

1. Add the following polynomials:

   (x2+x+1) + (x4+x3+x2+1)
   (x3+x2+x) + (x4+x+1)
   (x4+x+1) + (x4+x3+x2+x+1)
   

2. Multiply the following polynomials, modulo the irreducible polynomial (x⁵+x²+1):

   (x2+1) × (x3+x2+1)
   (x3+1) × (x2+1)
   (x4+1) × (x3+x2+1)
   

3. Compute the following exponentiations using the "square and multiply" algorithm modulo the irreducible polynomial (x⁵+x²+1) (this works exactly the same for polynomials as for integers, just do polynomial additions, multiplications and modulo reductions):

   (x+1)13
   (x2+1)11
   (x3+1)6