Assignments

• Script #1 shows you all 26 possible decipherings from which you can choose the correct one. (See the second paragraph on page 57.)
• Script #4 gives a count of how many times each letter appears, and compares this count to the frequency distribution of letters in English text. From the patterns you can figure out how much to shift the cipher text so that it becomes plain text. Script #5 is a color graphics version of this.
• Script #3 will encipher any text with any Viginère key---hence will decipher any Viginère-enciphered text. If the enciphering key is the letter "d" (the number 3), then the deciphering key is the letter "x" (the number 23 = 26 - 3).

AWYVPQCTBLWYLPASQJWUPGBUSHFACELDLLDLWLBWAFAHS
EBYJXXACELWCJTQMARKDDLWCSXBUDLKDPLXSEQCJTNWPR
WSRGBCLWPGJEZIFWIMJDLLDAGCQMAYLTGLPPJXTWSGFRM
VTLGUYUXJAIGWHCPXQLTBXDPVTAGSGFVRZTWTGMMVFLXR
LDKWPRLWCSXPHDPLPKSHQGULMBZWGQAPQCTBAURZTWSHQ
MBCVXAGJJVGCSSGLIFWNQSXBFDGSHIWSFGLRZTWEPLSVC
VIFWNQSXBOWCFHMETRZXLYPPJXTWSGFRMVTRZTWHWMFTB
OPQZXLYIMFPLVWYVIFWDPAVGFPJETQKPEWGCSSRGIFWB

Exercise 1.9 Now suppose that our message units are digraphs in an N-letter alphabet. Find a formula for the number of different affine enciphering transformations there are. How many are there when N = 26, 27, 29, 30?
Exercise 1.10 You intercept the ciphertext message "PWULPZTQAWHF", which you know was encrypted using an affine map on digraphs in the 26-letter alphabet, where, as in the text, a diagraph whose two letters have numerical equivalents x and y corresponds to the integer 26x + y. An extensive statistical analysis of earlier ciphertexts which had been coded by the same enciphering map shows that the most frequently occurring digraphs in all of that ciphertext are "IX" and "TQ", in that order. It is known that the most common digraphs in the English language are "TH" and "HE", in that order.
(a) Find the deciphering key, and read the message.
(b) You decide to have the intended recipient of the message incapacitated, but you don't want the sender to know that anything is amiss. So you want to impersonate the sender's accomplice and reply "GOODWORK". Find the enciphering key, and determine the appropriate ciphertext.
Exercise 2.1 Use frequency analysis to decrypt the following message, which was encoded in the 26-letter alphabet using a Viginère cipher with a 3-letter key-word. Do this in the following way. To find the first letter of the key-word, work with the sequence consisting of every third letter starting with the first. Do not assume that the most frequently occurring letter is necessarily the ciphertext for "E". List the four most frequently occurring letters, and try out the possibility that each one in turn is the encryption of "E". If one of the other three frequently occurring letters would then have to be the encryption, say, of "Z" or "Q", then you know that you made a wrong choice for "E". By an elimination process, find the letter that must be "E" and then the key-word letter which produces this translation. In this way find the key-word and decipher the message. [The ciphertext appears above. You may use Script #4 or Script #5 rather than following exactly the procedure outlined in the exercise.]
Exercise 2.4 Find all solutions (x, y) modulo N to the following pairs of equations, writing x and y as nonnegative integers less than N.
(a) 17x + 11y = 7 mod 29 and 13x + 10y = 8 mod 29.
(d) 9x + 20y = 10 mod 29 and 16x + 13y = 21 mod 29.
(e) 9x + 20y = 1 mod 29 and 16x + 13y = 2 mod 29.
 

• Chapter III, Section 2, Exercise 7.

You intercept the message "SONAFQCHMWPTVEVY", which you know resulted from a linear enciphering transformation of digraph vectors, where the sender used the usual 26-letter alphabet A-Z with numerical equivalents 0-25, respectively. An earlier statistical analysis of a long string of intercepted ciphertext revealed that the most frequently occurring ciphertext digraphs were "KH" and "XW" in that order. You take a guess that those digraphs correspond to "TH" and "HE", respectively, since those are the most frequently occurring digraphs in most long plaintext messages on the subject you think is being discussed. Find the deciphering matrix and read the message.
• Problem 1, Section 4 of "Introduction to Cryptography" (on web).

Decipher this Playfair cipher text, which was enciphered using the key word king: KL KZ FG CS FG HS.
• Find the three-letter key for this Viginère cipher and decipher it. (Use Script #5.)

waxvrfstmbambtkcqgfrehrhhuivrejrroahhuisnvhuebqxvrioexvjeg
jmhusigjceqoahjbmrnrrqefxrsfwknwicsbglsseqrstglsqiscebqxvr
wdvvwgsttsrzsjrhicsbglsseqrstglsjehrvgnrrtsrfewqpsgxvrvsoi
zvkvgebqxvrvsjegymuuxoahubhgnahuizvkvgxvnxwgaofkcbhoahubh
rvzwqirglsymuuxtesaglsqefxrsfw

• Chapter IV, Section 2, Exercise 1 (page 95). Script #13 will raise x to the y modulo n (at the bottom).
• Chapter IV, Section 2, Exercise 2 (page 96). Script #14 implements the "stupidest known algorithm".

• Suppose n = 8655877619 and j(n) = 8655691296. Factor n by the method of Proposition I.3.4, page 22.
• Repeat the previous problem with n = 1311504533 and j(n) = 1311398988
• The cipher 4764880969 was obtained by transforming a sequence of letters to a number according to the usual base-26 scheme, and then enciphering using the public key (8655877619, 5555555555). What was the original message?

• Zero-knowledge proof of having found a square root.

Suppose you want to convince someone that you have have found x such that x² = y modulo p, without revealing to him what the value of x is. Describe an interactive procedure, similar to the one described on page 120, that will accomplish this. Explain why it works.
Go through a few illustrative steps of your procedure for p = 88003 and y = 40420 = 20528².
 
• To which bases is 35 a pseudoprime? To which bases is 91 a pseudoprime? (Note that if n is a pseudoprime to the base b, and n is a pseudoprime to the base c, then n is a pseudoprime to the base bc. See Proposition V.1.1.)

• Make tables showing all the quadratic residues and nonresidues modulo 23 and modulo 29.
• Find a generator g for each of the two fields in the preceding problem and verify that the quadratic residues are exactly the even powers of g.
• Write each of the primes less than 40, that are congruent to 1 modulo 4, as the sum of two squares. Verify that each of the primes less than 40, that are congruent to 3 modulo 4, cannot be written as the sum of two squares.
• Check the equation 2^(p-1)/2 = (2/p) mod p for each of the first six odd primes. (To calculate the Legendre symbol (2/p), either find x such that x² = 2 mod p, or show that there is no x such that x² = 2 mod p.)

• Exercises 10 and 11 on pages 50 and 51.
• Exercise 21 on page 137. (List the bases in part (a).)
• Find a number b so that 561 is an Euler pseudoprime to the base b but 561 is not a strong pseudoprime to the base b. Show directly from the definitions that your number b satisfies these two conditions.