Public-Key Encryption with RSA

Encryption

Encryption enables you to take a text and convert it into a form that is not meaningful on its own. Decryption takes the encrypted text, often refered to as the cyphertext, and converts it back into its original, unencrypted, form. Encryption (decryption) often make use of a key which is used in converting the text (cyphertext) into cyphertext (text). If no key were used, the method for converting text (cyphertext) would be completely contained within the encryption (decryption). They key, which is supplied by the user of the encryption (decryption) software, allows the actual encryption (decryption) process to be different, based on the value of the key, each time the software is used.

It is often assumed by people new to encryption that you would always want to be able to decrypted whatever has been encrypted (assuming, of course, that you have the proper algorithms and keys). Being able to decrypted encrypted text is known as two-way encryption, and is very important in the private transfer of information. One-way encryption, however, means that the original text cannot be recovered from the encrypted text. Despite what it may seem at first, this is a very useful form of encryption. An excellent example of a use for one-way encryption is the UNIX password system. The UNIX password system stores passwords in encrypted form. When a user enters their password, it is encrypted and compared against the encrypted version of the password that the system maintains. Only if the two cyphertexts match is the user allowed access to the system. The benefit of one-way encryption is that nobody can decrypted the saved cyphertext to discover the password. Passwords can still be discovered by guessing, but that's a different issue.

Historically two-way encryption has used a single, private, key to do both the encryption and decryption. If two people, say Kim and Dana, want to exchange private messages, they would have to agree on a key and privately share it between them. Once they have agreed on the key, then they can exchanged private messages using encryption. The problem, however, is how can they privately agree on a private key. They could always meet in person, but that may not be practical. Kim and Dana have now found themselves in a Catch-22 situation.

Public-Key and RSA

Public-key two-way encryption is a recent development that allows Kim and Dana to communicate privately without ever having to meet. What makes this possible is that public-key encryption uses two keys, one key is used for encryption while the other is used for decryption, often called a key pair. Now, Kim can generate a key pair, $K$₁ and $K$₂, and Dana can generate another key pair $D$₁ and $D$₂. Kim sends Dana $K$₂ and Dana sends Kim $D$₂ in the clear. Now, whenever Kim wants to send Dana a message, Kim encrypts the text using $D$₂, the key that Dana sent, and sends Dana the resulting cyphertext in the clear. Since Dana is the only person with the key, namely $D$₁, that can decrypt the text sent by Kim, there is no harm in sending the cyphertext in the clear. It is interesting to note that not even Kim can decrypt the cyphertext. When Dana receives the cyphertext, it can be decrypted using the key $D$₁. Dana can send a private message to Kim using a similar process with the key $K$₁ supplied by Kim.

The RSA algorithm was one of the first public-key encryption algorithms developed. Named for it's developers, Ron Rivest, Adi Shamir, and Leonard Adleman, RSA relies on the difficulty of factoring large numbers for its security.
[Sorry, but your browser doesn't support Java.]

To create a pair of RSA public-keys you must first pick two prime numbers, $p$ and $q$, and compute $n\; =\; pq$. Next, choose such that $d$ is relatively prime to $p-1$ and $q-1$. Now, find $e$ such that $de\; modulo\; (p-1)(q-1)\; =\; 1$. The number $n$ is called the moulus and the key pairs are $(d,\; n)$ and $(e,\; n)$. For example, if you pick $p\; =\; 23$ and $q\; =\; 29$, then $n\; =\; 667$. Choose $d\; =\; 53$, giving $e\; =\; 93$. The key pairs are then $(53,\; 667)$ and $(93,\; 667)$. Try your hand at creating a pair of RSA public-keys.

NOTE: Due to limitations with the RSA implementation used here, the value of n should not be too small (i.e., less than 256).

In order to encrypt a text $T$, first you must represent the message as a number between $0$ and $n-1$. If $T$ is too large it can be broken up into a number of smaller pieces such that each piece could be represented by such a number. If each piece of the message is represented by $T$_i, then each by raising it to the $eth$ power $modulo\; n$. The result is a cyphertext message $C$_i. To decrypt $C$_i raise it to the $dth$ power $modulo\; n$.

Since web pages cannot show non-printable ASCII characters, use this applet to convert text between ASCII and hexadecimal representations.

Now that you have a pair of RSA keys and a hex version of your text, write one of the keys down and use the other to encrypt your text: