伪随机数生成器

源于某一道赛题，明年可以作为招新题出

随机数

随机数分为真随机数和伪随机数，我们程序使用的基本都是伪随机数，其中伪随机又分为强伪随机数和弱伪随机数。

真随机数，通过物理实验得出，比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等。需要满足随机性、不可预测性、不可重现性。
伪随机数，通过一定算法和种子得出。软件实现的是伪随机数。
强伪随机数，难以预测的随机数。需要满足随机性和不可预测性。
弱伪随机数，易于预测的随机数。需要满足随机性。

只要这个随机数是由确定算法生成的，那就是伪随机。只能通过不断算法优化，使你的随机数更接近随机。

有限状态机不能产生真正的随机数的，所以，现代计算机中，无法通过一个纯算法来生成真正的随机数，无论是哪种语言，单纯的算法生成的数字都是伪随机数，都是由可确定的函数通过一个种子，产生的伪随机数。

这也就意味着，如果知道了种子，就可以推断接下来的随机数序列的信息。这就有了可预测性。

常见种类及攻击方法：

线性同余生成器，LCG

特征：$x_{n+1}\equiv(ax_n+c) \pmod n$

经典（去年招新题）：

class PRNG1(object):
    def __init__(self, bits):
        self.n = random.getrandbits(bits)
        self.a = 0
        self.b = 0
        self.s = 0
        while not (self.a < self.n and self.gcd(self.a, self.n) == 1):
            self.a = random.getrandbits(bits)
        while not (self.b < self.n and self.gcd(self.b, self.n) == 1):
            self.b = random.getrandbits(bits)
        while not (self.s < self.n and self.gcd(self.s, self.n) == 1):
            self.s = random.getrandbits(bits)
		#对参数的随机化
    def gcd(self, a, b):
        while b:
            a, b = b, a % b
        return a

    def next(self):
        self.s = (self.a * self.s + self.b) % self.n
        #核心：s2 = a*s1 + b
        return self.s

java的random类：

protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

安全性非常得差，只要知道连续几个就可以直接推出整个序列，而且序列是循环的

分析和攻击方法：

先求n，只要稍作变形就可
$$
\left
{\begin{aligned}
t_0 & = s_1-s_0&\pmod n\
t_1 & = s_2-s_1=a*(s_1-s_0)=at_0&\pmod n\
t_2 & = s_3-s_2=a(s_2-s_1)=at_1&\pmod n\
t_3 & = s_4-s_3=a(s_3-s_2)=a*t_2&\pmod n\
\end{aligned}}
\right
$$

然后进一步转化：

$$
t_1^2-t_0*t_2\equiv0\pmod n
$$

然后造出3个n的因数，取gcd后得到的数及其因子都是可能的n（然而很多时候就是n），要拿hint判

接下来我们干a

$$
\left
{\begin{aligned}
s_1\equiv s_0a+b \pmod n \
s_2\equiv s_1a+b \pmod n
\end{aligned}}
\right
\Longrightarrow
a\equiv(s_0-s_1)/(s_1-s_2) \pmod n
$$

然后a也有了，搞b

$$
s_1\equiv s_0a+b \pmod n
\Longrightarrow
s_1-s_0a\equiv b \pmod n
$$

然后b就搞出来了，一个一个地推就好啦

python&c++：梅森旋转算法

通常称为mt19937算法，MT 是 Mersenne Twister 的缩写；而 19937 则取自算法中用到的梅森素数$2^{19937}-1$，梅森素数是算法生成伪随机数的循环长度（period)，而旋转则说的是算法内部对定长二进制串循环位移的过程。

特征：比特位移动后进行&运算

unsigned int Rand()
{
    if(!isInit)
        srand((int)time(NULL));
    if(index == 0)
        generate();
    unsigned int y = MT[index];
    y = y ^ (y >> 11);                 //y右移11个bit
    y = y ^ ((y << 7) & 2636928640);   //y左移7个bit与2636928640相与，再与y进行异或
    y = y ^ ((y << 15) & 4022730752);  //y左移15个bit与4022730752相与，再与y进行异或
    y = y ^ (y >> 18);                 //y右移18个bit再与y进行异或
    index = (index + 1) % 624;
    return y;
}

或者对其进行魔改（今年面试题&最近某比赛赛题）：

class func(object):
  def __init__(self, keys, num=0x1145141919810aaa):
      self.mask = keys		#用于&运算的mask
      self.seed = num		#随机种子，及伪随机数的第一位
      self.bits = [random.randint(-32, 32) for i in range(4)]		#位移的随机

  def shift(self, m, k, c):
      if k < 0:
          return m ^ m >> (-k) & c
      return m ^ m << k & c		#梅森旋转的核心步骤：位移+与

  def convert(self, m):
      for t in range(4):
          m = self.shift(m, self.bits[t], self.mask[t])
      return m		#做四次，其实做多少次都可以

  def getrandom(self):
      self.seed = self.convert(self.seed)
      return self.seed

分析和攻击方法：

首先运算的优先级是位移>&>异或

那就先拆开了看，先看不带mask的（左移右移是一样的）：

1	y0 = y ^ (y >> 11)

假设y是32位的，那这次运算后我们就失去了后21位的信息，但前11位留下了，把这11位与y0的12-23位做异或，就得到了y的12-23位，以此类推可以11位11位地推出信息，如此这个过程就逆完了

再看带mask的：

1	y = y ^ ((y >> 7) & 2636928640)

其实和上面是一样的，就是加了一个mask吓人

def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

xorshift RNG

原理是：$\beta$为一个n维的非零二进制向量(b1,b2,…,bn)，T为$\beta$的一个线性变换，则整个循环为$\beta$，$\beta T$，$\beta T^2$…

且该伪随机数序列的循环节为$2^n-1$。

特别的，当我们把T矩阵变成$(I+L^n)$，其中L是一个主对角线全1的对角矩阵，这个T在位运算上代表的操作就是y^(y<<n)，同理可知右侧

所以最经典的xorshift的变换就是$(I+L^a)(I+R^b)(I+L^c)$其实和梅森回旋是一个东西

这是一个更复杂的样例，用三维的矩阵去进行迭代，同时生成三个随机数：

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;

  tem = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (tem ^ (tem >> 8));
}

LFSR，和上面那个好像关系蛮大的

线性反馈移位寄存器：