RSA with BigInts

In BigInt - multiprecision integers I described my BigInt class for arbitrarily large integers. Now let's put it to some good use by trying to create and use an RSA key pair (see RSA encryption with small numbers for a demo of RSA using 32-bit integers). In an attempt to add a touch of class, we'll use the primes from the original RSA challenge, which are 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 and 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

A simple example

First, to show how easy BigInts are to use, here's a snippet that multiplies together the two prime factors:

        BigInt p = "398075086424064937397125500550386491199064362342526708406385189575946388957261768583317";
            
            BigInt q = "472772146107435302536223071973048224632914695302097116459852171130520711256363590397527";
            
            Console.WriteLine(String.Format("{0} * {1} = \n{2}\n", p, q, (p* q)));

Now before we can do RSA encryption we need one elementary function...

ModPower

In RSA encryption with small numbers, I described the modpower() function that calculates a^b mod c. Provided that you use appropriate values for a, b and c, this function gives the RSA encryption of a through the key (b,c), which can be decrypted using a^d mod c, where (d,c) is (b,c)'s partner key. Now things get interesting - we have all the functions we need to implement modpower() for BigInts! The wrinkle is that the modpower() method that I described needs the binary representations of a and b. Since BigInts are stored in base 10, we must either convert them to binary, or make a base 10 version of modpower(). I went the base 10 route. Now, when calculating the residuals, you must raise them to the power of 10 instead of squaring them. One way of doing this, of course, is to multiply the number by itself ten times. But x¹⁰= x²* x⁸, and x⁸= (x²)³, so I managed to shave off a few multiplications and mods by calculating and reusing x². Another change from binary is that when you come to combine the residuals you must multiply the i^th residual by itself b_i times, where b_i is the i^th digit of b. All in all, the BigInt modpower function is too slow to be of much practical use in RSA encryption, but it does get the right answer.

Demo source code

All we need for this demo is a key generation function and a main routine to generate a key pair and apply it to a message. Here's the C# file:

BigIntRSA.cs

Generating the keys

The key generation routine is almost identical to that used in my 32-bit RSA demo. About the only difference is the change of datatype from int to BigInt!

The Demo

To see the demo, simply call BigIntRSA.DoDemo(). Here is the output (with line breaks!):

public key is (229, 188198812920607963838697239461650439807163563379417382700763

        35642298885971523466548531906060650474304531738801130339671619969232120573403187

        9550656996221305168759307650257059)

        private key is (1643657754765135055359801218005680697005795313357357054155138484

        04357082720728965489360864418578350694390790098454911162868000298819292059436405

        6066685719109768957923941277, 18819881292060796383869723946165043980716356337941

        73827007633564229888597152346654853190606065047430453173880113033967161996923212

        05734031879550656996221305168759307650257059)

        plaintext is 130107090319172105011309198

        plaintext encrypted using public key: 130107090319172105011309198 -> 17712175543

        90228500403719279179119520152829488877225209178794560281090223786358803450610401

        48158115595068244776735427572951894053682415421324674454366981561909567776153369

        379

        cyphertext decrypted using private key: 1771217554390228500403719279179119520152

        82948887722520917879456028109022378635880345061040148158115595068244776735427572

        951894053682415421324674454366981561909567776153369379 -> 1301070903191721050113

        09198

Sure enough, decrypting the encrypted message recovers the original.

Top links