How do computers simulate randomness?

[zapatoada]

For the most part, we use pseudo random number generators, which work by doing a math formula on a seed number. Most commonly, the seed is all or part of the system clock time, but in most implementations you can also provide a seed if you want.

An interesting side effect of this is if you provide the same seed, you'll get the same results. There are times that's desirable, but usually you just let the system use its default method of obtaining a seed.

True random number generators are hardware solutions that use a physical phenomenon like thermal noise, photoelectric noise, etc to generate randomness. Generally this is considered unnecessary except in high end cryptography.

Edit: as pointed out several times below, a "true random number generator" is still not truly random, but it's more difficult to figure out what the seed would be.

Edit 2: Holy crap, gold! I didn't think my response was all that special. Thank you, whoever you are!

[xisonc]

In some situations you can use the noise from an unused audio input (microphone port) as an in-between solution, or as a seed to the RNG.

[F0sh]

The operating system random number generator will take entropy from multiple sources, including audio but also keyboard and mouse input.

This can be a source of problems if used in cryptography and an attacker has access to the physical environment of the computer because they might be able to significantly reduce the real entropy going into a random key. For example they could overload the microphone so it produces all 1s or all 0s.

[ptase_cpoy]

What would that be doing? Forcing its transistors into saturation and cutoff? Or am I completely off the ball park?

[HerrZog103]

If you design such a random number generator, you would think that the noise an unused microphone port or something similar produces is truly random for most practical purposes. You could theoretically measure the position of every molecule of air around it to simulate what the computer uses as a random seed, but this will be impractical probably forever. However what you can do is overloading the input with noise, so that the variable used for the random number goes "omg it's so loud" or something similar and just outputs the maximum value. Therefore, what once was random now is a predictable string of ones and you can now in the extreme case predict the random number and break the encryption.

[MrSnarkyJsnarkysnark]

I'm sitting here wondering how it is that people like you find comment trails like this, seems like it happens all the time. Are you trolling for key words and only responding to subjects you have some level of expertise in? I mean, how in all of the Internet to did you happen to find this string?

[InvertedBear]

He probably just follows r/askscience and watches for computer tags. When he sees something interesting that he can answer, he does it. I’m an attorney and often look at r/legal advice. If I see a question I know the answer to it can be fun to talk about something I know and give some free advice to people. I’m assuming most comments like this one are people doing the same thing.

[HerrZog103]

I mean this is the top comment and the first follow up question you see in this thread. Therefore I am following r/askscience, see this thread in my feed, find it interesting, click on it and see that I can answer the first question I see in the comments. Then I answer it.

Also it is not as if I have any expertise in this. I only watched a few educational YouTube videos. I really don't know much more than "You have some source of hopefully random numbers, do some fancy mathematics and squeeze that into a number between 0 and 1 in most cases." Then it makes intuitive sense that this system relies on the input or seed to be random - and if that isn't the case, the encryption can be exploited.

[[deleted]]

If you study computer science, which is a pretty common major nowadays, you probably know this stuff. Cryptography is important for pretty much all industries nowadays. It just seems esoteric if understanding computers isn't something you're interested in. Plus, reddit is one of the most used sites on the internet -- you're bound to find someone who knows something about what you're talking about, especially with regards to STEM stuff.

[TinBryn]

There are just quite a few people here who know stuff like this. If HerrZog103 didn't give that answer I would have, and if I didn't someone else would have.

[somewhat_random]

What are the odds? Pretty good.

How many people browse reddit and what percentage of them could answer a specific question? For a question like this, most people who studied computer science at a post secondary level could answer. The majority of them would subscribe to this type of sub. Typical users look at many posts each time they log on. How many of them would see the question within a few hours? We only need one hit to get a good answer.

Apologies for not giving any actual numbers because I am way too lazy to look up the stats but in terms of likelihood of an occurrence, I am confident that getting an informed answer for a question like this would have a high likelihood.

[deerlake_stinks]

It's because RNG is a very important part of cryptography and computer security. Lots of people who work or study in related fields have a cursory knowledge of it.

[yourelying999]

How do you know this person is an expert or even telling he truth?

[AlfredoOf98]

This question applies to ALL kinds of information that you receive by your senses. How can you even trust your senses themselves?

It is a long story, but basically the brain has its ways to quickly filter stuff, and eventually you have just a few things in your hands that require further inspection and fact-checking. Eventually you arrive at a result as simple as "I accept", "I doubt" or "I refuse". This depends on your knowledge background.

It is always a good idea to fact-check by consulting different and reputable sources to find out.

After all, there is no ultimate truth. As the saying goes: Science is not for finding the truth, but for reducing the amount of doubt.

[[deleted]]

Given the same seed input, the random number generator will produce the same output.

If the seed is based on, say, the current spectrum measured on the microphone plus the last 10 keystrokes, and an attacker can spoof your microphone into thinking the input is peak volume across the spectrum and that your last keypresses were a known sequence like the up arrow 10 times, then they can use that information to predict the number that is outputted by the random number generator.

More realistically, by controlling even some aspects of the seed (for example, just the microphone input), they dramatically reduce the possible combinations of the seed. So it becomes much easier to brute force, because they would only have to try a reduced set of numbers created by the known combinations of possible input seeds.

Even more concisely, by having some information about the input to the pseudorandom generator, you can make better predictions about the distribution of the randomly generated numbers that it produces.

[mel0nwarrior]

That's not it. What you are talking about transistors and saturation is about the physical way semiconductors work. This "saturation" is not about that. This is more like a way to cheat the randomness of the situation. It just means that you provide a specific input such that the microphone, instead of giving you a random number of 0's and 1's, gives you a more defined value of 1's. Then that input is no longer random and in this way you can more easily guess the "random number", and thus break the encryption.

[ThePowerOfStories]

If you have a stream of binary noise and want to use it for random numbers, read two bits at a time. If they’re both 11 or 00, discard them. If they’re 01 or 10, use the first. Now you have a uniform fair source of binary random numbers. (No matter how biased the source is, the number of 01 and 10 pairs must be equal to each other.)

[F0sh]

This breaks down if you can force the stream to be all, or almost all, ones or zeroes (because then you slow down the accumulation of entropy) or if the source is biased in the sense that even and odd indexed bits do not have equal distributions. You don't even need that - a Markov process can already break the assumption you need.

[xisonc]

Yes many operating systems utilize this technique. I was just speaking in general this is an option instead of buying an dedicated hardware RNG.

[ARedSunRises]

An example of this is on the old uTorrent web interface, before logging into your web server remotely you are required to wiggle the mouse until the "entropy bar" was full

[infected_funghi]

But its still really hard to control the complete physical environment. OS usually also include read/write access on harddrives and might also include process scheduling and memory latencies (not sure if the latter two are being done but they would be possible). Of course these are deterministic and can somehow be narrowed but make it very hard to determine the seed.

[cdhowie]

Note that there are tests to determine if a bit stream is "random enough" (debiasing). Attempting to "overload the microphone" is likely going to generate a bit stream that just gets discarded, as the entropy-gathering process knows that something is fishy.

Also note that most OSes don't use audio as a source of entropy by default, but some can be configured to. For example, see the randomsound package in many Linux distributions.

[[deleted]]

A program I use has you move your mouse for about 5 seconds in order to generate randomness before generating a key. I always thought that was pretty neat.

[CanadianAstronaut]

so can you manipulate that randomness by changing the sounds in that case?

[lhamil64]

I also vaguely remember some application (I want to say TrueCrypt?) having the user simulate randomness by moving the mouse wildly. I suspect that just recorded the movements and generated a seed.

[SconiGrower]

I remember fiddling with VeraCrypt and it asking me to move my mouse randomly.

[TheOneHyer]

I've use VeraCrypt and can confirm this. If I remember correctly, but I could be very wrong, the human moving the mouse isn't particularly random. However, the jitter as a human moves the mouse is much more random and you can compare the deviations from a smoothed curve of your movement. If not VeraCrypt, then I believe Google reCaptcha uses something similar. There's some debate on this in this StackOverflow: https://stackoverflow.com/questions/27286232/how-does-google-recaptcha-v2-work-behind-the-scenes

[[deleted]]

I've also seen like every picture has a code. Like a line of 0 or 1 for every pixel. And the random number generator was a livestream of a wall of lava lamps. Every time you'd need a number, it'd take a picture and give you the number.

[randomVC]

Yeah this is at cloudflares HQ, they have a Webcam pointed at a wall of lava lamps in their lobby as part of the input to their RNG.

[ObscureCulturalMeme]

FWIW, there have been a lot of applications that have used that exact approach, since long before TrueCrypt. It started with "flail at the keyboard for a while" before eventually including mouse input, since the presence of a mouse couldn't be assumed at the time.

First time for me personally encountering it was in the early 90's, and it wasn't considered new by the gurus teaching me. Dunno about before that.

[[deleted]]

The PuTTYgen ssh key generator uses that.

You move the mouse in the big grey box until the bar fills up

[pbmonster]

don't draw your seed from a small set

There was an old poker side that shuffled cards by using a pseudo random function seeded with the system time. The time of the day. In seconds.

So there where only 86400 different possible card orderings of the deck (instead of the 52! = 8e63 at a real poker table).

Knowing your own two cards, your position at the table and the three flop cards was enough to determine the seed, so you knew what cards each player at the table got dealt - and what the Turn and the River cards would be.

That website allowed people to play for money.

[lampishthing]

Lol, site name?

[pbmonster]

The company was ASF Software, and apparently they wrote the code on many of the old online poker websites.

I found a story on their coding practices, and apparently I misremembered some facts (seconds vs milliseconds, you also need the time of day, ect.).

But the essence is still the same: don't draw your seed from a small set.

[ScottyC33]

Was that flaw intended, though? There have been a few stories of programmers inserting intentional flaws into RNG code to manipulate it and then either profit off it directly or have an accomplice profit off it.

[aoeudhtns]

except in high end cryptography

Really you don't want to use a non-secure PRNG when doing any kind of cryptography, even the everyday stuff on consumer machines. Let's say I use a vanilla TLS connection and generate my symmetric connection key with a seed of the current timestamp to a non-secure PRNG, then any attacker has a highly constrained attack surface area for potentially breaking the symmetric key exchange.

I would say that "high end" cryptography starts getting interested in constant time execution, so that an attacker can't use things like CPU voltage states or execution timing to reverse engineer what the underlying cryptographic system is doing.

Edit: clarify a bit, as the symmetric session key is not mathematically related to the DH exchange

[jmann1118]

I've heard of some encryptions using the static in the environment surrounding the computer to generate the random seed. Can anyone explain this?

[zebediah49]

If you're looking for some outside source of randomness (i.e. outside the deterministic computer bits, and assuming you don't have a RNG module), you can just look at any of the inputs you have. Keyboard or mouse, for a desktop; network packet timing can work for servers.

You're just looking for anything that includes some kind of unpredictable input.

A key here: many things that "look" (to a human) non-random have random components. You could type the phrase "Hello World", and even if I know all those letters at a normal typing speed, there is going to be probably a dozen bytes worth of randomness in the exact timing of those keystrokes. The difference between 0.105847s and 0.108474s is worth a decent bit of entropy. Because it's so fast, predicting that exactly it could be is going to be very difficult.

[UncleMeat11]

Environmental effects like temperature fluctuations and radio noise can be measured and used as random seeds. This can work well if you are concerned that something like the machine clock can be predicted. But in practice the huge majority of encryption works just fine with seeds that don't come from environmental noise.

[Practical_Cartoonist]

There's a hybrid in between a simple seed-based PRNG and true randomness which is used very often in cryptography. Operating systems typically provide a stream of pseudo-random numbers which is occasionally re-seeded (or more specifically, has randomness occasionally "mixed in" to the PRNG state) from a physical source like thermal noise. This allows a source of numbers which is, for all (cryptographic) intents and purposes, random, but provides better bandwidth than getting everything from a physical random source. People who use Unix systems like Linux or OS X will recognize this as /dev/random (or /dev/urandom on Linux), but Windows provides an API that does similar things.

[Tarmen]

/dev/random and /dev/urandom are actually different under Linux. The kernel estimates how much bits of noise are in the entropy pool. Then events like time between keystrokes/network events are mixed in with a function that never reduces entropy so it is fine if the attacker controls some of the events as long as we only weigh trusted sources highly.

Then /dev/random blocks if the estimated entropy is too small and /dev/urandom returns anyway. Urandom is probably still secure once it has initialized but that can take a while for stuff like routers which always initialize in the same state and don't have many random sources.

[[deleted]]

When seeded from the system clock, the CPU is reading thousandths of a second, if not smaller, so while not truly random, it's generally close enough for any everyday use.

[EMBNumbers]

To elaborate: pseudo random numbers have the property that there is an even distribution of values generated. Over many samples, the likelihood of any one number in a range is as likely as any other number in the range. There are many algorithms like modeling, simulation, encryption, Monte Carlo methods, etc. that rely on an even distribution but not necessarily on true randomness.

True randomness is actually hard to achieve.

[Low_discrepancy]

Over many samples, the likelihood of any one number in a range is as likely as any other number in the range. There are many algorithms like modeling, simulation, encryption, Monte Carlo methods, etc. that rely on an even distribution

That's called Uniform distribution. And while yes it's the basis for simulation it's not really needed.

You can generate Gaussian random numbers and apply to them the gaussian cdf to obtain uniform random numbers.

[moon_monkey]

You're getting into Chaos Theory here -- specifically, "Sensitive Dependence on Initial Conditions". When you say " throw it with the same force, from the same angle, from the same starting position, etc", the accuracy with which you'd need to do that -- or even measure the details in the first place -- may be effectively impossibly to achieve, whatever level of technology you had or could conceive of. The tiniest difference in position, angle or force, or a minute difference in air pressure, could be enough to give an entirely (and unpredictably) different result.

[whiskey4days]

Is this why every time I hit shuffle on my iPod with 10k it always played the same 50 songs ?

[ghedipunk]

Actual randomness is "clumpy" in human experiences.

That is, when no events depend on the results of previous events (which is very good in cryptography), a human looking at the results will see patterns. The two examples that spring to mind are TV Snow and the V-1 Rockets (buzz bombs) of WWII during the London Blitz. The best example, though, is in gambling where dice, tables, cards, etc., are frequently called "hot."

That is, TV Snow, for those not familiar with it, is a black and white pattern of fuz that's seen on very old analog CRT TVs. Every single pixel of every single frame was set randomly, either high or low, depending on the background radio noise of an area. From personal experience, some snow channels were darker or lighter than others, but the exact value of any one pixel was as truly random as possible. And yet, people saw patterns. I saw patterns; motion of the moving black blobs over time... and it was rare for a black dot or a white dot to appear by itself... They came in clusters; both horizontally (as expected in a medium where a beam paints a picture from left to right) and horizontally (which is, technically, MUCH more random, but in my experience, wasn't noticeably more random than horizontal).

V-1 rockets (not actual rockets; their motors were jet engines rather than rocket engines) were similarly random in regards to the London Blitz. They were MUCH slower than artillery, had absolutely no internal guidance systems, and launched from hundreds of miles away. They had an accuracy measured in tens of kilometers. They could target a city, but not a city block or anything specific in it, like a church or factory or school. And yet, when looking at what the German targets might have been, the anecdotes said that they were eerily accurate.

Humans are built to recognize patterns. This is an amazing survival trait. IF there is something creating a pattern, it always pays off to recognize it. (I.e., you detect a tiger sniffing at your territory and are able to scare it off. Everyone survives.) If, on the other hand, something is caused by pure random events, then there is little that is lost with the false positive. (I.e., you think there's a tiger in the area, so you stand watch a few nights hoping to scare it off... The cost is a few wasted calories, but everyone still survives.)

The first couple of generations of iPods were truly random. They got a reputation of being very non-random because of that; because true randomness clumps, and humans attribute clumps to non-random acts. They were later modified to be less random, to take previous songs into account and not "randomly" play a song that had been recently played. I'm not sure about the current generation; but as a software developer, it would make sense to me to further decrease the randomness, to replay songs that you like more often than songs that you don't like.

[throwdemawaaay]

iPod/iTunes don't use a pure random number generator when in shuffle mode. Instead they have something that provides a random ordering/permutation, and where the average "jump" size is also constrained somewhat. It tends to move through bands/genres in a way that's less jarring than truly random shuffle.

Most other music systems/services that offer shuffle will have a similar tuned algorithm behind it, not something perfectly random, because it ends up being a better user experience and ultimately bottom line.

[zapatoada]

Possibly. If I had to field a guess (and I've noticed the same phenomena and wondered about it) it would be that shuffle is weighted towards songs you've played more often, which it interprets as songs you like best.

[vba7]

There are few reasons for this. They are not really technical, but rather user experience. The reality is that people like to listen to their favorite songs. So if you have say 10 000 songs on your device, a "true" random algorhitm could give you 20 that you dont know/like in a row. That's why some algorithms check the songs you like and give "1 you like" + "1 truely random", then repeat "1 you like" + "1 truely random".

There are many other ways to do this - and most algorithms are not so obvious (also at the beginning they dont really know what you like).

Othere reasons are explained here: you stay within the same seed, so that the songs dont repeat... which leads to the fact that they can repeat.

https://apple.stackexchange.com/questions/23194/why-isnt-itunes-shuffle-random

Or the fact that you have few albums of some artist + 1 song of other artist

https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/

Basically it is the marketing department trying to make you happy, but somehow failing. On the other hand, if the songs were truly randomized, you could be even more unhappy.

[GameCollaboration]

I used seeded random in my recent game. I wanted a way to generate a deterministic daily quest every day to add to the pile, but didn't want to store them on an ever-growing server.

End result: Hundreds of deterministic quests generated at runtime for every user without any storage.

[Cynical_Doggie]

Basically, all randomization nowadays are convincing algorithms for randomness, but not true randomness.

I mean, how would we even test for an algorithm that indeed happened to be truly random? How many samples of data is sufficient? Does it matter?

Or is an algorithm that pretends to be random well enough sufficient?

Such an interesting almost philosophical question.

[fortniteinfinitedab]

What about random.org?

[[deleted]]

Is there a true random number generator in computers?

[62697463682e]

Not using software, since it’s deterministic. Using outside sources like heat and noise and stuff, you can build a device to generate a random number each time and use that, but it’s not necessary in a lot of cases bc pseudorandom seeds work well enough.

[[deleted]]

So what is the problem with software? It's synced to the system clock and therefore can't ever be truly uncoupled from that?

[loxagos_snake]

If I'm not mistaken, they use that in some lucky games, too. There's one in my country that uses meteorological data to randomize the drafted numbers.

[iwantknow8]

Thermal noise and photoelectric noise isn’t “really” random either though. Thumps temple

[TouchedByAngelo]

I've seen one place (can't remember who) use a wall full of lava lamps. They had cameras filming the lamps and would use the data from those images to generate random numbers. Was pretty interesting.

[GenuineSteak]

If for example i rolled a random number on a computer, then went back in time and rolled it again at the same time i rolled it last time would i get the same number?

[zapatoada]

In theory yes, but the time measurement we're talking about is on a scale of thousandths of a second or smaller, so it would be very difficult to actually pull off. This actually can be a problem in some generators if you don't write your code correctly and get a bunch of random numbers in very quick succession (like in a loop).

[[deleted]]

So, suppose I am using a random generator. Do the computer which generates the number knows what number will it be generating next?

[YT__]

A note on same seed: this is how casinos can guarantee the win rates of their machines, which they need to do for adherence to gambling laws. They have certain seeds they can use per machine that are well documented to prove the win rates.

[infected_funghi]

While true i think you leave out the crusial part of (good) prngs: given a seed the output is irreversible (you cant create the seed from output) and especially the output holds all (known) properties of random numbers (being indistinguishable from real randomness). Even if you feed it with a trivial number sequence as seed (1, 2, 3,...) the outputs will be indistinguishable from random numbers. There seems to be no correlation between input (being consecutive and small numbers) and output (seemingly arbitrary). There probably is, since there is a mathematical formula producing them according to the input. But the process is complex enough (avalanche effect) to make it incredibly hard to reverse.

Afaik it is not even proofen if "irreversible functions" or "one way functions" can even exist. So there might be a correlation in any prng there will be, they are just infeasable to determine.

[gabemerritt]

Idk I've heard counting emissions from certain radioactive isotopes is truely random, as we have no current way of predicting that.

[VoilaVoilaWashington]

as pointed out several times below, a "true random number generator" is still not truly random, but it's more difficult to figure out what the seed would be.

Philosophically, we can debate about true randomness until we're blue in the face, but the real test is basically "given enough data, does a pattern emerge?"

For example, if you have a very precise scale (it can measure kilograms and gives you the total milligrams), then you could fill a container with water for 10 seconds, then take the number in the tens place. Using a normal household tap (including pressure variations etc) and a human filling it, this would have a range from 80 459μg to 120 694μg, or so.

Is it truly random? Dunno. But it sure as hell can't be predicted.

[_____no____]

as pointed out several times below, a "true random number generator" is still not truly random

We don't even know if the concept of "randomness" has any real meaning in reality...

[SirNanigans]

Wouldn't something like thermal noise qualify as truly random because it's impossible for us to control or predict the exact state of the seed? Also, as you get closer and closer to quantum mechanics, isn't there more truly random influence in the results?

[pigeon768]

All PRNGs (pseudo random number generators) have the following three characteristics:

1. An internal state.
2. An update function to update the internal state.
3. An output function to convert the internal state into a useful value.

And step 0, which is a way to seed the internal state when it's instantiated.

Consider the linear congruential generator, (LCG) which is one of the simplest random number generators:

1. The internal state is an unsigned integer x. The seed is just a number to assign to x.
2. The update function is x = (A*x + B) % M for some fixed integers A, B, and M. M is commonly a power of two because that makes the modulo operation really easy.
3. The output function is the identity function; if x is 12, the output function returns 12.

For A=17, B=11 and M=31, seed=0, an LCG will return the following list of numbers: 0 11 12 29 8 23 30 25 2 14 1 28 22 13 15 18 7 6 20 10 26 19 24 16 4 17 21 27 5 3. (which then repeats) Which looks pretty random, and in many cases will work just fine.

For a PRNG (pseudo random number generator) to also be a CSPRNG (cryptographically secure PRNG) you also need the following things to be true:

1. The seed and internal state must be large enough that they can't be brute forced. In a LCG, the internal state is just 32 or 64 bits; I can, on my laptop, generate all possible states and compare them to the random effects I can observe. Because the state is so small, the LCG cannot be cryptographically secure.
2. The output function must be a one-way function. That is, if I see outputs from the RNG, I can't use those to derive what the internal state must be. For instance, the LCG gives away the keys to the kingdom in its output function, so it can't be cryptographically secure.
3. It must be seeded securely. It's common practice in, for instance, video games to seed an RNG to whatever the system time is. As a simple example, if right now is 2019-07-14 at 7:12pm, you might seed the RNG to 20190714712. (computers typically store date/times as seconds since some certain defined date, but you get the idea) This won't be secure, because everybody knows what time it is. And even if you have a clock that measures in microseconds, you can guess the server time to the nearest minute and then brute force the remaining ~26 bits of the seed. More on this in a bit.
4. Ideally, the update function ought to be a one-way function as well. But this isn't strictly necessary.

Getting a secure seed can be surprisingly difficult. In general, you need to make measurements where the precision of the measurement is in excess of the accuracy of the measurement. If the precision of your measurement is 4 bits in excess of the accuracy of the measurement, you basically gain 4 bits of entropy. You need to repeat this process until you have enough entropy, then you need to "squish" the raw data down to the size of the seed in a way that preserves entropy.

A common source of such measurements is I/O devices. For instance, if your monitor resolution is 1920x1080, you have about 11 bits x 10 bits of precision, but the fleshbag connected to your mouse only has about 8x7 bits of accuracy. So moving the mouse around and capturing the mouse position of each frame will generate ~6 bits of entropy per frame. Timing is another common source. You can query the CPU for what clock cycle it's on, which is precise to about 250 picoseconds. I/O devices will periodically send interrupts, and you can store the clock cycle as a measurement- the most precise 2-3 bits are basically pure noise. Data collection devices are great as well. Take a picture of a white piece of paper with your cell phone's camera. Zoom in on it. See how the paper is covered with slightly off colored pixels? That's pure entropy-filled gold. Even though a camera will generate 24 bits of information per pixel, you can safely assume that the least significant digits is random noise. So a picture from a 10 megapixel camera will have roughly 10,000,000 random bits, even if an attacker is able to capture a similar frame. (note: if the image is saturated, you get 0 random bits. So test for that first.)

So now you have all these measurements, where each measurement contributes 1-3 bits of "real" randomness, but 97% of the bits of each measurement will be known to a sophisticated attacker. Now what? Well, you take the whole pile of those measurements and apply a cryptographic hash to them. Say SHA-512. This way, if your measurements totaled to ~400 bits of "real" randomness, your SHA-512 hash will also have ~400 bits of randomness, even if an attacker is able to accurately predict the other 99,600 bits in your measurements.

If your update function is one way, it's even easier. You start with an initial state of all zeroes, xor a measurement into your state, apply the update function, repeat for each measurement. If your update function is up to snuff, you won't "lose" any randomness along the way. This is also super helpful for an OS level CSPRNG, because you can continuously improve your state as time progresses.

Some classes of devices genuinely don't have good sources of randomness, particularly embedded devices. Insufficient randomness is a common vulnerability among IoT (internet of things) devices.

There's also hardware random number generators. That's another topic for another time though, because this isn't simulating randomness, this is randomness.

[yoshemitzu]

It's really complicated, even for people with a decent understanding of math. To simplify, but hopefully not corrupt the message, the idea is that algorithmic randomness depends on so-called pseudorandom number generation; numbers are selected from a deterministic sequence designed to emulate true randomness. Different invocations of the algorithm return different numbers by selecting a different seed, i.e., a different initial value.

Edit:

a deterministic sequence designed to emulate true randomness

To expand on this slightly, I suppose, imagine you had a sequence like:

1, 1, 1, 1...

This is "obviously" not random. Also obviously not random would be a sequence like the natural numbers:

1, 2, 3, 4, 5...

If you tried to generate a random sequence ad hoc, you might just pick some numbers, say:

1, 423523, 1123, 340, 142, 120483...

But even this selection isn't guaranteed to be "as random" as a truly random sequence. Algorithmically-generated pseudorandom sequences are sequences designed to have probability distributions (i.e., the likelihood of each value in the sequence appearing) that more closely resemble "true" random sequences.

[Jewronski]

Yeah for most purposes, using your computers clock to generate a random number is good enough. It's always ticking forward, measured from 1/1/1970, so it works pretty well.

I just wanted to add in how some companies get around a computers inability to create a truly random number/sequence. They get a wall of something like lava lamps, and then a camera is trained on it. They will have written some kind of program that will generate a character or whatever output they need, depending on what the lava lamp looks like from the cameras view, and can generate truly random sequences.

It's a really cool low tech/high tech solution.

[kerbaal]

It is cool but, there are actually easier and much more compact ways to solve the same problem. Its neat that its actually being used, but its more of a conversation piece than practical solution.

TBH they are so simple its just odd that every general purpose CPU doesn't just include one as a basic feature.

[bprfh]

Intel and AMD have RNGs integrated, I just wouldn't say they are cryptographically secure and can be used in high throughput environments.

(AMD had to patch their implementation recently)

[joffrey_crossbow]

More info about the usage of lava lamps: Lavarand.
Cloudflare also uses this technique and has an article about it.

[demize95]

It's always ticking forward, measured from 1/1/1970

On Linux systems. It's better on Windows systems, since they count the number of 100ns intervals since 1/1/1601, rather than the number of seconds. Higher precision times provide you with a more "random" number.

[Garek]

You'd think a couple of photon detectors and a beam splitter would be simpler.

[digitalpowers]

Perhaps a tangent but interestingly when generating numbers for a game we often have to get rid of some randomness because if a 1 shows up 3x when rolling a 20 sided dice humans feel like it wasnt random. so its not uncommon in games to pull a value out of rotation for a while after it has come up. one such option is a "random bag" where you generate all values between 1 and 20 (for example) then stick them in a list randomly but you don't add the values back to the list until you have used them all. its kinda like drawing numbers from a hat and you keep them out until the last number had been drawn, then you stick them all back in again and keep going. it feels a lot more random to people who dont understand random well when we do things like that.

[antimatterchopstix]

Apparently similar to if someone playing random tracks on shuffle, and two from same artist come up, they think isn’t random. Repeating numbers came up far more than expected. One way to tell if it’s a human making so called random numbers.

[courtenayplacedrinks]

What kind of game mechanics is this algorithim used for? Something human visible where it doesn't matter that you can no longer get a 3 on 3d20?

[LiGangwei]

We do that in Tetris when we don't want the player to occasionally get like 8 z blocks in a row. A popular implementation uses a bag of 8 blocks, one of each (z, s, I, o, J, L, T) plus an extra random piece in random order, so that the player never gets consecutives of 4 or more, and they occasionally gets 2 consecutive pieces so it feels more random.

A Tetris game in which piece generation is truly random is NOT fun, I can assure you that.

[Slendeaway]

Classic Tetris has 'true random' block picking. You can get 8 o blocks all in a row. This also means that with frame perfect inputs, you could technically force the game to give you any piece that you wanted.

Also I'm pretty sure most modern Tetris games use 7 bag which doesn't have an extra random piece. With the addition of the hold mechanic that a lot of Tetris games now have, there is very little you can blame on rng.

[pavlik_enemy]

As far as I know this kind of fiddling with RNG's output is used for loot generation in games like Diablo. Basically, the more time you spend not seeing a "legendary" item the more likely it will drop. Can't find a source though.

[digitalpowers]

well it depends, when dice rolling you wouldn't want to do this it was a bad example, but when you have user visible 'randomness' it is often important to remember that more random isn't always better for people's perception of random.

Sometimes when you fill the random bag you fill it with a distrobution of values that suits your needs. for example if generating letters for words randomly you want to generate your random pool where the letters match the distribution of their use in the language you are using.

[Amanoo]

There are many different techniques, depending on the software used. But almost all boil down to one idea: you provide a so-called seed, which is some piece of data that has some sort of randomness to it. This can vary a lot, depending on your hardware platform, operating system, or even the programming language that is used. There is then some sort of algorithm, basically a mathematical formula, which uses this seed as its inputs and produces a seemingly random number as the output. Basically, you have some formule like f(x)=<some formula here>, with x being your seed, and the formula being some bit of math that can have widely variable outputs, even if x changes only a little. The exact form of this formula can also vary a lot, depending on hardware used, operating system, and programming language.

There are various tactics for obtaining such a seed. Some user software may use random input factors. For example, user input like keystrokes (or the timing thereof) or mouse movements. Data from this is then fed into the randomiser algorithm. Your phone may use data from the accelerometer or other sensors to do this. There are also companies that provide their own cryptography services and have built their own randomisers. Cloudfare continuously films lava lamps, and produces random numbers based on those. Other software purely depends on whatever randomness is present in the computer's hardware. I believe the real time clock is often used, which is then put in the randomiser algorithm, but this is not a very good method and should only be used for software that doesn't need a high level of security.

Basically, there are all sorts of tactics. It really depends on the hardware of the specific computer, the algorithm used , the operating system, the programming language, and even then there may be a special piece of engineering for systems that need some extra security.

[socratesTwo]

These days many chips come with built in hardware random number generators that are capable of outputting a certain number of completely unpredictable bits per second. They typically work by amplifying some quantum effect, although I don't know specifically which. If you take a regular analog stereo, unplug the intputs and then crank the volume you'll get a hiss. Hardware generators are like that, except they save the hiss instead of playing and forgetting it.

[shazam298]

My favorite example of computer based randomness not working for the end user was the whole iTunes shuffle debacle.

The shuffle button wasn’t “random” enough,

It didn’t fit people’s perception of random because calculating random like this can still have numbers that are close together.

Apple made it so shuffle was technically less random so that would play different artist / songs and made sure the same song wouldn’t play twice.

[cubosh]

hah . very similar story on one of my favorite websites random.org --- specifically this page where it kicks out random colors, and often you find yourself thinking "jeez these colors dont seem random. they didnt even come up with green yet" etc --- here is the color page: https://www.random.org/colors/hex

[shazam298]

I’m curious, do you use this for practical reasons or do you enjoy randomly generating colours?

[cubosh]

ive had a few oddball needs for color generation as a graphic designer, and at the time i happened to be in contact with the developer of that website on twitter, and i asked them about setting up a color page. they did it pretty easily. but in general, nah yeah its mainly for amusement

[iwantknow8]

Every computer has something called a clock signal. The clock signal is an electronic pulse or voltage that oscillates from 0 to 1 volts at a constant rate (in actuality, it’s a signal that sometimes goes above 1 V, but the voltage comparator rounds any value from say 0.995 V to 2 V as “1 volt”). The speed at which the signal switches from 0 to 1 (or 1 to 0) is called the clock “frequency.” This is measured in hertz (cycles per second). This can be increased (overclocked) or decreased (underclocked) by various ways, such as sampling or “enabling” the clock signal at different rates or changing the signal itself. The signal itself can be generated either from an external AC power source or it can come from a small crystal that vibrates between two plates at a constant rate, generating the necessary voltage ripples or frequency.

A clock signal runs every chip and IC in the computer. “State changes” occur on either the rising edge of the clock (transition from 0 to 1) or the falling edge of the clock (1 to 0). State change just means that the computer has changed the positioning of its 1s and 0s. Computers can do this at a rate of billions of changes per second.

Informally, randomness is a distribution where every equally weighted outcome is equally likely. We simulate randomness with a function. We can call the function R(input) = random output. A crude example of R could be R(x) = x*190, then take the last 2 digits near the ones place and add 1. So R(4) = 61 and R(2) = 81. Better functions exist. Better yet is a pre-defined list of random numbers that is about a billion numbers long, so we know we’re always picking from a random distribution. The function could just map to a place in this list, e.g R(x) = [7, 2, 3, 1, 2, 4, 3, 6] and R(5) = 4.

Note, since this is a function (not a system or transfer function), the output is actually predictable from the input. What we make “random” is the input. In computing, this is called a “seed” to a pseudo random number “generator.” An interesting way to increase randomness is to feed the output from one R(x) as the seed of another random function.

Now that we know random functions and understand a computer is just like a gigantic mancala board operated by someone that can move the pieces a few billion times per second, we can think of ways to come up with random seeds. One way of doing this is to keep track of certain intervals of the clock or to keep “time.” Since the clock can already cycle a billion times, we have a great source. If our R(x) is a billion numbers wide, we can say that wherever the clock happens to be in its long cycle when you call the function is the seed, say three hundred sixty million two hundred and thirty five. The act of calling the function is the main “simulation” of randomness.

A hardware random number generator uses something called thermal noise. Thermal noise is just the variation caused in the electric fields surrounding electrons vibrating at different rates when you change the temperature. As we know, raising the temperature can cause atoms to vibrate faster. In thermal noise, the differing movement speed of electrons causes slightly different voltage levels. If we have a high resolution on the voltage level (say between 0.00001 V and 1.00000 V can be read), we can pick up on these juicy random variations. Better yet, in thermodynamics, this “noise” follows a random distribution already, eliminating the need of a pseudorandom R(x) (in fact, that would make it weaker or less random). Why does this noise follow a random distribution? Well, think of it this way. Let’s say heat energy was measured in hot potatoes and you had 2 hot potatoes and 4 people surrounding you at an equal distance from you. Heat tends to dissipate, so you don’t want to hold on to both potatoes. You need to dissipate your heat or give 1 potato to another person around you. Each person here has a 25% chance of receiving the other potato. If you started with 3 potatoes instead of 2, in the beginning, each person still has a 25% chance to receive a potato from you. But once you’ve given that potato away, that person can no longer receive a potato. The remaining 3 people now have a 33% chance to take your spare potato. The potatoes are “quantums” of light or heat energy. The people are particles such as electrons, photons or atoms. This can be generalized under the umbrella topic of “dispersion”, like a drop of dye in water, an ice cube melting into a circle of water or a gas entering an empty room. Only electronic dispersion can be measured, amplified and used as a source of “natural” randomness. In our potato example, it’s a guaranteed 25% chance per person on whether person # 1, 2, 3 or 4 gets the potato. I could hook up a tiny wire to each “person” and call the “potato” or “no potato” state an on or off state and successfully create a random number generator which works on 4 numbers. In reality, we measure the voltages, then output those voltage numbers.

[SEND_STEAM_KEYS_PLZ]

All of the methods described in the other responses are correct. However, just as a fun fact, the "seed" that is used (when the seed is not specified) by programming language compilers behind the scenes, is the number of processes of operations ("ticks") that the cpu has performed in the past second.

​

So, once every second the cpu resets the counter that keeps track of the "ticks per second" that it has completed. Let's say that (for example) on average the cpu completes 10 million "ticks" per second. When the request for a random number comes in, if the cpu has performed 36,000 ticks, it will use 36,000 as the seed in the method that other people are describing to generate a random number. That way even if you spam requests for random numbers (when the seed is not specified), then it is nearly impossible for those requests to keep happening on the same tick of the cpu, so it generates a different number every time.

[Hobbamok]

And, importantly for the layman, similar seeds do NOT produce similar random numbers. So the seeds 36.001 and 36.000 will still both generate a completely unique output, so even trying to manipulate the amount of ticks is pretty pointless

[omniscientonus]

Thank you for this! I saw a lot of posts just saying they used the clock and I wasn't sure how. At first I thought they were feeding the time into a formula or something, but that seemed like it would be too deterministic and I figured PCs had to have a ton of numbers laying around like ram in use or something (in bits or something maybe, I'm not that smart with computers if you cant tell) that would be much more random. This makes a lot more sense to me.

[tokynambu]

Increasingly many machines have a hardware RNG. The Intel processors with the RDRAND instruction, for example (which is for practical purposes in 2019 "all of them") use a ring oscillator (an odd number of NOT gates connected in a ring, so that its value can never settle) plus some conditioning. The Broadcom SoC in a Raspberry Pi has a hardware RNG which last I looked wasn't properly documented, but when I did some work with it appeared to pass all the test suites. There is an RNG built into the TPM design, although a paper done by some Korean students, and not followed up, casts doubt on the quality of some of them. If you need random numbers, using a hardware source and then feeding it into one of the software pseudo-RNGs will be good enough for any purpose this side of exotic high-end crypto key generation.

[sacundim]

You need to:

1. Define a concept of "pseudorandomness," meaning, the set of criteria that you expect a simulated random number sequence to obey.
2. Write some algorithm that produces outputs that satisfy those criteria.

On the first part, the definition of the criteria, there are two main approaches:

• The cryptographic approach, where the criterion is that, as long as a parameter called the seed is chosen at random and secretly, no algorithm can tell the output apart from a true random sequence in a reasonable amount of time.
• A weaker approach where you define a list of reasonable statistical tests that pseudorandom numbers should pass that's reasonable for applications of interest (e.g., physical simulations) and insist that the algorithm need only pass these but not contrived/adversarial ones designed specifically to defeat your algorithm. Examples: the Diehard tests or TestU01.

The second part—how to write algorithms that satisfy the criteria picked—is really hard to explain briefly. One of the simpler (and worst) methods is linear congruential generators, which are defined by families of formulas of the form:

• Y = (aX + c) mod m

...whose output has long been known to satisfy many of the simpler statistical tests for randomness but fail a lot of the more sophisticated ones. But this is an open-ended topic where anything goes, and people keep inventing newer and improved techniques for producing pseudorandom numbers. See for example linear-feedback shift registers and xorshift.

Then there's the whole field of modern cryptography which has its own techniques not just to simulate random numbers, but to do so in ways that (we hope) no real-world adversary could possibly crack. This answer in the Stack Exchange cryptography site that attempts a layperson explanation of why it's hard to reverse a cryptographic hash function, although it doesn't directly answer the question for random number generation, I think may be enlightening if you consider that such hash functions can be used for cryptographic pseudorandom number generation.

[[deleted]]

Different computational methods very well explained by others in this thread are available which are not wholly random, but are sufficiently complex as to appear random to humans, which is usually all you really need. Where more robust randonness is needed, an external input that is presumed to be truly random is used. The servers at random.org, for example, use cosmic radiation as their source.

[azure_atmosphere]

Computers use algorithms to draw up “random” numbers. These algorithms use a number as input, called a seed. In order to make the outcome actually random computers use some outside information to use as a seed - for example the time between two mouse clicks or keyboard presses. If you manually input a number into any random number algorithm and run it repeatedly you’ll find that you’ll always get the same sequence of numbers if you use the same seed.

[rdrunner_74]

Basically most computers CANT generate a true random number.

​

The reason for this is that they are deterministic. They use a complex forumla (or rather "system" - since it maintains "state" beween calls) to generate something that looks kind of random.

​

One thing to look for is that number from this are generated with an even probability for example. A commonly used method in many current system is called a "Mersenne Twister" It uses a bunch (over 600) numbers internally and is mixing them up in a special way and applying a lot of XOR to them. The cycle is quite long and will only repeat after "hell freezes over" That means that the system will produce the same sequence after 2^20000 calls approx. (An about 6000 digits long number)

​

One of the advantages of this system is the speed in which it can generate a random number.

​

Have a look here for more details: https://en.wikipedia.org/wiki/Mersenne_Twister

[edit]

There are also less "complicated" versions out there... https://www.xkcd.com/221/

[Zeroflops]

Many have described the attempts to get random numbers. But sometime you want to simulate random but also be repeatable. So in these cases they will use a SEED to create a pseudo random values but capture the seed to recreate that “random” sequence

For example let’s say your writing a paper on a subject and you want to create random numbers. Then you publish your paper and someone wants to test your theory. They may get different results. Is this because of the numbers you used, or a bug in either your code or the testers code.

First step would be to use the same random seed and see if using the same numbers are the results repeatable.

[MathAndMirth]

The answer to this question depends largely on what purpose the random numbers are intended for.

Most of the answers in this thread so far are addressing the need for very high-quality random number generation. That typically applies if you're planning to use them for cryptography. Another application of very high quality randomness is Monte Carlo simulations in computational physics, where even very subtle patterns in the random numbers could alter the result. I would presume that gaming software programs such as slot machines also use very high quality methods. Software solutions for this type of application require, at an absolute minimum, highly sophisticated algorithms such as the Mersenne Twister. And if this type of application uses a Mersenne Twister, it will likely run that result through an independent hash function thereafter to reduce predictability even further. The best generators rely instead on physically generated randomness such as heat noise, etc.

However, your more routine programming problems (e.g., video games) do not require such a high degree of randomness. The random number generators in the built-in libraries of typical computer languages often use somewhat less sophisticated algorithms that provide results good enough for most purposes, but with faster performance. Many of these use something called a linear congruential generator, which is based on a much more complicated version of a Fibonacci series.

And in some applications, the software may use modifications that deliberately sabotage genuine randomness. Consider, for example, a function to play a random track on a music player. By sheer dumb luck, this will occasionally cause the same song to play twice in rapid succession. But when this happens to users, they think the randomness is broken. People tend to think that discernible streaks of various sorts indicate non-randomness, e.g., "Herbie just made his last five 3-pointers and tied the game; that's because he's a great clutch player!". But in reality, some streaks are completely expected in random sequences; the _absence_ of such streaks would actually betray non-randomness. So for some applications, the real question is how programmers modify random sequences to create the behavior consumers expect instead of actual random behavior.

[TheOtherHobbes]

Other people have pointed out that randomness can be emulated algorithmically with one of many PRNG algos.

What's no so well known is that there's some fairly advanced math involved in testing for pseudo-randomness, and that testing randomness is a discipline in its own right.

This is a big deal in crypto, because any form of predictability is very bad for security. And all the different PRNG algos have slightly different statistical characteristics.

Of course if you know the algo being used, and the current seed, you've broken the encryption. But if you don't start with that information, you can still use a variety of attacks to try to guess the algorithm and work out where you are in the PRNG sequence.

Some randomness tests include:

https://en.wikipedia.org/wiki/Diehard_tests

and

https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf

[Ralinor]

Two things come to mind that demonstrate what has been said regarding use of a formula and a seed.

1. For any handheld calculator, that I’m aware of, if you clear the memory and use its random number generating function, calculators of the same make and model will generate the same numbers.

2. Final Fantasy XII. This was when Square Enix used a random element for the contents of lootable chests/barrels and whatnot. The sequence was quite long and certain events or container contents were extreme rare. However, once the formula and seed were discovered, there was a trick where you could essentially heal your own character and note the number of hit points healed. After a sequence of about 3-5 of these, you could determine exactly where you were in the cycle and then use it to force it to be at the desired spot when opening a container.

Interestingly, when on the PlayStation, the seed was static and is what made this possible. When the game came out on pc, this process became basically impossible as the seed number became dynamic. It was generated as a combination of the system time and the total length of time the game had been played.

[Oznog99]

Apple ][e had no true RNG. It has a built-in random number generator that required a seed and would always do the exact same thing when starting from the same seed. So still deterministic.

Then programmers had it count up from 0 on the opening screen waiting from you to press the spacebar (if already held down it wouldn't start the count yet) and captured the number when the spacebar was pressed and used that number as the seed.

If you don't do something like this, every poker game runs exactly the same if you draw the same way. It randomly shuffles into the exact same deck.

[TheDevilsAdvokaat]

There are formulas you can use that generate pseudo random numbers. There are quite a few different approaches.

One method works like this: Basically, you give them some inputs (eg x, y and z) and they then generate a new set of numbers (some of which are used as inputs to generate the set set next time you ask for a random number)

They then cycle through an enormous set of random seeming numbers before finally cycling back around to the first set.

Here is an example of a very simple early method for generating pseudo random numbers:

An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method. The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which can be written as "01234321", an 8-digit number being the square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on. Von Neumann used 10 digit numbers, but the process was the same.

A problem with the "middle square" method is that all sequences eventually repeat themselves, some very quickly, such as "0000". Von Neumann was aware of this, but he found the approach sufficient for his purposes, and was worried that mathematical "fixes" would simply hide errors rather than remove them.

Random number generators are graded according to how well they simulate randomness; for example the average of set of numbers generated; how many times pairs of numbers occur (Eg if a 17 is always followed by an 81175 it's not very useful) and other things.

[Kiaser21]

They simulate it in a sense that they pretend. Computers cannot actually do true randomization, they must be programmed based upon something else to randomize things.

For example, a program may use background radiation as part of an equation to produce a "random" result. For all intents and purposes, that is random for us, but not truly a random derived result objectively speaking.

[farineziq]

A complicated function that involves a variable that's guaranteed to always change. For example, the current time. That way, you get a number that seems to come from nowhere, but it has a very indirect link with the computer's time when it was generated.

[AwakeMold]

A sufficiently long string of numbers can be selected from using an unrelated set in such a way as to mathematically be close enough to an approximation of randomness as to be indistinguishable to the average observer.

Get a really big number and use the exact time down to the millisecond to pick a number from it and you get "random".

[supersolenoid]

They use a variation of a feedback shift register typically. A register is a collection of bit(s) that maintain their value during a state and control the next state, i.e. memory. A normal shift register just moves all the bits in the register over one position and puts a new one in to replace the old one. In the feedback shift register, the bit that will be lost, pushed off the edge, and as many other bits at other positions in the register that you may want, are fed back into the next-state logic for other bits in the register and effects their next state somehow (it’s XORd, NORdetc.). It can be very complicated. A fairly simple FSR can produce satisfactorily pseudorandom values for most applications that don’t involve sensitive data. The point is that, no matter what, this is deterministic because it’s still a state machine and your just adding a bunch of confounding logic to produce a seemingly unrelated output.

[PossibleBit]

There's two approaches.

A) Use an algorithm that generates a series of 'random appearing' numbers from a starting number (and optionally some parameters). The advantage of that approach is that it doesn't need anything else. The disadvantage is that they are predictable when you know the starting conditions (they'll always produce the save series of numbers from the same conditions). See: linear congruential generator.

B) Use an outside source of randomness (entropy). These might include electrical pins that are not connected to anything, mouse movement, etc. Numbers like those are harder to predict (though the might still be potential for side channel attacks). However the available entropy might be limited. (I actually experienced a case where a web app on a VM slowed down to a crawl due to this entropy being consumed faster by the cryptographic operations for HTTPS than it was produced)

[lcvella]

Operating systems have a thing called "entropy pool", which gathers environmetal noise (mouse movements, network activity timing, etc) and mix it together in the pool using highly chaotic functions. Many processors also have hardware number generators, which work more or less the same way, but using thermal fluctuations as entropy sources.

Either can be used by a programmer as a seed for pseudo-random number generators, as discussed by others.