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

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

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).

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 |

**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.

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