Cryptographic

Question1: (2 marks) Evaluate in GF (2⁸) with m(x) = x⁸ + x⁴ + x³ + x + 1:

1. 
   {02} · ({01} + {03}) · {04}
   
2. 
   ({88} × {04} + {E9}) · {03}
   

Question2: (2 marks) A left n-bit circular shift can be used to permute bit strings in cryptographic applications. For example the bit string 100 can be circularly shifted:

• 
  1-bit left by computing: 100 ×(010) mod (1001)
  
• 
  2-bits left by computing: 100 ×(100) mod (1001)
  

Represent the following left n-bit circular shifts as a binary computa- tion and evaluate the computation.

1. 
   left 3-bit circular shift on 11001.
   
2. 
   left 5-bit circular shift on C7.
   

Question3: (2 marks) The Diffie-Hellman Key Exchange Protocol involves estab- lishing a secret key s = g^ab mod p where p is prime and g is a primitive root of p. How many primitive roots (different values of g) are there if:

1. 
   p = 23
   
2. 
   p is any prime.
   

Explain each of your answers.

Question4: (4 marks) Let p be a prime and a ∈ Z⁺ such that a < p.

1. 
   Show that C(p, r) mod p = 0 for 1 ≤ r ≤ (p − 1), where
   

p!

C(p, r) =
.
(p − r)!r!

2. 
   
   
   
   Show that (k + 1)^p ≡ k^p + 1^p mod p using the Binomial Series
   

given by: (x + a)ⁿ
n
=
r=0
C(n, r)x^ra
n−r_.

3. 
   Use the results from a) and b) to prove that a^p ≡ a mod p using mathematical induction.
   
   • 
     Show the BASIS STEP (show that for a = 1...)
     
   • 
     Show the INDUCTIVE HYPOTHESIS (assume that when
     

a = k...)

• 
  Show the INDUCTIVE STEP.
  

4. 
   Use the result from c) to prove Fermat’s Little Theorem:
   

a^p−1 ≡ 1 mod p