4
$\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?

Improve this question
$\endgroup$
5
  • $\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
    Commented Mar 24, 2015 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
    Commented Mar 24, 2015 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
    Commented Jul 27, 2015 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
    Commented Jul 28, 2015 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
    Commented Jul 28, 2015 at 18:59

2 Answers 2

Reset to default
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.

In my opinion, the only technically² 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 at startup of a FIPS 140-2 device.

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.

¹ By general-purpose I mean intended as detecting any deviation from true random, with acceptance level set accordingly. This includes NIST SP 800-22 rev 1a.

² Getting rubber-stamped is a justifiable goal in itself.

³ Detecting gross malfunction is a justifiable goal at some design stage. Validating the design of a cryptographic gizmo (or worse, algorithm) primarily on the basis of the absence of detection of gross malfunction is poor methodology.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I only asked @fgrieu as Fermilab's Hotbits champion it as one if their tests. $\endgroup$
    – Paul Uszak
    Commented Jul 30, 2015 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 ♦
    Commented Jul 30, 2015 at 5:31
  • $\begingroup$ @fgrieu, Is "is to detect gross malfunction" also true for 800-22? $\endgroup$
    – Pacerier
    Commented Jan 29, 2020 at 12:45
  • $\begingroup$ @Pacerier: in my opinion, yes, specifically because NIST 800-22 rev 1a uses acceptance level aiming a detecting anything not perfectly random, thus falling into the between Scylla and Charybdis 1/2 dilemma in the question. That's now explicit in the added notes. $\endgroup$
    – fgrieu ♦
    Commented Jan 29, 2020 at 16:38
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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