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

• Return to index
• Exercise 4.1
• Exercise 4.2
• Exercise 4.3
• Exercise 4.4
• Exercise 4.5
• Exercise 4.6
• Exercise 4.7
• Exercise 4.8
• Exercise 4.9
• Exercise 4.10
• Exercise 4.11
• Exercise 4.12
• Exercise 4.13
• Exercise 4.14
• Exercise 4.15
• Exercise 4.16

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 \(GF(2^8)\) multiplication with your answer and the input byte. Note that you have to represent each byte first as polynomials in \(GF(2^8)\). The most significant byte of each byte represents the \(x^7\) 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: \(P(x) = x^8 + x^4 + x^3 + x + 1\).

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, \(26_{16}^{-1} = A8_{16}\), 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, \(F3_{16}^{-1} = 34_{16}\), 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

I write about computing stuff

Tweet Share