A truly random number

The answer to your question depends on what exactly you’re asking. What is “true randomness”. Is this 256-bit number random?

  • 58591fac78884996c807a983513e3a4ff49cb90895035a6b1b7f05541b8b754b

There's no obvious pattern to the bits and if I don't tell you the algorithm that made it, you'll not be able to figure it out. (It's actually the SHA-256 cryptographic hash of your question!)

Cryptographic hashes are, by design, deterministic algorithms that act as one-way functions, you can't tell from the number what input they came from and look like arbitrarily chosen (random) numbers.

So, if your algorithm is allowed to have input, cryptographic hashes provide your answer. It's not hard to provide good/not-a-priori-knowable input to a hash. If your phone has a camera, take a photo of the outside. Your phone's camera has millions of photon detectors, each of which at the mercy of random quantum phenomena. No two pictures of the same scene will be identical (especially if it's a tree blowing in the wind). Provide that as input to hash.

Or, if you don't have access to external inputs, you could look “inside the machine” for your input. On a Mac or Linux machine, this would work well for just about anyone:

  • (date ; ifconfig ; netstat -rn ; ps augxww ; w ; last) | shasum -a 256

Here's the result of running that ten times in quick succession on a Linux machine:

  • 9332c185d51a591d239cda5ad4ae0862cac7ac974a4e29a35ab5060eb3a0343e
  • b2f1d2b211436cbde4ab2597d87941de86b04c8cc0b33a24531d42f86d585a50
  • 8427a1bc97ea48ebe810456ae2c0112e5ab894c3266fe6bc4c3c70fa1943fbb3
  • 600011b9833c60f37a5f5a133c00ce1f7a6391f3d56f85cf9bfb0c62a359ca66
  • c553de11051a56b189387a1d09a47729c28b4f1c677da5ada1ce16fd38b0a474
  • 4de79cc25e30bd0ee01d93533fc9e58811e35d8810b27fe785c03b3f99f5373e
  • 09b29034b5226225c3b787f50f3e50dab664f37885611b5d5e15833481d43998
  • 8d10a3ebb3bca31dd8867f6c5e7a38a20e79cb90181522c2a2ee21d8b28abe81
  • e3a8a4b09a83be7046d33767f726ca9e4dcd0f95d9ca5b37acac0359661034ef
  • acd70a3dfbd69afaf026cbcbdd1e1f1aea9a0f3e48c98d35d6deddca5c242506

As you can see, different every time the output was different. The input only changed a little between runs (on Linux, more changed on OS X), but thanks to the avalanche property of cryptographic hashes, the entire output looks different.

Of course, modern operating systems do something similar-but-much-better internally and provide it to programs (via /dev/random on OS X and Linux).

But maybe you don't want your program to run any external programs or open any special files or devices like /dev/random. Because you can't always count on /dev/random existing (or C++'s std::random_device working correctly), my own randutils for C++ (a simpler variant of which is a proposal for C++17) provides seeding for C++ RNGs using only entropy that is “local” to the program being run (see the definition of the local_entropyin the code).

But if you want something that reads nothing (not even the time), it's possible to get “entropy from (apparently) nowhere” on modern systems. I like to pose how you can do that as a puzzle to students by just showing them a program that does it and asking them to figure it out. (I usually show it running on a Banana Pi, so that the hardware is cheap, entirely solid state and similar to what's in a phone or tablet).

Here's the results of six runs of the program, which is (tellingly!) called par-rand and takes no input (not the time, nothing from the internet, no special CPU instructions, no-files-or-devices read from, really no reading in of any kind):

1: 9335 loops, 599 interferences, 1 wins, 2 total
0: 788 loops, 598 interferences, 1 wins, 2 total
state: 2b92ab55794ea030f57f8d51a8ccee28e6

1: 964 loops, 623 interferences, 1 wins, 2 total
0: 807 loops, 620 interferences, 1 wins, 2 total
state: ba6b1a6915cc6f30424311b29ee6326d29

0: 1105 loops, 821 interferences, 1 wins, 2 total
1: 8873 loops, 821 interferences, 1 wins, 2 total
state: a41b809f1355b39f34e4b59ddffe009307

1: 81556 loops, 612 interferences, 1 wins, 2 total
0: 137418 loops, 610 interferences, 1 wins, 2 total
state: 7780375f5c371a44d06de7557724945b71

1: 795 loops, 665 interferences, 1 wins, 2 total
0: 1006 loops, 660 interferences, 1 wins, 2 total
state: cae55ec2b67b935016b950a20b1fa68fc9

1: 813 loops, 635 interferences, 1 wins, 2 total
0: 959 loops, 630 interferences, 1 wins, 2 total
state: cb7cbc42c539db54934e68eff1e99b007e

It usually puzzles people because their instinct is that “computers don't work like that”. But I'm sure reddit can figure it out!

(You can find more about randomness at www.pcg-random.org, including “True” Randomness vs “Pseudo” Randomness, Predictability, and Statistical Tests.)

/r/compsci Thread