Fibonacci-XOR-rotate 是單向旋轉嗎？
使固定 $ n\in\mathbb{N} $ 和 $ n > 2 $ 並考慮以下方法。
挑選相對優質的種子 $ x_1, x_2 \in {0,1}^n $ （在哪裡 $ x_1, x_2 $ 被解釋為二進制數。然後繼續以下算法（C程式碼如下）：
- 讓
r = x1 ^ x2（按位異或；“斐波那契”步驟）。- 向右旋轉
r1 個位置。- 讓
x1 = x2和x2 = r。- 輸出
x1並重複。**問題。**給定未知數量的步驟後的一些未知種子輸出，是否“計算上難以”找到一對在若干步驟後產生給定輸出的種子？
這是C程式碼：
#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; }
這個過程的輸出位是 $ \mathbb{Z}_2 $ -輸入位的線性函式。具體來說，如果你寫 $ x_1, x_2 $ 作為位的列向量，則
$$ \begin{bmatrix} x’_1 \ x’_2 \end{bmatrix}
\left[ \begin{array}{cccc|cccc} 0 & 0 &\cdots & 0 & 1 & 0 & \cdots & 0 \ 0 & 0 &\cdots & 0 & 0 & 1 & \cdots & 0 \ \vdots &\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 1 \ \hline 0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 1 \ 1 & 0 & \cdots & 0 & 1 & 0 & \cdots & 0 \ 0 & 1 & \cdots & 0 & 0 & 1 & \cdots & 0 \ \vdots &\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \ \end{array} \right] \begin{bmatrix} x_1 \ x_2 \end{bmatrix} $$ 該矩陣是可逆的，這意味著您可以輕鬆地反轉過程的一次迭代。當然，您可以反轉任意數量的迭代。
實際的倒數如下。如果 $ x’_1 = x_2 $ 和 $ x’_2 = \textsf{rot}_R(x_1 \oplus x_2) $ , 那麼你已經有了 $ x_2 (=x’_1) $ 你可以計算 $ x_1 $ 作為： $$ \begin{align*} x’_1 \oplus \textsf{rot}_L(x’_2) &= x’_1 \oplus \textsf{rot}_L(\textsf{rot}_R(x_1 \oplus x_2)) \ &= x’_1 \oplus x_1 \oplus x_2 \ &= x_2 \oplus x_1 \oplus x_2 \ &= x_1 \end{align*} $$