MATH 195: CRYPTOGRAPHY HOMEWORK #10

Problem R1. Let k be a finite field, #k = q, and let k[X] be the ring of polynomials with coefficients in k. For f = ∑_{i=0}^{n} c_{i}X^{i} ∈ k[X] and a ∈ k, write f(a) for the element ∑_{i=0}^{n} c_{i}a^{i} of k.

(a) Let b ∈ k and define f = 1 − (X − b)^{q−1}. Prove:

f(a) = \begin{cases}0, & a ∈ k, a ≠ b; \\ 1, & a = b. \end{cases}

(b) Prove that there are precisely q^{q} different maps g : k → k and that for each of them there is a unique polynomial f ∈ k[X] of degree < q such that for all a ∈ k one has g(a) = f(a).

Problem R2. Refer to the notation in the notes on the Rijndael cipher from Tuesday, April 2.

(a) Prove: τ_{s}^{2} = id_{S} and τ_{s}^{−1} = τ_{s} for all s ∈ S.

(b) Prove σ^{4} = id_{S} and σ^{−1} = σ^{3}.

Problem R3.

(a) Prove: βσ = σβ independently of the map B : 𝔽_{256} → 𝔽_{256} used to define β.

(b) Prove: μτ_{s} = τ_{μ(s)}μ for all s ∈ S independently of the linear function M : 𝔽_{256}^{4} → 𝔽_{256}^{4} used to define μ.

Date: April 9, 2002.

R1, R2.