INTRODUCTION

The word cryptography is a combination of two Greek words: crypto, meaning “hidden” or “secret,” and grapho, which means “writing.” Cryptography then is the study of making “secret writings” or codes.

In this section we will consider a system of encoding and decoding messages that requires both the sender of the message and the receiver of the message to know:

• a specified rule of correspondence between a set of symbols (such as letters of the alphabet and punctuation marks from which messages are composed) and a set of integers; and
• a specified nonsingular matrix A.

Encoding/Decoding

A natural correspondence between the first 27 nonnegative integers and the letters of the alphabet and a blank space (to separate words) is given by

(1)

From (1) the numerical equivalent of the message

SEND THE DOCUMENT TODAY

is (2)

The sender will encode the message by means of the nonsingular matrix A and, as we shall see, the receiver of the encoded message will decode the message by means of the (unique) matrix A⁻¹. The numerical message (2) is now written as a matrix. Since there are 23 symbols in the message, we need a matrix that will hold a minimum of 24 entries (an m × n matrix has mn entries). We choose to write (2) as the 3 × 8 matrix

(3)

Note that the last entry a₃₈ in the message matrix M has been simply padded with a space represented by the number 0. Of course, we could have written (2) as a 6 × 4 or a 4 × 6 matrix but that would require a larger encoding matrix. A 3 × 8 matrix allows us to encode the message by means of a 3 × 3 matrix. The size of the matrices used is only a concern when the encoding and decoding are done by hand rather than by a computer.

The encoding matrix A is chosen, or rather constructed, so that

• A is nonsingular,
• A has only integer entries, and
• A⁻¹ has only integer entries.

The last criterion is not particularly difficult to accomplish. We need only select the integer entries of A in such a manner that det A = ±1. For a 2 × 2 or a 3 × 3 matrix we can then find A⁻¹ by the formulas in (4) and (5) of Section 8.6. If A has integer entries, then all the cofactors C₁₁, C₁₂, and so on, are also integers. For the discussion on hand we choose

(4)

You should verify that det A = −1.

The original message is encoded by premultiplying the message matrix M by A; that is, the message is sent as the matrix:

(5)

You should try to imagine the difficulty of decoding (5) without knowledge of A. But the receiver of the encoded message B knows A and its inverse, and so decoding is the straightforward computation of premultiplying B by A⁻¹:

AM = B     implies     M = A⁻¹B.

For the matrix (4) we find from (5) of Section 8.6 that

A⁻¹ = .

Thus, the decoded message is

or 19 5 14 4 0 20 8 5 0 4 15 3 21 13 5 14 20 0 20 15 4 1 25 0.

By also knowing the original correspondence (1), the receiver translates the numbers into

SEND_THE_DOCUMENT_TODAY

where we have indicated the blank spaces by lines.

Some observations are in order. The correspondence or mapping (1) is one of many such correspondences that can be set up between the letters of the alphabet (we could even include punctuation symbols such as the comma and period) and integers. Using the 26 letters of the alphabet and the blank space, we can set up 27! of these correspondences. (Why?) Furthermore, we could have used a 2 × 2 matrix to encode (2). The size of the message matrix M would then have to be at least 2 × 12 in order to contain the 23 entries of the message. For example, if

,

then B = AM = .

Using A⁻¹ = , we obtain as before

There is no particular reason why the numerical message (2) has to be broken down as rows (1 × 8 vectors) as in the matrix (3). Alternatively, (2) could be broken down as columns (3 × 1 vectors) as shown in the matrix

Finally, it may be desirable to send the encoded message as letters of the alphabet rather than as numbers. In Problem 13 in Exercises 8.14, we shall show how to transmit SEND THE DOCUMENT TODAY encoded as

OVTHWFUVJVRWYBWYCZZNWPZL.

8.14 Exercises Answers to selected odd-numbered problems begin on page ANS-21.

In Problems 1−6, use the matrix A and the correspondence (1) to encode the given message. Verify your work by decoding the encoded message.

1. A = ; SEND HELP
2. A = ; THE MONEY IS HERE
3. A = ; PHONE HOME
4. A = ; MADAME X HAS THE PLANS
5. A = ; GO NORTH ON MAIN ST
6. A = ; DR JOHN IS THE SPY

In Problems 7–10, use the matrix A and the correspondence (1) to decode the given message.

7. 
8. 

   

9. 

   

10. 

    

11. Using the correspondence (1), we encoded the following message by a 2 × 2 matrix:

    

    Decode the message if its first two letters are DA and its last two letters are AY.

12. 1. Using the correspondence

       

       find the numerical equivalent of the message

       BUY ALL AVAILABLE STOCK AT MARKET.

    2. Encode the message by postmultiplying the message matrix M by

       

    3. Verify your work by decoding the encoded message in part (b).
13. Consider the matrices A and B defined in (4) and (5), respectively.
    1. Rewrite B as B′ using integers modulo 27.^*
    2. Verify that the encoded message to be sent in letters is

       OVTHWFUVJVRWYBWYCZZNWPZL.

    3. Decode the encoded message by computing A⁻¹B′ and rewriting the result using integers modulo 27.

*For integers a and b, we write a = b (mod 27) if b is the remainder (0 ≤ b < 27) when a is divided by 27. For example, 33 = 6 (mod 27), 28 = 1 (mod 27), and so on. Negative integers are handled in the following manner: If 27 = 0 (mod 27), then, for example, 25 + 2 = 0 (mod 27) so that −25 = 2 (mod 27) and −2 = 25 (mod 27). Also, −30 = 24 (mod 27), since 30 + 24 (= 54) = 0 (mod 27).