MATH 195: CRYPTOGRAPHY HOMEWORK #11

Problem R4. Let c_{0}, c_{1}, c_{2}, c_{3} ∈ 𝔽_{256} be such that c_{0} + c_{1} + c_{2} + c_{3} = 1 and put

c = c_{0} + c_{1}Y + c_{2}Y^{2} + c_{3}Y^{3} ∈ 𝔽_{256}[Y].

Prove:

(a) c ≡ 1 (mod Y + 1).

(b) c^{4} ≡ 1 (mod Y^{4} + 1).

(c) The inverse of (c mod Y^{4} + 1) equals

c_{0}(c_{0}^{2} + c_{2}^{2}) + c_{2}(c_{1}^{2} + c_{3}^{2}) + (c_{1}(c_{0}^{2} + c_{2}^{2}) + c_{3}(c_{1}^{2} + c_{3}^{2}))Y

+ (c_{2}(c_{0}^{2} + c_{2}^{2}) + c_{0}(c_{1}^{2} + c_{3}^{2})) Y^{2} + (c_{3}(c_{0}^{2} + c_{2}^{2}) + c_{1}(c_{1}^{2} + c_{3}^{2})) Y^{3}.

Problem R5. Recall that we define the map

M : 𝔽_{256}^{4} → 𝔽_{256}^{4}
M(g) ≡ c · g (mod Y^{4} + 1).

where we identify the word space 𝔽_{256}^{4} with the set of polynomials

𝔽_{256}^{4} = {g ∈ 𝔽_{256}[Y] : deg g < 4}
(a_{0}, a_{1}, a_{2}, a_{3}) = a_{0} + a_{1}Y + a_{2}Y^{2} + a_{3}Y^{3}.

Here we let c ∈ 𝔽_{256}^{4} be

c = (X, 1, 1, X + 1) = X + Y + Y^{2} + (X + 1)Y^{3},

where

𝔽_{256} = 𝔽_{2}[X]/(X^{8} + X^{4} + X^{3} + X + 1).

Prove that M^{4} is the identity map on the set of words, and that M^{−1} = M^{3} is given by

M^{−1}(g) ≡ d · g (mod Y^{4} + 1)

for all words g, where

d = (X^{3} + X^{2} + X) + (X^{3} + 1)Y + (X^{3} + X^{2} + 1)Y^{2} + (X^{3} + X + 1)Y^{3}.

[Hint: Do problem R4 before trying this problem.]

Problem R6. Find all words w ∈ 𝔽_{256}^{4} with M(w) = w. Find a pair of words v, w with

M(v) = w, M(w) = v

where w ≠ v.

Date: April 16, 2002.

R4, R5, R6.