Encoding Problem & Algorithm
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
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
(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.