In cryptography, and in a number areas such as in gaming and modelling, we need to generate random numbers. A test for the distribution of values is the Monte Carlo value for Pi test. With this method, we take our random numbers and scale them be-tween 0.0 and 1.0. Next we take two values at a time and calculate \(\sqrt{x^2 + y^2}\). If this value is less than or equal to one, we place in the circle (with a radius of 1), otherwise it is out of the circle. The estimation of PI is then four times the number of points in the circle (M) divided by the total number of points (N).
Monte Carlo Test for Randomness |
Coding
The following is an outline of the code:
# https://asecuritysite.com/encryption/mc import sys import math values = [5,125,10,1,32, 101,33, 54,200,230,215,93,50,100,3,6,43] if (len(sys.argv)>1): values=eval(sys.argv[1]) max=255.0 inval=0.0 outval=0.0 ptr=0 print ("First Five Pairs:") print ("\tX\tY\tZ:") for i in range(0,len(values)//2): x = (values[ptr]-max/2)/(max/2) y = (values[ptr+1]-max/2)/(max/2) z = math.sqrt(x*x+y*y) if (i<5): print ("\t",round(x,3),"\t",round(y,3),"\t",round(z,3)) if (z<1): inval=inval+1 else: outval=outval+1 ptr=ptr+2 print ("\nInval:",inval," Outval:",outval) print ("\nResult: ",4.0*inval/(inval+outval)) print ("\n----------------\nValues Used:",values)
A sample run for values of 5, 125, 10, 1, 32, 101, 33, 54, 200, 230, 215, 93, 50, 100, 3, 6, 43 is:
First Five Pairs: X Y Z: -0.961 -0.02 0.961 -0.922 -0.992 1.354 -0.749 -0.208 0.777 -0.741 -0.576 0.939 0.569 0.804 0.985 Inval: 6 Outval: 2 Result: 3.0
Outline
Within cryptography random numbers are used to generate things like encryption keys. If the generation of these keys could be predicted in some way, it may be pos-sible to guess them. The two main types of random number generators are:
- Pseudo-Random Number Generators (PRNGs). This method repeats the ran-dom numbers after a given time (periodic). They are fast and are also deterministic, and are useful in producing a repeatable set of random numbers.
- True Random Number Generators (TRNGs). This method generates a true random number, and uses some which is random. One approach is to monitor the movements of a mouse pointer on a screen or from the pauses in key-strokes. Overall the method is generally slow, especially if it involves human interaction, but is non-deterministic and aperiodic.
Normally simulation and modelling applications use PRNG, so that the values generated can be repeated for different runs, while cryptography, lotteries, gambling and games use TRNG, as each value which is selected at random should not repeat or be predictable. Eve could thus guess the key created by the method that Bob uses to generate a key. So, in the generation of encryption keys for public key encryption, user’s are typically asked to generate some random activity. The random number is then generated based on this activity.
Computer programs, though, often struggle to generate TRNG, and hard-ware generators are often used within highly secure applications. One method is to generate a random number based on low-level, statistically random "noise" signals. This includes things like thermal noise and from the photoelectric effect.
Within cryptography, it is important that we are generating values which are as near random, so that Eve cannot guess the random numbers that Bob and Alice are used. With randomness we cannot determine how random the values are by just taking a few samples. For this we need a large number of samples, and make an estimation of the overall randomness.
There are various tests for randomness. For example, we could define an aver-age value which is half way between the number range, and then determine the ratio of the values above and below the half way value. This will work, but will not show us if the values are well distributed. Along with this we could determine the arithmetic mean of the values, and match it to the centre value within the range of numbers. An improved method to test for the distribution of values is the Monte Carlo value for Pi test. With this method, we take our random numbers and scale them between 0.0 and 1.0. Next we take two values at a time and calculate:
\(\sqrt{x^2 + y^2}\)
If this value is less than or equal to one, we place in the circle (with a radius of 1), otherwise it is out of the circle. The estimation of PI is then four times the number of points in the circle (M) divided by the total number of points (N). In the figure, the blue points are outside the circle and the yellow ones are inside: