3
$\begingroup$

Why do testing suites calculate $\pi$ (pi) using the Monte Carlo method to determine if a series of numbers are random? As far as I can tell, the Monte Carlo method can be used to estimate $\pi$ itself (as a numeric means of calculating it). It just so happens to use random numbers.

Why does it have to be $\pi$ if you're testing a numeric sequence for randomness? It seems that plotting random points inside and outside a circle to get $3.1415 \dots$ achieves exactly the same as plotting points inside /outside a triangle to get $0.5$. Is there something special about the circular shape pertinent to cryptography?

$\endgroup$
  • $\begingroup$ This is only very remotely related to cryptographic random number generators, but you're right: the circle is not inherently more useful for testing statistical randomness; it just happens to be one of the standard introductory examples for Monte Carlo simulations. $\endgroup$ – yyyyyyy Mar 24 '15 at 11:46
  • $\begingroup$ The point of computing an approximation to Pi compared to 0.5 is that Pi cannot be stored in a computer because it's binary notation doesn't terminate, whereas 0.5 is just written 0.1 in binary. $\endgroup$ – Florian Bourse Mar 24 '15 at 12:42
  • $\begingroup$ Not sure that's relevant. It's unlikely that you'd ever be testing a file sufficiently large that the resultant pi approximation wouldn't fit into a 64 bit variable. $\endgroup$ – Paul Uszak Jul 27 '15 at 22:49
  • $\begingroup$ I don't think that's relevant. But a 64 bit approximation is not nearly enough to estimate the quality of a RNG. If you think of applications which require a lot of random numbers (e.g. simulations), the required entropy might be higher. $\endgroup$ – tylo Jul 28 '15 at 18:21
  • $\begingroup$ @FlorianBourse the binary representability of the value being approximated is not relevant. Simpler tests like checking lsb or msb can be seen as a random estimation of 1/2. And of course the test must be able to evaluate how close the estimate is to pi, so it needs a sufficiently precise representation of the actual value. $\endgroup$ – bmm6o Jul 28 '15 at 18:59
7
$\begingroup$

Knowledgeable crypto practitioners do not calculate $\pi$ using a Monte Carlo method to determine if a series of numbers are random.

The test alluded to in the question is a general-purpose randomness test for random number generators with output a real number expected to be uniform of the range $[0\dots1[$. The test consists of drawing pairs $(x,y)$, and determining the proportion such that $x^2+y^2<1$, which should be about $\pi/4$ (because that's the area of the intersection of a square of side $1$ with a disc of radius $1$ and center in a corner of the square, and any subset of the square is expected to get a proportion of the random draws proportional to its area).

Variants of this test can be made for random number generators with bit or integer output, as used in cryptography. However this test is not particularly good, or often used.


Further, general purpose RNG tests are generally not very useful in cryptography:

  1. If applied to the output of a PRNG, such test will declare the RNG good including for cryptographically very weak and poorly seeded PRNG (such as a LFSR seeded with all 1).
  2. If applied to the output of a TRNG directly based on a physical phenomena (such as thermal noise filtered by removing the DC component, keeping polarity, and sampling at a relatively low frequency), many such general purpose tests will tend to fail due to minor bias in the conditioning circuitry, even though the TRNG is working as designed and perfectly usable after conditioning by a properly designed CSPRNG.

The only justifiable use of a general-purpose randomness test in a cryptographic context is to detect gross malfunction. The archetypal tests for that are the Monobit, Poker and Runs test formerly in FIPS 140-1 and FIPS 140-2; these tests are sound in principle, but had been specified to ridiculously stringent acceptance levels, making these tests usable only on the output of a PRNG, thus largely pointless (per 1. above). After a hiccup altering the acceptance levels, reason prevailed and these tests are no longer mandatory.

A sorry side effect of the above historical error is that the habit of running Monobit and Poker test sticks, hence designers of hardware TRNG strive to have their generators pass these tests to the most stringent levels, hence have an incentive to avoid exposing their inner entropy source before a fair amount of poorly documented conditioning. That makes it more challenging than needed to devise a good field test of the TRNG; that is, a test that reliably catches dangerous defects appearing in a deployed device (including purposely induced defects, e.g. when a Smart Card is cooled by evaporation of a liquefied gas in hope to literally freeze the TRNG), and do so without causing false alarms and/or permanently disabling perfectly good devices.

$\endgroup$
  • $\begingroup$ I only asked @fgrieu as Fermilab's Hotbits champion it as one if their tests. $\endgroup$ – Paul Uszak Jul 30 '15 at 0:01
  • $\begingroup$ @Paul Uszak: Generating random numbers, and testing them, is fascinating; that's the state of mind at fourmilab's hotbits. Their generator seems to be a high-quality, physically-seeded TRNG, with multiple statistical tests at the lightly-conditioned output, which is fine. However their use of the π-by-Monte-Carlo test is more an extra, simple demo that the thing works, for added confidence that there's no horrible goof, than a test designed for real use in fielded cryptographic devices. $\endgroup$ – fgrieu Jul 30 '15 at 5:31
0
$\begingroup$

I think that I've realised why you might calculate $\pi$.

It's easy: $x^2 + y^2 = 1$ is a simple calculation, thus fast. If you would pick another 2 dimensional shape with a non trivial perimeter, you'ld have a harder time estimating which side of the perimeter a point had fallen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.