Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method.
Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the following algorithm (C code is given below):
- Let
r = x1 ^ x2
(bitwise XOR; the "Fibonacci" step). - Rotate
r
to the right by 1 position. - Let
x1 = x2
andx2 = r
. - Output
x1
and repeat.
Question. Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?
Here's the C code:
#include <stdio.h>
unsigned rotate (unsigned n, int len);
// len == length of rotation (number of bits rotated)
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len);
// ---------------------------------
unsigned rotate (unsigned n, int len) // l == length
{
unsigned b = n & 1; // get right-most bit
n = n >> 1;
n = n | (b << (len-1));
// insert right-most bit at left end
return n;
}
// ---------------------------------
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len)
// Fibonacci XOR and then rotate
{
unsigned result = n1 ^ n2; // "Fibonacci" step
return rotate(result, len); // "Scramble" step
}
// ---------------------------------
int main()
{
int i = 0;
unsigned x1 = 0xd; // seed 1
unsigned x2 = 0x80; // seed 2
unsigned h; // helper variable
int my_len = 8; // length of rotation, here: 8 (-> byte length)
while (i < 100)
{
printf("%x,", x2);
h = x2;
x2 = fibo_xor_rotate(x1, x2, my_len); // fibo xor rotate
x1 = h; // set x1 to "old" x2
if (i % 10 == 9) {
printf("\n"); // newline after 10 prints
}
i++;
}
return 0;
}