Your Online Security Is Critically Dependent on the Generation of Random Prime Numbers
Your Online Security Is Critically Dependent on the Generation of Random Prime Numbers
It was Google who fundamentally changed cybersecurity. If not for them, we would probably still be connecting to insecure http sites. With Chrome, they pushed the industry to move towards https, and where any site that did not support it, would be marked as insecure. And so, nearly all of the sites we now connect to are secured with https. This creates a secure tunnel for the Web pages and also proves the identity of the remote Web site.
For identity, we use a digital signature, such as using RSA and ECDSA. This allows a Web site to sign a hash of data with its private key, and then verified with the associated public key. In most cases, these days, we use RSA signatures for this, and where an RSA key pair is created.
So, if these keys are not created in a secure way, it leaves us open to the private key of a Web site being cracked, and for an adversary to set up a fake site. With RSA, we generate two prime numbers (p and q), and then create a public modulus (N=p.q). If we can factorize N, we will easily discover the private key. If any of the values of p and q could be discovered — even for a single bit — it can considerably weaken the key pair created. These prime numbers must thus be as random as possible. So, let’s see if we can generate random prime numbers for a given number of bits.
Miller-Rabin test for primes
Miller-Rabin test for primes is one of the most popular methods for testing for prime numbers used in RSA. Given an odd number (n), we will have an odd number of (n−1), of which we can calculate the power of 2 with a value of s so that:
For example, if n is 25, (n−1) will be 24, and which is 2×2×2×3 and which is 2³×3. We then select a random value of a and which is between 1 and (n−1). We may have a prime if one of these is true:
and where r is a value between 0 and s−1. For example, if we take n=61, then (n−1)=60. This can be represented as: 2² ×15, thus s=2 and d=15. Let’s select a=5, so we get:
This does not pass the first test, so let’s try:
and which is equal to −1 (mod 61). It may thus be a prime.
Now we will try n=719 and where (n−1)=718. (n−1)=2×359, and thus s=1 and d=359. Let’s select a=7, and so the first test is:
This has worked, so it is a possible prime. Let’s not try a=9:
and so we have more proof of it being a prime number.
In the Miller-Rabin test, we perform k trials. If any of these trails returns a false, the value is not a prime number (and is a composite. If it returns a true, it is probably prime. First, we have a number to test (n) and produce a random number (a) and then compute d to solve (and where r is a value greater than 1):
We then compute:
If this is 1 or -1, we return a true value for a prime number. This is coded as [here]:
$a = Get-RandomBigInteger -Min 2 -Max ($n - 1);
$x= [System.Numerics.BigInteger]::ModPow($a, $d, $n);
If (($x -eq 1) -or ($x -eq ($n - 1))) {
return $True
}
Next, we keep squaring the value of x (mod n) while the value of d is less than (n−1) — and where we double d in each test. The code is [here]:
While ($d -ne ($n-1)) {
$x = ($x * $x) % $n;
$d = $d*2
if ($x -eq 1) { return $False }
if ($x -eq ($n-1)) {
"This is negative"
return $True
}
}The code for the Miller-Rabin method is then [here]:
function PrimeRabinMiller($d, $n) {
$a = Get-RandomBigInteger -Min 2 -Max ($n - 1);
$x= [System.Numerics.BigInteger]::ModPow($a, $d, $n);
If (($x -eq 1) -or ($x -eq ($n - 1))) {
return $True
}
While ($d -ne ($n-1)) {
$x = ($x * $x) % $n;
$d = $d*2
if ($x -eq 1) { return $False }
if ($x -eq ($n-1)) {
"This is negative"
return $True
}
}
return $False
}Generating random prime numbers
We can then generate a random odd number, and then test it for primality, if it isn’t prime we can increment by two, and test again until we find a prime number [here]:
"== Random Prime with Miller-Rabin Test == "
$randBytes=16
$randBytes = [int]$Args[0]
$val=GetRandomBigInteger($randBytes)
if ($val -le 0) { $val=-$val}
if (($val % 2) -eq 0) { $val=$val+1}"Random prime size: "+$randBytes+ " Bytes, Bits: "+$randBytes*8
"`nStarting value:`t"+$val
$flag=$False
$jumps=0
for ($i=0;$i -le 2000; $i=$i+1) {
$is_prime = isItPrime $val 4
if ($is_prime -eq $True) {
$flag=$True
$jumps=2*$i
break
}
$val=$val+2
}
if ($flag -eq $True) {"Random prime:`t"+$val
"Jump to find:`t"+$jumps
}
If you are interested, here’s the maths to determine the probability of finding a prime number for a given range:
https://asecuritysite.com/primes/nprime
Coding
As an example, I have coded in PowerShell [here]:
A sample run is [here]:
== Random Prime with Miller-Rabin Test ==
Random prime size: 128 Bytes, Bits: 1024
Starting value: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466313195
Random prime: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466314951
Jump to find: 1756
and for a 512-bit prime:
== Random Prime with Miller-Rabin Test ==
Random prime size: 64 Bytes, Bits: 512
Starting value: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773387
Random prime: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773583
Jump to find: 196
and for a 256-bit prime:
== Random Prime with Miller-Rabin Test ==
Random prime size: 32 Bytes, Bits: 256
Starting value: 678561933854231032073566346504160285991810520328758260539775958564099341129
Random prime: 678561933854231032073566346504160285991810520328758260539775958564099341417
Jump to find: 288
The jump value relates to the finding of the prime number from a random number start. In the example above, we increment by 288 to find the next prime number from our starting point. Generally, the smaller the prime number, the smaller the number of jumps will be. So, large numbers will often take much longer to generate, as there are likely to be more tests.
Conclusions
I repeat again, your online security is highly dependent on the generation of random numbers, especially in the generation of prime numbers. Any weaknesses of this could cause a whole trust infrastructure to collapse. So, watch those prime numbers!