s
Section 5.7 Matrices
469
c. After the matrix has been reduced to upper triangular form, show that there are
n(n + 1)
2
multiplications and
(n − 1)n
2
additions to solve for the n unknowns.
d. Explain why Gaussian elimination is Θ(n
3
) in the worst case.
56. DES, discussed in Section 5.6, is an encryption algorithm that is an example of a block cipher, where a
block of bits is encoded into a block of bits. Matrices can be used to create a simple block cipher. Consider
a 2 × 2 matrix with integer entries, for example,
a = c
2 7
1 4
d
a is an invertible matrix with
a
−1
= c
4 −7
−1
2
d
because
c
2 7
1 4
d # c
4 −7
−1
2
d = c
4 −7
−1
2
d # c
2 7
1 4
d = c
1 0
0 1
d
Break up the message to be encrypted into blocks of two characters, and apply a function mapping the
letters of the alphabet into the integers 0–25 as follows:
a b c D e f g h I
J K l
m n o p Q R S t u V W x Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Thus 3B R4 S 31 174. The heart of the encryption algorithm consists of multiplying the resulting 1 × 2
matrix by a using arithmetic modulo 26. Thus
31 174 # c
2 7
1 4
d = 319 754 S 319 234
and 319 234 S 3T X4. Therefore 3B R4 is encrypted as 3T X4. To decrypt, convert 3T X4 back to
319 234 and multiply the resulting 1 × 2 matrix by a
−1
, again using modulo 26 arithmetic.
319 234 # c
4 −7
−1
2
d = 353 −874 S 31 174
to be converted back to the original message 3B R4.
a. Using the encryption matrix a above, encrypt the block [V I].
b. Decrypt the result from part (a) to recover [V I].
c. Explain why the decoding process recovers the original (numerical) block.