Thread: 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
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.

Hello smithhall

I have a solution - but I'm not confident that the coded letters are correct. I say this because there are clearly errors in the problem description. For example:

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.

This is obviously wrong: DI is 86, not 80. Such an elementary mistake in work where numerical accuracy is vital doesn't inspire confidence!

Also

Now calculate Ci = Mei mod pq for each i.

should read:



and

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

should again read



It took me some time to discover this - having never seen this encryption before. These formulae are to be found, for example, at RSA - Wikipedia, the free encyclopedia.

So I have to ask: is this sequence correct?

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

I'm not sure.

Anyway, here are my answers.

(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!)

I used the Euclidean algorithm and found . Can you do this OK?

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

This is very straightforward: 147, 579, 568, 358, 512, 205. To save time and (hopefully) avoid the sort of arithmetic error above I used a look-up table in an Excel spreadsheet.

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

This is the part where the arithmetic gets very difficult. Again I used the Excel spreadsheet, but even so it was very tricky because finding can't be done in a single operation, because of overflow errors. In the end, I found I could calculate without causing errors. Then by careful manipulation of powers (I used ), I obtained the following numbers: 147, 108, 92, 358, 512, 676, which being interpreted is: FREEODUNSTAZ.

Not sure what that means, though!

Spreadsheet attached.

Grandad

Originally Posted by Grandad

It took me some time to discover this - having never seen this encryption before.

Grandad, I thought you knew eveything.

Hello aidan

Originally Posted by aidan

Grandad, I thought you knew eveything.

No, this stuff's only been around for about 30 years, and I'm much too old for that!

Grandad