C 403: RSA Key Formats (10 pts + 30 extra)

What you need:

A Web browser and a Google account, or
Any Linux or Mac computer with openssl will work, if you remove the ! from the start of the commands below.

Purpose

To understand the various ways RSA keys are stored, and convert among them.

Summary of RSA

Here's a diagram from the textbook showing the RSA calculations.

1. RSA Private Keys

PKCS #1 Version 2.1

This format is specified in RFC 3447: Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1, in "Appendix A. ASN.1 syntax", as shown below.

Using Google Colab

In a browser, go to

https://colab.research.google.com/

If you see a blue "Sign In" button at the top right, click it and log into a Google account.

From the menu, click File, "New notebook".

Generating a Private Key with OpenSSL

First we'll generate an RSA private key and print it on the Terminal. This is a 512-bit key, too short to be secure in the modern world, but it shows how the format looks.

In Colab, execute this command:

!openssl genrsa 512

You see a PRIVATE KEY, as shown below.

PEM Files

This format is called PEM (Privacy Enhanced Email). The private key is encoded as a big blob of Base64 text.

To parse it, you need to save it in a file and use the "rsa" command.

Execute these commands to generate a "key.pem" file, view it, and parse it.

!openssl genrsa -out key.pem 512 !cat key.pem !openssl rsa -in key.pem -text

You see the PEM file, followed by the parsed contents.

The important fields are as labelled below in red.

Displaying the Public Key

An RSA public key consists of two values:

n A long integer called the RSA modulus
e A positive integer, often small, called the RSA public exponent

Execute this command to generate the public key from your "key.pem" file.

!openssl rsa -in key.pem -pubout

Execute these commands to save the public key in a "public.pem" file, print it out, and parse it:

!openssl rsa -in key.pem -out public.pem -pubout !cat public.pem !openssl rsa -pubin -text < public.pem

This displays the "Modulus" n and the "Exponent" e, as shown below.

Making Longer Keys

The keys above are the default size of 512 bits, which is no longer considered secure.

Execute these commands to make a 2048-bit private key and display it.

!openssl genrsa -out key2.pem 2048 !cat key2.pem

It's much longer, as shown below.

Execute these commands to see the public key.

!openssl rsa -in key2.pem -out public2.pem -pubout !openssl rsa -pubin -text < public2.pem

The public key is also much longer, as shown below.

Encrypting the Private Key

If someone steals the private key file, they can read your encrypted data. To prevent that, the private key is usually stored as an encrypted file.

Execute these commands to generate a 2048-bit encrypted private key file. Enter a password, such as P@ssw0rd, when prompted to.

!openssl genrsa -out key3.pem -aes256 2048 !cat key3.pem

The first line now says the key is encrypted, as shown below.

Whenever you use this private key file, you'll need to supply the password.

Execute this command to display the public key.

!openssl rsa -in key3.pem -pubout

Enter your password to see the public key, as shown below.

C 403.1: Find p (5 pts)
Find p from the key below.
-----BEGIN RSA PRIVATE KEY----- MD0CAQACCQDTPWtAKLuWbwIDAQABAgh2uVRnKpyb0QIFAP2MzVUCBQDVR/SzAgRu u6WZAgQ2tLA1AgR2EBWK -----END RSA PRIVATE KEY-----
The flag is p in hex, like this:
7610158A

C 403.2: Find Public Key (5 pts)
Find the Public Key from the key below.
-----BEGIN RSA PRIVATE KEY----- MD0CAQACCQDTPWtAKLuWbwIDAQABAgh2uVRnKpyb0QIFAP2MzVUCBQDVR/SzAgRu u6WZAgQ2tLA1AgR2EBWK -----END RSA PRIVATE KEY-----
The flag is the public key in Base64, like this:
i810CAwEAAQ==

C 403.3: Find q (10 pts extra)

Find q from the key below. Portions of the key have been redacted, as shown in bold below.

The flag is q in hex, like this:

7610158A

C 403.4: Find p (20 pts extra)

Find p from the key below. Portions of the key have been redacted, as shown in bold below.

The flag is p in hex, like this:

EBD8272C95DB4A88139000001C56D338219B69AA55D5D94F331607FAFCB9CF9B

Sources

RSA Key Formats
Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1
ASN.1 key structures in DER and PEM
Cryptography Tutorials - Herong's Tutorial Examples
Use OpenSSL To Generate Key Pairs
Generate RSA private key from n, e, d, p, q values in bash with OpenSSL
RSA: Get exponent and modulus given a public key

Posted 3-23-16 by Sam Bowne
Updated to refer to "P" in chal d 11-20-17 3:23 pm
Added to Crypto Hero 4-15-18 9:33 pm
Ported to new scoring engine 7-8-19
Extra credit points specified 9-10-20
512 length added 10-20-20
openssl downgrade instructions added 10-31-23
Updated to use openssl 3 on 3-13-25
Video added 3-19-25