Geek Answers Handbook

I can not understand this simple pseudo-random generator from Schneier in 1992

Schneier posts posts 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.  */
}

And ends with a warning about blindly choosing a different feedback sequence. To avoid getting out of such dead ends, I read the LFSR and the polynomials that define them.

One place, http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm is kind enough to list polynomials of maximum length against many taps (which are shortened for clarity as more taps become an option). For 32-bit LFSR, I don’t understand where Schneier gets its polynomial from:

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

wikipedia 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);

:

[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);

XOR'ing ( ) 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 , , .

+4
2

. .

1 LFSR 107 359 437 . , 4 , 32 LFSR. .

, LFSR 0 , 1 , .

, , - Schneier - , .

, LFSR . ARCFOUR , , Shneier, , , . . : -)

0

[32, 7, 5, 3, 2, 1, 0] ( 16.2 , ).

#include <cstdio>

// regA should be initialized with some random n0n-zero value.
static unsigned long regA;

int rand_bit()
{
    int length = 32;
    regA = (((
          (regA >> 7)
        ^ (regA >> 5)
        ^ (regA >> 3)
        ^ (regA >> 2)
        ^ (regA >> 1)
        ^ (regA >> 0))
        & 0x00000001)
        << (length - 1))
        | (regA >> 1);
    return regA & 0x00000001;
}

int main()
{
    const unsigned long start = 0x00000001;
    regA = start;
    for (unsigned long c = 1; ; ++c)
    {
        int bit = rand_bit();
        //printf("%d\n", bit);

        if (regA == start)
        {
            printf("%#010x\n", c);

            break;
        }
    }

    return 0;
}

[32, 31, 30, 29, 5, 1] ​​ http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/32stages.txt, rand_bit. , Schneier [32, 31, 30, 29, 5, 1, 0].

int rand_bit()
{
    int length = 32;
    regA = (((
          (regA >> 31)
        ^ (regA >> 30)
        ^ (regA >> 29)
        ^ (regA >> 5)
        ^ (regA >> 1)
        ^ (regA >> 0))
        & 0x00000001)
        << (length - 1))
        | (regA >> 1);
    return regA & 0x00000001;
}
0

More articles:


All Articles