.NET 4 BigInteger and RSA Signature and Encryption

July 19, 2010

With the release of .NET 4, developers have access to arbitrary precision integer mathematics through the BigInteger type in the System.Numerics namespace. In previous releases of the .NET platform, a common approach to implementing arbitrary precision mathematics in managed code involved using the add-on .NET J# types in the java.math namespace contained in the vjslib.dll assembly. This article uses the new .NET 4 BigInteger type to demonstrate large number operations that are used in implementing RSA cryptographic processes, namely RSA digital signatures and RSA encryption. The RSA algorithms are an example of public key cryptography. The method involves use of an RSA public and private key which are chosen in a very specific way and are related to one another as described in official documentation available at the RSA Labs. Content data which is signed/encrypted with the private/public key of the key-pair can be signature-verified/decrypted only with the corresponding public/private key. The specific example discussed here demonstrates the key details of a typical 2048 bit RSA public/private keypair which today (2010) is considered the minimum size RSA key that should be used for e-commerce applications. This page describes the basic mathematical operations used to create and verify a digital signature and encrypt and decrypt content.

Microsoft Windows 2000+ supports creation, storage, importation and exportation of RSA keypairs with up to 16,384 bits (2048 bytes) in size. A 16,384 bit RSA keypair will have component prime numbers of length approximately 2460 decimal digits. The prime numbers created for large RSA keys are not usually "certified" (i.e. proven) prime numbers but are chosen to be very highly probable prime numbers using algorithms such as Rabin-Miller. It is interesting to note that a prime number of this size corresponds to about the largest size certified prime number known in 1962. For perspective, the largest known certified prime number to date (7/2010) is the Mersenne prime number
      M43112609 = 243112609 - 1
which contains 12,978,189 decimal digits!

This article does not discuss the highly important security issues and complexities associated with creation, protection, distribution and trust of certificates and keypairs which is the domain of PKI and operating system security design.

A 2048 bit RSA keypair

Using the Windows SDK tool makecert.exe, a self-signed certificate with an associated RSA keypair can be easily created for testing and demonstration purposes. The keysize, validity period, type and Distinguished Name details of the generated certificate can all be specified. For any realistic commercial application, a properly issued certificate from a well known certificate authority (CA) should of course be used. The RSA "public key" which is typically made "public" to all users and is encoded into the associated certificate consists of two parts, the modulus m and the public exponent e. The certificate display in WinXP associated with the RSA keypair in this example is shown to the right. The highlighted section of the "Public key" field (ASN.1 encoded) shows the beginning part of the actual RSA modulus (identical to the full modulus hex display below). The "size" of an RSA key is the size in bits of the corresponding modulus in its octet (byte) representation which in our example is 1024 bits. The RSA "private key", which is protected by operating system mechanisms and which is typically accessed only indirectly through cryptographic operations, can be described using various parameters which are equivalent. Here the private key is described using the private exponent d and the same modulus. The exponents and modulus must be chosen in a very specific way as described in official documentation available at the RSA Labs. The modulus is in fact the product of two large odd prime numbers p and q of comparable size. Since the density of prime numbers suitable for RSA usage is extremely high for large key sizes (> 1024 bit), the RSA key generation process (used by makecert.exe) can be considered to be random and unpredictable. The "strength" of signatures and encrypted content created using RSA signature and encryption algorithms is directly dependent on the inability to factor the modulus into its two component prime numbers, p and q using known and available strong computing resources. Being able to factor the modulus into its component primes would expose the private key contents since knowledge of p and q is equivalent to knowledge of the private exponent d, rendering the RSA key useless.

A good discussion of the resource and computation effort required to "break" RSA keys is provided in the RSA Labs 2002 technical article: Has the RSA algorithm been compromised as a result of Bernstein's Paper?.

The decimal values of the two prime numbers, p, q, the private exponent d, the public exponent e and the modulus m are shown below as directly extracted from the keycontainer contents using the .NET RSACryptoServiceProvider and RSAParameters classes. To provide access to the private key values, the certificate and key generation procedure must specify the key as exportable during creation. The key components in .NET are returned as big-endian ordered byte arrays. However the .NET 4 BigInteger constructor with a byte[] argument expects the byte array to represent the number in little-endian byte order. Therefore, we must reverse the byte array. Further, we must ensure that BigInteger treats the byte array argument as a positive number (since all RSA parameters should represent positive numbers). Since BigInteger uses both sign magnitude and two's complement (to support both positive and negative numbers) we must check if the highest bit of the high-order byte is set as described in the BigInteger (Byte[]) constructor documentation. If the highest bit is set then we must add an additional zero byte to have BigInteger interpret the byte[] argument as a positive number. The sample code below which generated the output shown indicates the basic steps:

	CspParameters cp = new CspParameters();
	cp.KeyContainerName = "thekeycontainername string";
	cp.KeyNumber = AT_SIGNATURE;
	RSACryptoServiceProvider rsaCSP = new RSACryptoServiceProvider(cp);
            	RSAParameters rsaParams = rsaCSP.ExportParameters(true);

	/* ---	Get the RSA key parameters which are in big-endian byte order;
		Reverse the byte order since BigInteger wants little-endian order for constructor
		Check if top bit of highest order byte is set; if so, add an extra high-order zero 
		to ensure positive value when used as argument to BigInteger constructor ....... */
	byte[] p = rsaParams.P;
	p = CheckArraySign(p);
	BigInteger primeP = new BigInteger(p);

	byte[] q = rsaParams.Q;
	q = CheckArraySign(q);
	BigInteger primeQ =  new BigInteger(q);

	byte[] d =rsaParams.D;
	d = CheckArraySign(d);
	BigInteger privexponent =  new BigInteger(d);

	byte[] e  = rsaParams.Exponent;
	e = CheckArraySign(e);
	BigInteger pubexponent =   new BigInteger(e);

	byte[] m = rsaParams.Modulus;
	m = CheckArraySign(m);
	BigInteger modulus =  new BigInteger(m);
	Console.WriteLine("p:\n{0}\n", primeP);
	Console.WriteLine("q:\n{0}\n", primeQ);

Consider the size of the numbers for the components of this 2048 bit key.The component prime numbers have 309 decimal digits and the corresponding modulus has 617 decimal digits. The "strength" of an RSA pkcs1.5 protected content against brute-force attack is directly dependent on the difficulty of factoring a (properly selected) 617 digit number into its two component prime numbers. (Of course in this example, the specific prime numbers p and q below have been exposed for discussion purposes and they are therefore worthless):






modulus (hex):

It is easy to verify that the product of the two primes is in fact the modulus using BigInteger overloaded multiplication:

	BigInteger PQ = primeP*primeQ;	//check product of primes is equal to modulus
with the following result as expected:

p*q (verify product of primes is modulus):

RSA Signature Creation

Next a pkcs1.5 signature for a simple text file with a SHA-1 hash value of:

was created using the above RSA keypair using the methods of the RSAPKCS1SignatureFormatter class. The signature process involves creating an encoded data block of the same size as the key modulus. The data block contains header constants, padding bytes, encoded algorithm information and the hash of the data covered by the signature. Then this data block is simply converted to a corresponding positive number and that number is exponentiated (mod modulus) using the private exponent d with the result being the pkcs1.5 signature. This pkcs1.5 signature will also be the same size (in bits) as the modulus of the key used for the signing, i.e. in this case 2048 bits (or 256 bytes). A hex display (big endian order) of the signature as generated programatically using the RSAPKCS1SignatureFormatter class is shown next:

pkcs1.5 signature (hex  big-endian) :
Verification of a pkcs1.5 digital signature first involves exponentiation of the pkcs1.5 signature block with the RSA public key e (mod modulus). This operation recovers the original data block described above. If is of course possible to use the .NET api methods to verify the signature but it is instructive to manually use the .NET 4 BigInteger methods again, and specifically the exponentiation modulus method for signature verification. Since pkcs1.5 signature data created with .NET (and also with Java) are output in big-endian order, we must again reverse the byte order and again check the sign bit of the highest order byte before constructing a .NET 4 BigInteger object. (Note that in J#, the java.math.BigInteger constructor expects byte[] data to be in BIG-endian order, consistent with Java api usage):

	byte[] pkcssig = GetFileBytes(pkcs15signature);
	Array.Reverse(pkcssig);		//convert from big-endian original pkcs1.5 signature to little-endian for BigInteger constructor argument
	pkcssig = CheckArraySign(pkcssig);	//make sure block will be interpreted as a positive number in BigInteger constructor
	BigInteger PKCSsig = new BigInteger(pkcssig) ;
	BigInteger original  = BigInteger.ModPow(PKCSsig, pubexponent, modulus) ;	//original data by public exponent exponentiation mod modulus
	Console.WriteLine("Original data block of decoded pkcs1.5 (hex) is\n0x{0:X}\n", original);

Original data block of decoded pkcs1.5 (hex) is
The result above is the big-endian order hex value display (with the leading zero byte of the block not displayed) and shows the data block formatting exactly as described in the signature process. As can be easily seen, the final 20 bytes of the block correspond exactly to the original SHA-1 hash value of the original data which essentially completes the mechanical process of signature verification. Note that only someone with knowledge of or access to the RSA private key can create a signature with this RSA keypair, but typically anyone can verify the signature as verification involves usage of the corresponding public key which is included in the associated public certificate.

RSA Encryption

RSA encryption procedes in a very similar manner. However in RSA encryption, the original data block contains random padding data (unlike the signature block which contains fixed FF padding bytes). Typically a secret symmetric key is often the content protected by the RSA encryption process (possibly futher encapsulated into a pkcs#7 structure). For RSA encryption, the resultant data block is exponentiated with the public exponent e of a recipient's keypair. Decryption, which is then only possible by someone with knowledge of the corresponding RSA private key (which is always highly protected and with very limited authorized access), is then achieved by exponentiation with the recipient's private exponent d. Note that typically anyone can create RSA-encrypted content intended for the "owner" of the private key as the encryption involves only usage of the RSA public key. The keypair used for RSA signature generation should not be the same keypair as used for RSA encryption as described in Practical Cryptography (Ref. 1). Usage of the same keypair opens up the possibility of various forms of attack which are not present with different keys (although technically a single keypair can be used for both).


This article has described the mathematical procedures involved in PKCS1.5 RSA signature generation and encryption. Since RSA involves operations with very large numbers of several hundred decimal digits, the new BigInteger class methods of .NET 4 can be used to study the mathematical operations used in RSA. The example 2048 bit RSA key is a realistic key example showing typical sizes of the RSA key components used in e-commerce. Futher tests using very large 16,384 bit RSA keys indicate that the new .NET 4 implementation of BigInteger functionality is impressive in terms of execution speed. A detailed description of the fundamentals of the RSA algorithm along with a good discussion of practical security issues can be found in Practical Cryptography (Ref. 1). This article has not discussed the highly important security issues and complexities associated with creation, protection, distribution and trust of certificates and keypairs which is in the domain of PKI and operating system security design.