12 Public Key Cryptography

Asymmetric cryptography, or public key cryptography, uses two keys. One key is used to encrypt data and the other key is used to decrypt the data. Typically, one of these keys is made public which means that, for example, anyone can encrypt data but only the person with the other key, the private key, can decrypt the data. This solves the issue of key exchange because the public key by definition can be made public and anyone can use it to encrypt a secret (symmetric) key to be shared with the person with the private key.

Public key algorithms are quite slow, and it is not feasible to use it to encrypt large amounts of data. However, such algorithms can be used to encrypt small amounts of data (for example a hash) and if a user does this with their private key it means that anyone can decrypt the data. This is not done to secure the data, and usually such an action is applied to public data anyway; it is done to provide authentication and to preserve integrity. Since the public key can only decrypt data encrypted with the private key it means that if the public data can be obtained from the cyphertext with the public key then it means that the cyphertext was generate with the private key. This is the principle of digital signatures.

It should be stated early on that it is not feasible to use public key cryptography to encrypt large amounts of data. The algorithms involved are just too slow. Instead, public key cryptography is more suited to encrypt small amounts of data, but the asymmetric property makes public key cryptography vital for digital signatures and key exchange, which are topics that are covered in later sections. In this section we will look at the public key algorithms that form the basis of those protocols.

The base class, AsymmetricAlgorithm, factors the common features of public key cryptography. These algorithms are based on public and private keys which are typically very large and unwieldy for a human to handle. AsymmetricAlgorithm defines methods, FromXmlString and ToXmlString, that allow algorithms to be initialized with a key (a single key or a key pair) represented by XML, or to persist a public key or a key pair to XML. The format of this XML is defined by KeyValue in the XML Digital Signature Standard. In effect, these XML schemas persist very large numbers and it does this by ordering the number in big-endian form and then applying base64 encoding.

There are two public key classes in the framework, and these are shown in the following table:

DSA is only used for for digital signatures, whereas RSA can be used for signatures and encryption. Similar to the framework symmetric key classes, the classes in the table above are abstract classes with a static Create method. Create will create an instance of the default implementation of the algorithm, for RSA this will be RSACryptoServiceProvider and for DSA this will be DSACryptoServiceProvider. The RSA class has two methods, EncryptValue and DecryptValue, which appear to be there to allow you to perform encryption. However, the RSACryptoServiceProvider subclass will throw an exception if you call these methods. This is actually a good thing because these methods do raw encryption without padding, so if you were to be able to call these methods you would have to make sure that you use a good padding algorithm on the data otherwise the result would be insecure. The RSACryptoServiceProvider class provides two methods, Encrypt and Decrypt which will perform the encryption/decryption using either OAEP or PKCS#1 v1.5 padding.

To see what the RSA keys look like create a file (rsa.cs) with the following, then compile and run it:

When you create an instance of RSACryptoServiceProvider a random key pair will be created.

This is an interesting point because key generation is a slow process, so creating an instance of the class will eat CPU cycles. Indeed, the pattern of calling the default constructor and then initializing the object with the FromXmlString method will take longer than it really should. Unfortunately, there is no constructor that takes an XML string parameter. There are two ways to get around this: use a key pair in a cryptographic container or use a certificate.

The call to ToXmlString will create an XML representation of the key. Here is the result of one run (I have added some newlines to make it readable):

Run this another time to convince yourself that a different key is created every time you create an instance.

The public key is represented by the <Modulus> and <Exponent> and, as you can see, the data is base64 encoded. The ToXmlString provides a way of persisting the public key (if the parameter is set to false) or the pair of keys. Clearly, if you want someone else to be able to encrypt data that only you want to decrypt, you'll persist just the public key. A corresponding application would import the key using FromXmlString to initialize the object. If you want to pass keys around in your application you can do this by calling ExportParameters which will create an RSAParameters object. (Note that there is a DSAParameters class too.) It is interesting that RSAParameters is marked with [Serializable], which means that it can be persisted, in addition ,it is marked with [StructLayout(LayoutKind.Sequential)] which implies that it can be passed to (or initialized from) unmanaged code. However, closer inspection shows that not all members are serializable:

Thus, only the fields that are used with the public key are serializable.

When you generate a key the CryptoAPI will use a key container by default this will be a temporary container with a name CLR<guid> where <guid> is a GUID generated for this temporary action. You may decide to create the key pair and persist it, and to do this you call the RSACryptoServiceProvider constructor that takes a CspParameters object. The information in this object is passed to the Crypto Service Provider when the RSA class creates the crypto object:

The constructor parameters are: the provider type code, the provider name and the key container name. A value of 1 for the provider type code means that you will get the full RSA implementation. A null for the provider name indicates that the default provider will be used. The final parameter is interesting: this gives the name of the key container to use. If you do not provide a key container name then a temporary container will be used, and hence the algorithm will generate a new key every time the algorithm is used. However, if you provide a particular container name the algorithm will attempt to load a key from that container. If the container does not have a key then the algorithm will generate a new key and store it in the container. This container will be persistent, and so the key can be reused in the future.

Encrypting data is straight forward, the only issue is to determine what type of padding you want to use and making sure that the same type of padding is used for decryption. Add a using statement for System.Text and then change the code to look like this:

Compile and run this code. Note that the cyphertext is rather large - the cleartext is 22 characters (and 22 bytes when converted to ASCII), yet the cyphertext is 128 bytes (1024 bits). This is because the RSA algorithm needs a full block which is the size of the key, and this is the reason why padding is necessary. It is also important to understand that you will need the private key to decrypt the data. Make the following changes:

This code encrypts data with a key pair (which actually encrypts with the public key) and then extracts only the public key. The public key is then used to initialize another RSA object which is then used to decrypt the cyphertext. Compile and run this code. You'll find that a CryptographicException will be thrown with the text Error occurred while decoding OAEP padding. (If you use PKCS#1 v1.5 padding then the error will be given as Bad Key). The reason for this is because the key is an exchange key and such keys are only used to encrypt with a public key and are only used to decrypt with a private key.

Typically you will not encrypt data like this instead you'll use it to create a signature. This is covered next.

A signature is an important thing. First, the signature has to be authentic, that is, it is unique to you and identifies you; next, it must not be forgeable, so only you can provide it; finally, it is cannot be repudiated, so once you have provided your signature you cannot claim that it is not yours. These things are true for your handwriting signature (more or less) and are vitally important for digital signatures. A digital signature is attached to, and created from, a document, this means that in addition to the previous statements when a digital signature is provided it means that the document cannot be changed. If the document is changed it will not match the signature. Also, since a digital signature is created from a particular document it means that it cannot be used with another document, this is important because it means that an attacker cannot extract a signature from one document and attach it to another.

To create a digital signature you encrypt the document (or more likely, a hash of the document) with your private key. Then you provide the signature and the public key with the document. Someone trying to authenticate the document can decrypt the signature with the public key, and then compare the result with the original data (or hash of the data). If the comparison fails it means one of two things: either the document has been tampered, or the public key does not correspond to the private key that was used to create the signature. In both cases the authenticator should not trust the signed document, because the signature is suspect.

There are two methods on RSACryptoServiceProvider and DSACryptoServiceProvider for signing data, SignData and SignHash. At this point it is important to say that when DSA is used to sign data it will always use SHA1, whereas RSA can use any hash algorithm. As the name suggests, SignHash takes an already created hash value that will be signed, whereas SignData will create a hash from the data and sign it. Along with the hash value, the SignHash method also take a string identifying the hash algorithm that will be used (even though this is redundant for DSA). This string is the ASN.1 Object Identifier (OID) for the algorithm. These OIDs are not immediately obvious, but to help you the framework has a method, CryptoConfig.MapNameToOID, that will return the OID in string form for the name of the hash algorithm that you supply. This method will take names in various forms, for example for SHA1 you can use SHA, SHA1, System.Security.Cryptography.SHA1 or System.Security.Cryptography.HashAlgorithm.

To test this out, create a file (sig.cs) that has the following in the Main method:

Compile and run this code to view the signature that is created.

If this code was used to sign a document, for example to transmit the data over a socket to another application, then you will extract the public key using ToXmlString (or ExportParameters) and transmit this along with the signature and the document.

Of course, signing a hash is only useful if you can also verify that the signature is correct. To do this you use VerifyHash, add the following code:

In this example the application reuses the signing object, in a real application you would create a new RSACryptoServiceProvider object and initialize it with the public key using FromXmlString or ImportParameters.

Compile and run this code. You should find that the signature is verified. Now change the hash (in this case it is assumed that the first byte in the hash is not zero) and run the code again:

This time you'll find that the signature is not verified. Change line you just added so that you alter the signature (again, assuming that the first byte is not zero):

Again, you'll find that the signature is not verified. So, as you can see, VerifyHash detects that either the data (ie the hash) or the signature is correct. (When you have finished this test remove the line that changes the signature.)

The SignData method will perform the hash and signature in one action. DSA always uses SHA1, so the method does not need any hash identifier, however RSA can use any hash algorithm and so SignData takes an object to identify the hash algorithm. This object is either a string (the name that you pass to MapNameToOID), a type object of the hash algorithm or an instance. Again there is a corresponding VerifyData to verify the data signed with the signature. Change the code to:

This is more compact code, which makes the code easier to read. Compile and run this to show that the signature is created. Now change the signature (sign) or the data (data) before calling VerifyData to confirm that the verification fails if the hash or signature are altered.

The previous mechanism creates the signature directly through the public key algorithm. The framework provides another mechanism to do the same thing. The RSAPKCS1SignatureFormatter class is initialized with a public key algorithm object (the parameter is a AsymmetricAlgorithm, but you should pass an object of an RSA derived class) , then you can set the hash algorithm, and finally you can call the object to create the signature. There is a corresponding RSAPKCS1SignatureDeformatter class to verify the signature.

Change the code to the following:

Compile and run this, and perform the tests shown earlier to confirm that if the hash or signature changes then the signature cannot be verified.

The DSA classes are only used for signature generation and will only use SHA1, the signature methods are CreateSignature and VerifySignature (these actually call SignHash and VerifyHash). Remove the lines that create the formatter and deformatter and make these changes:

Compile and run this code and perform the tests to confirm that the verification process works.

There is a corresponding DSASignatureFormatter and DSASignatureDeformatter class that provide an alternative way to sign and verify data.

So far on these pages you should have learned that:

• Large amounts of data should be encrypted with a symmetric algorithm because symmetric algorithms are faster than asymmetric algorithms
• Symmetric algorithms use keys that should be kept secret between the people who encrypt and decrypt the data
• Asymmetric algorithms use two keys, one that encrypts the data, and another that decrypts the data
• Typically, one asymmetric key is purposely made public

The problem with symmetric keys is key exchange: how do you pass the secret key from one party to another in such a way that a third party cannot intercept it? This is where public key cryptography excels. If Alice wants to encrypt some data so that Bob can decrypt it she needs to make sure that Bob knows her secret key. To do this Alice obtains Bob's public key and this should be easy to do because the key is meant to be public. Alice then encrypts her secret (symmetric) key with Bob's public key and sends the cyphertext to Bob. Only Bob has his private key, so only Bob can decrypt the cyphertext. Once he has decrypted this data he will have Alice's secret key and so Alice can send Bob encrypted data which he can decrypt.

To try this out I will generate two processes, one is Bob which will listen on a socket and responds to data sent over connected sockets; the other is Alice which will connect to Bob and exchange encrypted data with him.

First we need to set up the sockets infrastructure. Here's Bob.cs:

I'll explain this bit by bit.

This code listens on socket 5000, then the code blocks waiting for a client to connect. Once the client connects the listener obtains stream access to the socket so that it can read and write data to the connected socket. When the listener has finished handling the data from the client it calls Close which closes the stream and the client socket and the loop continues waiting for another client connection.

Next the listener checks data sent by the client:

This accepts data from the client, converts it to a string and checks to see if it is the string key. If it is not this string then it is interpreted as a command to close down so the client connection is closed and the loop is broken so that the listener can stop listening and the process can stop. Finally, the listener does this:

This sends an acknowledgement to the client that the client (Alice) should send the key.

Alice.cs looks like this:

Again, I'll go through this bit by bit.

This code simply connects to Bob. Next, the code checks the command line:

If the user provides a command line argument of quit then this is sent to Bob and Alice finishes. The idea is that to tell Bob to stop listening you should tell Alice to send him the message QUIT.

Here, Alice warns Bob that she is about to send him the key.

Bob should send the message ack to Alice to indicate that he wants to hear the key. Alice can then send the key, and in this case the key is merely a random number:

Now is a good time to compile both Bob and Alice. Open two command windows and start Bob in one and run Alice with a command line parameter in the other, the parameter you pass is unimportant. Verify that the number that Alice prints is also printed by Bob. Run Alice a few times and then finally run Alice with a command line parameter, so that Bob finishes. You'll see something like the following:

Now we want to perform the key exchange. Alice needs to know Bob's public key. To do this I will use a key container, but you could simply generate a key as XML and store it in an XML file. Bob will get all of this XML, but Alice will only get the public key parts. Of course, this supposes that you trust Alice's public key that you've got. Trust in public keys is an issue that is covered by certificates, which is a subject covered by a later page.

Using a key container is simple. Add the following to Bob:

Alice is a bit more complicated because I want to extract the public key from the key pair, here's the code:

This obtains Bob's key from the container and then exports Bob's public key and then imports it into rsaBobPubKey. As we saw in the last section, the framework contains two classes that can be used to encrypt keys in key exchange: RSAOAEPKeyExchangeFormatter and RSAPKCS1KeyExchangeFormetter. In this example we'll use RSAOAEPKeyExchangeFormatter:

The key exchange object is created and then initialized with Bob's public key. Then a random key is created by creating an instance of the Rijndael symmetric key object. Finally, the key is encrypted using CreateKeyExchange. You should now compile Bob and Alice and confirm that Alice passes some binary data to Bob.

The next thing is for Alice to send some encrypted data to Bob using this session key and then Bob needs to extract the session key from exchange key blob and use this to decrypt the encrypted data. The symmetric algorithm uses CBC mode so we need to obtain the initialization vector from Alice and pass that to Bob. Remember that the IV is important, but it does not have to be secret, so if it is made public, it does not compromise the security. Here's the code for Alice:

Again, before the code is send we first wait for Bob to send an acknowledgement. After the IV is sent we wait for another acknowledgement and then send the encrypted data:

This code creates a CryptoStream based on the socket stream so that as data is written to the stream it is encrypted. Note that the code makes sure that the final block is flushed.

Bob creates a deformatter object and initializes it with his private key, then he passes the encrypted session key to DecryptKeyExchange to extract the (symmetric) session key. This is used to initialize the symmetric algorithm object. Here's the code for Bob:

Now Bob needs to read the IV from the client, so Bob first sends an acknowledgement and then reads the data from the socket and uses the data to initialize an array:

Finally, Bob needs to create a CryptoStream object based on the socket and decrypt the data as it's read:

You should now compile both Bob and Alice. Run Bob in one command window and run Alice a few times in another window, each time passing a paramter. Check to make sure that the data that you pass on the command line to Alice is received and decrypted by Bob.

Errata

If you see an error on this page, please contact me and I will fix the problem.

Page Thirteen