RSA Encryption - an example

Following my previous blog about RSA encryption let's now try and encrypt the message 'all aliens are friendly'.

Using the Is it prime? program, we can choose a couple of prime numbers. We try some relatively small numbers 13 and 17 which you can easily verify are both prime. Run the Is it prime? program. X? is displayed. Enter 13 and press [EXE]. 1 is returned (1 - number is prime, 0 - number is not prime). So our number n=13x17=221 and φ(221)=(p₁-1)(p₂-1)=12x16=192.

Next we choose e. We choose e=13 and using the program gcd by subtraction you can verify that gcd(13,192)=1. Run the program. A? is displayed. Enter 13 and press [EXE]. B? is displayed. Enter 192 and press [EXE]. The result 1 is displayed indicating that the gcd(13,192)=1.

Next we calculate d which is the inverse of e modulo 192. Run the program Multiplicative inverses in Zn. A? is displayed. Enter 13 and press [EXE]. B? is displayed so enter 192 and press [EXE]. After a bit of a wait the result of 133 is displayed. So d=133.

So now we can encrypt the message 'all aliens are friendly'. The letter a corresponds to 1 and we can see immediately that m'=1 since 1¹³≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡12¹³(mod 221). Run the Exponentiation mod n program. X? is displayed. Enter 12 and press [EXE]. A? is displayed. Enter 13 and press [EXE]. B? is displayed, so enter 221 and press [EXE]. The result is 116 and this is m'. Thus so far the encrypted message is in numbers 1, 116, 116 for the word 'all'.

Continuing in this way we can obtain the full encrypted message 1, 116, 116, 79, 1, 116, 178, 122, 209, 32, 79, 1, 18, 122, 79, 214, 18, 122, 209, 4, 116, 77.

To decrypt the message we need to take each number m' in the encrypted message and calculate m≡(m')¹³³ (mod 221) which again you can use the Exponentiation mod n program to do.