多素数长度循环异或的安全性分析

First, let's break down your PRNG's behavior to make the analysis concrete, then address your question about how many outputs an attacker needs to start narrowing down future results.

Quick Model of Your PRNG #

From your description, here's how I'm modeling it:

• You have k arrays, each with a prime length p₁, p₂, ..., pₖ (all known to the attacker).
• Each array is pre-filled with fixed salt values (I'll assume bits for simplicity—adjusting for larger values like bytes is straightforward).
• The PRNG's internal state is just the current index pointer for each array: (i₁, i₂, ..., iₖ), where each iⱼ cycles from 0 to pⱼ-1 and wraps around.
• Each output is the XOR of the salt values at the current indices of all arrays. Then every index is incremented by 1 modulo its array length.

The total number of possible states is S = p₁ * p₂ * ... * pₖ—that's your "state size".

Now, the answer depends on whether the attacker knows the actual salt values in the arrays (a critical detail you didn't specify, so I'll cover both scenarios):

Scenario 1: Attacker Knows the Salt Arrays #

If the attacker has full access to the salt content of each array, this becomes a solvable linear algebra problem (since XOR is addition modulo 2).

Each observed output gives an equation linking the initial state to the salt values. For example, the t-th output is:
bₜ = s₁[(i₁ + t) mod p₁] XOR s₂[(i₂ + t) mod p₂] XOR ... XOR sₖ[(iₖ + t) mod pₖ]

Since the attacker knows all sⱼ values, they're just trying to find the initial index tuple (i₁,...,iₖ) that produces the observed output sequence.

How Many Outputs Are Needed? #

For well-chosen salt arrays (which yours must be, given it passes dieharder), the number of consecutive outputs needed to uniquely identify the state is roughly equal to the length of your longest prime array (p_max).

Why? Because each array's sequence repeats every pⱼ steps. Once the attacker has p_max outputs, they can test all possible initial index combinations for the shorter arrays against the longest array's cyclic sequence to find a match.

Relative to your state size S, this is a tiny fraction. For example:

• If you have 3 arrays with primes 101, 103, 107: S ≈ 1,112,121, but p_max = 107—so just ~0.01% of the state size.

Once the attacker finds the state, they can predict all future outputs perfectly.

Scenario 2: Attacker Does NOT Know the Salt Arrays #

If the salt values are secret, the attacker has to infer both the salt arrays and the current state from the output sequence.

Your output sequence is the XOR of k periodic sequences (each with period pⱼ). Since the attacker already knows the periods (the prime lengths), they can use techniques like autocorrelation or Fourier analysis to decompose the output into its underlying periodic components.

How Many Outputs Are Needed? #

To fully solve for all salt bits and the initial state, the attacker needs roughly the sum of all your array lengths (sum(p₁...pₖ)). This is because each salt bit and each initial index is an unknown, and each output gives one bit of information (for bit outputs).

Again, relative to S, this is a small fraction. Using the same example as before: sum(p₁...pₖ) = 311, which is ~0.03% of S ≈ 1e6.

Even before reaching this number, the attacker can start narrowing down possibilities. Each output eliminates some combinations of salt values and states that don't match the observed data—so after just a handful of outputs, the number of possible future sequences will be less than the total possible (though still potentially large).

Key Notes for Your PRNG #

While your design achieves a long period and passes dieharder, the linearity of XOR makes it vulnerable to these kinds of attacks. For cryptographic-grade security, you'd want to add non-linear operations—like using the output to modify the index increments (instead of just adding 1 each time) or mixing the indices in a non-trivial way. This would make it much harder for an attacker to reverse-engineer the state from outputs.

内容的提问来源于stack exchange，提问作者h2kyeong