Test for Prime Number with C# and Bouncy Castle
[Primes Home][Home]
Your online security is fundamentally dependent on a special type of number: a prime number. In this case, we will use C# and the Bouncy Castle library to test for the primality of a large integer value.
MethodYour 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, in C#, 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: Normally, in C#, we define our Big Integers in C# within the System.Numerics library: 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, (v) 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: namespace Primes { 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); } } } } 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 |