.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;
	Array.Reverse(p);
	p = CheckArraySign(p);
	BigInteger primeP = new BigInteger(p);

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

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

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

	byte[] m = rsaParams.Modulus;
	Array.Reverse(m);
	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): 
 

p:
16919658989371234800052408977415375137474596831628885531211017076379849564211312
22990373212029304928097663144592622531525620885723762734105309422052975007476980
18863211240563250616209447207950324108617281939743126108253476984088930551584883
927967880751666536713807442811260180537771984147641735836334890823467

q:
14693170770947669857212755741964797493520961050687047721115987248939221946049225
97962016665072189314395144836412120235947884352773410329348232846590669397276303
12960778440844569329365679385318080563580926517662466426634367475136186289863173
782246073776396162136062760238745439115172895455523758027382280258303

d:
91737881910516011244171997662020280775866196720870551359227684649042629477971179
76098682670275130520654224683245753325222865795035971404152257134236502418746606
42432254875394958683536805222153673856989372980173545778578167978089751138779003
88443866463704377178906888862735073528862818838576511950084462320087515875117390
58366759392869512552993543427291864382007926821772582817862903981001524564308959
18090569728841626896274000692674180019308134047767122229498538901253442207945292
09206877039059965850735291848362907472685042063700587259335821302695233058782005
10761790186264915234588417792664852682165698563142516897

e:
65537

modulus:
24860343891703141866148280725999930289480412398675543021955444793434943797956488
62055819410196085134519169380854601950360283475063151083004988735554323763717318
66205270789649187095778000346693207589999638343539669490947227070708187315506779
59632176961758988451761581108985562826087837240422547401888378295863595684647125
29739020109733398027979188453358192091006248936822840701697548708284227202409837
24815039996608401538571369786587390895144437837798445825064540975460984639095088
17610679533565532161721074868842595129035139923110525166297339797027018388670854
016792277071544587788005574913035261875016415269133996501

modulus (hex):
0x0C4EE8E37801BBF4AF78D17676DD666D7C54137FFA26768312FC6E9839DD28C2C068631C0A3460
B5EE2F37D93EDF599B84AD115941A99F2B78403B0FAB034CB4B6C0A828B74763301BFA19F90DCB53
3F656615E0EDB0AA2A3CDAC66D30F3328D76FF145BBA817718361552EA87180A150002E01A8201E4
2889235476D54398EDE2633E4FD7E411EDA33DBD733465E95B5E101484F9265DB9935A7A588822B6
95C81AEA957FE6F3E9C0A52F57DBCF630EAA7EA7F2C59E387B27708DC243331E600655900DA42E58
B35113019F0DB9FDFC5E724677CAA77E34550B7252CAC9FDB2BBFC2E1C8F897DB7DA8C8119E7A149
4042563DA41E8D064BC5E936144B48BD1D5
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):
24860343891703141866148280725999930289480412398675543021955444793434943797956488
62055819410196085134519169380854601950360283475063151083004988735554323763717318
66205270789649187095778000346693207589999638343539669490947227070708187315506779
59632176961758988451761581108985562826087837240422547401888378295863595684647125
29739020109733398027979188453358192091006248936822840701697548708284227202409837
24815039996608401538571369786587390895144437837798445825064540975460984639095088
17610679533565532161721074868842595129035139923110525166297339797027018388670854
016792277071544587788005574913035261875016415269133996501

RSA Signature Creation

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

	34-C7-A6-98-C1-88-C1-8D-7F-E3-E3-6B-12-9A-34-32-5F-76-EC-78
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) :
0x7FE0118C20F7BEACDFC01B354F74CBD4A5921E0A795A220BAFF8FF6AE308A76A45E200B0B05561
E22C89A700088870AE430549E9A0A3CC45D7CA0BB47CE14AEEF40355276E7A15CBFB32D22494A3D1
341BED5127657656D1881531E3CB0E5C4E13D04A9B2CAF9BA23D165343088B78DA9EEE492A0570B2
CA0EE811A61C248F0E872282D30322C458B6F0F4452FF1128A4997919B16B1CA68DF7FBFE4893E04
97401DEECCDB2BA6845330C54D542FD12B86A7B150BF403899A862FC4BEF78D9B32A6C8399896BC4
6C0FE9F572EFD3006FAE6727E1FB4DC8D439960638761FE19712DE584C1D00DB669C817175BA45F2
BD807BE33D07FE29C1C3530D097E96CB6A
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
0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A0500041434C7A698C
188C18D7FE3E36B129A34325F76EC78
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).

Summary

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.

References