See section 10B in the text by Childs.
We shall encode and then decode the very short message
| Tomorrow at 4:15 |
as an example of RSA-style encryption.
The first step is to convert the message, which is a sequence of text characters, into a sequence of numbers. We shall use the standard ASCII scheme for this. This scheme matches characters with the integers from 32 to 126 represented in base 16 as follows:
0123456789ABCDEF
2 !"#$%&'()*+,-./
3 0123456789:;<=>?
4 @ABCDEFGHIJKLMNO
5 PQRSTUVWXYZ[\]^_
6 `abcdefghijklmno
7 pqrstuvwxyz{|}~
Thus, for example, the character for the numeral `5' is represented by the hexadecimal expression 35 (for the number 53) while the lower case letter `k' is represented by the hexadecimal expression 6B (for the number 107). The numbers 0-31, which are represented as the hexadecimal range 00-1F, are reserved for ``control'' characters. An example of this is the linefeed, which is given the hexadecimal value 0A, i.e., is represented by the number 10.
Our short sample message is represented (with ordinary notation) in ASCII by the sequence
| 84, 111, 109, 111, 114, 114, 111, 119, 32, 97, 116, 32, 52, 58, 49, 53, 10 . |
We shall use the square-free modulus m = 253 = (11)(23). The least common multiple of 10 and 22 is mu = 110. The encrypting exponent will be 7. The encrypted sequence then is
| 149, 199, 43, 199, 137, 137, 199, 169, 142, 224, 162, 142, 233, 108, 25, 235, 175 . |
Since 7 . 63 EQUIV 1 (mod 110), one has
| y EQUIV x^{7} (mod 253) if and only if x EQUIV y^{63} (mod 253) . |
Therefore, the original sequence may be recovered from the encrypted sequence using 63 as the decrypting exponent.
Following that the original message may be reconstructed using the ASCII chart.
Computing Precision Note that without extra arrangements most ordinary computer programs are able to represent integers with complete precision only up to size 2^{31}, which is a 10 digit integer. This means that such a program can run into trouble trying to multiply two 5 digit integers with complete precision. So if one tries to use the method above in the case where the square-free modulus m is 111547 = (331)(337), there is a problem. For this reason one needs to have what is called arbitrary precision integer arithmetic available.