bug in Random
- To: mathgroup at smc.vnet.net
- Subject: [mg47333] bug in Random
- From: Veit Elser <ve10 at cornell.edu>
- Date: Mon, 5 Apr 2004 05:23:50 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
There's a flaw in Mathematica's random number generator for large
integers that can have serious consequences in some applications. The
example below illustrates my point (I'm using version 5.0.1.0):
r = Table[Random[Integer, {1, 2^62}], {10^5}];
Union[Table[r[[i]] + r[[i + 24]] - r[[i + 20]], {i, 10^5 - 24}]]
{-2147483647, 1, 2147483649, 4611686016279904256, 4611686018427387904,
4611686020574871552}
We see that every combination r_i + r_(i+24) - r_(i+20) obtained from
the list of 10^5 numbers gives only six outcomes (1-2^31, 1, 1+2^31,
2^62-2^31, 2^62, 2^62+2^31) ! This only happens when the size of the
integers generated by Random[] is large. The onset seems to be near the
size used in the example, 2^62. There are other linear relations among
successive outputs of Random[], this seems to be the simplest.
I discovered this flaw when using Mathematica to generate instances of
the knapsack (subset sum) problem. The function Random[] was used to
generate a sequence of large integers r ("knapsack"), a binary sequence
x was chosen as the key, and the sum is given by r.x = s. In
cryptographic contexts the knapsack and sum (r and s) are public
information and the key (x) is private. The scheme is not secure if an
adversary can determine x from r and s. In the 1980s Lagarias and
Odlyzko found that when the number of bits in the knapsack integers is
sufficiently large in relation to the length of the knapsack, the key
could be found by a trick that involves using the LLL algorithm on a
suitably defined lattice basis. When I used this method on the
instances generated by Mathematica, I found that my knapsacks were
highly insecure: LLL could discover x even when the knapsack parameters
were such that the probability should have been extremely low. After
some experimentation the issue was resolved when it came to light that
LLL was discovering the linear relations of the kind described above.
The Mathematica documentation on random number generators mentions a
cellular automaton algorithm as well as subtract-with-borrow. I suspect
that this flaw is not intrinsic to either of these, but rather the
result of how large integers are assembled out of 31-bit pieces. It's
easy to eliminate the linear relations by reversing the base-10 digits
(since this scrambles the base-2 correlations, reverseDigits[x_] :=
FromDigits[Reverse[IntegerDigits[x]]]) but this is obviously not a
solution for cryptographic applications.
Veit Elser
Department of Physics
Cornell