Asymmetric Key Cryptography

Overview

The problem posed with symmetric key ciphers, MACs, and HMACs is how to get the secret key to the recipient so that the recipient can decrypt the ciphertext when it is received. Asymmetric key cryptography is one answer. It is called asymmetric key cryptography because the keys used for performing encryption and decryption are different and are normally referred to as public and private keys.

This chapter introduces the concepts of asymmetric key cryptography, including how to use public and private keys for exchanging secret keys and creating digital signatures. Asymmetric algorithms come in a variety of shapes , and you will look at what parameters are required for key creation and what padding mechanisms are appropriate when messages are being encrypted. Unlike symmetric algorithms, asymmetric algorithms are not appropriate for bulk encryption, and you will see how asymmetric and symmetric cryptography is combined to achieve this.

By the end of this chapter, you should be able to

• Use and understand the most popular algorithms in use to date
• Understand the methods for performing key exchange and key agreement, as well as some of the pros and cons of using them
• Understand how to use padding mechanisms with asymmetric keys
• Create and verify digital signatures

Finally, you will also have a good knowledge of the various Java APIs that are in place for supporting the generation, manipulation, and use of asymmetric keys and ciphers.

Getting Started

This chapter extends the Utils class so that it also includes an implementation of SecureRandom , which will produce predictable output. Although this sounds insane from a cryptographic point of view, it will make it a lot easier for me to talk about the examples that use it, as you will be able to reproduce the output exactly.

Here is the class:

package chapter4; import java.security.MessageDigest; import java.security.SecureRandom; /** * Utility class for chapter 4 examples */ public class Utils extends chapter3.Utils { private static class FixedRand extends SecureRandom { MessageDigest sha; byte[] state; FixedRand() { try { this.sha = MessageDigest.getInstance("SHA-1", "BC"); this.state = sha.digest(); } catch (Exception e) { throw new RuntimeException("can't find SHA-1!"); } } public void nextBytes( byte[] bytes) { int off = 0; sha.update(state); while (off < bytes.length) { state = sha.digest(); if (bytes.length - off > state.length) { System.arraycopy(state, 0, bytes, off, state.length); } else { System.arraycopy(state, 0, bytes, off, bytes.length - off); } off += state.length; sha.update(state); } } } /** * Return a SecureRandom which produces the same value. * This is for testing only! * @return a fixed random */ public static SecureRandom createFixedRandom() { return new FixedRand(); } }

As you can see, it just builds on the idea of using a message digest to generate a pseudorandom stream of bytes. Type the new Utils class in to start off the chapter4 package and you are ready to begin.

The PublicKey and PrivateKey Interfaces

Any discussion on how asymmetric cryptography is done in Java needs to mention two interfaces: java.security.PublicKey and java.security.PrivateKey. All keys related to asymmetric encryption will implement one of these interfaces, and consequently, you will often see them as return values for methods on the various classes used to manipulate keys and key material.

The interfaces themselves directly extend java.security.Key but do not introduce any new methodsthey simply provide type safety. You will see why this is the case as you look into the various algorithms in more detail. For the most part, each algorithm has its own set of key interfaces. This is because, unlike the case with symmetric key algorithms, which are basically one size fits all, every asymmetric algorithm is not only different in terms of how it behaves, but also in terms of the parameters required to construct a key.

This chapter starts by looking at regular encryption, but you will see that asymmetric cryptography also forms the foundation for key agreement and digital signatures.

The RSA Algorithm

The RSA algorithm was initially publicized in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adleman. Recently declassified documents reveal that the method used by RSA was first discovered by Clifford Cocks in 1973 at GCHQ in Great Britain.

The algorithm gets its security from the difficulty of factoring large numbers . Essentially , the public and private keys are functions of a pair of large primes, and recovering the plaintext from a given ciphertext and the public key used to create it is believed to be equivalent to the problem of recovering the primes used to make the keys. How big a key has to be is an interesting question. The keys in the examples were chosen so they would be easy to type in and produce output that would fit on a line, not for reasons of security. In practice, the key size should be a minimum of 1,024 bits; double that if your application is required to keep messages protected for more than 10 years .

Although full derivation of the algorithm is well beyond the scope of this book, the algorithm itself is quite simple to express. Given two primes p and q , if you have other numbers n, e , and d such that:

n = pq

and

ed 1mod(( p - 1)( q - 1))

then, given a message m,

c = me mod n m = cd mod n

where c is the ciphertext. There are longer names for n, e , and d as well; they are the modulus , the public exponent , and the private exponent, respectively. In general, we choose the value of the public exponent so that the encryption step is computationally cheap to perform, and then generate the private exponent accordingly . As for n, p , and q : It is the size of n that determines how many bits the RSA key you have generated is said to have, so p and q need to have a bit length half that of the key size.

To make use of the algorithm, you need to make sure you can represent any message you want to encrypt as a positive big integer that is less than n . This is quite easy to do. In the case of Java, you just take the bytes making up the message and then create a positive BigInteger object from them.

Of course, in this case, because you are dealing with the JCE, you never have to convert a message into a BigInteger yourself. However, it is important to know that this is what is happening under the covers, as it does affect the way in which you can safely use the RSA algorithm. For example, I have already mentioned that the message m needs to have a value arithmetically less than n . The reason is that the arithmetic used in RSA is based on doing calculations mod n , or put another way, by dividing numbers by n and taking the remainder as the answer. The result is that any value greater than n will be reduced to that value mod n by the encryption process. You will see how you deal with large messages and RSA a bit later, but for the moment just remember that the fact you are doing everything using big-integer arithmetic means that the behavior of the algorithm is dictated by the underlying mathematics.

Try It Out: Basic RSA

As a starting point, try to run the following example. It will introduce you to the basic classes used for RSA, as well as show how the JCE allows you to take advantage of the common API even though the underlying implementation of RSA is very different from any algorithm you have encountered to date. The key size is 128 bits, one- eighth of the minimum recommended size, but it is big enough for the purposes here.

package chapter4; import java.math.BigInteger; import java.security.KeyFactory; import java.security.interfaces.RSAPrivateKey; import java.security.interfaces.RSAPublicKey; import java.security.spec.RSAPrivateKeySpec; import java.security.spec.RSAPublicKeySpec; import javax.crypto.Cipher; /** * Basic RSA example. */ public class BaseRSAExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance("RSA/None/NoPadding", "BC"); // create the keys KeyFactory keyFactory = KeyFactory.getInstance("RSA", "BC"); RSAPublicKeySpec pubKeySpec = new RSAPublicKeySpec(new BigInteger("d46f473a2d746537de2056ae3092c451", 16), new BigInteger("11", 16)); RSAPrivateKeySpec privKeySpec = new RSAPrivateKeySpec(new BigInteger("d46f473a2d746537de2056ae3092c451", 16), new BigInteger("57791d5430d593164082036ad8b29fb1", 16)); RSAPublicKey pubKey = (RSAPublicKey)keyFactory.generatePublic(pubKeySpec); RSAPrivateKey privKey = (RSAPrivateKey)keyFactory.generatePrivate(privKeySpec); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

When you run the example, you should see the following output:

input : beef cipher: d2db15838f6c1c98702c5d54fe0add42 plain : beef

How It Works

In terms of how the Cipher class is used, the example is not that different from what you have seen before. What has changed is that the classes representing the key material for the keys in addition to the interfaces representing the keys themselves are now more specialized. Just from looking at the names given to them, it is evident that they are for RSA.

I will go into the details about the specification objects in more detail a bit later, but as you can see, the initialization of the RSA cipher involves defining some value objects that contain the numbers that define the RSA public and private keys. These are then converted into keys that are passed to the cipher object using a new factory class that deals with asymmetric keys ”the KeyFactory class. After that, it looks like business as usual. The next step is to understand the KeyFactory class and what it does. Remember, as the KeyFactory class is an abstraction, what is said about it applies to all asymmetric algorithms.

The KeyFactory Class

The java.security.KeyFactory class provides the necessary abstraction layer to allow you to convert key specifications that you have created outside a provider's environment into Key objects that you can use within the provider, or take existing keys and convert them into specifications that you can then export. Like the Cipher class, it uses the getInstance() factory pattern, and KeyFactory.getInstance() behaves exactly as other getInstance() methods in the JCA in the manner in which it follows precedence rules and finds algorithm implementations .

The KeyFactory class has four conversion methods. Two of the methods convert key specifications into keys, generatePublic() and generatePrivate() . One method creates key specifications, getKeySpec() . The final method translates keys from one provider into keys suitable for use in another ”the translateKey() method.

The two methods of most interest are the generatePublic() and generatePrivate() methods. In the example, you can see they are being used to convert the specification objects containing the key material for RSA keys into Key objects. Take a look at the specification objects and key interfaces now.

RSAPublicKeySpec and RSAPublicKey

As the suffix on the class name suggests, RSAPublicKeySpec is a value object that contains the necessary objects that can be used to create an RSA public key ”the modulus and the public exponent.

Passing the RSAPublicKeySpec object to the KeyFactory.generatePublic() returns a PublicKey object. In this case, because it is RSA, the KeyFactory returns an object implementing RSAPublicKey , which has the same method signatures as RSAPublicKeySpec . There is a getModulus() method, which returns the BigInteger representing the modulus, and the getPublicExponent() method, which returns the BigInteger representing the public exponent.

RSAPrivateKeySpec and RSAPrivateKey

The RSAPrivateKeySpec is also a value object and in this case contains the objects that are required to create an RSA private key ”the modulus and the private exponent.

Other than the fact you use KeyFactory.generatePrivate() to create the key object implementing RSAPrivateKey , and that you have a getPrivateExponent() method rather than a getPublicExponent() , the basic class and interface for dealing with RSA key material and RSA keys are essentially the same as their public key equivalents. You might expect this to be the case, because it follows from the symmetry inherent in the RSA algorithm.

Creating Random RSA Keys

You can also generate keys randomly , rather than having to have all the key material beforehand. As you have already seen, asymmetric algorithms require a public and a private key. Consequently, rather than using a KeyGenerator to generate a single Key object, you introduce KeyPairGenerator to generate a KeyPair .

You will look at these classes in more detail in a minute. A good way to understand them is to try using them first.

Try It Out: Creating Random RSA Keys

Try the following example. It creates an RSA key pair from a random source, encrypts a simple message with the pair's public key, and then recovers the message using the pair's private key to decrypt the ciphertext.

package chapter4; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; /** * RSA example with random key generation. */ public class RandomKeyRSAExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance("RSA/None/NoPadding", "BC"); SecureRandom random = Utils.createFixedRandom(); // create the keys KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC"); generator.initialize(256, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

Running the example produces the following output:

input : beef cipher: 8274caf4a1f54b3b58f6798755d2cfce3e33f710a3f520865c0ccdca0a672601 plain : beef

Notice how as the key size goes up so does the size of the block of ciphertext. Even though at this point you are still only at a key size of 256 bits, one-fourth of what you would be using in an application, you can see that RSA is expanding the original 4-byte message substantially. There is no equivalent to CTR mode with RSA ”you just have to accept the expansion as a necessary expense.

How It Works

As with BaseRSAExample, the example does look very similar to what you have seen before in Chapter 2; the only real difference being the use of KeyPair and KeyPairGenerator because you are now dealing with an asymmetric algorithm rather than a symmetric one. To really understand the example, you just need to understand the classes involved in the public and private key generation.

The KeyPair Class

The java.security.KeyPair class serves as a holder for a private key and its associated public key. It is a simple value object with two methods. The getPrivate() and getPublic() methods return the private and public keys making up the key pair.

The KeyPairGenerator Class

The java.security.KeyPairGenerator is like the KeyFactory class in the manner in which it is created, via the call to KeyPairGenerator.getInstance() , and in how calls to getInstance() are resolved by the JCA framework in terms of the precedence rules and which provider is chosen if one is not specified.

The class itself is very simple to use. There are four initialize() methods, two that take an integer key size ”one with a user -specified source of randomness ”and two initialize() methods that take AlgorithmParameterSpec objects instead. You will see as you go further that the AlgorithmParameterSpec versions are the most powerful, as often with asymmetric algorithms the key size is only one of several parameters that can be specified and often not the only one you want to control.

Finally, there are the actual methods that return the key pair that the class generates: KeyPairGenerator.generateKeyPair() and KeyPairGenerator.genKeyPair() . These methods are functionally equivalent; which one you use really depends on whether you prefer gen to generate .

As it turns out, there is an AlgorithmParameterSpec class specific to RSA, the RSAKeyGenParameterSpec class. It is also one of the simplest you will run into, so take a look at it next.

The RSAKeyGenParameterSpec Class

As mentioned earlier, when generating RSA key pairs, you normally try to choose a value for the public exponent and allow the private exponent to be derived from that accordingly. The JCA allows you to specify both the key size you want and the public exponent for RSA key pairs generated by KeyPairGenerator object by using the KeyPairGenerator.initialize() method that takes an AlgorithmParameterSpec object as a parameter. The class you use for this is java.security.spec.RSAKeyGenParameterSpec , which appeared in JDK 1.3. It is very simple to use, just taking a key size and a public exponent in its constructor.

For example, if you wanted to specify one of the standard public exponents such as the value F4, recommended in X.509, and the default for the Bouncy Castle provider, you could change the call to the initialize() method on the generator object to the following:

generator.initialize(new RSAKeyGenParameterSpec(256, RSAKeyGenParameterSpec.F4), random);

All RSA public keys generated by the generator object would have the public exponent set to the value represented by F4 ”the integer 0x10001.

Improving RSA Performance

A cursory examination of the first RSA example shows that the private exponent of the private key is considerably larger than the public exponent. This is the reason why use of an RSA private key is so much slower than the use of the public key. The reasons for the difference make sense; it means that encrypting data is quick, which can be very useful if you are using a client with limited CPU power, and also, as you will see later, that digital signature verification is quick as well.

Can you speed up use of the private key? As it turns out, you can. It requires knowledge of the primes used to create the modulus, which you should be keeping to yourself, but because you should be keeping the details of the private exponent secret anyway, adding a few more things to keep with the same secret is not such a big issue. The reason that knowledge of the primes is so important is that knowing them means you can take advantage of the Chinese Remainder Theorem.

Chinese Remainder Theorem

Discovered by a first century Chinese mathematician Sun Tse, the Chinese Remainder Theorem, briefly , says the following:

Given a number n that has a prime factorization of p1 * p2 * *pi, the system of simultaneous congruencies of the form:

( x mod p j ) ‰ a j , j = 1,2, , i

has a unique solution modulo n .

Or put another way, a number less than n can be uniquely identified by the results of taking the number mod each of the primes making up n .

I am not going to go into the mathematics of this in more detail, as it is covered in other publications , but the important point is that the theorem means that you can perform the calculations involving the private exponent using a different formula to that used for the public exponent. Because the calculation involves using much smaller big integers than the modulus, the calculation will be substantially faster.

In Chapter 4, I mention that using Chinese Remainder Theorem (CRT) involves keeping the prime factors of the modulus (referred to in the theorem as n ). It turns out that in the implementation of CRT, there are several other values that you can precompute and keep that will further improve the speed of the calculation. For this reason, you will see that the RSAPrivateCrtKey and RSAPrivateCrtKeySpec classes have methods for extracting eight values rather than two.

RSAPrivateCrtKeySpec and RSAPrivateCrtKey

java.security.spec.RSAPrivateCrtKeySpec is a value object that provides the key material for a RSA private key that can take advantage of CRT.

In exactly the same manner as for an RSAPrivateKeySpec, you can pass an RSAPrivateCrtKeySpec to a KeyFactory object that was created for RSA, and you should get back a key that implements java.security.interfaces.RSAPrivateCrtKey, which extends RSAPrivateKey. If you get back a key that implements only RSAPrivateKey after passing in an RSAPrivateCrtKeySpec, it probably indicates that the underlying provider does not implement CRT. If private key operations with RSA seem very slow, this may well be the reason.

RSAPrivateCrtKeySpec and RSAPrivateCrtKey have the same method signatures. The methods available on both allow you to retrieve the values making up the CRT key. They are as follows:

• q getModulus() returns the value of the modulus n .
• q getPrivateExponent() returns the value of the private exponent d .
• q getPrimeP() returns the value of the prime p .
• q getPrimeQ() returns the value of the prime q .

Finally, the getPrimeExponentP(), getPrimeExponentQ(), and getCrtcoefficient() methods all return values based on p and q, which are precomputed in order to further speed up use of the RSA private key.

In the case of the Bouncy Castle provider, RSAPrivateCrtKey objects are returned by the underlying KeyPairGenerator implementation, but if you want to get some idea of how expensive private key operations are without CRT, you can always roll your own RSAPrivateKeySpec by taking the equivalent values it requires from an RSAPrivateCrtKey.

Multi Prime Chinese Remainder Theorem

If you recall the initial discussion about CRT, it relies on having access to the primes used to generate the modulus. The interesting thing about it is that the theorem does not say there has to be two primes for generating a modulus, nor does RSA. You could have four primes instead; so, for example, if you were using a 2,048-bit key, rather than having two primes of 1,024 bit involved in the generation of the key and the subsequent use of the private key, you could have four primes of 512 bits involved in the generation of the key and the calculations involving the private key. Issues about the changes in the difficulty of factoring that the presence of more than two primes in the generation of the modulus makes notwithstanding, private key operations in the four prime case will be substantially faster than the corresponding operations in the two prime case.

The interface java.security.interfaces.RSAMultiPrimePrivateCrtKey and the classes java.security.spec.RSAMultiPrimePrivateCrtKeySpec and java.security.spec.RSAOtherPrimeInfo are provided to support this method of calculation. I will not discuss it in more detail here, as currently there is no implementation of it in the Bouncy Castle provider, and the method is subject to patents as well. However, if you would like to know more about it, have a look at the JavaDoc and the associated standard RSA Security's PKCS #1. You will find that it follows quite naturally from what I discussed initially about CRT.

At this point, you have more or less covered the mechanics of the RSA algorithm itself. Now you can look at the mechanisms that are ultimately used to convert the bytes you want to encrypt into a big integer that can be used in the algorithm.

RSA Padding Mechanisms

The big difference between RSA and a regular symmetric cipher can be demonstrated by replacing the line:

byte[] input = new byte[] { (byte)0xbe, (byte)0xef };

with the line:

byte[] input = new byte[] { 0x00, (byte)0xbe, (byte)0xef };

Doing this produces the following output instead:

input : 00beef cipher: 09d9c77b2e43a0b6c0b1114523dd4458a7b68b0eee381da2c22895e7a4f44c96 plain : beef

There are two things you probably noticed here. The most glaring is that the plaintext is not the same as the ciphertext ”the leading zero has disappeared. The second is that the ciphertext with the new input is the same as the ciphertext with the old input. Although this might explain why the plaintext generated does not have the leading zero, you still might be left wondering what happened between providing the input data and the encryption process that stripped it off. Does this mean that RSA, or at least the implementation, is broken?

Fortunately, both the RSA algorithm and the implementation are fine. Think back to the explanation of how the algorithm works at the start of this section and you will realize that the byte array provided as input is converted into a big integer so that the algorithm can be applied. It is this process of conversion to a big integer where the leading zeros are dropped ”in the world of numbers, leading zeros are not meaningful.

Of course, in this case, leading zeros are meaningful, so including extra padding that allows you to preserve them makes sense. Padding does not just serve the purpose of allowing you to maintain leading zeros. Try changing the example now so that the public exponent is F0 (the value 0x3) rather than F4 (the value 0x100001). You can do this by importing java.security.spec.RSAKeyGenParameterSpec and changing the call to generator.initialize() as follows:

generator.initialize(new RSAKeyGenParameterSpec(256, RSAKeyGenParameterSpec.F0), random);

Making this change and running the example again should produce something like this:

input : 00beef cipher: 00000000000000000000000000000000000000000000000000006a35ddd3c9cf plain : beef

It is one thing to lose the leading zero, but something worse has happened here. The data you have encrypted can now be recovered by simply taking the cube root of the ciphertext. The reason is that the input data, when converted to a big integer and raised to the power of the public exponent, is actually less than the modulus. So rather than further complicating the life of someone trying to recover the original message, doing the mod step in the calculation has returned the original number raised to a power. As you can see, padding the message so that it becomes a big integer closer in size to the modulus before it is raised to the public exponent serves more than just the purpose of protecting leading zeros.

I already mentioned PKCS #1 in the context of detailing methods of using Chinese Remainder Theorem. As it turns out, PKCS #1 also details padding mechanisms for use with the RSA algorithm. Originally, it only specified one mechanism, which is the reason for the naming convention you are about to see. However, it has since been revised and now specifies some other padding mechanism as well. The convention in Java is to refer to the original padding mechanism that was specified in PKCS #1 version 1.5 as PKCS1Padding . The extra padding mechanisms created since then are referred to by the names given in PKCS #1 instead. Let's consider the original mechanism first.

PKCS #1 V1.5 Padding

PKCS #1 originally just described a mechanism with three types of padding modes for a block to be encrypted. The first, type 0, is to use nothing but zeros, equivalent to NoPadding in the JCE. The second, type 1, is used when the RSA algorithm is applied to the data to be encrypted using the public key. The third, type 2, is used when the algorithm is being applied to the data using the private key. These second and third techniques are referred to as PKCS1Padding in the JCE.

Type 1 PKCS #1 padding is quite simple to apply. Given a message M the padded message M p will be

M p = 0x000x01F0x00M

where F is a string of bytes of the value 0xFF. The – is a concatenation operator. There are some restrictions on how big M can be. F must be at least at least 8 bytes long, so M can be no longer than the length of the key in bytes less 11.

Type 2 PKCS #1 padding is also quite simple. Given a message M the padded message M p will be

M p = 0x000x02R0x00M

where R is a string of pseudorandom bytes, which must again be at least 8 bytes long.

The interesting difference between these two mechanisms is that while both will produce big integers that are within a byte or so of the size of the key being used, type 1 guarantees that the same value of M encrypted with the same key will always produce the same ciphertext. Type 2, on the other hand, guarantees the opposite . It is highly unlikely a type 2 padded message will ever encrypt to the same ciphertext. For this reason, type 1, as you will see later, is used with signatures, which are created by processing using the private key. Imagine that the same document signed with the same key might produce the same signature. Type 2, on the other hand, is what the Cipher object uses when it is created using the padding mode PKCS1Padding , and a public key is used for the encryption step.

Try It Out: PKCS #1 V1.5 Padding

Try the following example. Note that the data now has a leading zero on it and PKCS1Padding has been specified. Because it uses the public key to encrypt with, the padding is type 2 and would normally uses random data. I have therefore passed in a fixed random generator in order to reliably reproduce the output.

package chapter4; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; /** * RSA example with PKCS #1 Padding. */ public class PKCS1PaddedRSAExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { 0x00, (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance("RSA/None/PKCS1Padding","BC"); SecureRandom random = Utils.createFixedRandom(); // create the keys KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC"); generator.initialize(256, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

You should see the following output demonstrating that the padding has allowed the leading zero to be maintained :

input : 00beef cipher: 01fce4a90b326bb1c3ebc2f969a84024d157499038f73ee03635c4e6ffb3377e plain : 00beef

Try the modification given earlier to change the public exponent to the value F0. You will see that the padding is not just helping preserve the original plaintext but helping protect it as well.

How It Works

The difference, of course, is that the leading zero is preserved because the original message has first had the padding added, and then the result string of octets is converted into a big integer. Before, with no padding, just the message was converted into a big integer.

The other effect of this is that now you are dealing with a big integer that is much closer to the size of the modulus. Therefore, even when you are using a small public exponent like the value F0, or 3, the mod arithmetic is able to make its presence felt and make the RSA process meaningful.

OAEP Padding

Optimal Asymmetric Encryption Padding, or OAEP, is the latest method of padding specified in PKCS #1. It was originally outlined by Mihir Bellare and Phillip Rogaway in 1994 and has since been adopted as a method in PKCS #1 under the full name RSAES-OAEP. OAEP has the advantage that it is provably secure in the random oracle model, or put another way, that if the hash functions OAEP is based on are ideal, the only way to break an OAEP-encoded encrypted RSA message is to break RSA itself. Before you continue with what OAEP actually looks like on the wire, it's worth having a look at exactly what this last statement means.

In this context, an oracle is essentially a black box that you can prod for information. It might be something that decrypts the older PKCS #1 formatted messages, for example. Say you want to know what a particular message decrypts to and you can get the oracle to return the result of decrypting a message. It is possible, as outlined in the "Million Message Attack" discussed in RFC 3218 and originally detailed in Daniel Bleichenbacher's paper "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1," to generate a number of transforms of the ciphertext you are trying to decrypt and then use the information you get back from the oracle when you try to get it to decrypt the transformed messages to slowly recover the plaintext of the ciphertext.

You can do this because there are some things in the structure of a PKCS #1 type 2 message that you can predict. An OAEP message, on the other hand, will always come back not only looking completely random, but while a correctly decrypted one will have internal consistency, OAEP makes use of a masking function based on a cryptographic hash. This means that you cannot actually check the message for consistency until you have XORed it with a stream of bytes generated by a function whose output you cannot predict, because you are not sure you have the right input. In a similar way to the use of the hash function in key agreement, the combined effect of the hash and masking function here is to deprive an attacker of the capability to take advantage of the mathematical properties of the underlying algorithm. The oracle, or black box, available to you will, at best, be sending back "random" noise.

Having gone through all that, although it is recommended that new applications use OAEP wherever possible, the message here is not necessarily the case that traditional PKCS #1 padding is insecure . The real message is you should always try to avoid giving anything intelligible away when rejecting a message: Take as long to handle a rejection as an acceptance and give out only the minimal amount of information ”none if you can get away with it. Avoid leaks!

So how does OAEP actually work? As I have already alluded to, it involves a cryptographic hash function, H(), and a mask function, Mask(), based on the hash function. Broadly speaking, it breaks down into the following three steps, given a message M , a parameter string P , and a random seed S :

1. M 1 = Mask((H( P ) – PS – 0x01 – M ), S )
2. M 2 = Mask( S, M 1 )
3. M p = 0 —00 – M 2 – M 1

where PS is a pad string of zeros, – is concatenation, and M p is the resulting masked and padded message. The mask function operates by using its second argument as a seed to a pseudorandom octet generator, which is then used to mask the octets making up the first one. I will not discuss the mask function here in detail, as it is detailed in PKCS #1, other than to mention the name of it ”MGF1. You will see that MGF1 is used in a number of other places later. The parameter string P is defined by default as the empty string, so, as you will see in the example that follows, normally there is no need to specify it.

A cursory glance at the equations shows that the masked and padded message M p is a concatenation of two masked messages, one hiding the seed for masking the message you are trying to protect, and the other masking the padded message itself. It also reveals that using this padding mechanism has a substantial overhead, as you need space for the seed as well as space for the hash of the parameter string P . As the seed is the same size as the hash, if hLen is the length of the hash in octets and kLen is the size of the key in octets, this gives the maximum size for the messages you can encrypt as:

MaxLen = kLen ˆ’ 2hLen ˆ’ 2

Unlike in traditional PKCS #1 padding, the pad string PS can be of zero length.

Try It Out: OAEP Padding

Compare the following example to the PKCS1PaddedRSAExample class you looked at earlier. You will note that, even though the message being encrypted is the same size as before, the key size has had to expand from 256 to 384 bits in order to provide the minimum required space for the padding to fit.

package chapter4; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; /** * RSA example with OAEP Padding and random key generation. */ public class OAEPPaddedRSAExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { 0x00, (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance("RSA/None/OAEPWithSHA1AndMGF1Padding", "BC"); SecureRandom random = Utils.createFixedRandom(); // create the keys KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC"); generator.initialize(386, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

In this case, running the example should produce the following output with the expanded ciphertext:

input : 00beef cipher: 020692d99b7b73e8284134590f1f04dbdbdfeee627d3da72a18acf244e41da4a012a834c 1c890213a8508f5406816ef74b plain : 00beef

Of course, 384 bits is well below an acceptable key size, so in practice the extra overhead OAEP requires is not generally an issue. The main thing to remember is that it does not give you as much room in an RSA block as the older PKCS #1 padding mechanism specified in PKCS #1 V1.5.

How It Works

Of course, the trick here is that you have simply included a different padding string in the cipher name passed to Cipher.getInstance(). The JCE then does the rest for you.

One thing to note about what is happening under the covers: Look at the format given for the name of the cipher's padding string, it really reads OAEPWithDigestAndMaskFunctionPadding . This naming convention is outlined in "Java Cryptography Architecture API Specification and Reference," which is provided in the standard Java documentation hierarchy and allows for the specification of a range of digests and masking functions. So, for example, to do OAEP-encoded based on SHA-256 with its default parameters, the padding string you would use would be OAEPwithSHA256andMGF1Padding ; likewise for any other digest algorithm or mask function that might be supported by the provider you are using.

The previous example should work in any JCE with the BC provider installed. However, if you are using JDK 1.5 or later, a number of classes were added to the JCE to better support OAEP, and as it is now the padding mode of choice, you can expect to make use of them.

The PSource Class

The javax.crypto.PSource class is used to specify a source for the P parameter that appears in the equations above for creating the padded string. Currently there is only one type of parameter that can be supported and this is provided by a public extension of PSource, PSource.PSpecified. This parameter takes a byte array for its constructor; by default, this is of zero length, so defining a default PSource equivalent to the object PSource.PSpecified.DEFAULT for use with an OAEP padding parameter specification would look like:

PSource defaultPSource = new PSource.PSpecfied(new byte[]);

Ordinarily you would not change this; however, if you wanted to explicitly label every OAEP-encoded message encrypted with a given key from a given server with a message number you might use instead

PSource labeledPSource = new PSource.PSpecified(msgNumber);

where msgNumber is a byte array representing the message number of the encrypted block been sent. Any message decrypted without the correct P parameter set will be rejected.

In terms of get methods, PSource has only one method on it, PSource.getAlgorithm(), which returns the algorithm name. The extension class PSource.PSpecified adds one more method, PSource.PSpecified.getValue(), which simply returns the byte array that it was constructed with. For the most part, the get methods associated with PSource and PSource.PSpecified are only used by the underlying JCE provider you are using.

The MGF1ParameterSpec Class

The java.security.spec.MGF1ParameterSpec class is used to represent the standard mask generation function MGF1. It also takes only one parameter for its constructor ”the name of the message digest function used to drive the masking function.

For example, the default digest for MGF1 is SHA-1, so a default definition for the MGF1ParameterSpec in regular OAEP looks like:

MGF1ParameterSpec defaultMGF1 = new MGF1ParameterSpec("SHA-1");

The class also has a number of default value objects: MGF1ParameterSpec.SHA1, MGFParameterSpec.SHA256, MGFParameterSpec.SHA384, and MGFParameterSpec.SHA512, which allow you to define versions of MGF1 for SHA-1, SHA-256, SHA-384, and SHA-512.

The MGFParameterSpec method has a single get method, MGFParameterSpec.getDigestAlgorithm(), which returns the name of the digest algorithm the MGF1 function is based on.

The OAEPParameterSpec Class

Putting it all together, you have java.security.spec.OAEPParameterSpec. Like the PSource.PSpecified class, it also has a default value that can be used: OAEPParameterSpec.DEFAULT. Defining the default value for the OAEPParameterSpec long hand, you would end up with the following definition:

OAEPParameterSpec defaultOAEPSpec = new OAEPParameterSpec("SHA-1", "MGF1", MGF1ParameterSpec.SHA1, PSource.PSpecified.DEFAULT);

As you can see, the construction of the OAEPParameterSpec object follows from the original equations describing the padding mechanism. The first argument is the hash function H, the second argument is the name of the mask function Mask, and then the parameters of the mask function are given, in the default case, a parameter specification object for the MGF1 function based on SHA-1. Finally the parameter string P is given, in this case an empty byte array.

Ordinarily, you will use this object so you can set the parameter string P. When you are using it, the only rule you need to be aware of with constructing an OAEPParameterSpec is that it is recommended in PKCS #1 that the same hash algorithm is used for both the function H and the mask generation function. So, for example, if you wanted to use SHA-256 for H, you should have a definition that looks something like this:

OAEPParameterSpec sha256OAEPSpec = new OAEPParameterSpec("SHA-256", "MGF1", MGF1ParameterSpec.SHA256, PSource.PSpecified.DEFAULT);

although you might want to have a different value passed for the parameter string P. Currently, MGF1 is the only mask generation function supported. Follow PKCS #1 and IEEE P1361 if you are interested in further developments in this area.

The OAEPParameterSpec class has get methods on it that allow you to retrieve the values it was constructed with, as with PSource, and MGF1ParameterSpec the get() methods are really of most relevance inside the provider you are using.

Which brings me to the last point. Having created an OAEPParameterSpec, how do you use it? As you would expect, it is just passed to Cipher.init(), so using the sha256OAEPSpec as an example you could write

Cipher c = Cipher.getInstance("RSA/None/OAEPWithSHA256AndMGF1Padding"); c.init(Cipher.ENCRYPT_MODE, publicKey, sha256OAEPParameterSpec, new SecureRandom());

Wrapping RSA Keys

You saw in Chapter 2 that it was possible to use symmetric keys to wrap other symmetric keys. You can achieve the same effect for wrapping asymmetric keys using exactly the same API.

Try It Out: Wrapping an RSA Private Key

Look at the following example. Note that, unlike the example in Chapter 2, you are now using Cipher.PRIVATE_KEY to tell the wrapping cipher what kind of key you are expecting. If you had wrapped a public key ( strange I will admit), you would need to pass Cipher.PUBLIC_KEY.

package chapter4; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; public class AESWrapRSAExample { public static void main(String[] args) throws Exception { Cipher cipher = Cipher.getInstance("AES/ECB/PKCS7Padding", "BC"); SecureRandom random = new SecureRandom(); KeyPairGenerator fact = KeyPairGenerator.getInstance("RSA", "BC"); fact.initialize(1024, random); KeyPair keyPair = fact.generateKeyPair(); Key wrapKey = Utils.createKeyForAES(256, random); // wrap the RSA private key cipher.init(Cipher.WRAP_MODE, wrapKey); byte[] wrappedKey = cipher.wrap(keyPair.getPrivate()); // unwrap the RSA private key cipher.init(Cipher.UNWRAP_MODE, wrapKey); Key key = cipher.unwrap(wrappedKey, "RSA", Cipher.PRIVATE_KEY); if (keyPair.getPrivate().equals(key)) { System.out.println("Key recovered."); } else { System.out.println("Key recovery failed."); } } }

Try running the example and you should be rewarded with the message Key recovered .

How It Works

Just as with the example in Chapter 2, internally the Cipher object doing the wrapping calls the Key.getEncoded() method on the PrivateKey object passed in to the Cipher.wrap() method. This produces an encrypted byte stream containing the wrapped key. Likewise, unwrapping the key is a matter of passing the encrypted bytes to the Cipher.unwrap() method. A feature of using wrapping is that if the provider being used is based on a hardware adapter that will not expose the contents of private keys in the clear, the internal equivalent of the getEncoded() method and the accompanying encryption can be carried out in the confines of the hardware adapter.

It is interesting to note that you do not need to use a specific wrapping mechanism here. Unlike the situation with symmetric keys where the getEncoded() method returns just the bytes making up the key, in the case of an asymmetric key, there is quite a lot of structural information in the encoding of the key in addition to the key material. If you attempt to use unwrap() on an asymmetric key with the wrong secret key, it will fail quite badly , as the unwrapping mechanism will not be able to put the key back together.

Secret Key Exchange

As you have seen, using RSA limits the size of the message you can encrypt to what fits within a single block. Often this space will be further restricted because you also have to make use of padding. The question then remains: How do you make use of this technology to safely encrypt larger amounts of data? You could try breaking the data into chunks, but depending on the number of chunks required, this might be very slow. In some cases, if an attacker has some knowledge of the data you are trying to encrypt, breaking it into chunks might further compromise the private key of the person you are encrypting the data for.

The answer, as it turns out, is quite simple.

Try It Out: Secret Key Exchange

Try the following example program:

package chapter4; import java.io.ByteArrayOutputStream; import java.io.IOException; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; import javax.crypto.spec.IvParameterSpec; import javax.crypto.spec.SecretKeySpec; /** * RSA example with OAEP Padding and random key generation. */ public class RSAKeyExchangeExample { private static byte[] packKeyAndIv( Key key, IvParameterSpec ivSpec) throws IOException { ByteArrayOutputStream bOut = new ByteArrayOutputStream(); bOut.write(ivSpec.getIV()); bOut.write(key.getEncoded()); return bOut.toByteArray(); } private static Object[] unpackKeyAndIV( byte[] data) { byte[] keyD = new byte[16]; byte[] iv = new byte[data.length - 16]; return new Object[] { new SecretKeySpec(data, 16, data.length - 16, "AES"), new IvParameterSpec(data, 0, 16) }; } public static void main(String[] args) throws Exception { byte[] input = new byte[] { 0x00, (byte)0xbe, (byte)0xef }; SecureRandom random = Utils.createFixedRandom(); // create the RSA Key KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC"); generator.initialize(1024, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // create the symmetric key and iv Key sKey = Utils.createKeyForAES(256, random); IvParameterSpec sIvSpec = Utils.createCtrIvForAES(0, random); // symmetric key/iv wrapping step Cipher xCipher = Cipher.getInstance( "RSA/NONE/OAEPWithSHA1AndMGF1Padding", "BC"); xCipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] keyBlock = xCipher.doFinal(packKeyAndIv(sKey, sIvSpec)); // encryption step Cipher sCipher = Cipher.getInstance("AES/CTR/NoPadding", "BC"); sCipher.init(Cipher.ENCRYPT_MODE, sKey, sIvSpec); byte[] cipherText = sCipher.doFinal(input); System.out.println("keyBlock length : " + keyBlock.length); System.out.println("cipherText length: " + cipherText.length); // symmetric key/iv unwrapping step xCipher.init(Cipher.DECRYPT_MODE, privKey); Object[]keyIv = unpackKeyAndIV(xCipher.doFinal(keyBlock)); // decryption step sCipher.init(Cipher.DECRYPT_MODE, (Key)keyIv[0], (IvParameterSpec)keyIv[1]); byte[] plainText = sCipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } } Running the example, you should get the following output:input : 00beef keyBlock length : 128 cipherText length: 3 plain : 00beef

As you can see, the technique is not without overhead; on the other hand, it does remove most limits on how much data you can actually send and gives you the full advantage of the greater speed that you can get from the use of symmetric key algorithms.

How It Works

The trick, of course, is in the wrapping of the key of the symmetric cipher using xCipher and encrypting the data using the symmetric key using sCipher. If you look at Figure 4-1, you can see that you send both the encrypted data and the encrypted key to the receiver, who then recovers the symmetric key using a private key and then recovers the data by decrypting it using the secret key.

Figure 4-1

You can use RSA as you have above, or as you will see, El Gamal, to provide this sort of encryption. The overall process has a good feel to it. The asymmetric algorithm is used for what it is best at, and the symmetric algorithm is used for what it is best at ”everything in the right place.

Note that there is one element missing from the example. We have not done anything about providing a means of verifying the integrity of the data that was encrypted. Remember, it is important to include a MAC, a digest, or some other verifying information so that the decrypted data can be verified .

Key Agreement

Key agreement algorithms do not make it possible to encrypt messages in the same way as one can with an algorithm such as RSA. What they do offer is a means for two, or in some cases, more parties to agree on a common secret key with which they can then encrypt messages that they want to pass between each other.

The Diffie Hellman Algorithm

The Diffie-Hellman algorithm takes it name from Whitfield Diffie and Martin Hellman, who invented the algorithm in 1976. GCHQ in Britain has also declassified documents showing that the algorithm dates back to 1974, when it was developed by Malcolm Williamson. Like RSA, the algorithm uses modulus arithmetic. Unlike RSA, the algorithms security relies on the difficulty of solving the discrete logarithm problem and the Diffie-Hellman Problem. The two problems are related and essentially boil down to the difficulty of finding a number x for a given y such that G x = y , where G is a generator for numbers in the group covered by P , a large prime number. It turns out that this is difficult enough, at least at the moment, to be regarded as intractable.

Although the process cannot be used for regular encryption, it does allow two parties to arrive at the same secret key through a series of calculations. If you compare Figure 4-2 to Figure 4-1, you can see the process is quite different. The algorithm is quite simple: Given a large prime number P , a generator G for the group over P , party A chooses a private number U and party B chooses a private number V . Then:

1. A sends B G U mod P (A's public key).
2. B sends A G V mod P (B's public key).
3. Communication is then carried out using a session key based on G UV mod P .

Figure 4-2

One more piece of notation you need to be familiar with: The private value associated with a given party is normally referred to as X , and the public value, G X mod P , is normally referred to as Y .

The algorithm does not seem too complicated; fortunately, the code is not complicated either.

Try It Out: Diffie-Hellman Key Agreement

Try the following example:

package chapter4; import java.math.BigInteger; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.MessageDigest; import javax.crypto.KeyAgreement; import javax.crypto.spec.DHParameterSpec; public class BasicDHExample { private static BigInteger g512 = new BigInteger( "153d5d6172adb43045b68ae8e1de1070b6137005686d29d3d73a7" + "749199681ee5b212c9b96bfdcfa5b20cd5e3fd2044895d609cf9b" + "410b7a0f12ca1cb9a428cc", 16); private static BigInteger p512 = new BigInteger( "9494fec095f3b85ee286542b3836fc81a5dd0a0349b4c239dd387" + "44d488cf8e31db8bcb7d33b41abb9e5a33cca9144b1cef332c94b" + "f0573bf047a3aca98cdf3b", 16); public static void main(String[] args) throws Exception { DHParameterSpec dhParams = new DHParameterSpec(p512, g512); KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DH", "BC"); keyGen.initialize(dhParams, Utils.createFixedRandom()); // set up KeyAgreement aKeyAgree = KeyAgreement.getInstance("DH", "BC"); KeyPair aPair = keyGen.generateKeyPair(); KeyAgreement bKeyAgree = KeyAgreement.getInstance("DH", "BC"); KeyPair bPair = keyGen.generateKeyPair(); // two party agreement aKeyAgree.init(aPair.getPrivate()); bKeyAgree.init(bPair.getPrivate()); aKeyAgree.doPhase(bPair.getPublic(), true); bKeyAgree.doPhase(aPair.getPublic(), true); // generate the key bytes MessageDigest hash = MessageDigest.getInstance("SHA1", "BC"); byte[] aShared = hash.digest(aKeyAgree.generateSecret()); byte[] bShared = hash.digest(bKeyAgree.generateSecret()); System.out.println(Utils.toHex(aShared)); System.out.println(Utils.toHex(bShared)); } }

Running the program shows you that you get the following shared secret on each side:

98f2669e0458195dece063e99f0b355598eb096b 98f2669e0458195dece063e99f0b355598eb096b

As far as generation of key pairs go, the program looks like any other. A slightly deeper look reveals that there are a number of consequences from the use of Diffie-Hellman and key agreement in general.

The first consequence, as you can see from the fact that the fixed random allows you to fix the value of the final shared secret, is that if you reuse the keys used in a key agreement, you will get the same shared secret as a result. The same shared secret means the same shared symmetric key. This gives rise to the following maxim about the keys used by the KeyAgreement class and their lifetime:

The second consequence, perhaps not as obvious, is that if you imagine a situation where the agreement was not taking place in the safety of a single file, you could instead imagine the agreement was being done in a situation where attackers might be able to introduce a phase or two of their own ”the socalled man-in-the-middle attack, shown in Figure 4-3. There is nothing in the previous code that tells you how to verify the origins of the key the other party has sent you.

Figure 4-3

As mentioned earlier, the setup for the program looks very similar to that used for RSA. However, other than the use of the string DH in the selection of the key pair generator, there are some other classes provided by the JCE for supporting Diffie-Hellman. You will look at those classes in the next sections.

The DHParameterSpec Class

The javax.crypto.spec.DHParameterSpec class is a value object that contains the two, or three, parameters. As you can see from the example, the standard constructor takes the values P and G , the prime and the generator for the group represented by the prime, respectively.

There is also a second constructor that you can use to speed up the key exchange process. The second constructor takes a bit length for the private value and will limit the size of the value generated. By default, the private value generated as part of the key generation process will be less than P but with 8 bits of its size. With a P value that is 1,024 bits long, this will make the calculation of the public key for the key agreement slower than it probably needs to be. Depending on the application, you might decide that a private value of no greater than 512 bits is adequate, in which case, given p1024 and g1024 being a 1,024-bit prime and its generator, you might construct a DHParameterSpec as follows :

DHParameterSpec dhSpec = new DHParameterSpec(p1024, g1024, 512);

DHParameterSpec objects can also be generated using the provider. You will see how a bit later, in the section dealing with the AlgorithmParametersGenerator class.

Specification Objects for Diffie-Hellman Keys

The JCE also provides objects for carrying key and parameter material for Diffie-Hellman keys in a provider-independent manner. These objects can be used to carry around material related to keys for any of the Diffie-Hellman-based algorithms. The two classes used for this purpose are javax.crypto.spec.DHPrivateKeySpec and javax.crypto.spec.DHPublicKeySpec.

DHPrivateKeySpec takes the private value X and the P and G values that are required to use it, as in:

DHPrivateKeySpec dhPrivateSpec = new DHPrivateKeySpec(x, p, g);

DHPublicKeySpec takes the public value Y and the P and G values that it was created with. As a code example simply:

DHPublicKeySpec dhPublicSpec = new DHPublicKeySpec(y, p, g);

Like other key specification classes both DHPrivateKeySpec and DHPublicKeySpec are simple value objects, so the only functionality they offer consists of get() methods for recovering the values they were constructed with.

Interfaces for Diffie-Hellman Keys

In the previous example, you relied on the Key class. If you need greater type safety, the JCE does provide javax.crypto.interfaces.DHPrivateKey, javax.crypto.interfaces.DHPublicKey, and a parent class for both of them that extends Key, namely, javax.crypto.interfaces.DHKey.

DHKey provides a single method, DHKey.getParams(), which returns the DHParameterSpec associated with the public and private keys.

DHPrivateKey also has a single method, called DHPrivateKey.getX(), which returns the private value that is not transmitted as part of the agreement process.

DHPublicKey also has a single method called DHPublicKey.getY(). The value returned by getY() is G X mod P , where X is the value return by the corresponding private key's getX() method and G and P are the values of the associated DHParameterSpec object.

Diffie Hellman with Elliptic Curve

The capability to perform key agreement is not just restricted to traditional Diffie-Hellman; it is also possible to use elliptic curve cryptography to perform it.

Elliptic curve cryptography is built using the properties of finite fields. As a cryptographic method it was originally proposed in 1985 by two people, quite independently: Neal Koblitz at the University of Washington and Victor Miller at IBM.

A field is basically a mathematical group that provides operations for addition, subtraction, multiplication, and division that always produce results in the field. I use the term finite when referring to the previous fields because the fields have a limited number of members . It is this property of being finite that makes it possible to do cryptography with the curves that exist over the fields. Two particular field constructions are of most interest here: F p contains curves over the prime finite field p, and F m 2 is a field made up of curves that can be derived from what is referred to as an optimal normal basis representation or a polynomial representation derived from m -bit strings. F m 2 is an interesting space because being binary, it can be handled very efficiently by computers. It is also an area covered by a number of patents, so, at least for your purposes, you will concentrate on curves over F p . You will see from looking at the examples that whether a curve is over F m 2 or F p , from the JCE/JCA point of view, it is pretty much the same to deal with.

The method derives its security from the difficulty of the Elliptic Curve Discrete Logarithm Problem, which could be summed up as follows:

Given two points on a curve, P and Q , find a number k such that kP = Q .

It turns out that for a sufficiently large value of k , solving this problem is a very lengthy process. Looking at how elliptic curve derives its security also gives you some idea of how it works.

Imagine A and B agree on a curve and some fixed point G . This information does not need to be secret. In order for A and B to communicate, as with the original Diffie-Hellman, A and B choose two secret numbers x and y .

1. A sends B xG (A's public key).
2. B sends A yG (B's public key).
3. Communication is then carried out using a session key based on xyG , which both A and B are now able to calculate.

The next important thing is to have a well- formed curve. Fortunately, a large number of these have already been published in publications like X9.62 and FIPS PUB 186-2. The curve in the following example is one such standard.

Try It Out: Diffie-Hellman with Elliptic Curve

Have a look at the following example:

package chapter4; import java.math.BigInteger; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.MessageDigest; import java.security.spec.ECFieldFp; import java.security.spec.ECParameterSpec; import java.security.spec.ECPoint; import java.security.spec.EllipticCurve; import javax.crypto.KeyAgreement; public class BasicECDHExample { public static void main(String[] args) throws Exception { KeyPairGenerator keyGen = KeyPairGenerator.getInstance("ECDH", "BC"); EllipticCurve curve = new EllipticCurve( new ECFieldFp(new BigInteger( "fffffffffffffffffffffffffffffffeffffffffffffffff", 16)), new BigInteger("fffffffffffffffffffffffffffffffefffffffffffffffc", 16), new BigInteger("64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", 16)); ECParameterSpec ecSpec = new ECParameterSpec( curve, new ECPoint( new BigInteger("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", 16), new BigInteger("f8e6d46a003725879cefee1294db32298c06885ee186b7ee", 16)), new BigInteger("ffffffffffffffffffffffff99def836146bc9b1b4d22831", 16), 1); keyGen.initialize(ecSpec, Utils.createFixedRandom()); // set up KeyAgreement aKeyAgree = KeyAgreement.getInstance("ECDH", "BC"); KeyPair aPair = keyGen.generateKeyPair(); KeyAgreement bKeyAgree = KeyAgreement.getInstance("ECDH", "BC"); KeyPair bPair = keyGen.generateKeyPair(); // two party agreement aKeyAgree.init(aPair.getPrivate()); bKeyAgree.init(bPair.getPrivate()); aKeyAgree.doPhase(bPair.getPublic(), true); bKeyAgree.doPhase(aPair.getPublic(), true); // generate the key bytes MessageDigest hash = MessageDigest.getInstance("SHA1", "BC"); byte[] aShared = hash.digest(aKeyAgree.generateSecret()); byte[] bShared = hash.digest(bKeyAgree.generateSecret()); System.out.println(Utils.toHex(aShared)); System.out.println(Utils.toHex(bShared)); } }

Running the example should produce the following output:

5ea61569aed14f67b67377dc6ca223e7ab013844 5ea61569aed14f67b67377dc6ca223e7ab013844

The example manages to generate the same key on both sides as expected.

How It Works

Looking at the example, you can see that other than the setup parameters of the key generator and the fact the KeyAgreement.getInstance() method is passed ECDH rather than DH , it is identical to the original example using Diffie-Hellman. Very different math, but at the level the JCE abstraction layer sits at, essentially the same to use.

So what about the differences? Have a look at how the parameters are constructed; it will tell you a bit more about how the method works and how the objects used in the previous example relate to the discussion at the beginning of this section.

ECField, ECFieldFp, and ECFieldF2m

The interface java.security.interfaces.ECField is the base interface for elliptic curve finite fields. Both java.security.spec.ECFieldFp and java.security.spec.ECFieldFm implement it. ECField has a single method, ECField.getFieldSize(), which returns the size of the finite field ”in the case of ECFieldFp, the bit length of the prime p , or in the case of ECFieldF2m, the bit length of m .

ECFieldFp serves as the holder for the prime number that distinguishes the field over which a curve constructed with it is operating. It has a single constructor, which takes a prime, and a single get method, ECFieldFp.getP(), which returns it.

ECFieldF2m, as its name implies, serves as the holder for the distinguishing information for the field over which any curve created with it is operating. In terms of construction, it has more variations than ECFieldFp, because it allows for F m 2 curves to be constructed over both a normal basis and a polynomial basis. Likewise, its get methods may return null depending on what kind of basis it was constructed for. If you want to fully understand this one, you really need to read up on elliptic curves first.

Having said that, from your point of view, the important thing to remember is that, like ECFieldFp , it just serves to distinguish the field.

Having established the field over which the curve will operate , the next step is to specify the curve.

The EllipticCurve Class

As its name suggests, java.security.spec.EllipticCurve is a holding class for the values that describe an elliptic curve. As expected, it has get() methods for retrieving the objects associated with its component parts . It is the construction of the object, however, that is of more interest.

To understand how an EllipticCurve is put together, you need to be aware that the typical equation that the kind of elliptic curve you are interested in follows, with minor variations:

y 2 = x 3 + ax 2 — b

with the values x and y restricted to a particular finite field and the values a and b being constants.

Take another look at the construction of the curve used in the previous example, using the base constructor for the EllipticCurve class.

EllipticCurve curve = new EllipticCurve( new ECFieldFp(new BigInteger( "fffffffffffffffffffffffffffffffeffffffffffffffff", 16)), new BigInteger("fffffffffffffffffffffffffffffffefffffffffffffffc", 16), new BigInteger("64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", 16));

Comparing it to the requirements of the equation, you can see the first argument is the field, in this case based on the prime number represented by the BigInteger passed in to the constructor of ECFieldFp. The second and third arguments are just the values of the constants a and b , as expected from the equation.

The second constructor for the elliptic curve object also takes a seeding value.

Now that you've specified a curve, the other piece of published information you need is a fixed point on the curve that you can then use to calculate the public keys.

The ECPoint Class

The java.security.spec.ECPoint class provides the containing object for the coordinates of a point on an elliptic curve, and consequently the space it operates in.

There is not much to say about this class. It is constructed from the (X, Y) coordinates of the point, both of which are BigInteger objects, and ECPoint.getAffineX() and ECPoint.getAffineY() return the X and Y coordinate values, respectively. The one thing to remember about it is that it does contain Java's idea of the infinite point, ECPoint.POINT_INFINITY, which returns null for both its get() methods.

The ECParameterSpec Class

The java.security.spec.ECParameterSpec class serves to bring everything together so you can use the elliptic curve for cryptography.

The class has a single constructor that takes the curve you want to use, a base point, the order of the base point, and what is referred to as a cofactor . You have already read about the curve parameter and what makes up the base point, or generator, as it is referred to in the ECParameterSpec class. The only two parameters you still need to look at are the order and the cofactor. It would help at this time to have another look at a definition of the class, so here is an extract of use from the previous example.

ECParameterSpec ecSpec = new ECParameterSpec( curve, new ECPoint( new BigInteger("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", 16), new BigInteger("f8e6d46a003725879cefee1294db32298c06885ee186b7ee", 16)), new BigInteger("ffffffffffffffffffffffff99def836146bc9b1b4d22831", 16), 1);

The order is the last BigInteger appearing in the constructor. It and the cofactor, which is 1 in this case, relate some properties that the base point has to the curve it is being used with. The order is a large prime, and when multiplied by the cofactor, it gives the number of points available on the curve. For efficiency reasons it is better to keep the cofactor as small as possible, so you will normally see curves with cofactors in the range of 1 to 4.

Used together, these values allow you to calculate your private value and the point on the curve that you can then publish to people you want to interact with, be it by key agreement or so they can verify digital signatures you have created.

The ECGenParameterSpec Class

As mentioned earlier, there are a large number of predefined, or named , curves with reference points already described. Typically, they appear in documents such as X9.62 and FIPS PUB-186-2. Depending on which curves your provider supports, you can take advantage of these named curves and point parameters by using the java.security.spec.ECGenParameterSpec.

As it happens, the curve used in the BasicECDHExample is called prime192v1 and is specified in X9.62. Consequently, if you wanted to, rather than specify the curve and parameter specification as

EllipticCurve curve = new EllipticCurve( new ECFieldFp(new BigInteger( "fffffffffffffffffffffffffffffffeffffffffffffffff", 16)), new BigInteger("fffffffffffffffffffffffffffffffefffffffffffffffc", 16), new BigInteger("64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", 16)); ECParameterSpec ecSpec = new ECParameterSpec( curve, new ECPoint( new BigInteger("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", 16), new BigInteger("f8e6d46a003725879cefee1294db32298c06885ee186b7ee", 16)), new BigInteger("ffffffffffffffffffffffff99def836146bc9b1b4d22831", 16), 1);

you could have just imported java.security.spec.ECGenParameterSpec and said this instead:

ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime192v1");

Try making the change; you will see it produces exactly the same result.

The named elliptic curve parameters supported by the Bouncy Castle provider are listed in Appendix B. If you are using a different provider, you should find a list of the curves supported in the documentation associated with it.

Elliptic Curve Cryptography Before JDK 1.5

Prior to JDK 1.5, there was no explicit support for elliptic curve cryptography in Java. If you are trying to use a version of Java that predates 1.5, the APIs used were always particular to the provider you were using. Appendix B has a description of how to do elliptic curve cryptography prior to JDK 1.5 using the Bouncy Castle API. These classes are similar to, but not quite the same as, those provided by the JCA today, and you will probably find this applies to most providers. Having said that, if you are planning to use a lot of elliptic curve cryptography in Java, these days it is worth moving to JDK 1.5 ”there is a lot to be said for having to write something only once.

Diffie Hellman for More Than Two Parties

An interesting feature of Diffie-Hellman key agreement is that the traditional implementation can be used to generate an agreed key between more than two parties. This is the reason that KeyAgreement.doPhase() is capable of returning a key.

Try It Out: Three-Party Diffie-Hellman

You can modify the previous BaseDHExample program to generate an agreed key between three parties by making a few simple changes. The first change involves adding a third KeyAgreement object to take part in the process and create a key for the object as follows:

KeyAgreement cKeyAgree = KeyAgreement.getInstance("DH", "BC"); KeyPair cPair = keyGen.generateKeyPair();

Next, you need to initialize the KeyAgreement object in the same fashion as the other KeyAgreement objects were:

cKeyAgree.init(cPair.getPrivate());

At this point the process you follow changes. Before the KeyAgreement objects are invoked with the lastPhase parameter set to true, you introduce an extra step where KeyAgreement.doPhase() is called with the lastPhase parameter set to false. This step gives you three intermediate keys that you'll use in the next phase (you will need to add an import for java.security.Key as well).

Key ac = aKeyAgree.doPhase(cPair.getPublic(), false); Key ba = bKeyAgree.doPhase(aPair.getPublic(), false); Key cb = cKeyAgree.doPhase(bPair.getPublic(), false);

Taking the intermediate keys, you replace the calls representing the last phase of the agreement with these three lines:

aKeyAgree.doPhase(cb, true); bKeyAgree.doPhase(ac, true); cKeyAgree.doPhase(ba, true);

At this point, all three KeyAgreement objects should now be in such a state that calls to KeyAgreement.generateSecret() will return the same value in all three cases. You can show this by adding the following line to the end of the modified example before you run it.

byte[] cShared = hash.digest(cKeyAgree.generateSecret()); System.out.println(Utils.toHex(cShared));

And, assuming you are still using the fixed random from the Utils class, you will get the following output:

dd602f60ae382db7b435dd71b0674f5ab64bbb7b dd602f60ae382db7b435dd71b0674f5ab64bbb7b dd602f60ae382db7b435dd71b0674f5ab64bbb7b

How It Works

As you can see, despite its age, Diffie-Hellman is still a useful algorithm. Imagine instead trying to use the RSA algorithm to do a three-way agreement. In the most na ve case, where each party would have to exchange keys with every other party, setting up a three-way conversation could take as many as six RSA key exchanges. Also, each party would be left with the added problem that it would have to keep track of which key to use depending on who it was sending a message to or receiving one from, or another round of negotiation would have to be added to allow the parties to then agree on a common key. In a case where a common key between multiple parties is useful, key authentication issues not withstanding, Diffie-Hellman key agreement is still the simplest approach.

The El Gamal Algorithm

El Gamal is a variant on Diffie-Hellman and derives its security from the same ideas. Although in some ways it is not as "neat" as the RSA algorithm, El Gamal is still very widely used ”it is still the algorithm of choice for most keys used for encryption in Open PGP (RFC 2440).

In El Gamal, to send a message to another party whose public key is G y mod P , you create a temporary public key, G x mod P , encrypt the message by multiplying it by G xy mod P , the multiplication also being modulo P , and send the temporary public key and the enciphered message as a single block. Although it works, as you will see, it does have the effect of making the ciphertext twice the size of the key.

Try It Out: El Gamal Encryption

Following is an example of random key generation and encryption using El Gamal. You will find it runs a lot slower than the equivalent RSA example. You will read about the reasons for this a bit later, but if you run it first, you will get a much better idea of what is meant by "a lot slower."

package chapter4; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import javax.crypto.Cipher; /** * El Gamal example with random key generation. */ public class RandomKeyElGamalExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance( "ElGamal/None/NoPadding", "BC"); KeyPairGenerator generator = KeyPairGenerator.getInstance("ElGamal", "BC"); SecureRandom random = Utils.createFixedRandom(); // create the keys generator.initialize(256, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

Running the program produces the following:

input : beef cipher: 8c2e699772c14496bc82400d11decae4f662fe90864e8c553b78136679fcdfaa60c378b5 69083525c021fcf77e40f661525da56ed4133df92848aaba2459dff5 plain : beef

How It Works

Overall, there is not much to say here about the use of the algorithm itself. As far as using the public key for encryption, El Gamal is pretty much like RSA; because it is based on math, you will have trouble with leading zeros if you do not use padding. The big difference you will notice when comparing the output to that of the RSA example is that the block of ciphertext produced is twice the size of the key ”unlike RSA, where it is the same size as the key. Whether this is important to you really depends on the constraints of your application, but the larger cipher block size is one of the reasons El Gamal is not favored.

The biggest problem, at least in this case, is the speed of the key generation. As you saw previously, the generation of an El Gamal key pair requires Diffie-Hellman parameters, and calculating these values from scratch is very expensive. Internally, when initialized only with a key size, the KeyPairGenerator has to first generate the P and G values before it can generate the key pair. You will find, at least in the case of the Bouncy Castle provider, that this is a one-off cost ”generating successive key pairs is much quicker because the P and G values calculated for the first key pair can be reused. Not surprisingly, you will also find that the Diffie-Hellman key pair generator exhibits the same behavior.

Can you pre-generate a DHParameterSpec so that you can pass in parameters like you did with Diffie-Hellman? As it turns out, you can; you just need to use an AlgorithmParametersGenerator object to create them.

The AlgorithmParameterGenerator Class

Like other classes in the JCA, java.security.AlgorithmParameterGenerator is created using the getInstance() factory pattern, and further, in keeping with classes like MessageDigest, it follows the same rules with regard to the precedence rules used if the Java runtime encounters more than one implementation for a given algorithm. The methods on AlgorithmParameterGenerator that are of most of interest to you are the init() methods, of which there are four, and the generateParameters() method, which is used to retrieve the generated AlgorithmParameters object.

AlgorithmParameter Generator.init()

The init() method comes in two flavors: two that just take a size value with an optional source of randomness and two that take AlgortihmParameterSpec objects for situations where it may be necessary to pass parameters other than the size to the generator. It depends on what you are generating as to what suits best. For something like Diffie-Hellman/ElGamal, the size attribute is enough to generate the prime P and the generator G that will provide the basic parameters. Then again, you want to create a parameters object for Diffie-Hellman that takes advantage of the ability to limit the size of the private value ”in this case just the size will not be enough, and you will need an AlgorithmParameterSpec object to pass the necessary information in.

Take a look at examples of both over the next two sections.

AlgorithmParameter Generator.generate Parameters()

This returns the AlgorithmParameters that you want to generate. I already covered the AlgorithmParameters object in Chapter 2, so there's no need to go into too much detail here, other than to mention, as you have probably guessed, AlgorithmParameters is used everywhere.

Enough background though. You can now try using the class.

Try It Out: El Gamal Using AlgorithmParameterGenerator

Have a look at the following example and compare it with the RandomKeyElGamalExample . Try running the example and then read on.

package chapter4; import java.security.AlgorithmParameterGenerator; import java.security.AlgorithmParameters; import java.security.Key; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import java.security.spec.AlgorithmParameterSpec; import javax.crypto.Cipher; import javax.crypto.spec.DHParameterSpec; /** * El Gamal example with random key generation. */ public class AlgorithmParameterExample { public static void main(String[] args) throws Exception { byte[] input = new byte[] { (byte)0xbe, (byte)0xef }; Cipher cipher = Cipher.getInstance( "ElGamal/None/NoPadding", "BC"); SecureRandom random = Utils.createFixedRandom(); // create the parameters AlgorithmParameterGenerator apg = AlgorithmParameterGenerator.getInstance( "ElGamal", "BC"); apg.init(256, random); AlgorithmParameters params = apg.generateParameters(); AlgorithmParameterSpec dhSpec = params.getParameterSpec( DHParameterSpec.class); // create the keys KeyPairGenerator generator = KeyPairGenerator.getInstance("ElGamal", "BC"); generator.initialize(dhSpec, random); KeyPair pair = generator.generateKeyPair(); Key pubKey = pair.getPublic(); Key privKey = pair.getPrivate(); System.out.println("input : " + Utils.toHex(input)); // encryption step cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); byte[] cipherText = cipher.doFinal(input); System.out.println("cipher: " + Utils.toHex(cipherText)); // decryption step cipher.init(Cipher.DECRYPT_MODE, privKey); byte[] plainText = cipher.doFinal(cipherText); System.out.println("plain : " + Utils.toHex(plainText)); } }

Because of the fixed seed used in the "random" number generator, you should see that this prints the same results as the original RandomKeyElGamalExample. The reason is that the process that takes place internally to the provider, at least in Bouncy Castle's case, is exactly the same as the process you have made explicit in the code.

How It Works

In the new example, you are generating the parameters for the P and G values and then passing them to the key pair generator class explicitly, rather than letting it create them based on the key size. This relieves the key pair generator of the need to generate its own set of parameters.

Although it is probably hard to tell the difference in speed just from running the examples, if you add some timing code around the key pair generation in RandomKeyElGamalExample and AlgorithmParameterExample, you will see that the time spent in KeyPairGenerator.generateKeyPair() is substantially less in the later case.

You read in earlier discussion that the AlgorithmParameterGenerator class can also take an AlgorithmParameterSpec object on its init() methods. As it happens, there is an AlgorithmParameterSpec class that is applicable to parameter generation for Diffie-Hellman type parameters ”the DHGenParameterSpec class.

The DHGenParameterSpec Class

As you read earlier, an optimization to Diffie-Hellman is to limit the size of the private value associated with a public key. As you also learned, you can construct a DHParameterSpec that will limit the size of the private values it generates when used with a suitable KeyPairGenerator object. It would be useful to be able to incorporate this information into our generated parameters as well, so the JCE provides a class that allows us to configure an AlgorithmParameterGenerator object created for Diffie-Hellman algorithms ” javax.crypto.spec.DHGenParameterSpec. So rather than simply specifying a size for the prime P , as you do on the line:

apg.init(256, random);

if you wanted to limit the private value to, say, 200 bits, you could have instead said

apg.init(new DHGenParameterSpec(256, 200), random);

where the arguments to the constructor of DHGenParameterSpec are the size of the prime P in bits and the maximum size in bits of the private value Y . This would then produce DHParameterSpec objects with the DHParameterSpec.getL() method returning 200 thus limiting the private values to 200 bits.

Digital Signatures

The utility of digital signatures relies on the fact that a digital signature is created using some secret known only to the creator of signature, and the digital signature can be verified using public information published by the signature creator. In addition to being authentic , digital signatures are non-reputable. If a signature is put forward by a particular creator, then for the creator to deny making it, the secret would have to have been compromised, or the creator is not telling the truth.

The other thing about digital signature algorithms is they are all based on the use of cryptographic hashes, or message digests. This is due to the limitations in size that asymmetric algorithms impose on the messages they can process. This leads to an important point: It is the size of input restrictions on the message digest used in the signature that determines the amount of data it is safe to sign with a given algorithm. The key size serves only to protect the digest. If the data you are signing is larger than the maximum allowable for a particular digest algorithm, increasing the key size will not help.

There are two processes that are associated with digital signatures: signature construction and signature verification. As you will see, these are not quite the same as the two processes associated with ciphers, encryption, and decryption. A user only has to be able to verify a signature; there is no requirement that users can read its contents, and in Java the two processes required for the creation and manipulation of digital signatures are encapsulated in the class Signature .

The Signature Class

Objects that provide the underlying functionality offered by java.security.Signature are created using the getInstance() factory pattern like other classes of a similar kind in the JCA. Accordingly, Signature.getInstance() will obey whatever precedence rules that have been configured in your Java runtime if you fail to specify a provider. Unlike the Cipher class, the Signature class does not have static integers to represent its various modes, but instead goes into a particular mode depending on which one of two methods are called. The methods are Signature.initSign() and Signature.initVerify(), and they put the Signature object into a state for signature creation or signature verification, respectively.

Using the Signature Class in Signature Creation Mode

There are two variations of the method Signature.initSign() that can be called to put a Signature object in signature creation mode. Both take a private key, which is the most important bit, and one initSign() method also gives you the option of passing in a source of randomness.

After the Signature object is initialized for signing, the use of it is then very similar to what you saw with the MessageDigest class. There is a set of Signature.update() methods that are then used to feed data into the Signature object, and when all the data has been fed in, Signature.sign() is called. Depending on which version is called, it will either return the digital signature as a byte array or load it into a passed in byte array.

Using the Signature Class in Signature Verification Mode

There are also two variations of the method Signature.initVerify(). Unlike with the initSign() method, the second variation, which takes a Certificate as its argument, is simply a convenience version of the first initVerify() method, which takes a public key.

Feeding data into the Signature object as part of the verification process is identical to that of the signature creation process; you just use the update() methods. The actual verification step itself, however, is slightly different. Once all the data used in the original signature generation is fed into the Signature class using the update() methods, the boolean method Signature.verify() is called with the byte array representing the signature being checked passed in as an argument. If the verify() method returns true, the signature is okay; if it returns false, the data and the signature do not match.

Signature.setParameter() and Signature.getParameters()

In the same way as Cipher, or KeyPairGenerator, objects can use AlgorithmParameterSpec objects to provide extra information or return an AlgorithmParameters object that tells you what extra information would be required if you needed to repeat the operation being performed by the Cipher, or KeyPairGenerator, object, so too can Signature objects. As you would expect, Signature.getParameters() returns the AlgorithmParameterSpec object associated with the current operation. However, there is a difference with the passing in of the AlgorithmParameterSpec object. In the case of the Signature class, rather than passing the AlgorithmParameterSpec as part of the object's initialization, you use Signature.setParameter(). The setParameter() method will throw an InvalidAlgorithmParameterException if the passed in parameters are inappropriate for the signature implementation.

You will see an example of dealing with parameters when you deal with the RSA PSS digital signature type a bit later. First, have a look at an algorithm that was purpose-built only for the job of signature creation and verification.

The Digital Signature Algorithm

The Digital Signature Algorithm (DSA) was originally proposed by the U.S. National Institute of Standards and Technology (NIST) in August 1991. DSA then became the first digital signature scheme to be recognized by a government with the publication FIPS PUB 186, which described the Digital Signature Standard (DSS). You will occasionally see the algorithm referred to under both titles, although they are not quite the same, as DSS specifically requires the use of the SHA-1 message digest.

The interesting thing about DSA is that it cannot be used for encryption. If you look at Figure 4-4, you will see that the algorithm is designed only to allow verification of a signature via a calculation using the public key that does not expose the data used to create the signature in the first place.

Figure 4-4

Regular DSA

Traditional DSA, like Diffie-Hellman, derives its security from the discrete logarithm problem. To use it, you need the following:

• q A prime number Q , such that 2 159 < Q < 2 160
• q A prime P with the property that Q divides ( P ˆ’ 1)
• q A generator G for a unique cyclic group of order Q in the field of P

I will not go into the math required to calculate the generator here. The important point is that having acquired values for P, Q , and G , you can then create a public key by choosing a private value X , where 1 ‰ X ‰ Q , and compute a public value Y , which is G X mod P . The public key then becomes the values Y, P, Q , and G . The private key is represented by the value X, P, Q , and G .

Having created public and private keys, you then need to be able to create signatures and verify them. Unlike with the RSA algorithm where public and private key operations can be done using the same method, DSA uses one set of calculations for creating a signature and a different set for verifying one.

Given a hash function H() ”SHA-1, if you are following the DSS ”creating a signature in DSA for a message M goes through the following steps:

1. Choose a random secret integer K , such that 0 < K < Q .
2. Calculate R = ( G K mod P ) mod Q .
3. Calculate S = (( K ˆ’ 1 mod Q )(H( M ) + XR )) mod Q.

The signature is then represented by the numbers R and S.

In the case of verification of a signature, you start with the public key of the signer, the values R and S, and perform the following steps:

1. Verify 0 < R < Q , and 0 < S < Q , rejecting the signature otherwise .
2. Calculate A = S ˆ’ 1 mod Q, B = ( A H( M )) mod Q , and C = ( RA ) mod Q .
3. Compute V = ( G B Y C mod P ) mod Q .

If V is equal to R , accept the signature; reject the signature otherwise.

I am not going to dwell further on the math here, as you can find more in depth discussions in books referred to in Appendix D, such as in Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone. What is really more relevant to you is how much of this do you have to worry about if you are using Java and the Signature class?

Try It Out: DSA

Here is an example of doing DSA and your first use of the Signature class as well. As you can see, not withstanding the need to at least know the algorithm name , the Signature class hides all the underlying calculations and reduces the use of DSA to just dealing with the results of the creation and verification process.

package chapter4; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import java.security.Signature; public class BasicDSAExample { public static void main(String[] args) throws Exception { KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DSA", "BC"); keyGen.initialize(512, new SecureRandom()); KeyPair keyPair = keyGen.generateKeyPair(); Signature signature = Signature.getInstance("DSA", "BC"); // generate a signature signature.initSign(keyPair.getPrivate(), Utils.createFixedRandom()); byte[] message = new byte[] { (byte)'a', (byte)'b', (byte)'c' }; signature.update(message); byte[] sigBytes = signature.sign(); // verify a signature signature.initVerify(keyPair.getPublic()); signature.update(message); if (signature.verify(sigBytes)) { System.out.println("signature verification succeeded."); } else { System.out.println("signature verification failed."); } } }

Run the example and you should see the output:

signature verification succeeded.

How It Works

As with any asymmetric algorithm, you start by creating a key pair for the algorithm you want to use. After that, you initialize the signature object to use your private key in the following line:

signature.initSign(keyPair.getPrivate(), Utils.createFixedRandom());

If you remember back to the description of the DSA algorithm, a random number is required to generate a signature, so you are using the initSign() method that takes a random number source as well as a private key. If you had not included the random number source, a default one would have been created for you by the provider.

The next step is to feed the data you want to sign into the signature object, which you do by calling the update() method. After using update(), you then calculate the signature retrieving a byte array representation of it using the sign() method.

The last half of the example just verifies the signature you created in the first half. You use the initVerify() method, passing in the public key of the signer; do another call to the update() method to feed the data you believe the signature is based on into the signature object; and then call the verify() method, passing it the byte array representation of the signature. If the signature is valid for the data, as it should be in the case of the example, verify() returns true. In the event that the signature was not valid for the data, verify() would have returned false .

If you look at the use of KeyPairGenerator, there is no sign of the parameters that were discussed earlier because they were passed before key creation was done. This is because you are playing the same game as you were originally with El Gamal ”the KeyPairGenerator instance you are using is creating the parameters for you. As with Diffie-Hellman and El Gamal, it is possible for you to calculate parameters beforehand and use them. To carry these parameters around, the JCA provides the DSAParameterSpec class.

The DSAParameterSpec Class

The java.security.spec.DSAParameterSpec object serves as the holding class for the DSA parameters discussed previously. It has a single constructor that takes the P, Q , and G values used in the key generation process and three get() methods that allow the values to be retrieved.

As with objects of the type DHParameterSpec, DSAParameterSpec objects can also be generated using the AlgorithmParameterGenerator class. So if you wanted to create a DSAParameterSpec object for 512-bit keys like the ones you are using previously, the following code could be used to create the parameter object:

AlgorithmParameterGenerator apg = AlgorithmParameterGenerator.getInstance( "DSA", "BC"); apg.init(512, new SecureRandom()); AlgorithmParameters params = apg.generateParameters(); AlgorithmParameterSpec dsaSpec = params.getParameterSpec( DSAParameterSpec.class);

Having created the parameter object, you could then use it for generation of your key pairs by passing it to an instance of the KeyPairGenerator class when you call KeyPairGenerator.initialize() .

Of course, rather than generating keys randomly , you might want to produce them using a KeyFactory class. To make this possible, the JCA also provides specification classes for carrying key material for DSA keys.

Specification Objects for DSA Keys

The JCA also provides objects for carrying key and parameter material for DSA keys, and they can be used to create simple value objects that can then be used to pass around key material for DSA keys. The two classes used for this purpose are java.security.spec.DSAPrivateKeySpec and java.security.spec.DSAPublicKeySpec.

DSAPrivateKeySpec has a single constructor that just takes the private value X and the parameters used to create the public value from it P, Q , and G ”the values in the DSAParameterSpec object. An example of use might look as follows :

DSAPrivateKeySpec dsaPrivateSpec = new DSAPrivateKeySpec(x, p, q, g);

DSAPublicKeySpec also has a single constructor that takes the public value Y and the parameters that were used to create it, P, Q , and G , leading to usage like:

DSAPublicKeySpec dsaPublicSpec = new DSAPublicKeySpec(y, p, q, g);

As usual with the other key specification value objects, the only methods on DSAPrivateKeySpec and DSAPublicKeySpec are get() methods for retrieving the various values used to construct them.

Interfaces for DSA Keys

In the BasicDSAExample program, you just used the KeyPair class directly after generating the keys. If you need greater type safety, the JCA does provide java.security.interfaces.DSAPrivateKey, java.security.interfaces.DSAPublicKey, and a parent class for both of them that extends Key , namely, java.security.interfaces.DSAKey, which you can use to distinguish DSA keys from other asymmetric keys you are using.

DSAKey provides a single method, DSAKey.getParams(), which returns the DSAParameterSpec associated with the public and private keys.

DSAPrivateKey also has a single method on it, DSAPrivateKey.getX(), which returns the private value that is not transmitted as part of the agreement process.

DSAPublicKey also has a single method on it, DSAPublicKey.getY(). The value returned by getY() is G X mod P, where X is the value return by the corresponding private keys getX() method and G and P are the values of the associated DSAParameterSpec object.

Elliptic Curve DSA

There is also an algorithm for doing DSA signing using elliptic curve cryptography rather than the algorithm described in the DSS. The algorithm is referred to as ECDSA, and in the same manner as Diffie-Hellman using elliptic curve is similar to the original Diffie-Hellman using primes, DSA with elliptic curve also involves creating a signature that consists of the two numbers, R and S . Likewise, the signature is verified by calculating a number V from the signature and the signer's public key and confirming that it is equal to R .

Other than that, ECDSA is described in detail in X9.62 and requires some knowledge of the fundamentals of elliptic curve cryptography, so I will not go into the methodology further here. As you will see, the differences in the underlying math that make ECDSA work are completely hidden when you are using it in Java.

Try It Out: DSA with Elliptic Curve

Have a look at the following example and compare it with the BasicDSAExample class you looked at earlier. You create a different KeyPairGenerator object as you would expect, but after that the only difference is the ECDSA parameter passed to Signature.getInstance(). The mechanics of both signing and verifying are identical to before.

package chapter4; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import java.security.Signature; import java.security.spec.ECGenParameterSpec; /** * Simple example showing signature creation and verification using ECDSA */ public class BasicECDSAExample { public static void main( String[] args) throws Exception { KeyPairGenerator keyGen = KeyPairGenerator.getInstance("ECDSA", "BC"); ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime192v1"); keyGen.initialize(ecSpec, new SecureRandom()); KeyPair keyPair = keyGen.generateKeyPair(); Signature signature = Signature.getInstance("ECDSA", "BC"); // generate a signature signature.initSign(keyPair.getPrivate(), Utils.createFixedRandom()); byte[] message = new byte[] { (byte)'a', (byte)'b', (byte)'c' }; signature.update(message); byte[] sigBytes = signature.sign(); // verify a signature signature.initVerify(keyPair.getPublic()); signature.update(message); if (signature.verify(sigBytes)) { System.out.println("signature verification succeeded."); } else { System.out.println("signature verification failed."); } } }

Run the example and you should get the message signature verification succeeded.

How It Works

As I mentioned earlier, the magic is in the abstraction layer provided by the JCA. With relatively minor changes, it is possible to change code to use a completely different implementation.

One thing worth noting in this example is that it is using the ECGenParameterSpec that you discussed earlier, so you could move to a completely different curve and key size by just changing the string passed to ECGenParameterSpec's constructor. For example, if you wanted to move from 192 to a 239 bit key size, you could change

ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime192v1");

to

ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime239v1");

RSA Based Signature Algorithms

Signatures are created using the RSA algorithm by applying the RSA algorithm using the private key and then distributing the result as the signature. Because of the way the RSA algorithm works, this means the signature can be decrypted using the public key, giving you the process you see in Figure 4-5. The reason it works so well is that if a signature decrypts successfully with a given public key, then it must have been created with the corresponding private key.

Figure 4-5

As with padding modes, the most popular methods for using RSA with signatures are outlined in PKCS #1. After the same fashion as padding modes, there are two types, an earlier one based on PKCS #1 version 1.5 and a more recent one that appeared in PKCS1 version 2.

PKCS #1 1.5 Signatures

PKCS #1 version 1.5 signatures use type 1 PKCS1 padding. To rehash the discussion before, type 1 PKCS #1 padding is when, given a message M , the padded message M p is

M p = 0x00 0x01 F 0x00 M

where F is a string of octets of the value 0xFF and – is the concatenation operator. F must be at least 8 octets long, so M can be no longer than the length of the key in octets less 11.

Try It Out: RSA Signature Generation

Try running the following example; you will see that once again the changes are quite minor.

package chapter4; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.SecureRandom; import java.security.Signature; public class PKCS1SignatureExample { public static void main(String[] args) throws Exception { KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA", "BC"); keyGen.initialize(512, new SecureRandom()); KeyPair keyPair = keyGen.generateKeyPair(); Signature signature = Signature.getInstance("SHA1withRSA", "BC"); // generate a signature signature.initSign(keyPair.getPrivate(), Utils.createFixedRandom()); byte[] message = new byte[] { (byte)'a', (byte)'b', (byte)'c' }; signature.update(message); byte[] sigBytes = signature.sign(); // verify a signature signature.initVerify(keyPair.getPublic()); signature.update(message); if (signature.verify(sigBytes)) { System.out.println("signature verification succeeded."); } else { System.out.println("signature verification failed."); } } }

Once again you should see the message signature verification succeeded .

How It Works

Once again you see that if you change the call to Signature.getInstance() and provide the appropriate key pair, everything else just falls into place.

One thing you can see in this example that you have not seen before with the Signature class is that the name of signature algorithm appears to have an underlying structure to it. As it turns out, it does, and the structure is described in the standard naming conventions outlined in the JCA documentation as well. The format is " Digest with Encryption ", so if you were going to use SHA-224, the name string would be SHA224withRSA , SHA-256 would be SHA256withRSA , and so on.

PSS Signatures

RSASSA-PSS, or PSS for short, is similar in function to OAEP, and is outlined in PKCS #1 version 2. Like a traditional signature method, it involves using a hash function H() to create calculate a digest of the message to be signed. Creating the signature involves creating a padded data block containing the digest and masking it with mask function Mask, based on the hash function H() and a random salt S . The padded data block is then encrypted using the private key of the signer.

To create a signature Ms for a message M and the key K you perform the following steps:

1. M 1 = 0x00 – 0x00 – 0x00 – 0x00 – 0x00 – 0x00 – 0x00 – 0x00 – H( M ) – S
2. M 2 = P – 0x01 – S
3. M 3 = Mask( M 2 , H( M 1 )) – H( M 1 ) – 0xBC
4. M S = RSAEncrypt( K, M 3 )

P in this case is pad string of octets of the value 0x00. The length of P given by:

kLen ˆ’ sLen ˆ’ hLen ˆ’ 2

where kLen is usually the block size in octets, sLen is the length of S in octets, and hLen is the length of the hash in octets.

Verification of a PSS signature is simply a matter of decrypting the signature using the public key, extracting the salt, and then reconstructing H( M 1 ) from the data that was signed. If the reconstructed value is the same as that found in the decrypted block, the signature is valid for the data. Otherwise, it should be rejected.

Note that unlike the older method the presence of the random salt means that two signatures generated from the same input data and the same private key will not have produced the same byte arrays. To allow for this possibility, it is possible to have a salt of zero length, meaning the calculation will always produce the same result for the same data and the same private key.

As you can see, PSS is very different from the older PKCS #1 signature encoding; however, since PSS is also based on RSA, you can create an example of using PSS by changing only a single line in the code for PKCS1SignatureExample.

Try replacing the line:

Signature signature = Signature.getInstance("SHA1withRSA", "BC");

with the line:

Signature signature = Signature.getInstance("SHA1withRSAandMGF1", "BC");

and you are now using PSS.

Like the previous PKCS #1 mechanism, you can see that the PSS signature algorithm name also has a specific structure. The structure reflects the fact that PSS is related to OAEP and goes " Digest withRSAand MaskFunction ". Although MGF1 is currently the only mask function available, a variety of digests such as SHA-256, SHA-384, and SHA-512 can be used in place of SHA-1. If you try one of the other digests remember the hyphen (-) is left out of the digest name ”for instance, SHA-256 becomes SHA256.

Like OAEP, PSS signatures can also have parameters; you will look at the parameter class now.

The PSS Parameter Spec Class

The java.security.spec.PSSParameterSpec class first appeared in JDK 1.4, where it could be used to change the size of the salt associated with the signature. More recently, in JDK 1.5, it now allows setting all the available parameters for the PSS signature mechanism. This gives you two ways of constructing a PSSParameterSpec depending on what you want to set. As the older constructor is really a subset of the newer constructor, you will have a look at the newer constructor first.

The PSSParameterSpec class provides a default value, which is PSSParameterSpec.DEFAULT. Coded the long way it looks like this:

PSSParameterSpec defaultSpec = new PSSParameterSpec( "SHA-1", "MGF1", MGF1ParameterSpec.SHA1, 20, 1);

Used with the signature object in the example that was modified to use PSS, you would pass it in as follows:

signature.setParameter(defaultSpec);

Comparing the constructor for the PSSParameterSpec to the OAEPParameterSpec you saw earlier, the similarities between the two are obvious. The first parameter is the message digest to be used, the second parameter is the mask generation function to be used, and the third is the algorithm parameter specification for the mask generation function. The only different ones are the fourth and the fifth.

The fourth parameter is the value that can be passed to the older single parameter constructor; it gives the size of the salt that is to be used in the signature generation.

The fifth parameter is what is referred as the trailer field . This tells the signature generator what trailer byte to put at the end of the signature. At the moment only one value for the trailer field has been specified, the value 1, which maps to a trailer byte in the signature of 0xBC. You will have a closer look at how this mapping is done in the next chapter, but for the moment you will have to take my word for it.

Finally, the PSSParameterSpec class, as its name implies, is a simple value object, so the only methods on it are get() methods for retrieving the values an instance of PSSParameterSpec was constructed with.

Summary

This brings you to the end of looking at the basics of asymmetric cryptography. You have now covered the fundamentals for asymmetric encryption, symmetric key exchange, key agreement, and the creation of digital signatures, as well as the algorithm parameters that they might require. You have also looked at the encryption algorithms RSA and El Gamal, the key agreement algorithms Diffie-Hellman and elliptic curve Diffie-Hellman, as well as digital signature algorithms based on RSA, DSA, and elliptic curve DSA.

Over the course of this chapter, you learned how to

• Create asymmetric keys from key specification objects using the KeyFactory class.
• Create random asymmetric keys using the KeyPairGenerator class.
• Do asymmetric encryption with the Cipher class.
• Do key agreement using the KeyAgreement class.
• Create digital signatures with the Signature class.
• Use AlgorithmParameters objects with Cipher and Signature classes.
• Use the AlgorithmParameterGenerator class to create AlgorithmParameters objects.

Finally, you also saw how to use an asymmetric key to encrypt, or wrap, a symmetric key and how to wrap asymmetric keys using secret key objects.

I mentioned earlier that encoded asymmetric keys include a large amount of structural information inaddition to the key material. The same also applies to algorithm parameters and the contents of some signatures. This structural information is built upon a language that is also the foundation for X.509 certificates and many protocols surrounding cryptography and certificate management. So before you can go much farther, it would be good to have a basic understanding of how this language for describing structures works. This is what you will look at next .

Exercises

Answers