Linear Algebra Review



Chapter 7: Hill Ciphers

In this chapter we look at block or polygraphic ciphers, where groups of plaintext are enciphered as units. In particular, we look at the Hill Cipher, which enciphers groups of two or more plaintext characters using matrix multiplication. In order to understand this method, we give a brief review of matrices and their operations.

7.1 Matrices

Matrices are used in a variety of applications, and there are entire courses devoted to the subject. Our goal in this section is to review basic concepts involving matrices so that we can apply them to cryptology.

7.1.1 Definition and Basic Terminology

A matrix is a rectangular array of numbers (usually real) made up of rows and columns. The size of a matrix represents its number of rows and number columns, which is written as (# rows) [pic](# columns). For example, here are the matrices A, B, c, and d with their corresponding sizes:

[pic] (Size: 2[pic]4) [pic] (Size: 3[pic]2)

[pic] (Size: 1[pic]4) [pic] (Size: 3[pic]1)

We will refer to a matrix that contains a single row as a row matrix, and a matrix that contains a single column as a column matrix.

To indicate an individual entry in a matrix, we use the notation

[pic] (represents the element in the [pic] row and [pic]column of the matrix A)

Thus, we have for the matrix [pic], we have the elements [pic] and [pic] and for the matrix [pic], we have the elements [pic] and [pic].

A matrix A of size [pic] has the form

[pic]

A square matrix is a matrix where (# rows) = (# columns) or m = n. When this is case, we say the matrix is a square matrix of order n. Here are some examples of square matrices:

[pic] (2[pic] 2 square matrix of order 2)

[pic] (3[pic]3 square matrix of order 3).

7.1.2 Matrix Operations

Matrices can be combined by addition, subtraction, scalar multiplication, and multiplication. We describe these operations next.

Matrix Addition and Subtraction

Matrices can only be added and subtracted if they have the same size. To add or subtract matrices, we add or subtract each corresponding component.

Example 1: Given the [pic] matrices[pic] and [pic], determine [pic] and [pic].

Solution:

█

Example 2: Given the [pic] matrix[pic] and the [pic] matrix [pic], determine [pic] and [pic].

Solution:

█

Scalar Multiplication of Matrices

When working with matrices, numbers are referred to as scalars. To multiply a matrix by a scalar, we multiply each entry of the matrix by the given scalar.

Example 3: Given[pic], compute [pic].

Solution:

.

█

Example 4: If [pic]and [pic], compute [pic].

Solution: [pic].

█

Matrix Multiplication

To understand matrix multiplication, one must first understand how to multiply a row vector times a column vector. If [pic] is a [pic] row vector and

[pic]

is a [pic]column vector, then the product of A and B is the scalar produced by multiplying each corresponding entry of A and B and adding. That is

[pic].

Example 5: If [pic] and [pic], compute ab.

Solution:

.

█

Multiplication of matrices in general involves multiple multiplications of rows and columns. If A is a [pic] matrix and B is a [pic]matrix, the product C = AB is the matrix where each element [pic] is made up of the product of the [pic] row of the left matrix A multiplied to the [pic] column of the right matrix B. That is,

[pic].

Note! For the matrix product AB to exist, the number of columns of the left matrix A must equal to the number of rows in the right matrix B. The size of the product will be

(the number of rows in A) [pic](the number of columns in B).

It can be easier to see this by examining the following:

[pic]

Example 6: If [pic] and [pic], determine aB.

Solution:

.

█

Example 7: For the matrices, [pic], [pic], compute the products AB and BA

Solution: After observing

[pic]

that the size of the product is a [pic] matrix, we obtain the product [pic] by computing:

[pic].

To compute the product [pic], we observe

[pic]

and compute

[pic].

█

Example 8: Given the matrices [pic] and [pic], compute the products AB and BA.

Solution:

The previous two examples illustrate a very important fact when multiplying matrices:

FACT: In general, matrix multiplication is not commutative, that is, given matrices A and B, it is true in most cases that [pic].

7.1.3 Identity and Inverse Matrices

The multiplicative identity matrix, usually referred to just the identity matrix I, is the [pic] matrix defined by

[pic].

Note that I has 1’s on the main diagonal and 0’s elsewhere. The following represent [pic], [pic], and [pic] identity matrices:

[pic].

Since I serves as the multiplicative identity. If A is a [pic] matrix, then

AI = IA = A.

Note that I is always a square matrix, that is, the number of rows equals the number of columns. Of course, the size of I is dependent on the size of A when multiplying on the left and right as the next example demonstrates.

Example 9: Given the [pic]matrix [pic], compute [pic] and [pic].

Solution: To be multiplicatively compatible, the size of the identity I on the left must be [pic] and on the right [pic]. This gives

[pic]

and

[pic].

█

Determinants

The determinant of a [pic] matrix [pic] is given by

det(A) [pic].

Example 10: Find the determinant of the matrix [pic].

Solution:

█

Example 11: Find the determinant of the matrix [pic].

Solution:

█

A fact to note is that the determinant of a [pic] matrix is defined to be the entry of the matrix. For example, if [pic], then [pic]. Another important note to make is that is possible to take determinants of larger size square matrices (larger than [pic]) , which will be discussed in the Exercises.

Matrix Inverses

The multiplicative inverse , or inverse for short, of a [pic] matrix [pic], if it exists, is denoted by [pic], and is defined to be the [pic] matrix where

[pic],

where [pic] is the [pic] identity matrix. It can be shown that [pic] is unique. Note the inverse only exists for square matrices where the row and column number are the same.

Note: To show that [pic], we only have to find a matrix B were [pic]. If [pic], then it can be shown that [pic] will also be true. Hence, we say [pic]

Example 12: Show that the matrix [pic] is the inverse of the matrix [pic],

Solution: To show B is the inverse of A, one must show that [pic]. For example,

[pic].

A similar calculation can be shown for [pic]. Hence, [pic].

█

Given a matrix [pic], how do we know if [pic] exists, and if it does, how can we calculate [pic]? For matrices larger than [pic], the recommended method involves a method involving row reduction. However, for [pic] matrices, there is a method based upon the following:

FACT: For a given [pic] matrix[pic], the matrix [pic] exists only if [pic]. If this is so, the inverse of the matrix is defined to be:

[pic].

Note that the matrix part of the formula for [pic] is obtained by switching the main diagonal elements and negating the back diagonal elements.

Example 13: Given the matrix [pic] determine if [pic] exists, and if so, compute.

Solution:

█

Example 14: Given the matrix[pic], determine if [pic] exists, and if so, compute.

Solution:

█

7.1.4 Matrices with Modular Arithmetic

We can extend the mod operation to matrices. For a matrix A with entries [pic], we say

[pic] is the matrix where the mod operation is applied to each entry, [pic].

Example 15: Compute the matrix[pic].

Solution:

█

The concepts of matrix addition, subtraction, and multiplication can be computed using modular arithmetic. The following two examples illustrate these concepts.

Example 16: Given the [pic] matrices[pic] and [pic], determine [pic] and [pic] mod 5.

Solution:

█

Example 17: Given[pic], compute [pic] mod 13.

Solution:

Example 18: For the matrices, [pic], [pic], compute the product AB mod 26.

Solution: After observing that the size of the product AB is a [pic] matrix, we obtain the product [pic] by computing:

[pic].

█

The inverse of a matrix can exist for modular arithmetic modulo m as well. For a square matrix A with entries in[pic] }, the inverse of A modulo m, if it exists, is a matrix B with entries in [pic]and with the property that [pic]. This inverse, when it exists, is denoted [pic].

Example 19: Consider the following matrices A and B.

[pic] and [pic]

To see whether [pic], we compute the following.

[pic]

Thus, [pic].

█

To find the inverse of a [pic] matrix in modular arithmetic, we use the same formula as for the real number system, except that the reciprocal of the determinant is represented by [pic], which will represent the multiplicative inverse of [pic].

FACT: For a given [pic] matrix[pic], the matrix [pic] exists if and only if [pic]. If this is so, the inverse of the matrix is defined to be:

[pic].

With Hill ciphers, all of our calculations will be done modulo 26. For convenience, each value of det(A) mod 26 for which [pic] mod 26 exists is shown along with [pic] mod 26 in Table 1.

[pic] |1 |3 |5 |7 |9 |11 |15 |17 |19 |21 |23 |25 | |[pic] mod 26 |1 |9 |21 |15 |3 |19 |7 |23 |11 |5 |17 |25 | |

Table 1: Corresponding values of [pic] and [pic] mod 26

Example 19: Determine if the inverse of the matrix [pic] mod 26 exists, and if so, find the inverse.

Solution:

█

Example 20: Determine if the inverse of[pic] modulo 26 exists, and if so, find the inverse.

Solution:

█

Some Suggested Textbook Exercises for Practice for Section 7.1

p. 242: # 1-12

7.2 A Maplet for Matrix Computations

Some Suggested Textbook Exercises for Practice for Section 7.2

p. 250: # 1-8

7.3 Hill Ciphers

The Hill Cipher was developed by Lester Hill of Hunter College in 1929. It involves breaking the plaintext into blocks whose size depends on the size of a key matrix used for encipherment. For our examples, we will focus on [pic] matrices, although the method can easily be extended to matrices of larger sizes.

The key to our encryption will be a [pic] invertible matrix A modulo 26. We use the same mod 26 alphabet assignment introduced back in Chapter 5.

Alphabet Assignment

[pic] [pic] [pic]

Suppose [pic] are the numerical equivalents of n plaintext letters (we will assume n is divisible by the size of the matrix 2, if not, an extra letter can be padded to the plaintext to make this so). The ciphertext [pic] is computed by grouping the plaintext into row vectors of two elements each and computing the following matrix vector products:

[pic].

To decipher, we compute the inverse of the key matrix [pic] and reverse the process by computing the following matrix vector products:

[pic]

Example 21: Use the key matrix [pic] to encrypt the message BE HERE AT SEVEN.

Solution:

Example 22: Suppose the key matrix [pic] was used to create the ciphertext message MYBGX HTMTY IU. Decipher the message.

Solution: To decipher, we need the inverse of the key matrix. Noting that [pic] and [pic], we find the inverse as follows:

[pic]

We next convert the the ciphertext message into its numerical equivalents in [pic].

M |Y |B |G |X |H |T |M |T |Y |I |U | |12 |24 |1 |6 |23 |7 |19 |12 |19 |24 |8 |20 | |

Grouping the ciphertext into groups of column vectors of two elements each, we calculate the following matrix vector products.

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

The numerical equivalents of the plaintext and corresponding letters in [pic]are

8 |22 |8 |11 |11 |1 |4 |11 |0 |19 |4 |0 | |I |W |I |L |L |B |E |L |A |T |E |A | |

Hence, the plaintext is I WILL BE LATE. █

Example 23: Use the key matrix [pic] to encrypt the message EAGLES DARE.

Solution: To encrypt this message, we first convert the plaintext message into its numerical equivalents in [pic].

E |A |G |L |E |S |D |A |R |E | | | |4 |0 |6 |11 |4 |18 |3 |0 |17 |4 | | | |

Grouping the plaintext into groups of column vectors of three elements each, noting that we pad the last block with two extra A’s to make it three elements, we calculate the following matrix vector products.

[pic]

[pic]

[pic]

[pic]

The numerical equivalents of the ciphertext and corresponding letters in [pic]are

6 |24 |8 |7 |0 |20 |25 |18 |21 |18 |24 |6 | |G |Y |I |H |A |U |Z |S |V |S |Y |G | |

Hence, the plaintext is GYIHA UZSVS YG. █

Example 24: Suppose the key matrix [pic] was used to create the ciphertext message CWPQR ATWD. Decipher the message.

█

Some Suggested Textbook Exercises for Practice for Section 7.3

p. 259: # 1-3

7.4 A Maplet for Hill Ciphers

Some Suggested Textbook Exercises for Practice for Section 7.4

p. 263: # 1-2

7.5 Cryptanalysis of Hill Ciphers

Having just the ciphertext when trying to cryptanalyze a Hill cipher is considerably more difficult to break than for a monoalphabetic cipher. The character frequencies are obscured, as can be seen from the repeating letters in the plaintext message from Example 21 BE HERE AT SEVENA that was enciphered as WRIXC HRYEI KLAN. For [pic] key matrices, since letters are enciphered in two-letter groups, there are [pic] two-letter blocks possible. Each of these enciphered blocks can be regarded as a monoalphabetic cipher on a 676 character alphabet. If a large amount of ciphertext is available, it may be possible to match the most frequently occurring digraphs in English with the most frequently occurring digraphs in the ciphertext to read portions of the plaintext. If an adversary suspected that a [pic] matrix was used, a brute force approach may cause the adversary to try up to [pic] different matrices. However, these methods of attack can be made significantly harder by simply increasing the size of the key matrix.

However, if the adversary has the ciphertext and a small amount of corresponding plaintext, then the Hill Cipher is more vulnerable. To demonstrate, suppose the ciphertext

HJGID OZKEJ LPPRA IRBXX DTUWR QYFHA GELFP KPSTF

was produced using a [pic] key matrix A and it is known that the first four words of the plaintext is I BEG TO…. The key matrix is used to encipher the plaintext IB as the ciphertext HJ and the plaintext EG and the ciphertext GI. This says that

[pic]

and

[pic]

Compactly, these two encipherments can be written as the matrix equation

[pic]

To find the key matrix A, we need to multiply both sides of the equation by the inverse [pic]. How its determinant is [pic] and [pic]. Hence, the inverse does not exist. However, since there is more known plaintext to work with, we can use the fact that the plaintext TO enciphers as the ciphertext DO to form with the first pair of letters the equations

[pic]

and

[pic].

Compactly, this can be written as the matrix equation

[pic]

The matrix [pic]is invertible since its determinant is [pic] and [pic]. Noting that [pic], the inverse of the matrix is

[pic].

The key matrix A can then be found as follows:

[pic]

[pic]

[pic]

[pic]

The inverse of this key matrix is [pic]. Using the inverse matrix, it can be shown that the message HJGID OZKEJ LPPRA IRBXX DTUWR QYFHA GELFP KPSTF deciphers as the plaintext message

I BEG TO DIFFER ON YOUR OPINION ON THIS MATTER SIR

█

Some Suggested Textbook Exercises for Practice for Section 7.5

p. 267: # 1-4

7.6 A Maplet for Cryptanalysis of Hill Ciphers

Some Suggested Textbook Exercises for Practice for Section 7.6

p. 272: # 1-6

-----------------------

Size of

Product

[pic]

Size of

Product

[pic]

Size of

Product

[pic]

[pic] [pic][pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download