Big Integers and Testing For Primes

Your online security is fundamentally dependent on a special type of number: a prime number. Every time you connect to the Internet, there…

Big Integers and Testing For Primes

Your online security is fundamentally dependent on a special type of number: a prime number. Every time you connect to the Internet, there is a computation that is normally done that allows a symmetric key to be created between you and a Web site and which involves:

V = calc (mod p)

and where p is a prime number. Along with this, we must verify a remote Web site with its signature, and so we also perform a calculation with involves a prime number (q):

S = calc (mod q)

And, so, both the security of the encryption tunnel and the trust in connection to a remote site are dependent on prime numbers. Often, for security reasons, the prime number number has to be extremely large, such as having 2,048 bits or more. Normally, though, our integer values have up to 64 bits in them, and which gives a range of up to:

>>> 2**64
18446744073709551616

But, with a 2,048 bit integer value, and which gives a range of:

>>> 2**2048
323170060713110073007148766886699519604441026697154840321303454275246551388
678908931972014115229134636887179609218980194941195591504909210950881523864
482831206308773673009960917501977503896521067960576383840675682767922186426
197561618380943384761704705816458520363050428875758915410658086075523991239
303855219143333896683424206849747865645694948561760353263220580778056593310
261927084603141502585928641771167259436037184618573575983511523016459044036
976132332872312271256847108202097251571017269313234696785425806566979350459
972683529986382155251663894373355436021354332296046453184786049521481935558
53611059596230656

We thus could not fit our numbers into our normal variables in a program. For this, we need Big Integers, and which store the values as a string rather than a numeric value. When then use special methods of these which implement the large calculations required to compute a result.

Normally, we define our Big Integers in C# within the System.Numerics library:

But with the integration of the Bouncy Castle DLL into our project:

dotnet add package BouncyCastle.Cryptography --version 2.2.1

We can then declare a Big Integer from a string (val) with:

var  v= new BigInteger(val);

Overall, the Big Integer class in the Bouncy Castle then gives us access to a range of useful methods:

So, how do we find a prime number, and test if it is actually prime or not Well, the Bouncy Castle library has a number of interesting methods which can test for a prime number and also find out the next prime number. In the following, we can test if a value is a prime number with 100% certainty using the in-built prime testing method, or with the Rabin Miller method:

var isPrime=v.IsProbablePrime(100);

var isPrimeRabin=v.RabinMillerTest(100,new SecureRandom());

And, if we have a random number, (p) we can then find the next prime number with:

var p=v.NextProbablePrime();

Now, we have the code, and can add a timer to see how well the methods perform [here]:

namespace SafePrimes
{
    using System;
    using Org.BouncyCastle.Math;
    using System.Diagnostics;
    using Org.BouncyCastle.Security;


    class Program
    {


        
        static void Main(string[] args)
        {
            var val="997";
            if (args.Length >0) val=args[0];

            try {

            Stopwatch timer = new Stopwatch();



            var  v= new BigInteger(val);
            
            timer.Start();

            var isPrime=v.IsProbablePrime(100);
            timer.Stop(); var t1=timer.ElapsedMilliseconds;  timer.Start();

            var isPrimeRabin=v.RabinMillerTest(100,new SecureRandom());
            timer.Stop(); var t2=timer.ElapsedMilliseconds;  timer.Start();

            var p=v.NextProbablePrime();
             timer.Stop(); var t3=timer.ElapsedMilliseconds;  timer.Start();

            Console.WriteLine("Value of {0} has {1} bits\n",v,v.BitLength);         
            Console.WriteLine("Value of {0} has {1} bits set to a '1'\n",v,v.BitCount);
            Console.WriteLine("Prime?\t{1}\tTime taken:\t{2} ms\n",val,isPrime,t1);
            Console.WriteLine("Prime (Rabin Miller)?\t{1}\tTime taken:\t{2} ms\n",val,isPrimeRabin,t2);
            Console.WriteLine("Next prime:\t{0}\tTime taken:\t{1} ms\n",v.NextProbablePrime(),t3);

            byte[] b = v.ToByteArray();
            Console.WriteLine("Byte array: {0}",Convert.ToHexString(b));

    } catch (Exception e) {
        Console.WriteLine("Error: {0}",e.Message);
    }
    }
    }



}

The following are a few tests:

  • Is 53 a prime number?. testprime
  • Is 997 a prime number?. testprime
  • Is 1001 a prime number?. testprime
  • Is 4354654212312954321 a prime number?. testprime
  • Is 99999999999999991 a prime number?. testprime
  • Is 909090909090909090909 a prime number?. testprime
  • Is 100000000000 … 00000000000000000000121 (210 bits) a prime number?. testprime
  • Is 10000000000000000 … 0000000000000283 (422 bits) a prime number?. testprime
  • Is 100000000000000 … 000857 (848 bits) a prime number?. testprime
  • Is 1000000000000 … 00000000000003143 (1,000 bits) a prime number?. testprime

For a value of 1000000000000000000000000000000000000000000000000000000000000121, we get 210 bits and see that the value is a prime number testprime:

Value of 1000000000000000000000000000000000000000000000000000000000000121 has 210 bits

Value of 1000000000000000000000000000000000000000000000000000000000000121 has 86 bits set to a '1'

Prime? True Time taken: 17 ms

Prime (Rabin Miller)? True Time taken: 48 ms

Next prime: 1000000000000000000000000000000000000000000000000000000000000307 Time taken: 57 ms

Byte array: 026E4D30ECCC3215DD8F3157D27E23ACBDCFE68000000000000079

Overall, it only takes 17 ms to test for primality. If we now for a 442 bit value, we can see that the time taken has increased to 63 ms testprime:

Value of 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000283 has 422 bits

Value of 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000283 has 174 bits set to a '1'

Prime? True Time taken: 63 ms

Prime (Rabin Miller)? True Time taken: 131 ms

Next prime: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001521 Time taken: 263 ms

Byte array: 3B174FEA33909EBFE8F947C4E2AD33AF9A7B94CBCAD0587D37E7E885B2E6C98F4DB7DBB9668000000000000000000000000000011B

Now, we can move up again to 848 bits testprime:

Value of 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000028310000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000857 has 848 bits

Value of 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000028310000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000857 has 360 bits set to a '1'

Prime? True Time taken: 249 ms

Prime (Rabin Miller)? True Time taken: 360 ms

Next prime: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000028310000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001249 Time taken: 506 ms

Byte array: 008865899617FB18717E2FA67C7A658892D0E50A3297E8C7A2252CD6CCBB9B0606AEBC361BB89D4493D7119D783E8B155BC8CE6189FEE87121F8501A27F950ACC009DE71A8147F64E4B43C8290BD3D945E85662EF7BC7436D7448180000000000000000000000000000359

and we now see that it takes 249 ms to test (0.249 seconds), with the Rabin Miller test taking a little longer at 360 ms. Finally, let’s prime a primality test for a value with 1,000 bits testprime:

Value of 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000283100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003143 has 1000 bits

Value of 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000283100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003143 has 409 bits set to a '1'

Prime? True Time taken: 318 ms

Prime (Rabin Miller)? True Time taken: 469 ms

Next prime: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000283100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003397 Time taken: 636 ms

Byte array: 00EEEA5D50049814781858CCFCE06CAC7426E6B70A63BB1951B6729713053C7C258AEB71666590D78A05D82822723FD36304C9DC5685720520D6C11ADA33AE98A2E2E074796A73DB145B7899FF379803E8A321E7D95FA456B5F003826AFCF0755EF812F2ED780D2760000000000000000000000000000000000000000C47

Conclusions

And, there you go, a little Big Integer, and some prime number testing.

Happy Crypto Christmas!