2
$\begingroup$

I am working in Python and created a B.B.S. implementation that outputs a sequence of pseudo random positive integers into a Python list. I would like to write this data to a binary file and pass it through ENT and Diehard to see how well it does, but I have no idea how to properly do this.

So far I have been writing these pseudo random sequences in python lists into binary files with the struct package, but even PRNG's like B.B.S. are horribly failing these tests, so I know I must be writing the data to the file incorrectly.

Would anyone be able to tell me the correct way to write a pseudo random sequence of integers of form [85285422, 1065539406, 1143357354, 812899410, 796171749, 531684531, 771767949, 527982099, ...] in a python list into a file for testing with ENT and Dieharder?

$\endgroup$
0
$\begingroup$

I would like to write this data to a binary file and pass it through ENT and Diehard to see how well it does

To test how well something does, we must have a definition of "well". For a RNG, that's almost universally: outputs independent uniformly random elements of some discrete set. That set is often integers in $[0,m)$ for some $m$. ENT is designed¹ for that with $m=2^8$, thus the set of all the possible bytes. Diehard(er) can test that too, that's what /dev/urandom outputs, and it's my suggestion.


The question's sequence is as obtained by²: $x_{i+1}\gets{x_i}^2\bmod1232592891$. That's against the security rationale of the Blum Blum Shub generator, which asks that

  1. Only a few low-order bits of $x_i$ obtained by $x_{i+1}\gets{x_i}^2\bmod n$ should be output.
  2. $n$ is a hard to factor integer³, implying that $n$ has at least 500 bits and it factors at least 150 bits for even mild hardness.

We can initially ignore the second issue. For the first, we can take few as 8 bits, that is reduce each number produced modulo 256, before writing each result as an individual byte in a file opened in binary mode with open. Or take it as 1 bit, reducing modulo 2 and grouping 8 consecutive bits in oen byte. In both cases, that's discarding most of the data, but that's a necessity to have a passably random-like sequence.


It's interesting to learn how to make a generator that pass ENT and Diehard(er). Importantly, one should realize that a statistical test can't validate a RNG, only invalidate it. If such test consistently yields a fail result, then the sequence tested has some serious defect⁴. But if it yields a pass result, that does not validate the cryptographic quality of the sequence. It is plain impossible to do this from the sequence. What generates the sequence must be examined.


¹ With the caveat that ENT's main test is insensitive to the order of the bytes in its input: it does not even try to assess the "independent" part of "independent uniformly random elements of some discrete set".

² That recurrence predicts the next value all over the sequence. I inferred it form from the question's "B.B.S." and the fact that the output values looked like 10-digit decimal integer with first digit either 1, or 0 and suppressed. I found the modulus by computing $\gcd({x_{i+1}}^2-x_i,\ {x_{i+2}}^2-x_{i+1})$ for various $i$ in the output sequence, then dividing by 2.

³ The modulus $n$ can be public, that's the salient feature in the construction.

⁴ Alternatively, the test was misused or is defective.

$\endgroup$
0
$\begingroup$

Blum Blum Shub requires larger parameters for security than parameters that are typically suggested for factoring (or QR). See this answer for references.

The short of it is that there are likely no issues with using struct, but that you likely need to use a modulus of $\approx 6800$ bits and extract no more than $5$ bits per iteration to a concretely secure PRNG from BBS.

$\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.