RSA Encryption and Authentication Primer

RSA Encryption is a cryptographic system that uses public and private keys to exchange messages. It was first published in 1977 by Ron Rivest, Adi Shamir, and Leonard Alderman. RSA stands for Rivest, Shamir, and Alderman.

The system works by generating two RSA encryption keys: one public and one private. The key generation itself requires a good random number generator and the ability to resolve very large prime numbers. (Wikipedia has a more precise explanation of how the keys are generated, but this is sufficient for our purposes).

The public key can:

  • Encrypt messages destined for the person who has the corresponding private key.

The private key can:

  • Encrypt messages for anyone who has a the public key (not used often)
  • Decrypt messages encrypted with the private key (99.9% of all usage)
  • Sign messages to authenticate “I am who I say I am”

The public key can be used to encrypt messages, but only the private key can decrypt messages.

Because a public key can encrypt, but only the corresponding private key can decrypt, this means:

  • I have to keep my private key a secret. I can’t share it, email it, or let anyone see / touch it.
  • I can give my public key to anyone without regard. I can publish it on the internet if I like.
  • This public / private key set can only be used to send me messages. If I want to send someone else a message, my keys won’t work.

This last point is very crucial. In order to have a conversation, you and your friend both have to have a public and private key set. You will keep your private key a secret, and your friend will keep theirs a secret. But, you have to email your public key to your friend and your friend has to email you their public key.

Once the exchange of public keys is complete, you can have a conversation.

How a Conversation Works

There are two parties to the conversation: You and your friend (who we will call “Friend” for simplicity’s sake).

  1. You send friend your public key.
  2. Friend sends you their public key.
  3. You use Friend’s public key to encrypt a message to them.
  4. You send the encrypted message to Friend.
  5. Friend receives the message.
  6. Friend uses his private key to decrypt the message.
  7. Fried reads the message.
  8. Friend uses your public key to encrypt his response.
  9. Friend sends you the message encrypted with your public key.
  10. You receive the message from your friend.
  11. You decrypt the message using your private key.
  12. You read the message.

At this point, if you want to respond, you’ll return to step 3 and repeat steps 3-12 until the conversation ends.

How RSA Authentication Works

RSA Authentication works similarly to how a conversation between two friends works above. The Both sides have to have private keys, and both sides must exchange their public keys so the other side has it. Then, a system known as challenge-response is used to prove to both sides that each is the entity it claims to be.

Typically, a server administrator will setup an application, system service, or daemon to use RSA keys for authentication. When they do this, they:

  1. Generate a public / private key pair for server A
  2. Generate a public / private key pari for server B.
  3. Give server A server B’s public key so that Server A can validate server B when it tries to sign in.
  4. Give server B server A’s public key so that it can validate Server A when it tries to sign in.
  5. Start the relevant system services or daemons.

Now, when server A attempts to authenticate with server B, the conversation goes something like this:

Server A: “Hello. I am Server A. I would like access please.”

Server B looks at the request, and doesn’t trust this “computer” who claims to be server A. So, Server B looks up the public key for Server A, and generates a random “challenge”, which it encrypts with server A’s public key. It then sends the encrypted challenge to the computer claiming to be server A.

Server A receives the encrypted challenge. Since Server A really is who it claims to be, this server has the private key needed to decrypt the challenge from Server B. So, it uses the private key to decrypt the message and finds out that the challenge phrase is “I love world peace and fluffy bunnies”. But, at this point, Server A still needs to convince Server B that they really are the computer they say they are. At the same time, we can’t send the challenge message back to server B in plain text. So, Server A uses Server B’s public key to re-encrypt the message, and then sends it back to server B. This is called the response.

Server B receives the response, decrypts it using its private key, and then checks to make sure the response message is identical to the challenge message. If it is, Server B will grant access. If it’s not, no access will be granted.

Note: In reality, the challenge string will not be human readable. It is much more likely to be a series of randomly generated values like: sxCz3yQ0jj94TNBHCavAK43jiIkOVOTBkSA4oQGClXw=