Solutions for problem set 3

Problem 1

For a symmetric algorithm they need a key per each pair, i.e. the first person needs 7 keys (one per every person other than themselves), the second one needs 6 more (he/she already has a key with the first person), and so on. The result:

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28

For a public key cryptography algorithm each person needs just one key. The result is 8.

Problem 2

Step 1 for both encryption and decryption is to translate letters into numbers using the table. Don't forget to insert spaces when encrypting a phrase. For instance, the beginning of the the given phrase will be translated as follows:

MIDWAY UPON THE -> 13, 9, 4, 23, 1, 25, 38, 21, 16, 15, 14, 38, 20, 8, 5

Encryption:

Let's number all the characters in the phrase, the first number is 1.
The new value for the character c whose number is k is computed as follows:
(c + (k * n) % p) % 50
50 is the number of characters in the table.

For instance, the first 4 characters are translated as follows:
(13 + (1 * 7) % 53) % 50 = 20 (corresponds to T)
(9 + (2 * 7) % 53) % 50 = 23 (corresponds to W)
(4 + (3 * 7) % 53) % 50 = 25 (corresponds to Y)
(23 + (4 * 7) % 53) % 50 = 51 % 50 = 1 (corresponds to A)

The complete translation is:

TWYA9Q*XZ5_SHCG;W8%BEC0)42RBOS:X15_1F.N3::,4M23W*_0SI0V3!W:*IY82@H6FG44P

Here spaces are shown as blue underscores (_).

The source of the quote: Dante, "The Divine Comedy", the very first lines of INFERNO.

Decryption:

Decryption is done by the opposite process: we subtract (k * n) % p from the character. If we end up with a negative number, then we need to add 50 to get a character value. The first 4 letters are decrypted as follows:
40 - (1 * 20) % 61 = 20 (corresponds to T)
48 - (2 * 20) % 61 = 8 (corresponds to H)
15 - (3 * 20) % 61 = -45; -45 + 50 = 5 (corresponds to E)
7 - (4 * 20) % 61 = -12; -12 + 50 = 38 (corresponds to space)

The complete translation, including one character that I have mistyped, is:

THE TIME IS OUT OF JOINT: O CURSED SPITE, THAT EVER I9WAS BORN TO SET IT RIGHT!

(Shakespeare, "Hamlet", end of Act I).

A typo in problems 3 and 5:

91 = 13 * 7 is not a prime number. However, the solutions are given as if it is.

Problem 3

A. If p = 91, then we need to try all possibilities for n. Since n must be less than 91 but greater or equal than 1, we have 90 possibilities. In each case we need to generate 15 keys to decode the message and to convert 15 characters. The result:

90 * (15 + 15) = 90 * 30 = 2700 units of time.

B. If p < 23, then we need to try all prime numbers less than 23, and for each of these numbers all possible values of n. Below is the table:

Prime p Number of values of n Units
2 1 30
3 2 60
5 4 120
7 6 180
11 10 300
13 12 360
17 16 480
19 18 540
Total: 69 2070

Problem 4

Another correction: 503 = 256 + 128 + 64 + 32 + 16 + 4 + 2 + 1 (no 8), so the result below is not correct.

A. The encoding is (8^7) % 943 = 2097152 % 943 = 863.

B. The decoding is computed as (354^503) % 943.
To compute the decoding, represent 503 = 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1.
Then compute the following:

354 % 943 = 354
354^2 % 943 = 125316 % 943 = 840
354^4 % 943 = (840 * 840) % 943 = 705600 % 943 = 236 (using Fact 2 in the lecture)
354^8 % 943 = (236 * 236) % 943 = 59
354^16 % 943 = (59 * 59) % 943 = 652
354^32 % 943 = (652 * 652) % 943 = 754
354^64 % 943 = (754 * 754) % 943 =830
354^128 % 943 = (830 * 830) % 943 = 510
354^256 % 943 = (510 * 510) % 943 = 775

The results is computed using Fact 1 in the lecture notes:
354^503 % 943 = (775 * 510 * 830 * 754 * 652 * 59 * 236 * 840 * 354) % 943 = 767.

Problem 5

A. Number e must be relatively prime to (p-1)*(q-1) = 52 * 90 = 4680. The numbers 2, 3, 4, 5, 6 all divide 4680. 7 is the first number relatively prime to 4680, so we choose e = 7.

Number d must be such that e*d has a remainder 1 when divided by (p-1)*(q-1). Writing it down as an equation, we get:

7 * d = k * 4680 + 1 for some integer k.
Trying values 1, 2, 3, 4, we don't get an integer value for d. Trying 5:
7 * d = 5 * 4680 +1
d = (5 * 4680 + 1) / 7 = 3343.

B. The public key is p * q = 53 * 91 = 4823 and e = 7.

The private key is p = 53, q = 91, and d = 3343.

That is, assuming that p = 91 is prime, which it is not (see above)

This page has been created and is maintained by Elena Machkasova
Comments and suggestions are welcome at emachkas@wellesley.edu
Spring Semester 2002