RSA Encryption - another example and discussion

Following on from my previous blog I thought I would encrypt a message that you out there can have a go at decrypting. Here it is: 331, 230, 230, 311, 392, 507, 180, 221, 187, 466, 283, 392, 442, 230, 127. The key information is n=551 and e=41. This should be enough for you to decrypt this message.

Of course with a programmable calculator there is a limit to what you can usefully do with RSA. One of the problems of the fx-50F is that there isn't a function which can do modulo arithmetic and nor  is there a way to find integer parts and remainders on division, and so the ways round this (the while loops in my exponentiation mod n program) make processing much too slow when n becomes larger than a 1000 or so. Hence, this doesn't make the encryption viable unless the keys are hidden.

In reality there is also the issue of finding two primes for n. You don't want to choose one of the primes to be large and the other small, as the small prime will easily be found as a factor in n. However, you also don't want to choose two primes that are very close in value because, as we shall see, n can again be factored quite quickly. So we need two similarly large primes that are not too close in value to make RSA work.

There are other issues as well. We don't want to have the message number m larger than n. Suppose we have the system as set up in my previous example and encrypt m=250, that is we want 250¹³ (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133¹³³ (mod 221) we find m=29. That's because 250 is congruent to 29 modulo 221. So we don't get a one-to-one relationship.

If we choose much bigger primes, n becomes sufficiently large that we can start encrypting blocks of text. For example, in the message 'all aliens are friendly' we could take the word 'all' and convert it into a single number 11212. The next three characters ' al' would be 270112 etc.

Finally, in some situations we find that the encrypted message number m' and the message number m end up being the same and this may be something to avoid.