patternMinor
Distribution of Ones in a Psuedorandom Sequence
Viewed 0 times
onesdistributionsequencepsuedorandom
Problem
Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?
Solution
Yup, it's possible. This generator is easily broken, as each output bit has degree only two. There's an efficient algorithm that, given the first $n$ bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.
Let $x_1,\dots,x_{128}$ denote the initial state of the first LFSR and $x_{129},\dots,x_{256}$ denote the initial state of the second LFSR. Then every bit produced by your generator can be expressed as a multivariate polynomial over $x_1,\dots,x_{256}$. The degree of this polynomial is two: each monomial is of the form $x_i x_j$ or $x_i$. Here were are working in the finite field $GF(2)$, i.e., working modulo two. In this field, the AND of $x_i$ and $x_j$ is the term $x_i x_j$ (the product). It follows that the output of the generator is a polynomial of degree two. (Why? Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p_1(x_1,\dots,x_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p_2(x_{129},\dots,x_{256})$ of degree one. Now the output of the generator is the AND of these two, i.e., it is the product $p_1(x_1,\dots,x_{128}) p_2(x_{129},\dots,x_{256})$, which is a polynomial of degree two.)
So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x_1,\dots,x_{256}$. If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x_1,\dots,x_{256}$. At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.
How do you solve the system of linear equations? One simple approach is linearization: if $n > 256^2/2$, then you can replace each monomial $x_i x_j$ by a new unknown $y_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination. If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough. (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.) For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.
To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher". For instance, you could use AES in CTR mode (counter mode). This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.
By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.
Let $x_1,\dots,x_{128}$ denote the initial state of the first LFSR and $x_{129},\dots,x_{256}$ denote the initial state of the second LFSR. Then every bit produced by your generator can be expressed as a multivariate polynomial over $x_1,\dots,x_{256}$. The degree of this polynomial is two: each monomial is of the form $x_i x_j$ or $x_i$. Here were are working in the finite field $GF(2)$, i.e., working modulo two. In this field, the AND of $x_i$ and $x_j$ is the term $x_i x_j$ (the product). It follows that the output of the generator is a polynomial of degree two. (Why? Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p_1(x_1,\dots,x_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p_2(x_{129},\dots,x_{256})$ of degree one. Now the output of the generator is the AND of these two, i.e., it is the product $p_1(x_1,\dots,x_{128}) p_2(x_{129},\dots,x_{256})$, which is a polynomial of degree two.)
So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x_1,\dots,x_{256}$. If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x_1,\dots,x_{256}$. At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.
How do you solve the system of linear equations? One simple approach is linearization: if $n > 256^2/2$, then you can replace each monomial $x_i x_j$ by a new unknown $y_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination. If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough. (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.) For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.
To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher". For instance, you could use AES in CTR mode (counter mode). This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.
By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.
Context
StackExchange Computer Science Q#40840, answer score: 3
Revisions (0)
No revisions yet.