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

M

which contains 12,978,189 decimal digits!

This article does

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 4042563DA41E8D064BC5E936144B48BD1D5It 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 moduluswith the following result as expected:

p*q (verify product of primes is modulus): 24860343891703141866148280725999930289480412398675543021955444793434943797956488 62055819410196085134519169380854601950360283475063151083004988735554323763717318 66205270789649187095778000346693207589999638343539669490947227070708187315506779 59632176961758988451761581108985562826087837240422547401888378295863595684647125 29739020109733398027979188453358192091006248936822840701697548708284227202409837 24815039996608401538571369786587390895144437837798445825064540975460984639095088 17610679533565532161721074868842595129035139923110525166297339797027018388670854 016792277071544587788005574913035261875016415269133996501

34-C7-A6-98-C1-88-C1-8D-7F-E3-E3-6B-12-9A-34-32-5F-76-EC-78was 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

pkcs1.5 signature (hex big-endian) : 0x7FE0118C20F7BEACDFC01B354F74CBD4A5921E0A795A220BAFF8FF6AE308A76A45E200B0B05561 E22C89A700088870AE430549E9A0A3CC45D7CA0BB47CE14AEEF40355276E7A15CBFB32D22494A3D1 341BED5127657656D1881531E3CB0E5C4E13D04A9B2CAF9BA23D165343088B78DA9EEE492A0570B2 CA0EE811A61C248F0E872282D30322C458B6F0F4452FF1128A4997919B16B1CA68DF7FBFE4893E04 97401DEECCDB2BA6845330C54D542FD12B86A7B150BF403899A862FC4BEF78D9B32A6C8399896BC4 6C0FE9F572EFD3006FAE6727E1FB4DC8D439960638761FE19712DE584C1D00DB669C817175BA45F2 BD807BE33D07FE29C1C3530D097E96CB6AVerification 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 188C18D7FE3E36B129A34325F76EC78The 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.

- Practical Cryptography, N. Ferguson and Bruce Schneier, Wiley 2003
- Planning for PKI, R. Housley and Tim Polk, Wiley 2001
- .NET Framework Security, B. LaMacchia et. al. Addison Wesley 2002
- Writing Secure Code, M. Howard and D. LeBlanc, 2nd Edn. Microsoft Press 2003
- The Largest Known Prime by Year: A Brief History (The Prime Pages @ UTM)