16.4 Extending the .NET Framework

In Chapter 15, we extended the .NET Framework by creating an implementation of the ElGamal algorithm that supported encryption. In this section, we extend our implementation to include support for creating and verifying digital signatures.

We have provided a C# implementation of the ElGamal algorithm only. Like almost all encryption algorithms, ElGamal relies on mathematical operations that are not possible in Visual Basic .NET without creating additional support functions to compensate for the limited numeric support the language provides.

16.4.1 The ElGamal Signature Functions Explained

The ElGamal algorithm supports encryption and digital signatures using the same key pair. Keys created by following the key generation protocol (discussed in Chapter 15) can be used to create and verify digital signatures using the functions that we explain in this section. As a reminder, the parameters p, g, and y form the public key, and the parameter x is the private key.

The basic protocol for creating an ElGamal signature is:

To verify an ElGamal signature, we follow the following protocol:

Notice that, unlike RSA, the ElGamal algorithm specifies different functions for data encryption and digital signatures.

16.4.2 Defining the Signature Function Class

Begin by defining the ElGamalSignature class, which implements the basic signature and verification functions that we described in the preceding section:

using System;
using System.Security.Cryptography;

public class ElGamalSignature {

Define the mod method to ensure that you always receive a positive result when using the modular arithmetic support included in the BigInteger class:

    public static BigInteger mod(BigInteger p_base, BigInteger p_val) {
        BigInteger x_result = p_base % p_val;
        if (x_result < 0) {
            x_result += p_val;
        }
        return x_result;
    }

The CreateSignature class implements the ElGamal signature function and creates a digital signature; the arguments to this method are the data to sign and the key to use:

    public static byte[] CreateSignature(byte[] p_data,
    ElGamalKeyStruct p_key_struct) {

Begin by generating a random number, k, that is relatively prime to p - 1. Refer to Table 15-6 for a summary of the methods we use in the BigInteger class:

        // define P -1
        BigInteger x_pminusone = p_key_struct.P - 1;
        // create K, which is the random number        
        BigInteger K;          
        do {
            K = new BigInteger(  );
            K.genRandomBits(p_key_struct.P.bitCount(  ) -1, new Random(  ));
        } while (K.gcd(x_pminusone) != 1);

The following statements compute the values of the signature elements, a and b. Although these statements may appear convoluted, they do compute the values that you require; their appearance is a result of the requirements of the BigInteger class and the fact that we have defined the mod method in this class:

        // compute the values A and B
        BigInteger A = p_key_struct.G.modPow(K, p_key_struct.P);
        BigInteger B = mod(mod(K.modInverse(x_pminusone) 
            * (new BigInteger(p_data) 
            -(p_key_struct.X*(A))),(x_pminusone)),(x_pminusone));

Having completed the computations, now create a byte array to hold the signature data and fill it with the signature elements that you created previously to create the complete signature:

        // copy the bytes from A and B into the result array
        byte[] x_a_bytes = A.getBytes(  );
        byte[] x_b_bytes = B.getBytes(  );
        // define the result size
        int x_result_size = (((p_key_struct.P.bitCount(  ) + 7) / 8) * 2);
        // create an array to contain the ciphertext
        byte[] x_result = new byte[x_result_size];
        // populate the arrays
        Array.Copy(x_a_bytes, 0, x_result, x_result_size / 2 
            - x_a_bytes.Length, x_a_bytes.Length);        
        Array.Copy(x_b_bytes, 0, x_result, x_result_size 
            - x_b_bytes.Length, x_b_bytes.Length);

        // return the result array
        return x_result;
    }

The VerifySignature method implements the ElGamal verification function, accepting arguments that represent the data that was signed, the signature to verify, and the key with which to perform the verification:

    public static bool VerifySignature(byte[] p_data, byte[] p_sig,
        ElGamalKeyStruct p_key_struct) {

We begin by splitting the signature into two sections and creating instances of the BigInteger class to represent the signature elements a and b:

        // define the result size
        int x_result_size = p_sig.Length/2;

        // extract the byte arrays that represent A and B
        byte[] x_a_bytes = new byte[x_result_size];
        Array.Copy(p_sig, 0, x_a_bytes, 0, x_a_bytes.Length);
        byte[] x_b_bytes = new Byte[x_result_size];
        Array.Copy(p_sig, x_result_size, x_b_bytes, 0, x_b_bytes.Length);

        // create big integers from the byte arrays
        BigInteger A = new BigInteger(x_a_bytes);
        BigInteger B = new BigInteger(x_b_bytes);

The remaining statements compute the two verification elements, and the method returns 2 if the elements have the same value (the signature is valid) and false otherwise (the signature is not valid):

        // create the two results
        BigInteger x_result1 =  mod(p_key_struct.Y.modPow(A, p_key_struct.P) 
            * A.modPow(B, p_key_struct.P), p_key_struct.P);

        BigInteger x_result2 =  p_key_struct.G.modPow(new BigInteger(p_data), 
            p_key_struct.P);

        // return true if the two results are the same

        return x_result1 == x_result2;
    }
}

16.4.3 Implementing the Managed Class Methods

We now define the implementations for the signature function methods in the managed algorithm class, which we left unfinished in Chapter 15. The Sign and VerifySignature methods call the static CreateSignature and VerifySignature methods in the ElGamalSignature class, which we defined in the preceding section. Both methods check to see if the user has specified a key and will create a new pair as required:

public class ElGamalManaged : ElGamal {

        // ... other methods

    public override byte[] Sign(byte[] p_hashcode) {
        if (NeedToGenerateKey(  )) {
            // we need to create a new key before we can export 
            CreateKeyPair(KeySizeValue);
        }
        return ElGamalSignature.CreateSignature(p_hashcode, o_key_struct);
    }

    public override bool VerifySignature(byte[] p_hashcode, byte[] p_signature) {
        if (NeedToGenerateKey(  )) {
            // we need to create a new key before we can export 
            CreateKeyPair(KeySizeValue);
        }
        return ElGamalSignature.VerifySignature(p_hashcode, 
          p_signature, o_key_struct);
    }

        // ... other methods
}

This implementation means that the Sign and VerifySignature methods depend directly on the "raw" signature functions, which are created without PKCS #1 formatting. We define separate formatting classes in the following sections.

16.4.4 Defining the PKCS #1 Helper Class

We have defined the ElGamalSignatureFormatHelper class to simplify our formatter and deformatter implementations. This class is responsible for formatting blocks of data in accordance with the PKCS #1 formatting technique:

using System;
using System.Security.Cryptography;

public class ElGamalSignatureFormatHelper {

We begin by defining the set of algorithm IDs that we listed in Table 16-1. These IDs are included in the PKCS #1-formatted data; see Section 16.2 for details of PKCS #1. We have defined the algorithm IDs as byte arrays to simplify the formatting process:

    private static byte[] MD5_BYTES
        = new byte[] {0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86,
                         0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x05, 0x00,
                         0x04, 0x10};

    private static byte[] SHA1_BYTES
        = new byte[] {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0E, 0x03, 
                         0x02, 0x1A, 0x05, 0x00, 0x04, 0x14};

    private static byte[] SHA256_BYTES
        = new byte[] {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                         0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05,
                         0x00, 0x04, 0x20};

    private static byte[] SHA384_BYTES
        = new byte[] {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                         0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05,
                         0x00, 0x04, 0x30};

    private static byte[] SHA512_BYTES
        = new byte[] {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                         0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05,
                         0x00, 0x04, 0x40};

The GetHashAlgorithmID returns a byte array representing the ID for a hashing algorithm, which is specified as the method argument:

    private static byte[] GetHashAlgorithmID(HashAlgorithm p_hash) {
        if (p_hash is MD5) {
            return MD5_BYTES;
        } else if (p_hash is SHA1) {
            return SHA1_BYTES;
        } else if (p_hash is SHA256) {
            return SHA256_BYTES;
        } else if (p_hash is SHA384) {
            return SHA384_BYTES;
        } else if (p_hash is SHA512) {
            return SHA512_BYTES;
        } else {
            throw new ArgumentException("Unknown hashing algorithm", "p_hash");
        }
    }

CreateEMSA_PKCS1_v1_5_ENCODE formats a block of data in accordance with the PKCS #1 technique that we described in Section 16.2 of this chapter:

    public static byte[] CreateEMSA_PKCS1_v1_5_ENCODE(byte[] p_hashcode,
        HashAlgorithm p_hash_alg, int p_key_length) {

        //  Concatenate the algorithm ID for the hash algorithm 
        // and the hash code to form T
        byte[] x_algorithm_id = GetHashAlgorithmID(p_hash_alg);
        byte[] T = new byte[p_hashcode.Length + x_algorithm_id.Length];
        Array.Copy(x_algorithm_id, 0, T, 0, x_algorithm_id.Length);
        Array.Copy(p_hashcode, 0, T, x_algorithm_id.Length, p_hashcode.Length);

        // Generate an octet string PS consisting of p_key_length - T.Length - 
        // 3 octets with hexadecimal value 0xff. 
        // The length of PS will be at least 8 octets.
        int x_PS_length = p_key_length - T.Length -3;
        byte[] PS = new byte[x_PS_length < 0 ? 8 : x_PS_length];
        for (int i = 0; i < PS.Length; i++) {
            PS[i] = 0xFF;
        }
        // Concatenate PS, the DER encoding T, and other padding to form the 
        // encoded message EM as EM = 0x00 || 0x01 || PS || 0x00 || T .
        byte[] EM = new byte[3 + PS.Length + T.Length];
        EM[0] = 0x00;
        EM[1] = 0x01;
        Array.Copy(PS, 0, EM, 2, PS.Length);
        EM[PS.Length + 2] = 0x00;
        Array.Copy(T, 0, EM, PS.Length + 3, T.Length);
        // Output EM.
        return EM;

    }
}

16.4.5 Defining the Signature Formatter Class

The ElGamalPKCS1SignatureFormatter class extends AsymmetricSignatureFormatter, and uses ElGamalSignatureFormatHelper to create a PKCS #1-formatted hash code, which is passed to the Sign method of the ElGamalManaged class:

using System;
using System.Security.Cryptography;

public class ElGamalPKCS1SignatureFormatter : AsymmetricSignatureFormatter {
    private string          o_hash_name;    // the hash algorithm to use
    private ElGamalManaged  o_key;          // the ElGamal algorithm

    public override void SetHashAlgorithm(string p_name) {
        o_hash_name = p_name;
    }

    public override void SetKey(AsymmetricAlgorithm p_key) {
        if (p_key is ElGamalManaged) {
            o_key = p_key as ElGamalManaged;
        } else {
            throw new ArgumentException(
                "Key is not an instance of ElGamalManaged", "p_key");
        }
    }

    public override byte[] CreateSignature(byte[] p_data) {
        if (o_hash_name == null || o_key == null) {
            throw new 
                CryptographicException("Key and Hash Algorithm must be set");
        } else {
            // create the hashing algorithm
            HashAlgorithm x_hash_alg = HashAlgorithm.Create(o_hash_name);
            // create a PKCS1 formatted block from the data
            byte[] x_pkcs 
               = ElGamalSignatureFormatHelper.CreateEMSA_PKCS1_v1_5_ENCODE(p_data, 
               x_hash_alg, o_key.KeyStruct.P.bitCount(  ));
            // create and return the signature
            return o_key.Sign(x_pkcs);
        }
    }
}

16.4.6 Defining the Signature Deformatter Class

The ElGamalPKCS1SignatureDeformatter class extends AsymmetricSignatureDeformatter and uses ElGamalSignatureFormatHelper to create a PKCS #1-formatted hash code to verify a signature, using the VerifySignature method of the ElGamalManaged class:

using System;
using System.Security.Cryptography;

public class ElGamalPKCS1SignatureDeformatter : AsymmetricSignatureDeformatter

    private string               o_hash_name;    // the hash algorithm to use
    private ElGamalManaged       o_key;          // the ElGamal algorithm

    public override void SetHashAlgorithm(string p_name) {
        o_hash_name = p_name;
    }

    public override void SetKey(AsymmetricAlgorithm p_key) {
        if (p_key is ElGamalManaged) {
            o_key = p_key as ElGamalManaged;
        } else {
            throw new ArgumentException(
                "Key is not an instance of ElGamalManaged", "p_key");
        }
    }

    public override bool VerifySignature(byte[] p_data, byte[] p_signature) {
        if (o_hash_name == null || o_key == null) {
            throw new 
                CryptographicException("Key and Hash Algorithm must be set");
        } else {
            // create the hashing algorithm
            HashAlgorithm x_hash_alg = HashAlgorithm.Create(o_hash_name);
            // create a PKCS1 formatted block from the data
            byte[] x_pkcs 
               = ElGamalSignatureFormatHelper.CreateEMSA_PKCS1_v1_5_ENCODE(
                   p_data, x_hash_alg, o_key.KeyStruct.P.bitCount(  ));

            // create and return the signature
            return o_key.VerifySignature(x_pkcs, p_signature);
        }
    }
}

16.4.7 Testing the Algorithm

The following statements test the support for raw and PKCS #1-formatted ElGamal signatures:

using System;
using System.Text;
using System.Security.Cryptography;

public class Test {
        
    public static void Main(  ) {
        // define the byte array that we will use
        // as plaintext
        byte[] x_plaintext 
            = Encoding.Default.GetBytes("Programming .NET Security");

        // Create an instance of the algorithm and generate some keys
        ElGamal x_alg = new ElGamalManaged(  );
        // set the key size - keep is small to speed up the tests
        x_alg.KeySize = 384;
        // extract and print the xml string (this will cause
        // a new key pair to be generated)
        string x_xml_string = x_alg.ToXmlString(true);
        Console.WriteLine("\n{0}\n", x_xml_string);

        // create a signature for the plaintext
        ElGamal x_sign_alg = new ElGamalManaged(  );
        // set the keys - note that we export with the
        // private parameters since we are signing data
        x_sign_alg.FromXmlString(x_alg.ToXmlString(true));
        byte[] x_signature = x_sign_alg.Sign(x_plaintext);

        // verify the signature
        ElGamal x_verify_alg = new ElGamalManaged(  );
        // set the keys - note that we export without the
        // private parameters since we are verifying data
        x_verify_alg.FromXmlString(x_alg.ToXmlString(false));
        Console.WriteLine("BASIC SIGNATURE: {0}", 
            x_verify_alg.VerifySignature(x_plaintext, x_signature));

        // check the formatted signature support
        // - create a hash code for the plaintext
        HashAlgorithm x_hash_alg = HashAlgorithm.Create("SHA1");
        byte[] x_hashcode = x_hash_alg.ComputeHash(x_plaintext);

        // check the PKCS#1 signature formatting
        ElGamalPKCS1SignatureFormatter x_sig_formatter 
            = new ElGamalPKCS1SignatureFormatter(  );
        x_sig_formatter.SetHashAlgorithm("SHA1");
        x_sig_formatter.SetKey(x_sign_alg);
        x_signature = x_sig_formatter.CreateSignature(x_hashcode);

        // verify the signature
        ElGamalPKCS1SignatureDeformatter x_sig_deformatter 
            = new ElGamalPKCS1SignatureDeformatter(  );
        x_sig_deformatter.SetHashAlgorithm("SHA1");
        x_sig_deformatter.SetKey(x_verify_alg);

        Console.WriteLine("PKCS#1 SIGNATURE: {0}", 
            x_sig_deformatter.VerifySignature(x_hashcode, x_signature));
    }

    private static bool CompareArrays(byte[] p_arr1, byte[] p_arr2) {
        for (int i = 0; i < p_arr1.Length; i++) {
            if (p_arr1[i] != p_arr2[i]) {
                return false;
            }
        }
        return true;
    }
}