This problem is about the RSA cryptosystem; a process by which people can

communicate securely. It is widely used in today’s society.

It is possible to turn every English phrase into a sequence of numbers. Assign the letters of the

alphabet A,B,C,. . .,Y,Z with the numbers 0, 1, 2, . . . , 24, 25, respectively.

We’ll deal with 2 letters at a time: every pair of letters can be uniquely represented by a number

less than 676 in base 26 notation. Every pair of letters corresponds to some between 0 and 675

inclusive, and any such number corresponds to a pair of letters.

For example, to convert DISCRETE into numbers we would do the following: DI–SC–RE–TE

becomes

D is 3, I is 8: so DI is 3 × 26 + 8 = 80.

S is 18, C is 2: so SC is 18 × 26 + 2 = 470.

R is 17, E is 4: so RE is 17 × 26 + 4 = 446.

T is 19, E is 4: so TE is 19 × 26 + 4 = 498.

Thus, DISCRETE would be written 80–470–446–498.

Conversely, if we are given a sequence of numbers less than 676, then we can convert them into

English by using the division algorithm with divisor 26. To translate 352–501–13–278 we find

352 = 13 × 26 + 14

501 = 19 × 26 + 7

13 = 0 × 26 + 13

278 = 10 × 26 + 18;

and so we’d get letters 13,14,19,7,0,13,10,18; which reads NOTHANKS.

A simplistic version of the RSA cryptosystem works in the following way: select two primes p and

q so that pq is just bigger than 676. The best available choice is p = 7, q = 97, so that pq = 679.

Now choose any integer e > 1 which is relatively prime to (p − 1)(q − 1). It turns out we just need

to choose any integer e > 1 not divisible by 2 or 3.

To encrypt a message M, first turn it into a sequence of integers M1,M2, . . . ,Mk, all less than 676.

Now calculate Ci = Mei mod pq for each i. Your calculations will give you k numbers C1,C2, . . . ,Ck

all less than pq = 679. Convert this sequence back to English to get your encrypted message. (If you get 676,677 or 678, then use the symbols “!”, “?” and “#”, respectively.)

To decrypt, convert the encrypted message into numbers C1,C2, . . ., and calculate Mi = Cdi mod pq,where d is an integer satisfying de ≡ 1 mod (p − 1)(q − 1). This will give you the message as a sequence of numbers less than 676, and you can then translate that back into English using the division algorithm as described above.

We have received an important encrypted message – it reads FRWHVWNUTSHX. We know the

message was encrypted using e = 257. In each of the following parts, show all of your working.

(a) Determine the d we need to use to decrypt this message. (HINT: use the Euclidean algorithm

to first solve 257x+(p−1)(q −1)y = 1 – you should then be able to determine d; think about

it!)

(b) Convert the encrypted message into a sequence of numbers less than 676.

(c) Decrypt the message using your answers to the first two parts and convert into English.