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

What you need:

Purpose

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

Google Cloud Linux Server

If you don't have a Linux machine handy, do project H 201 in the Blockchains section to make a Google Cloud Linux Server and use that.

Downgrading OpenSSL in Colab

Google Colab has openssl 3 which does not work.

Execute these commands to downgrade to version 1.

!openssl version

!wget http://security.ubuntu.com/ubuntu/pool/main/o/openssl/openssl_1.1.1f-1ubuntu2.20_amd64.deb
!wget http://security.ubuntu.com/ubuntu/pool/main/o/openssl/libssl-dev_1.1.1f-1ubuntu2.20_amd64.deb
!wget http://security.ubuntu.com/ubuntu/pool/main/o/openssl/libssl1.1_1.1.1f-1ubuntu2_amd64.deb

!sudo dpkg -i libssl1.1_1.1.1f-1ubuntu2_amd64.deb
!sudo dpkg -i libssl-dev_1.1.1f-1ubuntu2.20_amd64.deb
!sudo dpkg -i openssl_1.1.1f-1ubuntu2.20_amd64.deb

!openssl version
Now you can do the project below in Google Colab, by adding an exclamation mark before each command.

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.

Generating a Private Key with OpenSSL

In a Terminal, execute this command:
openssl genrsa 512
You see a PRIVATE KEY, as shown below.

PEM Files and Parsing ASN.1 Format

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 "asn1parse" 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 asn1parse -in key.pem
This reveals the RSA parameters, as labelled below in red.

Displaying the Public Key

An RSA public key consists of two values:

Execute these commands 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 
It's 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 this command to make a 2048-bit encrypted private key file. Enter a password, such as P@ssw0rd, when prompted to.

openssl genrsa -out key3.pem -aes256 2048
It's much longer, as shown below.

Execute this command to see the keyfile:

cat key3.pem
It's encrypted with AES-CBC, 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.
-----BEGIN RSA PRIVATE KEY-----
MIIBPAIBAAJBAOz8ZwiRyoTBYCoExLqzlnr1GJ3D1qk+yQXwSEET2mRfbU+B/cNP
cI6eQUnA4rSOHmwhsSwEXhPnzMvVjqIonPsCAwEAAQJBAIfNH3HOsaGfem65qs5e
xxxxxxxxxObZPrKzfYQlT0miNyOrzA65U3yDa6qAZgwXPJuWU6b86PTPFFUQCei9
TFkCIQD2l+VEohU9goQplYkRnpfujZ6flUm96B6biqnPk9tUTQIhAPYGr50vSZqI
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
jDyz+KS5z68xHakCIEfyCpb/xhlvsIQZPLMj1q0eaydxrS4OxU0WuiKOCSYPAiEA
nahcVY0yHAgXLvm1vSZgzYrcs1ESCKPQ+KWy8+meq80=
-----END RSA PRIVATE KEY-----
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.
-----BEGIN RSA PRIVATE KEY-----
MIIBPAIBAAJBANY4uzFtiUFp5zL5puSWi0UVRj6U1v3uJi23d7p40VgEh1SmR0lx
JjHNgHjqzU+gUeMoipx33kYvFRteCEH36JsCAwEAAQJBAMKsuYi4l0Qn3qBXedA/
xxxxxxxxxxxxxxxxD50ZEH2frkuuDlE/IVjIvbd78Rdgdwpt+hcrRh0NPLohTins
dgECIQDr2CcsldtKiBOQxxxcVtM4IZtpqlXV2U8zFgf6/LnPmwIhAOiHgwUpMSty
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
OUbS4KlR8bN0WwIhAJVYU8JAzp/E2j6pAGJhGbpKUnb9gZpwyXvdxFa8OWQBAiEA
41EhQq90+1NqwpMIBoqYvQvqYPTW/y9KEJDbkyXK2r8=
-----END RSA PRIVATE KEY-----
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