Due 2 September: Chapter III, Section 1, Exercises 1, 2, and 3.
(Pages 61 and 62.)
which are accessible from the Number theory and cryptography home
ciphers. With a one-letter key, these are just shift ciphers.
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).
Due 9 September: Chapter III, Section 1, Exercises 9 and 10; Chapter
III, Section 2, Exercises 1, and 4 parts (a), (d) and (e).
For Exercise 2.1 you can use Script #4 or Script #5 to get the counts,
and compare them with the frequencies of letters in English. The cipher
text for this exercise is given below. You can copy and paste it into Script
#4 or Script #5.
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
Exercise 2.4 Find all solutions (x, y) modulo
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.
Due 16 September: (Three problems)
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
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.)
Due 30 September:
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".
Due 7 October:
Recent versions of windows have calculators that will take square roots
of 32-digit numbers. Lots of calculators will take square roots of 10-digit
numbers. Alternatively, you can adapt Exercise I.1.16 to decimal numerals,
and use anything that will find exact squares of 5-digit numbers. (Try
Script #14 on the first two problems, in addition to solving them as indicated.)
Script #11 will do the Bézout thing for you.
Suppose n = 8655877619 and j(n)
= 8655691296. Factor n by the method of Proposition I.3.4, page
Repeat the previous problem with n = 1311504533 and j(n)
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?
Due 14 October: Chapter IV, Section 3, Exercises 4, 6 and 8.
Due 21 October
Zero-knowledge proof of having found a square root.
Suppose you want to convince someone that you have have found x
such that x2 = 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 = 205282.
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.)
Due 4 November
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 x2 = 2 mod
or show that there is no x such that x2 = 2 mod
Due 18 November
Partial solutions to these problems
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.