Line 68: Line 68:
  
 
A ubiquitous use of unpredictable random numbers is in cryptography, which underlies most of the schemes which attempt to provide security in modern communications. If a user wants to use an encryption algorithm, it is best that they select a random number as the key., and the key has to be unpredictable for any potential attackers. Using some public or simple random number generator is not a good choice, here is an example: "imagine if a simple 32-bit linear congruential pseudo-random number generator of the type supplied with most programming languages (e.g., as the 'rand' or 'rnd' function) is used as a source of keys. There will only be some four billion possible values produced before the generator repeats itself. A suitably motivated adversary could simply test them all; this is practical as of 2010, using readily available computers. Even if a linear congruential RNG is used with 1000-bit parameters, it is a simple exercise in linear algebra to recover the modulus m, and the constants a and b, where the formula is mentioned above, given only five consecutive values." As a result, any published random sequence will not pass the cryptographic standard. This pushes the implementation of enterprise use of random number generators, many informed observers even believe every computer should have a way to generate truly random numbers.
 
A ubiquitous use of unpredictable random numbers is in cryptography, which underlies most of the schemes which attempt to provide security in modern communications. If a user wants to use an encryption algorithm, it is best that they select a random number as the key., and the key has to be unpredictable for any potential attackers. Using some public or simple random number generator is not a good choice, here is an example: "imagine if a simple 32-bit linear congruential pseudo-random number generator of the type supplied with most programming languages (e.g., as the 'rand' or 'rnd' function) is used as a source of keys. There will only be some four billion possible values produced before the generator repeats itself. A suitably motivated adversary could simply test them all; this is practical as of 2010, using readily available computers. Even if a linear congruential RNG is used with 1000-bit parameters, it is a simple exercise in linear algebra to recover the modulus m, and the constants a and b, where the formula is mentioned above, given only five consecutive values." As a result, any published random sequence will not pass the cryptographic standard. This pushes the implementation of enterprise use of random number generators, many informed observers even believe every computer should have a way to generate truly random numbers.
 +
 +
As we could see, mostly the random number is used for science and cryptography, there is no ethic problem of using for the former because randomness is just a process, the result we obtain is nothing strongly related with random number. However, for the cryptography, there is one question: if I "guess" the random number others used for the key and get access to their resources, is that an illegal behavior? This push the improvement for pRNG program to provided more "random" random numbers to increase security.
  
  

Revision as of 18:56, 5 December 2022

Random Number In Modern Computer

Aaaaaaa.png


Introduction

Randomness is not something that truly exists very often in the natural world. Things tend to obey laws that make interactions predictable. However, sometimes it is important to be able to create a random number. Humans have been interested in generating randomness for thousands of years. Ancient dice have been dug up and discovered that belonged to civilizations long ago. Things like dice or coins have been used by people to make decisions randomly as long as we have been around it seems. Random numbers are only something we have recently begun to understand and even more recently began to need. Random numbers are constantly being used now in everyday life. Take online gambling as an example, blackjack is dependent on what numbers the dealer draws for the player. If the numbers are predictable, the game doesn't work and the player could figure out if they are going to win or lose. For this reason, it is important to create randomness in the game. Random numbers are also used all the time in modern video games, offering a way to generate new and unique worlds for a player. Random numbers also have uses outside of just entertainment. For example, they are vitally important in the world of cybersecurity and keeping electronic information safe. Math and numbers are typically thought of as anything but random, and follow strict rules around changing them. For this reason, creating randomness is a unique challenge seen in modern mathematics that has been approached with several different unique strategies.


Method

Almost all random number generation involves the use of some sort of seed to create the number. A seed is a number that is taken from somewhere and put into an algorithm to generate a random number. Then, the newly generated number is used as the seed for the next generation. Getting the initial seed is what makes this random. This can be done by using the current time, atmospheric noise, or some other source that can provide an unpredictable value. To give an example of how this might work, we will use the time to generate a seed. If you were to call on a random number generator at 11:38, the random number generator could use the current time to the millionth decimal place as a seed to create an unpredictable value that could not be replicated.

There are two main types of RNG: pseudo RNG, and true RNG. Pseudo RNG means that the numbers generated follow some sort of pattern, and could theoretically be predicted. In most scenarios, this isn’t a big deal. For example in a video game like Mario Kart, if the item a player is going to get from a mystery box is technically predictable or follows a pattern, it doesn’t matter too much as long as the player doesn’t catch on and is having fun. In something like online gambling, however, any sort of predictability is very dangerous. If a person could predict when to bet big and make millions of dollars, that would create problems. For this reason, sometimes true RNG is needed. True RNG is more complicated to do as it requires more instruments, but is more effective than pseudo RNG at creating unpredictable numbers.


True Random Generation In Computer

A truly random generator could provide a random number that is almost impossible to predict. we will not explore the true random generation in detail, because it is not high relative to math. Generally, a traditional computer that has the basic component cannot generate a True random number, it has to be obtained by a specific device. These devices will convert some phenomena into a number. Some examples of TRNG sources include atmospheric noise, time, and radioactive decay.

atmospheric noise uses processes occurring in the atmosphere for its RNG. Most often, it’ll capture the static generated by lighting flashes, which occur roughly 40 times per second. (Random.org is known to use atmospheric noise to generate random outcomes for all kinds of different scenarios). For times, the device will take the exact nanosecond when you click the mouse as a random number, just pick one from the sequence. There is also one kind of device that uses a method called Harvest Entropy to obtain a random number using radioactivity because nuclear decay is not predictable.


Psedo random number generation

The PRNG relies on algorithms and programs to generate a number sequence that seems to be random. But since it is using a fixed way to produce those numbers, it could be reproduced and predicted. This is because computer hardware is purely logical, which means it cannot provide output without input and processing, however that is exactly what random numbers obtain from, no source and reason. So, as suggested by the prefix “pseudo”, the sequence isn’t random, it just looks like it. The two main components of a PRNG are an initial value or seed, and a pre-set algorithm. It follows the next several steps:

  1. receive a seed as the input;
  2. Generating a number according to the preset algorithm;
  3. take the output as the input for the next computation;
  4. repeat the process until a specific time or required length is achieved

Pseudo-random generators are deterministic and periodic. deterministic means that the number generated is fixed whatsoever as long as the seed and the algorithm are set, periodic means after a certain amount of recursion, the algorithm will start to provide a repeated number. A good generator should last a long period.

Here are two examples of popular random generation algorithm that is currently used:


Linear Congruential Algorithm

One algorithm used for pseudo-RNG is the linear congruential algorithm shown below.

Formula11.png

In this algorithm, Xn is the seed, so X₀ would be our initial seed gathered from one of the random methods we discussed. “a” is the multiplier in this formula, c is the increment, and m is the modulus. Both a and c must be greater than 0 and less than m. This way, with a pseudo-random seed number, we can use this algorithm to continue to generate numbers that would be functionally random, as long as the multiplier, increment, and modulus are unknown.

For example, we let X₀ = 235, a = 2,398, c = 8,738, and m=1,000,000 since we had the seed already, we can go into the next step, make the formula and finish the calculation.

Example11.png

1,000,000 fits into 572,268 0 times, leaving a remainder of 572,268

Example12.png

Our X₁ is 572,268, so to get our X₂, we just have to use our formula again

Example13.png

1,000,000 fits into 1,372,307,402 1372 times, leaving a remainder of 307,402.

Example14.png

By repeating these steps, we got the first 5 arrays of random numbers as follows: 572268, 307402, 158734, 652870, and 590998. they look pretty random, and that's how the algorithms work


Middle-Square Algorithm

A second method of doing pseudo RNG is with a middle square generator. This method takes an input value or seed and squares it. The resulting number then has its middle digits extracted to be the same length as the original seed, and then this number is used as the next seed. For example, if our initial seed was 3592, we would square it to get 12,902,464. Because our initial seed was 4 digits long, we would drop the 12 at the start and 64 at the end of the number to get our next seed, 9024. This method of RNG does require our squared seed to have twice the number of digits of the initial number and requires the seed to have an even number of digits. By possibly adding one leading zero to the square of the seed, make sure that you have an even number of digits. In the case of a squared seed not having twice the digits (such as 25*25 = 625), a 0 is added to the squared number to obey the rule (0625). In the same line of thinking, a 0 can be added to a number with an odd number of digits to be even, for example, 525 would be changed to 0525. While this seems unnecessary because the number is still really the same value, computers can interpret them differently so it is important to be consistent with following these rules.


Comparison between True and Pseudo random generation

picture from Pixabay

PRNGs have higher convenience since all you need is a computer and an algorithm, but a TRNG requires an external device that is costly and may need to maintain the working condition consecutively to avoid damage. However, for the cyber security part, the TRNG takes the cake. For a sequence of true random numbers, there is no relation between subsequent values besides the fact that they come from the same source of entropy, which makes TRNG numbers nearly impossible to predict, and therefore much safer defenses against cyber attacks. Another disadvantage for PRNGs is that they are deterministic; because each number in the sequence relies on previous ones, they are much easier to decrypt.


Conclusion and Application

Randomness is one really important part of modern computers, and such feature has been used for multiple areas such as Games, Politics, Science, and Cryptography. For the game, the famous example is video games like Minecraft which need to randomly generate a world for players. Online gambling is also another example that has a high demand for randomness. As for science, static sampling is basically defined by randomness; Also, for scientific analysis in the real world, almost all data will contain noise, for example, an experiment that tests specific X-rays. To determine the likelihood that a detected signal represents a genuine signal, random number generation is required. This fact also applies to model simulation, where the real phenomena are affected by unpredictable processes, such as radio noise or day-to-day weather, these models can be constructed through random numbers. And actually, "automatic random number generators were first constructed to carry out a computer simulation of physical phenomena, notably simulation of neutron transport in nuclear fission".

A ubiquitous use of unpredictable random numbers is in cryptography, which underlies most of the schemes which attempt to provide security in modern communications. If a user wants to use an encryption algorithm, it is best that they select a random number as the key., and the key has to be unpredictable for any potential attackers. Using some public or simple random number generator is not a good choice, here is an example: "imagine if a simple 32-bit linear congruential pseudo-random number generator of the type supplied with most programming languages (e.g., as the 'rand' or 'rnd' function) is used as a source of keys. There will only be some four billion possible values produced before the generator repeats itself. A suitably motivated adversary could simply test them all; this is practical as of 2010, using readily available computers. Even if a linear congruential RNG is used with 1000-bit parameters, it is a simple exercise in linear algebra to recover the modulus m, and the constants a and b, where the formula is mentioned above, given only five consecutive values." As a result, any published random sequence will not pass the cryptographic standard. This pushes the implementation of enterprise use of random number generators, many informed observers even believe every computer should have a way to generate truly random numbers.

As we could see, mostly the random number is used for science and cryptography, there is no ethic problem of using for the former because randomness is just a process, the result we obtain is nothing strongly related with random number. However, for the cryptography, there is one question: if I "guess" the random number others used for the key and get access to their resources, is that an illegal behavior? This push the improvement for pRNG program to provided more "random" random numbers to increase security.


Reference

Wikimedia Foundation. (2022, November 20). Random number generation. Wikipedia. Retrieved November 29, 2022, from https://en.wikipedia.org/wiki/Random_number_generation

Team, T. T. (2021, January 12). History of random number generators & how they work. Tech Magazine. Retrieved November 29, 2022, from https://techpages.net/random-number-generators-technology/

M. Haahr, True Random Number Service. (1998), RANDOM.ORG

A. Arobelidze, Random Number Generator: How Do Computers Generate Random Numbers? (2020), FreeCodeCamp.org

V. Ravindran, Linear Congruential Generator (2019), Vish Ravindran Blog

S. Pigeon, The Middle Square Method (Generating Random Sequences VIII) (2017), Harder, Better, Faster, Stronger

E. Herzstein. (2021, January 30). How do computers generate random numbers? Medium. Retrieved November 29, 2022, from https://levelup.gitconnected.com/how-do-computers-generate-random-numbers-a72be65877f6#5e79

Alumni Liaison

BSEE 2004, current Ph.D. student researching signal and image processing.

Landis Huffman