RSA Notes

A public/private keypair consists of a modulus, a private exponent, and a public exponent. The public key contains the modulus and the public exponent. The private key contains the modulus and the private exponent (http://en.wikipedia.org/wiki/RSA_(algorithm)).

Encoding Formats

PEM and DER are not really key formats, but rather a ways of serializing certain data structures. Knowing that you have a PEM or DER file is kind of like knowing that you have a CSV or a JSON document. It tells you about the syntax, but it doesn't tell you what the content means. The best way to find out what format your key is stored in is to dump view the encoded structure a DER-inspection tool.

PEM

A PEM file is a bas64-encoded DER file with a text header and footer.

More specifically, pem-data = "-----BEGIN PUBLIC KEY-----" + newline + base64( der-data ) + newline + "-----END PUBLIC KEY-----". For example:

DER

"DER" stands for 'Distinguished Encoding Rules', an ASN.1-based format for serializing structured information. Saying that a key is DER-encoded does not give a full picture, because you still need to know the encoded structure. I have seen both Public Key Info and RSA Public Key structures emitted by OpenSSL libraries. Both types of structures are described by X.509.

Public Key Formats

Raw Key Data

Since a public key is made of 2 integers, there is no such thing as 'raw public key data'. Some method of serialization must be used to encode the numbers as a byte stream. Usually public keys are stored as DER-serializations of one of the following X.509 structures:

Certificate

A signature is an ASN.1 structure that includes a Public Key Info structure along with a bunch of other stuff. I do not wish to familiarize myself with the details of 'other stuff', but read on for details about the public key structures.

Public Key Info

A Public Key Info is an ASN.1 sequence containing 2 elements: a header giving information about the algorithm used (this header is itself a sequence, with the name of the algorithm as the first element ("rsaEncryption", for RSA keys, and I don't know what the other element(s) are for; the ones I've looked at are empty), and a DER-encoded RSA Public Key structure (read: not the RSA Public Key sequence itself, but DER-serialized, so it will appear in the Public Key Info sequence as a BitString) providing the actual key data.

i.e. public-key-info = [ ["rsaEncryption", nil], der( rsa-public-key ) ], "rsaEncryption" is an object id (tag=6) and der( rsa-public-key ) indicates an RSA Public Key structure serialized using DER rules.

RSA Public Key

An RSA Public Key is an ASN.1 sequence containing 2 integers: the modulus (this should be a very large number) and the public exponent (a smaller one, usually 3, 17, or 65537). When encoded as an RSA Public Key in DER, a 2048-bit key usually takes up exactly 270 bytes.

i.e. [ exponent, modulus ], where exponent and modulus are integers.

Java's PublicKey#getEncoded() function returns a DER-encoded structure that includes a header ("rsaEncryption") and a BitString (tag=5) that includes the 'raw key data.' To inspect the structure of a DER-encoded key, you can use Ruby's OpenSSL::ASN1 module:

asn1 = OpenSSL::ASN1.decode(File.read('public-key'))

Key Data Generated by Standard Libraries

Generated with the help of some functions I wrote.

PHP openssl_* functions

function derToPem($der) {
	$pem = chunk_split(base64_encode($der), 64, "\n");
	$pem = "-----BEGIN PUBLIC KEY-----\n".$pem."-----END PUBLIC KEY-----\n";
	return $pem;
}

function pemToDer($pem) {
	if( !preg_match('#--+BEGIN PUBLIC KEY--+\n(.*)\n--+END PUBLIC KEY--+#s', $pem, $bif) ) {
		throw new Exception("Failed to parse PEM data: $pem");
	}
	$base64 = $bif[1];
	return base64_decode($base64);
}

$keyPair = openssl_pkey_new( array(
	'digest_alg' => 'sha1',
	'private_key_bits' => 2048, // For faster unit testing
	'private_key_type' => OPENSSL_KEYTYPE_RSA
) );
		
$det = openssl_pkey_get_details($keyPair);

/** PEM-formatted public key */
$pubKeyPem = $det['key'];
$pubKeyDer = pemToDer($pubKeyPem);

At this point $pubKeyDer is the following DER-encoded structure:

Sequence[
  Sequence[
    ObjectID:"rsaEncryption",
    null
  ],
  BitString (270 bytes)
]

Java

package togos.cryptosandbox;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;

public class RSAKeyGenerator
{
	protected static KeyPair generateKeyPair() {
		try {
			KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
			// On Harold...
			// 1024 bits = pretty much immediate
			// 2048 bits = takes a couple seconds
			// 4096 bits = takes many seconds
			kpg.initialize(2048);
			return kpg.generateKeyPair();
		} catch( NoSuchAlgorithmException e ) {
			throw new RuntimeException(e);
		}
	}
	
	public static void writeFile( String filename, byte[] data ) throws IOException {
		File f = new File(filename);
		if( !f.getParentFile().exists() ) f.getParentFile().mkdirs();
		FileOutputStream fos = new FileOutputStream(f);
		fos.write(data);
		fos.close();
	}
	
	public static void main(String[] args) throws
		NoSuchAlgorithmException, IOException
	{
		KeyPair keyPair = generateKeyPair();
		
		writeFile( "generated-keys/java/private-key", keyPair.getPrivate().getEncoded() );
		writeFile( "generated-keys/java/public-key", keyPair.getPublic().getEncoded() );
	}
}

The generated public key is the exact same structure as that generated by PHP:

Sequence[
  Sequence[
    ObjectID:"rsaEncryption",
    null
  ],
  BitString (270 bytes)
]

The private key is similar but has an integer and an OctetString instead of a BitString:

Sequence[
  Integer:0,
  Sequence[
    ObjectID:"rsaEncryption",
    null
  ],
  OctetString (1192 bytes)
]