不能完全理解 1992 年 Schneier 的这个简单的伪随机生成器

Question

Schneier 在 https://www.schneier.com/paper-pseudorandom-sequence.html 发帖:

int VERYRANDOM()  {
    static unsigned long regA, regB, regC;
    /*regA, regB, and regC should be initialized with some random value.*/
    regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
        & 0x00000001)<<31) | (regA>>1);
    regB = ((((regB>>30)^(regB>>2)) & 0x00000001)<<30) | (regB>>1);
    regC = ((((regC>>28)^(regC>>1)) & 0x00000001)<<28) | (regC>>1);
    /*regB is a 31-bit LFSR.  regC is a 29-bit LFSR.*/
    /*Both feedback sequences are chosen to be maximum length.*/
    return ((regA & regB) | (!regA & regC)) & 0x00000001;
    /*Above is equivalant to:  if A then return B else return C.*/
    /* Variants:  return ((regA & regB) | (regA & regC) | (regB & regC)) &
    0x00000001; Above variant returns the majority of A, B, and C.
    return (regA ^ regB ^ regC) & 0x00000001;
    Above variant returns the XOR of A, B, and C.  */
}

最后警告不要盲目选择不同的反馈序列。为了避免冒险走这样的死胡同，我阅读了 LFSR 和定义它们的多项式。

一处，http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm非常友好地列出了针对任意多个抽头的最大长度多项式(为了清楚起见，随着更多抽头成为一种选择，它被删减了)。对于 32 位 LFSR，我不明白 Schneier 从哪里得到他的多项式:

    regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
        & 0x00000001)<<31) | (regA>>1);

根据 LFSR 上的维基百科，等效多项式为:

    //Fibonacci x^1         x^26      x^28     x^30      x^31     x^32      
    regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
        & 0x00000001)<<31) | (regA>>1);

不在 table 上的:

[32, 31, 30, 29, 5, 1]
[32, 31, 30, 28, 27, 3]
[32, 31, 30, 28, 26, 13]
[32, 31, 30, 28, 23, 21]
[32, 31, 30, 28, 23, 18]
[32, 31, 30, 28, 20, 15]
[32, 31, 30, 28, 20, 3]
[32, 31, 30, 28, 19, 2]
[32, 31, 30, 28, 19, 1]
[32, 31, 30, 28, 17, 9]
[32, 31, 30, 28, 17, 4]
[32, 31, 30, 28, 17, 3]
[32, 31, 30, 28, 15, 5]
[32, 31, 30, 28, 14, 2]
[32, 31, 30, 28, 12, 9]
[32, 31, 30, 28, 10, 7]
[32, 31, 30, 27, 26, 9]

我不想在学习加密基础知识时误解任何东西，所以为什么我不明白这个？在尝试应用维基百科示例中的术语之前，我诊断多项式为:

    //                      25      27          29      30      31
    regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
        & 0x00000001)<<31) | (regA>>1);

但它是对(最左边的)MSbit 进行异或运算，然后下落不明，而且，奇数次抽头肯定是我错了。

多项式的维基百科翻译是:

    /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
    bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;

我猜 wikipedia 和 newwaveinstruments 使用不同的术语，但如果我不能破译它是什么，我就会忘记理解密码学。

Answer 1

哇。这段代码真的很糟糕。

当种子值为 1 时，第一个 LFSR 仅在 107,359,437 次迭代后重复自身。这远远低于最大长度 32 位 LFSR 所能达到的 40 亿次迭代。使用其他种子值，结果可能更糟。

事实上，由于其他两个 LFSR 在反馈循环中不包含位 0，因此将其中任何一个的值设为 1 将导致它们立即生成无限的零序列。

坦率地说，我很惊讶拥有 Schneier 证书的人可能会想出像这样垃圾的东西。

无论如何，LFSR 对于加密应用来说是完全没用的。 ARCFOUR 包含一个简单的伪随机生成器，它比 Shneier 的成果好得多，而且可能也快得多。但是不要去发明你自己的密码学方法。真的没有必要:-)