Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

Use the playfair cipher with the key THE GOLD BUG as below for the following problems.

1. Encrypt MEET TODAY AT NOON.
2. Decrypt the message SM HE OI LO KF QZ.
3. What letters can A get encrypted as using this Playfair square?

2.

In any Playfair cipher (not necessary the square above) can a letter ever be encrypted as itself? That is, can the plaintext E* ever go to ciphertext E_ or can *E ever go to _E? Explain how or why not.

3.

In any Playfair cipher (not necessary the square above), if the plaintext pair AX goes to the cipher text pair FT what, if anything, can you say about the what the cipher text can be for the plaintext pair XA? Consider all possible cases.

4.

In any Playfair cipher (not necessary the square above) can the same letter occur in the plaintext and the ciphertext, but not in the same location? That is, can a letter pair be encrypted such that the plaintext EK goes to the ciphertext -E? Or plaintext KE goes to ciphertext E-? Explain how or why not.

5.

Suppose you know the following PT and the corresponding CT. What does this tell you about what letters can occur in the same row and column in the playfair square? Construct as much of the row and column containing E as possible.

6.

The ciphertext below contains the phrase “there are” in it somewhere spaced as: TH ER EA RE. Find it.

XK NT BC TN IG TN XK RM FI RM KB HB NU YB KN YX XK GA XY RX CI VH BY TN LY BC EI WG RM WA NS VF RQ WI WQ DA OS VR QR OB XF CH UT ZU YX BT

7.

The ciphertext below contains the phrase “the weather” in it somewhere. Find it.

AZ CU WD ME VN CF MQ BC UZ IV HI BZ AB HI CU EQ HG KE ME NM UO PD DN HI NG TE EK PG NH

Bonus: Then find the keyword and decrypt the message.

8.

A different square was used to encrypt a message, and you happen to find some of both the cipher text and the plain text.

Recreate the playfair square and decrypt the rest of the cipher text.

1.

Which of the matrices below would be valid (decryptable) ones to use to encrypt message with the Hill Cipher?

\(\left[ \begin{matrix} 14 \amp 3\\ 5 \amp 2 \end{matrix} \right]\) \(\left[ \begin{matrix} 19 \amp 3\\ 4 \amp 1 \end{matrix} \right]\) \(\left[ \begin{matrix} 20 \amp 21\\ 4 \amp 1 \end{matrix} \right]\) \(\left[ \begin{matrix} 11 \amp 7\\ 9 \amp 4 \end{matrix} \right]\) \(\left[ \begin{matrix} 1 \amp 3\\ 5 \amp 9 \end{matrix} \right]\) \(\left[ \begin{matrix} 8 \amp 2\\ 3 \amp 1 \end{matrix} \right]\) \(\left[ \begin{matrix} 6 \amp 2\\ 5 \amp 7 \end{matrix} \right]\)

2.

Find the inverses mod 26 of all the valid matrices above.

3.

Consider the matrix \(\left[ \begin{matrix} 11 \amp 17\\ 1 \amp 2 \end{matrix} \right]\text{.}\) You may use Sage Computation 6.3.2.

1. Encrypt the plaintext HILL with the above matrix.
2. Encrypt the plaintext IH with the above matrix. You should notice something different from the Playfair cipher!
3. Find the inverse mod 26 of the above matrix.
4. Use your decryption matrix to decrypt the ciphertext FW EO OJ BU .

4.

Find the matrix that encrypts the plaintext DART as the ciphertext XJZC.

5.

The plaintext SICK is encrypted as the ciphertext WYOM.

1. Find all \(2 \times 2\) matrices that will do this encryption. (There is more than one!)
2. Which of the above matrices are valid (decryptable) for a Hill cipher?

6.

Consider a \(2 \times 2\) matrix where each entry is from the numbers 1,2,3,4 and repeats are not allowed.

1. How many ways are there to put the numbers 1,2,3,4 into a \(2 \times 2\) matrix (with no repeats)?
2. Find all such matrices that are valid (decryptable) for a Hill Cipher.
3. In general, are there valid Hill ciphers with the numbers, \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\) where two of the numbers are even and two of the numbers are odd? If so, what can you say about where the even and odd number must be located? If not, explain why it isn't possible.

7.

Consider a \(2 \times 2\) matrix where each entry is from the numbers 1,3,5,7 and repeats are not allowed.

1. Find all such matrices that are valid for a Hill Cipher.
2. In general, are there valid Hill ciphers with the numbers, \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\) where all of the numbers are odd? Explain why or why not.

8.

Consider a \(2 \times 2\) matrix where each entry is from the numbers 2,4,6,8 and repeats are not allowed.

1. Find all such matrices that are valid for a Hill Cipher.
2. In general, are there valid Hill ciphers with the numbers, \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\) where all of the numbers are even? Explain why or why not.

9.

Consider a \(2 \times 2\) matrix where each entry is from the numbers 1,2,4,6 and repeats are not allowed.

1. Find all such matrices that are valid for a Hill Cipher.
2. In general, are there valid Hill ciphers with the numbers, \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\) where exactly one of the numbers is odd? Explain why or why not.

10.

Consider a \(2 \times 2\) matrix where each entry is from the numbers 1,3,5,6 and repeats are not allowed.

1. Find all such matrices that are valid for a Hill Cipher.
2. In general, are there valid Hill ciphers with the numbers, \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\) where exactly one of the numbers is even? Explain why or why not.

1.

Below are 3 permutation boxes. Each of them acts on an input with 16 bits. Apply all 3 of them to 1110000011111111.

1. Permutation box 1:

   3	16	5	12	11	2	14	10
   4	7	6	9	13	1	15	8

2. Permutation box 2: (enlarger)

   4	15	2	14	4	4	3	3
   6	8	1	12	5	12	1	11
   9	10	9	10	13	16	16	7

3. Permutation box 3: (shrinker)

   9	1	12	5
   8	2	15	3

2.

S-boxes. S-boxes take input with 6 bits. Consider 110111.

1. To use the S-box take the first and the last bit, i.e., 11. This is a two bit number; convert it to decimal form. How many numbers can you form from 2 bits?
2. Now take the remaining 4 middle bits, 1011 and convert to decimal form. How many numbers can you form from 4 bits?
3. Below is the DES S-box for round 1. There is a connection between the number of rows and columns and your answers above. What is it?

   14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
   0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
   4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
   15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

4. Use the decimal number from (a) to specify a row and the decimal from (b) to specify a column. Start with column 0 and row 0. What number do you get? Convert that number to binary. This is how an S-box is applied to a six bit input.

3.

The message FUNCODES has been converted into ASCII and then binary to get the following 64 bit message; the top row gives the bit place and the bottom row gives the actual bit. That is, the first bit is 0, the second bit is 1, etc.

4.

Apply the initial permutation box, \(IP\text{,}\) to the message:

For the first ten bits of \(IP(M)\) you should get \(1111 1111 10.\) Find the remaining 54 bits of \(IP(M)\text{.}\)

5.

Take the right hand 32 bits of what you found above (you should have \(R_0= 0000 0000 0000 0000 0001 0100 1001 1101\)) and apply the expansion permutation box \(P_E\) below.

You should end up with 48 bits = \(P_E(R)\text{.}\) It should start with \(P_E(R) = 10000 00000 00 \cdots\text{.}\)

6.

Combine your 48 bits with 48 bits of the key using the xor operator to compute

Assume your 48 bits of key are \(K_1 = 01011 10011 10101 01110 10001 00011 11111 01000 01110 110\text{.}\) (There is a method for how to choose the appropriate 48 bits from the 64 bit key, but we are skipping that. ) \(C\) should start with \(110111 001110 \cdots\text{.}\)

7.

Break this 48 bits into eight 6-bit blocks to prepare for the S-boxes. Send each block of 6 bits through S-box 1. (Really there would be 8 different S-boxes, but you should get the idea.) Call your output \(D\text{.}\)

8.

Apply the permutation box, \(P\text{,}\) below to your output \(D\text{.}\) That is, compute \(E=P(D)\text{.}\)

9.

Compute \(F=E \oplus L_0\) where \(L_0\) is the left hand 32 bits of \(IP(M)\text{.}\) Then set \(L_{1} = R_0\) and \(R_{1} =F\) and repeat the steps 5-8, 15 times. No, don't really do this, but DES does!