Cryptographic Interoperability: Keys

• Download C++ code - 4.03 KB
• Download C# code - 32.2 KB
• Download Java code - 9.49 KB

  Checksums for the download files available here.

Introduction

The Crypto++ mailing list occasionally receives questions regarding importing public and private keys from other libraries, and exporting keys for use in foreign libraries. This article will demonstrate moving RSA key material between Crypto++, C#, and Java. In addition, we will explore the special case of loading RSA and DSA keys in C#, since the CLR presents some interesting issues.

On the surface, we would expect that Crypto++ would be the most difficult while C# and Java would be the least difficult. In practice, Crypto++ and Java are the easiest libraries for which we can achieve interoperability. This is due to the CLR's lack of standardized serialization support for key pairs.

We observe what a kludge C# can cause when we read articles such as Porting Java Public Key Hash to C# .NET [14]. Developers are forced to deviate from the well established key formats of PKCS #8 and X.509 so that C# can import or export keys using XML as specified in RFC 3275, XML-Signature Syntax and Processing [26]. Sections 4.4.1 and 4.4.2 specify definitions related to DSA (and RSA) parameters such as the KeyInfo element and KeyValue element. To overcome this limitation in C#, we will use presents AsnKeyBuilder and AsnKeyParser, which allows us to serialize and reconstruct keys in PKCS#8 and X.509.

We examine the details of the process below. We do this so that when issues occur, we will be able to quickly identify and correct the problem. Along the way, references into various standards are presented for further reading when things do go wrong. Topics to be visited are listed below.

• PKCS and X.509
  • PKCS
  • X.509
• Key Syntax
  • PublicKeyInfo
  • PrivateKeyInfo
  • EncryptedPrivateKeyInfo
  • RSAPublicKey
  • RSAPrivateKey
• Key Formats
  • RSA Public Key
  • RSA Private Key
  • DSA Public Key
  • DSA Private Key
• RSA Cryptosystem
  • Public and Private Key Generation
  • Public Key Encryption
  • Private Key Decryption
  • RSAPrivateKey Syntax versus RSA Private Keys
• Generating, Saving, and Loading Keys
  • Crypto++
  • Java
  • C#
• ASN.1
  • INTEGER
  • OBJECT IDENTIFIER
  • BIT STRING
  • OCTET STRING
  • NULL
  • SEQUENCE

Though an understanding of ASN.1 is required for reading and writing keys, it introduced last since it is only offered for completeness. While visiting other sections which rely on a basic knowledge of ASN.1, understand that it is a presentation layer protocol, like any other presentation layer protocol such as Base64 encoding and decoding. Also, keep in mind that ASN.1 is similar to a programming language — complete with a language, grammar, and productions.

Finally, an ASN.1 dumper will prove useful. A graphical tool such as Objective System's ASN.1 View, or a command line tool such as Peter Guttman's dumpasn1 works well. While at Guttman's page, read over the X.509 Style Guide. Take the time to visit Michel Gallant's JavaScience. Dr. Gallant has authored several articles for MSDN in the .NET Cryptography arena, and offers both .NET and Java source code. Also of interest may be Cryptographic Interoperability: Digital Signatures [22], which looks at the issues encountered when using DSA signatures between C++, Java, and C#.

Downloads

There are three downloads which are available at the beginning of the article. Each archive is a project for creating and verifying. For those who only want the source code, Table 1 identifies the download of interest.

Filename	Language
CryptoPPInteropKeys.zip	C++/Crypto++
JavaInteropKeys.zip	Java
CSInteropKeys.zip	C#
Table 1: Source Code Archives

PKCS and X.509

Public and private RSA keys can be moved between systems using PKCS#1, PKCS#8, and X.509. This section examines the formats defined by each standard. For those interested in the full specifications, RSA's FTP site conveniently provides the PKCS series. If PKCS#1, v1.5 [6] is too dated (for example, multi-prime RSA), please see RFC 3447 for version 2.1 of the standard [21]. For the ITU-T X Series publications (including X.509 and X.690), visit the ITU website.

PKCS

PKCS is Public Key Cryptography Standard. The standard is maintained by RSA labs [4]. There are currently 10 standards, numbered 1 through 15 (PKCS#2 and PKCS#4 were merged into PKCS#1; PKCS#13 and PKCS#14 are listed as under development) [5]. Of the standards, PKCS#1: RSA Cryptography Standard and PKCS#8: Private-Key Information Syntax Standard are of interest.

Using ASN.1, PKCS#1 defines the types RSAPublicKey and RSAPrivateKey. However, RSAPublicKey and RSAPrivateKey are not enough — the types simply define sequences of integers. For the next level of abstractions (the proper 'packaging'), we need PKCS#8 for PrivateKeyInfo and X.509 for PublicKeyInfo [2].

X.509 Certificates

A public key certificate is a digitally signed statement from one entity, stating that the public key of another entity is authentic. A signed certificate binds an entity to a public key. The certificate allows us (the users) to confirm the identity of the owner of a public key. In addition, it allows us (the users) to confirm the authenticity of the public key. If the public key were tampered, the signature on the certificate would no longer be valid. The same applies if the entity's information was tampered or changed.

One of the most common forms of a public key certificate is X.509. We regularly see X.509 certificates in use on the internet. In the case of web browsers and SSL, we usually do not know who we are trusting during a transaction. But we do trust a certification authority (CA), such as Verisign or Comodo, which has signed the other's certificate which is host to the public key. So, Verisign or Comodo attest to the identity of the person, group, or organization offering us their public key, by signing the organization's certificate. In addition, since the certification authority signed the public key certificate, we know the public key is authentic. We can trace the lineage of the X.509 certificate signers back to a CA which we trust. At the root, the authority signs its own certificate, which makes everything OK.

Key Syntax

In an effort to achieve interoperability, we use four formats provided in PKCS#1, PKCS# 8, and X.509. Using PublicKeyInfo and PrivateKeyInfo, we can encode the public and private keys for nearly all cryptosystems by specifying the desired object identifier or OID. For a list of the algorithms and identifiers used when specifying an AlgorithmIdentifier, see RFC 3279 [17] and RFC 4055 [18].

Figure 1: Logical Key Layouts

PublicKeyInfo

Even though X.509 is heavier than we need, it offers the first format: PublicKeyInfo [7]. Precisely, X.509 defines this as a SubjectPublicKeyInfo, with the public key being a SubjectPublicKey. We choose to drop the 'Subject' for aesthetics and consistency with PKCS.

PublicKeyInfo ::= SEQUENCE {
  algorithm AlgorithmIdentifier,
  PublicKey BIT STRING }

According to X.509, AlgorithmIdentifier is defined as:

AlgorithmIdentifier ::= SEQUENCE {
  algorithm ALGORITHM.id,
  parameters ALGORITHM.type OPTIONAL }

Algorithm is the OID for RSA, which is rsaEncryption (1.2.840.113549.1.1.1). The optional Parameters is usually not present in RSA. However, they are present in DSS, which we examine below in Key Formats.

The syntax of AlgorithmIdentifier is more complicated. It has been painted with a very broad brush. ALGORITHM is a class and ALGORITHM.id is a type. ALGORITHM.type is an open type with additional constraints. The constraints imposed depend on the value of ALGORITHM.id. This means that if ALGORITHM.id is one OID, ALGORITHM.type will assume a particular syntax. If ALGORITHM.id is a second distinct OID, ALGORITHM.type will assume a [possibly] different syntax.

Finally, the PublicKey (examined below) is encoded in a bit string. Details are important: a public key is encoded as a bit string, a private key is not.

PrivateKeyInfo

Moving to PKCS #8, we find the syntax for the second format, PrivateKeyInfo, shown below [9].

PrivateKeyInfo ::= SEQUENCE {
  version Version,
  privateKeyAlgorithm PrivateKeyAlgorithmIdentifier,
  privateKey PrivateKey,
  attributes [0] IMPLICIT Attributes OPTIONAL }

and

Version ::= INTEGER
PrivateKeyAlgorithmIdentifier ::= AlgorithmIdentifier
PrivateKey ::= OCTET STRING

AlgorithmIdentifier is again the OID for RSA, which is rsaEncryption (1.2.840.113549.1.1.1).There is no distinction made between a PublicKeyInfo OID and a PrivateKeyInfo OID. Both specify rsaEncryption.

Recall that a public key is encoded as a bit string. PrivateKeyInfo encodes the private key as an octet string.

EncryptedPrivateKeyInfo

Finally, PKCS#8 defines a EncryptedPrivateKeyInfo which standardizes an encrypted private key (suitable for storing). We will not explore the EncryptedPrivateKeyInfo, even though best practices dictate that we use it.

EncryptedPrivateKeyInfo ::= SEQUENCE {
  encryptionAlgorithm EncryptionAlgorithmIdentifier,
  encryptedData EncryptedData }

and

EncryptionAlgorithmIdentifier ::= AlgorithmIdentifier
EncryptedData ::= OCTET STRING

EncryptedData is the result of encrypting the private-key information (RSAPrivateKey) [8]. If interested, see Section 7 of PKCS#8. EncryptionAlgorithmIdentifier specifies the encryption algorithm (see PKCS #5, Password-Based Encryption Standard [19]). Since PKCS #5 is dated (using 8 bytes algorithms and MD2 and MD5), we also need to visit RFC 2898, Password-Based Cryptography Specification, Version 2.0 [20] for the latest specifications.

RSAPublicKey

PKCS #1 defines the third syntax, RSAPublicKey, as shown below [6]. For the purist, the type is specified in X.509 and is retained in PKCS#1 for compatibility.

RSAPublicKey ::= SEQUENCE {
  modulus INTEGER,
  publicExponent INTEGER }

RSAPrivateKey

Reading PKCS #1 further, we find the final syntax, an RSAPrivateKey [6].

RSAPrivateKey ::= SEQUENCE {
  version Version,
  modulus INTEGER,
  publicExponent INTEGER,
  privateExponent INTEGER,
  prime1 INTEGER,
  prime2 INTEGER,
  exponent1 INTEGER,
  exponent2 INTEGER,
  coefficient INTEGER }

and

Version ::= INTEGER

Key Formats

This section will present the programmatic structure of the keys, in an effort to bring the previous sections together in a meaningful manner. If the devil is in the details, it resides in finding the syntax (specification) for the PublicKeyInfo.PublicKey and PrivateKeyInfo.PrivateKey.

RSA Public Key

SEQUENCE                  // PublicKeyInfo
+- SEQUENCE               // AlgorithmIdentifier
   +- OID                 // 1.2.840.113549.1.1.1
   +- NULL                // Optional Parameters
+- BITSTRING              // PublicKey
   +- SEQUENCE            // RSAPublicKey
      +- INTEGER(N)       // N
      +- INTEGER(E)       // E

RSA Private Key

SEQUENCE                  // PrivateKeyInfo
+- INTEGER                // Version - 0 (v1998)
+- SEQUENCE               // AlgorithmIdentifier
   +- OID                 // 1.2.840.113549.1.1.1
   +- NULL                // Optional Parameters
+- OCTETSTRING            // PrivateKey
   +- SEQUENCE            // RSAPrivateKey
      +- INTEGER(0)       // Version - v1998(0)
      +- INTEGER(N)       // N
      +- INTEGER(E)       // E
      +- INTEGER(D)       // D
      +- INTEGER(P)       // P
      +- INTEGER(Q)       // Q
      +- INTEGER(DP)      // d mod p-1
      +- INTEGER(DQ)      // d mod q-1
      +- INTEGER(Inv Q)   // INV(q) mod p

DSA Keys

If we were interested in the Digital Signature Algorithm keys as defined in the Digital Signature Standard [16] and IEEE's P1363 [23], the keys would be as follows. DSA uses the OptionalParameters for the curve's domain parameters (recall the OptionalParameters is null in RSA). The syntax of the DSA domain parameters can be found in RFC 3279 [17] and its supplement RFC 4055 [18]. The syntax of DSAPublicKey and DSAPrivateKey are shown below. Note that both keys lack the extra SEQUENCE which was present with the RSA keys. Finally, DSAPrivateKey does not include a version field.

Dss-Parms ::= SEQUENCE {
  p INTEGER,
  q INTEGER,
  g INTEGER }

DSA Public Key

SEQUENCE                 // PublicKeyInfo
+- SEQUENCE              // AlgorithmIdentifier
   +- OID                // 1.2.840.10040.4.1
   +- SEQUENCE           // DSS-Params (Optional Parameters)
      +- INTEGER(P)      // P
      +- INTEGER(Q)      // Q
      +- INTEGER(G)      // G
   +- BITSTRING          // PublicKey
      +- INTEGER(Y)      // DSAPublicKey Y

DSA Private Key

SEQUENCE                 // PrivateKeyInfo
+- INTEGER               // Version
+- SEQUENCE              // AlgorithmIdentifier
   +- OID                // 1.2.840.10040.4.1
   +- SEQUENCE           // DSS-Params (Optional Parameters)
      +- INTEGER(P)      // P
      +- INTEGER(Q)      // Q
      +- INTEGER(G)      // G
   +- OCTETSTRING        // PrivateKey
      +- INTEGER(X)      // DSAPrivateKey X

RSA Cryptosystem

RSA is the work of Ron Rivest, Adi Shamir, and Leonard Adleman. The system was developed in 1977, and patented by the Massachusetts Institute of Technology. The RSA patent expired in September of 2000, and was subsequently placed in Public Domain. Though Rivest, Shamir, and Adleman are generally credited with the discovery, Clifford Cocks (Chief Mathematician at GCHQ — the British equivalent of the NSA) described the system in 1973. However, Cocks did not publish since the work was considered classified, so the credit lay with Rivest, Shamir, and Adleman.

Public and Private Key Generation

To generate a key pair, we perform the following [10]:

• Generate two large random (and distinct) primes p and q
• Compute n = pq and Φ = (p-1)(q-1)
• Select a random integer e with the following properties:
  • 1 < e < Φ
  • gcd(e, Φ) = 1
• Compute d with the following properties:
  • 1 < d < Φ
  • ed ≡ 1 mod Φ

When we compute d, we would use the Extended Euclidian Algorithm [10]. e is known as the encryption exponent, and d is the decryption exponent. The public key is (n, e); the private key is d.

Public Key Encryption

To encrypt a message, we perform the following [10]:

• Obtain the entity's public key
• Represent the message as an integer m such that 0 ≤ m ≤ n-1
• Compute c = m^e mod n

We would then send the cipher text c to the entity.

Private Key Decryption

To decrypt a message, we perform the following [10]:

• Compute m = c^d mod n

RSAPrivateKey Syntax versus RSA Private Keys

From Public and Private Key Generation, we know our keys consist of d, e, and n, yet RSAPrivateKey syntax specifies eight parameters. Taking from PKCS#1:

An RSA private key logically consists of only the modulus n and the private exponent d. The presence of the public exponent e is intended to make it straightforward to derive a public key from the private key. The presence of the values p, q, d mod (p-1), and q^-1 mod p is intended for efficiency... A private-key syntax that does not include all the extra values can be converted readily to the syntax defined here, provided the public key is known. [12]

Generating, Saving, and Loading Keys

Before we can exchange keys over SneakerNet, we must generate a key pair. The keys we generate are temporary and can be deleted. At times, we will encounter the terms ephemeral or temporal, which are sometimes used to describe discardable keys.

Best practice dictates that we use different keys for the purpose of key exchange and signing. This is known as Key Separation [11]. (Keep in mind we disregard the fact that we are saving private keys in PrivateKeyInfo format and not EncryptedPrivateKeyInfo format). This means we should have at least two sets of key pairs. While Crypto++ does not make a distinction, Java and C# will ask us our intentions since Java and C# expect us to place the keys in a 'Key Store' for future use.

Below, we will examine the code in a library-centric fashion, rather than each step (generating, saving, and loading) on a per library basis. It is easier to group all operations by library and discuss the library as a whole. In all cases, the file name for the key is formed as <type>.rsa.<library>.key. So, a public key generated using Crypto++ will be named public.rsa.cpp.key, while a Java private key will be named private.rsa.java.key.

Crypto++

Generating RSA keys in Crypto++ is straightforward once we know the classes which we need to use. In Crypto++, the private key is represented as InvertibleRSAFunction, while the public key is RSAFunction. Though Crypto++ provides many typedefs to ease library use, notably missing are the RSAPublicKey and RSAPrivateKey. To this end, we will perform the typedef so the code appears more like what we are accustomed to.

The RSAFunction class inherits from (among others) X509PublicKey. The InvertibleRSAFunction class inherits from (among others) RSAFunction and PKCS8PrivateKey. The classes offer customary functions such as GetPrime1, GetPrime2, GetModulus, and GetPrivateExponent.

Key Generation

The code below creates an RSA public and private key using a default parameter for the public exponent (e = 17). As with Java, the constructor we are using requires a pseudo random number generator.

// Convenience
typedef InvertibleRSAFunction RSAPrivateKey;
typedef RSAFunction RSAPublicKey;

// PGP RandPool design
AutoSeededRandomPool prng;

// Private Key
RSAPrivateKey privateKey;
privateKey.Initialize( prng, 1024 /*, e=17*/)

// Public Key
RSAPublicKey publicKey( privateKey );

If we wanted to initialize the RSAPrivateKey given parameters, we have two additional Initialize functions (const references have been removed for brevity):

Initialize(Integer n, Integer e, Integer d)
Initialize(Integer n, Integer e, Integer d, Integer p, 
           Integer q, Integer dp, Integer dq, Integer u)

The RSAPublicKey has one constructor and one initializer. The lone constructor takes a RSAFunction parameter. Recall that the InvertibleRSAFunction class inherits from RSAFunction. This explains why the code below compiles.

RSAPublicKey publicKey( privateKey );

If we wanted to initialize the key with parameters e and n, we would use:

Initialize(Integer n, Integer e)

Saving Keys

Recall that the InvertibleRSAFunction class and the RSAFunction class inherit from either X509PublicKey or PKCS8PrivateKey. X509PublicKey and PKCS8PrivateKey both inherit from the class ASN1Object, which provides Load and Save functions. The InvertibleRSAFunction class and RSAFunction override Load and Save. So, the code to serialize our Crypto++ keys is:

// Save as PKCS #8 (using ASN.1 DER Encoding )
privateKey.Save( FileSink("private.rsa.cpp.key") );

// Save as X.509 (using ASN.1 DER Encoding )
publicKey.Save( FileSink("public.rsa.cpp.key") );

Crypto++ uses a Unix pipeline paradigm, so we need a destination (the key is the source). This is the role of the FileSink. A FileSink will place the contents of the key in a file. We can examine the key using any ASN.1 dump program, as shown below in Figure 2.

Figure 2: Partial Private Key Dump Using dumpasn1

In Figure 2, we observe a few items. First, at file offset 0, we see a sequence. There are 628 content octets. Offset 0 marks the beginning of PrivateKeyInfo. At file position 4, we see the version (PrivateKeyInfo.version). Next, we have a sequence. Following the sequence, we observe the PrivateKeyInfo.privateKeyAlgorithm (the OID for RSA) at offset 9. At location 22, we see the octet string which wraps the RSAPrivateKey.

Offset 26 begins the RSAPrivateKey. There are 602 content octets. At offset 30, we have the RSAPrivateKey.Version (0 = v1998). Offset 33 begins the RSAPrivateKey.Modulus. We note that the modulus is 129 bytes, even though we generated a 1024 bit (128 bytes) key. This is because Crypto++ correctly added a leading 0x00 octet (recall that ASN.1 integers are signed). Finally, line 165 dumps RSAPrivateKey.publicExponent which is 17. The remaining fields are not visible.

Loading Keys

Loading a key is equally trivial. Below, we load the keys generated in C#. We use a true parameter with the FileSource to aid the compiler in the choice of FileSource constructors.

// Load as PKCS #8 (using ASN.1 BER Decoding )
privateKey.Load( FileSource( "private.rsa.cs.key", true ) );

// Load as X.509 (using ASN.1 BER Decoding )
publicKey.Load( FileSource( "public.rsa.cs.key", true ) );

If we inadvertently use DEREncodePublicKey or DEREncodePrivateKey as shown below (rather than Save):

publicKey.DEREncodePublicKey ( FileSink("public.rsa.cpp.key") );

we produce incorrect results. This is because only the ASN.1 integers are written (PKCS#1 RSAPrivateKey or PKCS#1 RSAPublicKey). The wrappers - PrivateKeyInfo (PKCS#8) and PublicKeyInfo (X.509) - are not present.

Figure 3: Serialization of RSAPublicKey (not PublicKeyInfo)

In Figure 3, we note that two ASN.1 encoded integers (n and e) are present. However, elements such as the enclosing ASN.1 bit string is missing, as is the OID for RSA (1.2.840.113549.1.1.1).

For completeness, we will again call the wrong function when we load a key. We attempt to load an encoded RSAPublicKey using BERDecodePublicKey. However, what really exists in the file is a PublicKeyInfo message. We expect that Crypto++ will throw a "BER Decode Error", which is in fact the case.

publicKey.BERDecodePublicKey(FileSource( "public.rsa.cpp.key", true ));

Java

Java enjoys greater popularity with better documentation, so the following is presented for completeness. The Java Cryptography Extension (JCE) Reference Guide [13] answers most questions.

Key Generation

To generate our RSA keys, we perform the following.

// Java Cryptography Provider
KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");

// Initialize and Generate
kpg.initialize(1024, new SecureRandom());
KeyPair keys = kpg.generateKeyPair();

// Retrieve keys
RSAPrivateKey privateKey = (RSAPrivateKey)keys.getPrivate();
RSAPublicKey publicKey = (RSAPublicKey)keys.getPublic();

Saving Keys

Saving a key in Java is only slightly more complicated since we have to construct a FileOutputStream. Below, getEncoded returns the key in its primary encoding format (PKCS#8 or X.509).

DataOutputStream dos = new DataOutputStream( new FileOutputStream("private.rsa.java.key"));
dos.write(privateKey.getEncoded);
dos.close();

Loading Keys

Loading a key in Java is shown below. The FileInputStream is needed because using InputStream's available only reports the number of bytes which can be read without blocking.

// Retrieve bytes
FileInputStream fis = new FileInputStream("private.rsa.java.key")
DataInputStream dis = new DataInputStream(fis);
byte[] octets = new byte[(int) fis.length()];
dis.readFully(octets);
dis.close();

// Reconstruct Key
PKCS8EncodedKeySpec spec = new PKCS8EncodedKeySpec(b);

KeyFactory factory = KeyFactory.getInstance("RSA");
RSAPrivateKey privateKey = (RSAPrivateKey)factory.generatePrivate(spec);

Above, the RSAPrivateKey provides access to d and n. Since we wrote the private key using full syntax, we could actually use:

RSAPrivateCrtKey privateKey = (RSAPrivateCrtKey)factory.generatePrivate(spec);

If we were reading a public key, the code above would be modified as follows.

FileInputStream fis = new FileInputStream("public.rsa.java.key");
DataInputStream dis = new DataInputStream(fis);
...

X509EncodedKeySpec spec = new X509EncodedKeySpec(b);

KeyFactory factory = KeyFactory.getInstance("RSA");
RSAPublicKey publicKey = (RSAPublicKey)factory.generatePublic(spec);

C#

C# is the most complicated of the examples, closely following its CAPICOM heritage. In addition, there are unwritten rules we must follow when importing keys. This section will attempt to examine the issues we are faced with when working within the confines of the CLR.

RSA Key Generation

Our C# first task is to generate a key pair. We set the ProviderType and KeyNumber for RSA per MSDN. Note that attempting to set the ProviderType to a value other than PROV_RSA_FULL or KeyNumber to AT_SIGNATURE would result in a CryptographicException stating 'Provider type not defined' for the CLR's implementation of RSACryptoServiceProvider.

Figure 4: Provider Type Not Defined

We use the RSACryptoServiceProvider which accepts a CspParameters and an integer bit count because we want the library to create a key pair for us. We also configure other parameters to suit our needs, such as the container name. We then call ExportParameters to retrieve the keys.

CspParameters csp = new CspParameters();

csp.KeyContainerName = "RSA Test (OK to Delete)";
csp.ProviderType = PROV_RSA_FULL;        // 1
csp.KeyNumber = AT_KEYEXCHANGE;          // 1

RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(1024, csp);

RSAParameters privateKey = rsa.ExportParameters(true);
RSAParameters publicKey = rsa.ExportParameters(false);

Note that if we were using the Win32 API, we would retrieve a PUBLICKEYBLOB (or PRIVATEKEYBLOB) which would house the public or private key blob. The Win32 blob would be in Little Endian order, which we would later have to convert to Big Endian. When we access the RSAParameters using C#, it is returned in Big Endian format so we do not need to reverse the byte ordering before serialization.

Saving RSA Keys

Next, we need to serialize the keys. Since C# does not support our needs (unless we desire XML), we use the AsnKeyBuilder class to provide the functionality. In fairness to the CLR, we can use P/Invoke and the Win32 API. Dr. Gallant demonstrates the technique at JavaScience.

AsnKeyBuilder offers four static methods to prepare keys for serialization. Two methods apply to RSAParameters, the remaining two apply to DSAParameters. The two RSA methods are:

• PublicKeyToX509(RSAParameters publicKey)
• PrivateKeyToPKCS8(RSAParameters privateKey)

Each method simply extracts the pertinent values from either RSAParameters, packaging each in the proper ASN.1 object. Each method returns an AsnMessage, which is a thin wrapper for the underlying byte array. To keep things simple, we use the AsnMessage rather than separate classes for the PKCS#8 and X.509 keys. To save the keys, we would perform the following:

AsnMessage privateEncoded = PrivateKeyToPKCS8(privateKey);
SaveEncodedKey("private.rsa.cs.key", privateEncoded.GetBytes());

AsnMessage publicEncoded = PublicKeyToX509(publicKey);
SaveEncodedKey("public.rsa.cs.key", publicEncoded.GetBytes());

The SaveEncodedKey method simply wraps a BinaryWriter:

internal static void SaveEncodedKey(String filename, byte[] encoded)
{
  using (BinaryWriter writer = new BinaryWriter(
      new FileStream(filename, FileMode.Create, FileAccess.ReadWrite)))
  {
    writer.Write(encoded);
  }
}

In Figure 5, we examine the resulting private key created using C#:

Figure 5: C# Generated RSA Private Key

Because the CLR's native key format is either RSAParameters or DSAParameters, we can mistakenly save keys in the wrong format (the parameters does not have a notion of public key or private key — it contains all information). The write operation will succeed — the problem will not become apparent until the key is retrieved. Below is an example of saving a key in the wrong format.

// Should be using PrivatKeyToPKCS8(...)
AsnMessage privateEncoded = PublicKeyToX509(privateKey);
SaveEncodedKey("private.rsa.cs.key", privateEncoded.GetBytes());

Loading RSA Keys

Next, we load the private key using Java to verify encoding correctness. Notice the modulus (file offset 33) and public exponent (file offset 165) in Figure 5 match those displayed by our Java program in Figure 6.

Figure 6: C# Generated RSA Private Key

Now, we will examine the case of loading a X.509 encoded PublicKeyInfo. This is the format of our AsnKeyBuilder class wrote to a file (and which Java consumed in Figure 6). First, we construct an AsnKeyParser, passing the constructor the pathname of the file. In this case, we are using the public key. There is no loss of generality — we could also pass the private key pathname and call ParseRSAPrivateKey. In both cases, we are returned an RSAParameters after parsing.

AsnKeyParser keyParser = new AsnKeyParser("public.rsa.cs.key");

RSAParameters publicKey = keyParser.ParseRSAPublicKey();

Next, we construct a CspParameters to pass to the RSACryptoServiceProvider constructor. By using only the constructor which accepts CspParameters, we do not invoke a key generation. This makes sense, since we are resurrecting the key from a file.

CspParameters csp = new CspParameters;
csp.KeyContainerName = "RSA Test (OK to Delete)";

csp.ProviderType = PROV_RSA_FULL;    // 1
csp.KeyNumber = AT_KEYEXCHANGE;      // 1

RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(csp);
rsa.PersistKeyInCsp = false;

Unlike key generation, we are not confined to using only MSDN specified values for ProviderType and KeyNumber. However, the RSA implementation is s bit diminished, so choosing other types results in a cryptographic exception.

We are free to import either a public key or a private key, depending on our desired key usage. Below, we choose a public key which could be used for encryption or signing, and we import our parsed RSAParameters using ImportParameters.

rsa.ImportParameters(publicKey);

Finally, we call Clear on the provider when we are finished using it.

rsa.Clear();

If we neglect to call Clear, interesting errors and artifacts surface. For example, when running the sample code for this article, the author would receive a CryptographicException stating 'Keyset does not exist' when the program exited Main.

Figure 7: CryptograhicException when Exiting Main

In addition, an event is written to the application event log stating '.NET Runtime version 2.0.50727.1433 — Fatal Execution Engine Error (79FFEE24) (80131506)'.

Figure 8: Application Log

The reason is not readily apparent. In the sample, we call CreateRsaKeys and LoadRSAKeys, which do not share any parameters (to simulate key exchange over SneakerNet). However, each method opens a container named 'RSA Test (OK to Delete)', and each method sets PersistKeyInCsp = false. When garbage collection occurs, each managed object attempts to free the shared native resource. To avoid the situation, we must finalize the object by calling Dispose, Close, or Clear in the method which opened the resource.

DSA Key Generation

Next we turn our attention to DSA. During key generation, we perform the same basic steps as with RSA. However, per MSDN, we specify a ProviderType of PROV_DSS_DH. In the case of DSA, we also can use the KeyNumber of AT_SIGNATURE. When we construct the provider, we use a constructor which accepts an int to specify the size. Again, this causes the provider to create the keys.

CspParameters csp = new CspParameters();
csp.KeyContainerName = "DSA Test (OK to Delete)";

csp.ProviderType = PROV_DSS_DH;      // 13
csp.KeyNumber = AT_SIGNATURE;        // 2

DSACryptoServiceProvider dsa = new DSACryptoServiceProvider(1024, csp);

After the key pair is created, we call the provider's ExportParameters to retrieve the keys. Finally, we use AsnKeyBuilder to serialize the keys. Figure 9 shows the result for our private key.

DSAParameters privateKey = dsa.ExportParameters(true);
AsnMessage key = AsnKeyBuilder.PrivateKeyToPKCS8(privateKey);

Figure 9: C# DSA Private Key

Saving DSA Keys

As with RSA, we save an RSA key in PKCS #8 or X.509 format using either the PrivateKeyToPKCS8 or the PublicKeyToX509 method:

AsnMessage privateEncoded = PrivateKeyToPKCS8(privateKey);
SaveEncodedKey("private.dsa.cs.key", privateEncoded.GetBytes());

AsnMessage publicEncoded = PublicKeyToX509(publicKey);
SaveEncodedKey("public.dsa.cs.key", publicEncoded.GetBytes());

Loading DSA Keys

Next we move on to opening the container. In this case, the DSACryptoServiceProvider uses a constructor which accepts only the CSP (as opposed to a CSP and integer bit count). This indicates to the provider that we do not want a key pair generated. Note that we use PROV_DSS rather than PROV_DSS_DH because we no longer have parameters such as J and the seed.

CspParameters csp = new CspParameters();

csp.ProviderType = PROV_DSS;      // 3
csp.KeyNumber = AT_SIGNATURE;     // 2

DSACryptoServiceProvider dsa = new DSACryptoServiceProvider(csp);

Above, we create a provider using PROV_DSS using the provider constructor which only accepts a CspParameters, since we do not need the runtime to generate a fresh pair. We would then use AsnKeyParser to return a DSAParameters key.

AsnKeyParser keyParser = new AsnKeyParser("private.dsa.cs.key");
DSAParameters privateKey = keyParser.ParseDSAPrivateKey();

Common Errors

Next, we will explore the most common reasons for failures during key import, which can lead to exceptions such as the ubiquitous 'Bad Data' exception shown in Figure 10.

Figure 10: Bad Data

First, we cannot specify a KeyNumber of AT_EXCHANGE when using DSA. This should be fairly obvious, because DSA is a signature algorithm. Should we try the PROV_DSS_DH/AT_EXCHANGE pair, we receive 'The specified cryptographic service provider (CSP) does not support this key algorithm.'

Figure 11: PROV_DSS_DH/AT_EXCHANGE

Next is our key parser. When we exported the keys, we wrote four integers (p, q, g, and x or y). ASN.1 integers are signed using a 2s compliment representation (see the discussion on ASN.1 integers below). So, we prepend a 0x00 octet as required to ensure they are positive according to the ASN.1 syntax. We observe this in Figure 9: at file offset 24, the domain parameter p is prepended with a single byte of value 0x00 (as is q at offset 156 and g at offset 179).

However, when we attempt to import the value into the servicer provider, we receive a 'Bad Data' exception. When we import a key, we must strip the 0x00 if present. RSA does not appear to suffer from this limitation, which makes us suspect that DSA fails internal validation because it considers the parameter size to be 1024+8 = 1032 bits. Our AsnKeyParser attempts to check for this condition below. values are the content octets of the parsed ASN.1 integer.

byte[] r = null;
if ( (values.Length > 1) && (0x00 == values[0]))
{
  r = new byte[values.Length - 1];
  Array.Copy(values, 1, r, 0, values.Length - 1);
}

Recall that we created the keys with ProviderType of PROV_DSS_DH and KeyNumber of AT_EXCHANGE. This results in the key parameters as shown in Figure 12.

Figure 12: DSAParameters

However, when we reconstruct the key which was serialized using PKCS#8 or X.509, the result will be similar to that shown in Figure 13.

Figure 13: PKCS#8 Serialized Private DSA Key

Because PKCS#8 and X.509 do not serialize the validation parameters, we cannot use PROV_DSS_DH. In this case, we must specify ProviderType = PROV_DSS, and not PROV_DSS_DH. Using PROV_DSS_DH will result in 'Bad Data'. The missing values such as a seed an J (group parameter factor) allow us to validate the derived domain parameters. See Cryptographic Interoperability: Digital Signatures [22] for details of the DSA signature parameters. The serice provider's FromXMLString does not suffer this limitation because the method writes all parameters.

For completeness, RFC 2492 [24] (and ANSI X9.42 [25]) includes the ASN.1 syntax for the Diffie-Hellman key exchange, which is shown below. The syntax for the missing C# parameters is shown below:

DomainParameters ::= SEQUENCE {
  p INTEGER,
  g INTEGER,
  q INTEGER,
  j INTEGER OPTIONAL,
  validationParms ValidationParms OPTIONAL }

and

ValidationParms ::= SEQUENCE {
  seed BIT STRING,
  pgenCounter INTEGER }

The OID is 1.2.840.10046.2.1. Whether this can be loaded into Java for DSA operations is questionable. 10046 is the ANSI-x942 arc in the OID tree, while 10040 (used for DSA) is the x9-57 arc.

If we try to export the public key as a private key using ToXMLString, we will catch an exception stating 'Key not valid for use in specified state' as shown in Figure 14.

// Load public key
AsnKeyParser keyParser = new AsnKeyParser(...);
RSAParameters publicKey = keyParser.ParseRSAPublicKey();

...

rsa.ImportParameters(publicKey);

// Export as private key
String xml = rsa.ToXmlString(true);

Figure 14: PKCS #8 Private Key/ToXmlString

Writing a key using ToXMLString after reading a PKCS#8 or X.509 DSA key (RSA keys do not have validation parameters) results in a file with domain parameters P, Q, G, and public key Y or private key X. This is expected since the key did not have J, the seed, or the counter.

Figure 15: ToXMLString from PKCS#8 Encoded Key

This is a valid key syntax according to RFC 3275, section 4.4.2.1:

Parameters seed and pgenCounter are used in the DSA prime number generation algorithm specified in [DSS]. As such, they are optional, but must either both be present or both be absent.

With our new found knowledge, we will try to break the provider. First, we write the DSA key out to a file in XML format. Next, we delete the seed as shown in Figure 16.

Figure 16: XML Encoded Keys

Next we copy the key and delete the seed. When we attempt to load bad.dsa.key.xml, we catch the exception "Input string does not contain a valid encoding of the 'DSA' 'Seed' parameter." We receive a similar exception when only the counter is deleted.

Figure 17: Exception due to Missing Seed Parameter

ASN.1

ASN.1 is Abstract Syntax Notation One, which is a presentation layer protocol. It is a formal language for describing data and the properties of the data [3]. ASN.1 encoding rules are specified by the ITU in X.690 (X.208 was deprecated in 2002) [1]. For questions regarding ASN.1 and its use, visit the ASN.1 Consortium. Join their mailing list and then send questions to asn1@asn1.org.

There are three types of encoding — BER, CER, and DER. Each offers varying degrees of freedom for encoding a value, with BER being the least restrictive and DER being the most restrictive. We usually find applications implement DER encoders and BER decoders. That is, an application attempts to write the most correct ASN.1 notation, while reading the least correct syntax.

For example, if we wanted to encode the string "Crypto Interop", the single encoded string would satisfy BER, CER, and DER. However, if we used BER (the 'loosest'), we could also represent it with three strings that would be concatenated: "Crypto", " ", "Interop". This string concatenation is not a valid DER encoding. For more information on BER, CER, and DER encoding, please refer to X.690, sections 8, 9, and 10. For restrictions placed on BER encodings by CER and DER, please refer to X.690, section 11.

There are exceptions to every rule, and this is no different. According to PKCS#8, "... [in] an RSA private key, ... the contents are a BER encoding of a value of type RSAPrivateKey" [8]. So, an encoder could use the less encumbered BER encoding.

The fundamental ASN.1 unit is an Octet, which is an 8-bit byte. An ASN.1 encoding, composed of octets, usually has three parts: an Identifier, a Length, and Contents (except for type Null, which has only two, and when encoding using indefinite length which has four). For more information, refer to X.690, section 8.1.

An identifier is further broken down: the 5 low order bits are a Tag number, the three high order bits are bit fields consisting of Class and Primitive/Constructed fields. For our purposes, the three high order bits are usually 0, so our tag number is the identifier (an exception to this is the encoding of a sequence). Tag numbers denote the type — integer, bit string, printable string, etc. There are also user defined types which we do not use.

The length specifies the size of the content octets (the data values we are encoding). There are three ways to encode length: short (a definite form), long (a definite form), and indefinite form. We only use the first two forms (the third is equivalent to a runtime length encoding). In the short form, there is only one octet. The high bit of the octet is zero, and the remaining seven bits specify the number of octets that follow, which are content octets. In long form, the high bit is one. The remaining seven bits specify the number of octets which follow, that specify the length. Examples are shown in Table 2.

Length Octet(s)	Meaning
0x01	MSB high bit 0, content octets are length 1
0x02	MSB high bit 0, content octets are length 2
0x81 0x01	MSB high bit 1, next octet is length (content length = 1)
0x81 0x02	MSB high bit 1, next octet is length (content length = 2)
0x82 0x01 0xFF	MSB high bit 1, next two octets are length (content length = 0x01FF)
0x82 0x7F 0xFF	MSB high bit 1, next two octets are length (content length = 0x7FFF)
0x83 0x00 0x7F 0xFF	MSB high bit 1, next three octets are length (content length = 0x7FFF)
0x83 0x07 0xFF 0xFF	MSB high bit 1, next three octets are length (content length = 0x07FFFF)
Table 2: Example Length Encodings

From above, we see we can encode a length of one in a few ways: '0x01', '0x81 0x01', and '0x82 0x00 0x01'. BER, being the loosest encoding, would allow all three. DER is most restrictive, and only allows '0x01' (from X.690, section 10.1: the definite form of length encoding shall be used, encoded in the minimum number of octets).

We only use a subset of elements from the specification: INTEGER, BIT STRING, OCTET STRING, NULL, OBJECT IDENTIFIER, and SEQUENCE, which are explained below.

INTEGER

An ASN.1 integer is assigned a tag number 2. It is a signed integer using a 2's compliment representation (the same as in most personal computers). Because it is signed, if we want to represent a positive integer which has its high bit set, we must prepend a 0x00 to the content octets. Examples are shown in Table 3. For more information, please refer to X.690, Section 8.3.

Value	Integer Encoding
1	0x01
-1	0xFF
2	0x02
-2	0xFE
255 (0xFF)	0x00 0xFF
-255 (0xFF)	0xFF 0x01
Table 3: Example Integer Encoding

In cryptographic applications which exchange information, we are assured of the 2's compliment issue when we choose a key size which is a multiple of 8 (for example, 512 bits or 1024 bits). As a concrete example, suppose we want a 512 bit modulus. We need two random prime numbers, p and q, each of which is 256 bits in length. We ask the pseudo-random number generator for 256 bits. Prime numbers are odd, so we set the lowest order bit of the number (p or q) to 1. In order to assure the number is the required size (256 bits), we set the highest order bit to 1. We then test the number for primality.

Because we set the highest order bit to 1, the ASN.1 integer would be interpreted as negative if the content octets were not modified. A peer system may or may not interpret the number as negative (though it should). This could cause our peer to reject the key. So we prepend 0x00 to the content octets before transferring the key material, to assure a positive number is received. We see an example of the prepending to assure a positive integer, in Figure 2.

BIT STRING

An ASN.1 bit string is assigned a tag number 3. An ASN.1 primitive bit string is an initial octet followed by zero, one, or more subsequent octets. The initial octet is a discard count, which specifies how many trailing bits are unused. The initial octet is 0x00 if no bits are discarded, and must be between 0 and 7 inclusive. It is used when the number of bits is not a multiple of 8.

For example, to encode the bit string 1111 1111 1111, the string must be a multiple of 8, so our content octets would be 0x04 0xFF, 0xF0. 0xFF 0xF0 (1111 1111 1111 0000) is the bit string, while 0x04 specifies four bits are unused.

There is also a constructed variant of a bit string, which does not use an initial octet (which we do not use). For more information, please refer to X.690, Section 8.6.

OCTET STRING

An ASN.1 octet string is assigned a tag number 4. An ASN.1 octet string is zero, one, or more octets. There are no special rules to remember as with integers and bit strings. For more information, please refer to X.690, Section 8.7.

NULL

An ASN.1 null is assigned a tag number 5. Unlike other types, this object consists of only an identifier and length, which is 0. So, a null encoding is 0x05 0x00.

OBJECT IDENTIFIER

An ASN.1 OID is assigned a tag number 6. ASN.1 performs special packing of the arcs of the tree, similar to length encoding. For our purposes, it is the ASN.1 encoded object identifier 1.2.840.113549.1.1. For more information, please refer to X.690, Section 8.19.

SEQUENCE

An ASN.1 sequence is assigned a tag number 16. However, it is a constructed object, so the identifier we encounter is 0x30 (0x10 | 0x20). A sequence acts as an ordered container (this is in contrast to a set, which acts as an unordered container). A set can contain zero, one, or more elements. The content octets of a sequence are the octets of the types it contains.

For example, to wrap an INTEGER (with value 4) in a SEQUENCE, our encoding would be 0x30 0x03 0x02 0x01 0x04. 0x02 0x01 0x04 is the integer 4, which becomes the content octets of the sequence. As another example, a sequence with no elements is encoded 0x30 00. For more information, please refer to X.690, Section 8.9.

Acknowledgements

• Wei Dai for Crypto++ and his invaluable help on the Crypto++ mailing list
• Dr. A. Brooke Stephens who laid my Cryptographic foundations

Checksums

• CryptoPPInteropKeys.zip
  • MD5: 79D51470C98CCAB607D3A9DCFA35E572
  • SHA-1: 0F41CF6A6EDC78CE10C383470B22F20EC85B3808
• JavaInteropKeys.zip
  • MD5: 0700318CB99866DB1C2FBF6AB669B919
  • SHA-1: 412B9379912FED187A3EAE803C03DA256CC39B7C
• CSInteropKeys.zip
  • MD5: CCC3B793F929B8F2CED38E4D31F4B052
  • SHA-1: 023F5B78CC4A13D889AD32C1654B0558F1E5B338

References

1. Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER), X.690, August 2002.
2. The Directory: Public-key and Attribute Certificate Frameworks, X.509, August 2005.
3. W. Richard Stevens, TCP/IP Illustrated, Volume 1: The Protocols, Addison Wesley Publishing, ISBN 0-2016-3346-9, p. 387.
4. Public-Key Cryptography Standards (PKCS), RSA Laboratories.
5. What is PKCS?, RSA Laboratories.
6. PKCS #1: RSA Encryption Standard, RSA Laboratories, November Version 1.5, 1993, p. 6.
7. The Directory: Public-key and Attribute Certificate Frameworks, X.509, August 2005, p. 12.
8. PKCS #8: Private-Key Information Syntax Standard, RSA Laboratories, Version 1.2, November 1993, pp. 3-4.
9. PKCS #8: Private-Key Information Syntax Standard, RSA Laboratories, Version 1.2, November 1993, pp. 2-3.
10. A. Menenzes, et. al., Handbook of Applied Cryptography, CRC Press, ISBN 0-8493-8523-7, p. 286.
11. A. Menenzes, et. al., Handbook of Applied Cryptography, CRC Press, ISBN 0-8493-8523-7, p. 567.
12. PKCS #8: Private-Key Information Syntax Standard, RSA Laboratories, Version 1.2, November 1993, p. 7.
13. Java Cryptography Architecture (JCA) Reference Guide.
14. Shaheryar Ch Porting Java Public Key Hash to C# .NET.
15. FIPS 186-2, Digital Signature Standard.
16. RFC 3279, Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile.
17. RFC 4055, Additional Algorithms and Identifiers for RSA Cryptography for use in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile.
18. PKCS #5: Password-Based Encryption Standard, RSA Laboratories, Version 1.5, November 1993.
19. RFC 2898, Password-Based Cryptography Specification, Version 2.0, September 2000.
20. RFC 3447, Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1, February 2003.
21. J. Walton, Cryptographic Interoperability: Digital Signatures.
22. IEEE P1363, Standard Specifications For Public-Key Cryptography.
23. RFC 2459, Internet X.509 Public Key Infrastructure Certificate and CRL Profile, January 1999.
24. ANSI X9.42, Public Key Cryptography for the Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography, January 2003.
25. RFC 3275, XML-Signature Syntax and Processing, March 2002.