Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 4 Solutions - Ex4.13

- 4 mins

Exercise 4.13

We consider the first part of the ByteSub operation, i.e, the Galois field inversion.

  1. Using Table 4.2, what is the inverse of the bytes 29, F3 and 01, where each byte is given in hexadecimal notation?
  2. Verify your answer by performing a multiplication with your answer and the input byte. Note that you have to represent each byte first as polynomials in . The most significant byte of each byte represents the coefficient

Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

1. As per Table 4.2:

2. Instead of doing long-hand multiplications and reductions, I will be using the Mod2Polynomial class I wrote for earlier exercises.

Just as a reminder, the reduction primitive polynomial is the AES polynomial: .

This is expressed as a Mod2Polynomial class as follows (it takes least significant bit first):

mod = Mod2Polynomial([1, 1, 0, 1, 1, 0, 0, 0, 1])

The first pair, , can be checked as follows:

When multiplied together, these should produce an output of 1:

mod = Mod2Polynomial([1, 1, 0, 1, 1, 0, 0, 0, 1])
a = Mod2Polynomial([0, 1, 1, 0, 0, 1, 0, 0])
b = Mod2Polynomial([0, 0, 0, 1, 0, 1, 0, 1])
print (a * b) % mod

This does produce an output of 1.

The second pair, , can be checked as follows:

When multiplied together, these should produce an output of 1:

mod = Mod2Polynomial([1, 1, 0, 1, 1, 0, 0, 0, 1])
a = Mod2Polynomial([1, 1, 0, 0, 1, 1, 1, 1])
b = Mod2Polynomial([0, 0, 1, 0, 1, 1, 0, 0])
print (a * b) % mod

This does produce an output of 1.

The 01 case is pretty trivial and doesn’t really need to be checked, but we will anyway:

When multiplied together, these should produce an output of 1:

mod = Mod2Polynomial([1, 1, 0, 1, 1, 0, 0, 0, 1])
a = Mod2Polynomial([1, 0, 0, 0, 0, 0, 0, 0])
b = Mod2Polynomial([1, 0, 0, 0, 0, 0, 0, 0])
print (a * b) % mod

This does produce an output of 1.


Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora