Asymmetric Encryption: RSA

The Rivest-Shamir-Adlemen (RSA) algorithm has been used for decades. It is commonly used to sign files and to exchange temporary symmetric keys.

Learning Objectives

You should be able to:

• Create a public key/private key pair with GnuPG
• Export public and private keys
• Sign a file with a private key
• Encrypt a file with a private key

Video Walkthrough

Use this video to follow along with the steps in this lab.

About RSA

The Rivest-Shamir-Adlemen (RSA) cryptosystem is widely used. Everybody simply refers to it as RSA. It is a cryptosystem in that is more than just one algorithm. The RSA algorithm's security comes from the difficulty of factoring extremely large numbers. Below is a sample number that represents a public key:

8885433994858512806658715134858541745334378786271
2968331381848895031329615390611363677038236989872
6207590351381649865201542888928197263259697442353
2126587482050441559219248206185582048503670130227
8341028669573086937176752770346609141404604235125
8484081749958759328089377609803747581648962695820
5837508048842628731477104128542503308748449459001
9169018558093907762953687243840019791957078963913
7711209705478706065025451012043381766201060123580
3380861412558915949015080482947098099719725556023
5345214960340870779166321318368512982288168762606
3859407642992756090551248261843554783232903036734
612066227567443149785711799

A private key could look like the following:

2108667219405523084361266944390457414981100204719
9307203395284381153222757946337921885021264571719
6410130390769578361273853676133972540889441275375
9474283569859934251048504737796243179884389957977
0319434276737961042366904179340813692562855003898
8650281952786162820187411823447359607477793424160
7003620729583545933151625312686717844011644780183
4476800207659890363928165409520291568362358485983
0493317498161766597797777750507042302651705303121
0902833845226416239942102500184765407260305077879
0932784226771957796904573649393088878115602311774
9485626366363910908053025829076120576865569521648
29704687199975950062033355959

(There are some other numbers that make up the public and private keys, but those are not important for now.)

Those numbers are big. Really big. It is not currently computationally feasible to "crack" a private key if you have the public key and some sample data. Because those numbers are so big, they are typically represented in a much more compact format. However, most people never even have to look at the keys. The keys just live on computers and applications use them when needed.

Downside of RSA

RSA keys are computationally expensive to create. Instead of creating a new private key/public key pair every time somebody wants to exchange a secret, the same private/key public key pair is reused. The fact that the key is reused means that RSA key exchange does not provide perfect forward secrecy (PFS). Imagine that somebody captured all of your encrypted network traffic for a year. In that year, the attacker could not read any of the data. But, at the end of that year, the private key became compromised and the attacker got a hold of it. The attacker could go back and decrypt all of your data. Not great.

RSA is still very popular for encrypting emails and signing files, but it is no longer the preferred solution for key exchange. For modern key exchange, Elliptic Curve (EC) cryptography is preferred. With EC cryptography, a new public key/private key pair is created each time a temporary symmetric key needs to be exchanged which dramatically reduces the effects of a compromised private key.

Create a Key Pair with GnuPG

The GnuPG application can be used to create RSA key pairs.

• Launch your Linux virtual machine and connect to it.
• In the terminal, run the following command to ensure that you are in your home directory.

cd ~

• Run the following command to start the key creation wizard.

gpg --full-generate-key

• Choose RSA and RSA (the default.)

• Enter 3072 for the key size.
• Enter 0 for the key expiration. This key will not expire.
• Confirm that the key will not expire.
• Enter a name. Use your real name if you want, or enter a fake one. Gpg does not know your true identity.
• Enter an email address (real or fake).
• Enter a comment or leave it blank. A comment could be a note about how the key is intended to be used.
• Enter o to confirm that the key settings are correct.

• You will need to enter a passphrase. Enter something simple (and remember it).
• Notice the messages that appear during and after entering the passphrase.

• The RSA private key is very large and requires a lot of randomness for the key to be secure. This process is computationally expensive.
• Once the key has been made, some key details are displayed.

Export RSA Keys with Gpg

Right now, the private key/public key pair only lives on your computer. But you might want to copy your private key to another computer you own. And you might want to email your public key to colleagues so that you can send them digitally signed messages.

• Export your public key with the following command. (Replace the email address with the email that you used when creating your key.)

gpg --output public.key --armor --export bugs@bunny.com

• Run ls and verify that the file public.key exists in the directory.
• View the contents of the key file with the cat command.

cat public.key

You should see something similar to the following.

• Notice that the text says "PGP" public key block. Think of PGP as a wrapper for RSA.
• Export your private key with the following command.

gpg --output private.key --armor --export-secret-key bugs@bunny.com

• Run the following command to display the contents of the key file.

cat private.key

You should see output similar to the following.

Sign a File

Signing a file verifies that you are the person who had control of the file when it was signed. It basically confirms authorship.

• Run the following commands to create a text file and edit it in nano.

touch message.txt
nano message.txt

• Add a controversial opinion to the text file.

• Save the file with control+o. Exit with control+x.
• Now you will clear-sign the file. Clear signing leaves the file in a readable format.

gpg --clearsign message.txt

• Confirm your passphrase.

• There will not be a file called message.txt.asc in the directory. View it with the cat command.

cat message.txt.asc

You should see output similar to the following.

• Notice that your message is intact. The PGP signature can be verified with your public key.

At this point, you could send your public key and this signed file to anybody in the world and they could verify that it was your private key that was used to sign it.

Encrypt Files with a Public Key

Clearsigning the file left it in a human-readable format. But what if you were concerned about spies? If you have somebody's public key, you can encrypt data using they public key, and then only they can decrypt it.

• Run the following command to encrypt data for yourself. (Replace the email address with the one you used previously.)

gpg --encrypt -r bugs@bunny.com message.txt 

• The above command encrypts the file for the recipient bugs@bunny.com using Bugs' public key.
• If the command works, a file message.txt.gpg will now exist in the directory.
• Use cat to view its content.

cat message.txt.gpg

You will see output similar to the following.

Now, the only person in the world who can decrypt this is the person with the private key associated with the public key.

Clean up

When you are finished with the exercise, you can delete the 5 files created in your home directory.

rm message.*
rm *.key

The "*" character is the wildcard character that matches any character. The above commands delete all files that start with "message." or end with ".key."

The keys you created still exist on your computer, but it is fine to leave them there. If you really want to delete the keys from your system, run these commands (replacing the email as needed). The first command deletes the private key, and the second command deletes the public key.

gpg --delete-secret-keys bugs@bunny.com
gpg --delete-keys bugs@bunny.com

Reflection

• What techniques could be used to protect private keys?
• If you wanted to encrypt your email with your private key, where would that private key need to live? On your computer? On a remote email server? What would be the dangers of keeping the key in either place?
• In this exercise, Bugs Bunny was used for the name. If anybody can pick a name, how can we know the true identity of the person who created the key pair? (Hint: search the internet for "web of trust" for some possible answers.)

Key Terms

• RSA Cryptosystem: A widely used asymmetric cryptographic algorithm named after its inventors Rivest, Shamir, and Adleman. It relies on the mathematical properties of large prime numbers to provide secure data encryption, decryption, and digital signatures. RSA uses a pair of keys: a public key for encryption and a private key for decryption.
• Clearsign: A method of digitally signing a message in a way that the signed message remains human-readable. Clearsigning allows the recipient to verify the authenticity and integrity of the message using the sender's public key without needing to decrypt the message content.
• Perfect Forward Secrecy (PFS): A property of secure communication protocols that ensures session keys will not be compromised even if the private key of the server is compromised in the future. PFS achieves this by generating unique session keys for each communication session, which are not derived from the server's private key.