Anatomy of a PEM file
Let’s see how a PEM file is constructed and what does its content mean. We will use an RSA private key stored as a PEM file for our reference in this article.
What is PEM
From wikipedia -
Privacy-Enhanced Mail (PEM) is a de facto file format for storing and sending cryptographic keys, certificates, and other data, based on a set of 1993 IETF standards defining “privacy-enhanced mail.”
So any private key/public key/certificate, etc that we generate can be stored in a PEM file format (.pem).
An example of such private key is -
-----BEGIN RSA PRIVATE KEY-----
MCUCAQACAwDZhwIDAQABAgIIAQICAO8CAgDpAgIAkQICAMECAgDH
-----END RSA PRIVATE KEY-----
RSA
From wikipedia -
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers are kept secret. Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the prime numbers.
Let’s see an example on how an RSA public/private key pair is generated and used.
**Warning: maths ahead**
First we create a public key and encrypt a message -
Step 1 — Select 2 prime numbers, say p = 7 and q = 11.
Step 2 — Calculate modulus n = p*q, so n = 77.
Step 3 — Calculate public exponent e which is less than n and relatively prime to (p-1)*(q-1). So we want e (<77) relative prime to 60, say e = 7.
Now combination of modulus and public exponent, ie. our n and e is our public key. We can use this public key to encrypt any message m into ciphertext C = (m^e)%n. If m is 9, then C = 9⁷%77, so C = 37.
We successfully encrypted our message 9 into ciphertext 37.
Now let’s see how we can decrypt our ciphertext using our private key -
Step 1 — Calculate private exponent d as (d*e)%((p-1)*(q-1)) = 1. So (7*d)%60 = 1, which gives d = 43.
Combination of modulus and private exponent, ie. our n and d is our private key. We can use this private key to decrypt out ciphertext C into original message m = (C^d)%n. So m is 37⁴³%77 = 9.
We successfully decrypted out ciphertext 37 into original message 9.
Since now we know how to use and generate a private/public key pair and use it, let’s see how we store a private key.
PEM File Format
To store any kind of data (eg. a private key) in PEM format, we just need to base64 encode DER serialization of ASN.1 representation of our data.
Let’s break down what the above statement actually means 😄.
Data
The data can be pretty much anything. For us, it is our private key. We already saw above that a private key mainly consists of 2 numbers, modulus n and private exponent d. In an actual private key, we store the following information -
- version — value 0
- modulus — n
- public exponent — e
- private exponent — d
- first prime number — p
- second prime number — q
- first exponent — d%(p-1)
- second exponent — d%(q-1)
- coefficient — (inverse of q)%p
- some other info (optional)
ASN.1
Again, from wikipedia -
Abstract Syntax Notation One (ASN.1) is a standard interface description language for defining data structures that can be serialized and deserialized in a cross-platform way.
ASN.1 provides a standard definition for any data in a language neutral way.
A (PKCS1) RSA private key’s ASN.1 structure is -
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponentINTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
Here, SEQUENCE is equivalent to “struct” in most programming languages. It holds a fixed number of fields of different types.
Each datatype in ASN.1 has an assigned tag value which is used in serialization/deserialization of data (next section). A list of some common ASN.1 types and their tags are -
DER Encoding
Once again, wikipedia -
DER (Distinguished Encoding Rules) is a restricted variant of BER for producing unequivocal transfer syntax for data structures described by ASN.1
The most significant DER encoding constraints are:
Length encoding must use the definite form
Additionally, the shortest possible length encoding must be used.
Bitstring, octetstring, and restricted character strings must use the primitive encoding.
Elements of a Set are encoded in sorted order, based on their tag value.
DER is a serialization-deserialization format for ASN.1 structures. It uses a simple tag-length-value format to serialize an ASN.1 structure.
Eg. If we have an integer x = 10, then its DER serialization will be — 00000010 0000001 00001010
here, tag (2) = 00000010
, length (1) = 00000001
and value (10)= 00001010
.
Keeping this in mind, we can now convert our example private key fields into DER serialized format (each byte represented as an integer value)-
- version (tag = 2, length = 1, value = 0) => [2, 1, 0]
- modulus n (tag = 2, length = 1, value = 77) => [2, 1, 77]
- public exponent e (tag = 2, length = 1, value = 7) => [2, 1, 7]
- private exponent d (tag = 2, length = 1, value = 43) => [2, 1, 43]
- first prime number p (tag = 2, length = 1, value = 7) => [2, 1, 7]
- second prime number q (tag = 2, length = 1, value = 11) => [2, 1, 11]
- first exponent d mod (p-1) (tag = 2, length = 1, value = 1) => [2, 1, 1]
- second exponent d mod (q-1) (tag = 2, length = 1, value = 3) => [2, 1, 3]
- coefficient (inverse of q) mod p (tag = 2, length = 1, value = 2) => [2, 1, 2]
Encompassing above data is our SEQUENCE field (tag = 48, length = 27, value = <concatenation of above data>) => [48, 27, 2, 1, 0, 2, 1, 77, 2, 1, 7, 2, 1, 43, 2, 1, 7, 2, 1, 11, 2, 1, 1, 2, 1, 3, 2, 1, 2]
Converting it all to actual bytes (represented as hexadecimal) gives us -
301b02010002014d02010702012b02010702010b020101020103020102
BASE64 ENCODING
Wikipedia -
Base64 is a group of binary-to-text encoding schemes that represent binary data (more specifically, a sequence of 8-bit bytes) in sequences of 24 bits that can be represented by four 6-bit Base64 digits.
Base64 encoding can be used to convert any data into string.
For eg. base64 encoding of string abc
is YWJj
.
Base64 encoding of our private key data bytes gives -
MBsCAQACAU0CAQcCASsCAQcCAQsCAQECAQMCAQI=
Adding Header and Footer
Last step to produce a private (or any) key is to add appropriate header and footer. Since we constructed an RSA private key, we will add -----BEGIN RSA PRIVATE KEY-----
as header and -----END RSA PRIVATE KEY-----
as footer. This generates a complete private key -
-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAU0CAQcCASsCAQcCAQsCAQECAQMCAQI=
-----END RSA PRIVATE KEY-----
Code
Although we never have to write any code to do all of the above steps to generate a key pair, it is still fun to do it 😄.
Below is an implementation in golang on how to calculate individual parts of a private key and combine them to form a full fledged key.
Please note that above code is just for demonstration. It lacks many “security” and “validation” aspects. Do not use this in production.
Conclusion
We saw what does contents of a private key means and how we can construct it from the basic, ie. our two prime numbers p and q. In reality almost every language has this implementation built-in (or some famous and robust library) so we don’t need to implement it from scratch but its always good to know what happens under the hood.
Happy coding!