Are You Lucky?
Read Euler, Read Euler. The master of us all. — Pierre−Simon Laplace
This is the Ulam spiral and which is drawn with prime numbers which start in the centre and spiral out:
If we could find a pattern, our public key methods would likely be cracked.
Getting lucky
So how lucky are you? Well, basically, some people are more lucky than others, and it is the way that life goes. Many of us rely on lucky numbers, such as 7, 3 and 11, and see 13 are unlucky. But, Leonhard Euler found that a polynomial of:
k² + k -n
had six lucky numbers of 2, 3, 5, 11, 17 and 41 that produced a sequence of prime numbers [here]. A simple Python program to produce these is [here]:
import sys
n=41
if (len(sys.argv)>1):
n=int(sys.argv[1])
print(f"Trying lucky number of {n} for k^2-k+{n}\n")
for k in range(1, n):
prime=k*k-k+n
print(prime, end=' ')And for an input of 41, we get a sequence of 41 prime numbers [here]:
Trying lucky number of 41 for k^2-k+41
41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461
503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447
1523 1601The number of primes?
The Greek mathematician Euclid showed that there is no “largest” prime number, and we can go onto infinity and never find the last prime.
So if we pick a prime number of a certain size, how do we know how many prime numbers that an intruder has to search through to find the one (or ones) we have used? If we select a small value, such as between 0 and 15 (4 bits), it is not going to be difficult, as the prime numbers will be:
2, 3, 5, 7, 11, 13, 17 and 19
But if we pick 10⁵⁰, how can we estimate the number of prime numbers there are. Well in cryptography we can use the pi(x), function to estimate the number of primes between 0 and x.
One of the simplest methods of calculating π(x) is to generate them and count. The following code does a sieve derived from a method defined by the Greek mathematician Eratosthenes. With this we filtering out multiples of each prime [here]:
# https://asecuritysite.com/encryption/nprime
import sys
from mpmath import *
start = 0
end = 100
if (len(sys.argv)>1):
start=int(sys.argv[1])
if (len(sys.argv)>2):
end=int(sys.argv[2])
def sieve(n):
"""
Generate the primes less than or equal to n using the sieve of
Eratosthenes.
"""
primes, sieve = [], [True] * (n + 1)
for p in range(2, n + 1):
if sieve[p]:
primes.append(p)
for i in range(p * p, n + 1, p):
sieve[i] = False
return primes
def pi(x):
"""Calculates the number of primes less than or equal to x."""
return len(sieve(x))
print ("Range from",start,"to ",end)
est= pi(end)-pi(start)
print ("Estimation of primes:\t\t\t",est)
print ("Possibility of finding prime (%):\t",est/float(end-start)*100)
print ("\n----- Using Riemannr method to estimate")
print ("Estimation is:\t",int(riemannr(end)))
print ("\nRange\tEst number of primes")
val=1
for x in range(1,31):
val=val*10
print ("10^",x,"\t","{:,}".format(int(riemannr(val))))One of the methods used is to calculate the prime counting function π(x) using Schoenfeld’s inequality:
One method which can be used to estimate the number of prime numbers is the Riemann R function. This is a smooth approximation for π(x). The function is defined using the rapidly convergent Gram series:
A sample run is [here]:
Range from 0 to 1000000
Estimation of primes: 78498
Possibility of finding prime (%): 7.8498
----- Using Riemannr method to estimate
Estimation is: 78527Range Est number of primes
10^ 1 4
10^ 2 25
10^ 3 168
10^ 4 1226
10^ 5 9587
10^ 6 78527
10^ 7 664667
10^ 8 5761551
10^ 9 50847455
10^ 10 455050683
10^ 11 4118052494
10^ 12 37607910542
10^ 13 346065531065
10^ 14 3204941731601
10^ 15 29844570495886
10^ 16 279238341360977
10^ 17 2623557157055978
10^ 18 24739954284239496
10^ 19 234057667300228928
10^ 20 2220819602556027136
10^ 21 21127269485932298240
10^ 22 201467286689188773888
10^ 23 1925320391607837261824
10^ 24 18435599767347541311488
10^ 25 176846309399141946490880
10^ 26 1699246750872419937812480
10^ 27 16352460426841662628560896
10^ 28 157589269275973244548022272
10^ 29 1520698109714271704874745856
10^ 30 14692398897720432138328735744In this case, if we were to select a number at random between 0 and 1,000,000, the probability that we will find a prime number is 7.84%. Often when we pick a random prime number, we start with a random number, and then keep subtracting one from the value, and testing it, until we find a prime.
And so, if our attacker can tries 1 billion prime numbers per second, then if we select a prime number in the range of 1⁰⁵⁰, it will take around 29,800 seconds — or just eight hours — to try them all. So we need to make sure that the prime number size is large enough, so that an intruder will have too many prime numbers to find in order to crack the keys.
If you are interested 10³⁰ is equivalent to 99 bits. Normally with RSA we use 2,048, so there’s lots of primes that an intruder would have to search through. Here is my little simple Python code that coverts 10³⁰ to bits:
>>> import math
>>> y=10**30
>>> print math.log10(y)/math.log10(2)
99.6578428466Finding the jump
In generating a random prime number of a given bit size, we just generate a random number in the number way (and with a given number of bits). We then make it an odd numberm and can then use the Miller-Rabin method to determine it is prime or not. If not, we increment by two, and then test again. We will continue until we find a prime number. And so, it the probably of finding a prime number if 10%, we have a 1 in 5 chance of finding a prime number, so it is likely to take us, on average, five increments to find a prime number.
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=0for ($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"+$jumpsIf 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
As an example, I have coded in PowerShell [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=0for ($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"+$jumpsA sample run is [here]:
== Random Prime with Miller-Rabin Test ==
Random prime size: 128 Bytes, Bits: 1024Starting value: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466313195
Random prime: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466314951
Jump to find: 1756and for a 512-bit prime:
== Random Prime with Miller-Rabin Test ==
Random prime size: 64 Bytes, Bits: 512Starting value: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773387
Random prime: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773583
Jump to find: 196and for a 256-bit prime:
== Random Prime with Miller-Rabin Test ==
Random prime size: 32 Bytes, Bits: 256Starting value: 678561933854231032073566346504160285991810520328758260539775958564099341129
Random prime: 678561933854231032073566346504160285991810520328758260539775958564099341417
Jump to find: 288The 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.
