# Encoding Problem & Algorithm

• Apr 30th 2009, 10:33 AM
smithhall
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.
• May 1st 2009, 05:26 AM
Encryption
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:
Quote:

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
Quote:

Now calculate Ci = Mei mod pq for each i.

$\displaystyle C_i = M_i^e\mod pq$

and
Quote:

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

$\displaystyle M_i = C_i^d\mod pq$

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?
Quote:

We have received an important encrypted message – it reads FRWHVWNUTSHX.
I'm not sure.

Anyway, here are my answers.
Quote:

(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 $\displaystyle d = 65$. Can you do this OK?
Quote:

(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.
Quote:

(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 $\displaystyle c^{65} \mod 679$ can't be done in a single operation, because of overflow errors. In the end, I found I could calculate $\displaystyle c^3 \mod 679$ without causing errors. Then by careful manipulation of powers (I used $\displaystyle 65 = 3\times 3\times 2\times 2 + 3\times 3\times 3 + 2$), I obtained the following numbers: 147, 108, 92, 358, 512, 676, which being interpreted is: FREEODUNSTAZ.

Not sure what that means, though!

• May 1st 2009, 03:39 PM
aidan
Quote:

Originally Posted by Grandad
It took me some time to discover this - having never seen this encryption before.

Grandad, I thought you knew eveything.
• May 1st 2009, 11:10 PM