Zohar's blog

Java - 学习与思考 Java 中的随机数与随机数生成器

JavarandomRNGPRNGjava randomSecureRandomRandomMath.randThreadLocalRandom

真正的随机数就像薛定谔的猫,你得去量子世界中才能寻找到

线性同余方法

Java 的 Random 类使用线性同余方法生成伪随机序列,是一个线性同余发生器。{线性同余发生器}(Linear Congruential Generator) 是 一种能产生具有不连续计算的伪随机序列的分段线性方程的算法,它代表了最古老和最知名的伪随机序列生成器算法之一,其理论相对容易理解,并且易于实现和快速, 特别是在可以通过存储位截断提供模运算的计算机硬件上。

定义

线性同余方法的基本思想是通过对前一个数进行线性运算并取模,从而得到下一个数。其循环关系定义为:

符号 范围 描述
  随机数列
模数
乘数
增量
初始值

时,为和同余法,当 时为{乘同余法(乘法同余发生器)}(Multiplicative Congruential Generator), 又叫{Lehmer生成器}(Lehmer RNG),当 时为混合同余法

生成伪随机序列

线性同余方法生成的产生的随机序列的均匀性和随机性取决于乘数、增量与模数。三者的组合可以多种多样,只要能保证有较好的均匀性和高随机性即可。

生成的随机序列最大周期为 m,即从随机数开始工作后,要生成一个已生成过的数,最久可以在 m 次后才生成。虽然最大周期为 m,但通常情况下周期都小于 m, 要使得周期达到最大,应满足 Hull-Dobell 定理:

  1. 互质;
  2. 的所有质因数都能整除
  3. 是 4 的倍数, 也是;
  4. 都比 小;
  5. 是正整数。

一个优秀的线性同余发生器应该做到:

  1. 是一个完整周期的发生器,即在产生重复前,能生产出 0 到 m 之间所有的数。
  2. 产生的序列看起来应当是随机的。

对于优秀的线性同余方法参数组合可以参考:TABLES OF LINEAR CONGRUENTIAL GENERATORS OF DIFFERENT SIZES AND GOOD LATTICE STRUCTURE

以上内容可以启发我们可以思考,线性同余法要做到随机与均匀分布,在于我们对特定的参数条件的选择。理想情况下,我们希望构造一个序列周期为 M,在周期内所有数字 仅出现一次,且数字出现的顺序足够随机。因此合格的随机数生成器必须是特定参数条件下的线性同余发生器

伪随机性

一方面线性同余发生器产生的随机数是可以预先确定的,并且是可以重复地生产和复制的;一方面该序列又具有某种随机序列的随机特性(即统计特性), 因此这种序列是伪随机序列。而此种伪随机数生成器就属于统计学伪随机数生成器

java.util.Random

Random 类是 Java 中较为常用的随机数生成类,也是其他随机数生成工具的父类,定义了获取随机数各方法的基本协议。

  1. 使用 48 位的随机种子。

  2. 通过{线性同余方程}(linear congruential formula)生成随机种子。

  3. 伪随机,根据种子生成能通过随机性测试的随机数列,若种子初始值相同,则生成完全相同的随机数列。

  4. 线程安全,但如果多个线程争用同一 Random 实例可能导致性能低下。

  5. 非密码安全。

  6. 可序列化。

线性同余方法参数

这三个参数是 Random 类的核心。

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

对应了上文线性同余方法中的各个参数,那么我们可以推断 Random 中的循环定义方程为:

但为什么是 0x5DEECE66DL0xBL1L << 48 呢?

  1. 在 Unix C 库函数中的 rand48() 函数族同样是使用这几个数作为同余方法的参数:

     int __drand48_iterate (unsigned short int xsubi[3], struct drand48_data *buffer)
     {
       uint64_t X;
       uint64_t result;
       /* Initialize buffer, if not yet done.  */
       if (__glibc_unlikely (!buffer->__init))
         {
           buffer->__a = 0x5deece66dull;
           buffer->__c = 0xb;
           buffer->__init = 1;
         }
       /* Do the real work.  We choose a data type which contains at least
          48 bits.  Because we compute the modulus it does not care how
          many bits really are computed.  */
       X = (uint64_t) xsubi[2] << 32 | (uint32_t) xsubi[1] << 16 | xsubi[0];
       result = X * buffer->__a + buffer->__c;
       xsubi[0] = result & 0xffff;
       xsubi[1] = (result >> 16) & 0xffff;
       xsubi[2] = (result >> 32) & 0xffff;
       return 0;
     }
    
  2. 验证线性同余发生器满周期的条件:

    参数 分解质因数
    0xB 11
    0x5DEECE66DL - 1 3527、787、3、2、2、757
    (1L << 48) - 1 673、257、241、97、17、13、7、5、3、3
    1. 互素:二者最大公因数为 1,互素成立

    2. 能被 所有质因数整除:

      的质因数
      25214903916 673 37466424
      25214903916 257 98112466
      25214903916 241 104626157
      25214903916 97 259947463
      25214903916 17 1483229642
      25214903916 13 1939607993
      25214903916 7 3602129130
      25214903916 5 5042980783
      25214903916 3 8404967972
    3. 是 4 的倍数, 也是:(1L << 48) - 1 并非 4 的倍数,满足。

    4. 都比 小: 生成需要对 取模,比 小,满足。

    5. 是正整数:满足。

    由此可见,Random 中的三个参数满足于 Hull-Dobell 定理,因此能够满周期地生成序列。结合数学家们的过往经验,这三个数在各种随机测试中表现 不错,如{碰撞校验}(The collision test),因此选定这三个数作为线性同余法的参数。

    但如大多数 LCG 一样,Java 使用的 LCG 在 Diehard Battery 检测中的 Birthday Spacings Test 中也是直接败下阵来。

随机数种子

  • 为保证线程安全,使用 Long 原子类型对 seed 进行存储。

      /**
       * The internal state associated with this pseudorandom number generator.
       * (The specs for the methods in this class describe the ongoing
       * computation of this value.)
       */
      private final AtomicLong seed;
    

主构造器与设置器

  • 主构造器

    根据传入的 seed,将 seed 始化为 Random 可接受的随机种子。

    如果是创建子类实例,则调用子类实现的 setSeed() 初始化随机种子。如果是本类实例,则调用 initialScramble() 进行初始化。 initialScramble() 方法先对 seed 与乘数进行{异或}(XOR)运算(这一步到现在还想不明白),再对于模数取模, 使 在模数范围之内。

      public Random(long seed) {
          if (getClass() == Random.class)
              this.seed = new AtomicLong(initialScramble(seed));
          else {
              // subclass might have overriden setSeed
              this.seed = new AtomicLong();
              setSeed(seed);
          }
      }
        
      private static long initialScramble(long seed) {
          return (seed ^ multiplier) & mask;
      }
    
  • 设置器

    Random 类中 setSeed() 操作的实现与主构造方法完全一致,同时将 haveNextNextGaussian 成员置为 false,该成员用于表明当前实例是否 存储有已经计算好的下一个符合高斯正态分布的数。既然 seed 被强行重置了,那基于之前种子的 nextGaussian 信息自然也要擦除, 将 haveNextNextGaussian 置为 false 等于从逻辑上擦除了。

      synchronized public void setSeed(long seed) {
          this.seed.set(initialScramble(seed));
          haveNextNextGaussian = false;
      }    
    

默认构造器

当不指定随机种子的时候,默认使用当前纳秒数来生成随机种子。

但并非是直接使用纳秒数,而是使用纳秒数与 seedUniquifier() 进行异或运算。seedUniquifier() 的作用如其名, 用于保证无参构造出的初始种子的唯一性。

seedUniquifier() 相当于 seedUniquifier 成员的 getter,但该方法的目的是维护 seedUniquifier 的唯一性。 该方法是一个自旋方法,每次都将旧的 seedUniquifier 更新后再返回。seedUniquifier 初始值是 8682522807148012L, 每次更新都乘以 181783497276652981L

/**
* Creates a new random number generator. This constructor sets
* the seed of the random number generator to a value very likely
* to be distinct from any other invocation of this constructor.
*/
public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);

private static long seedUniquifier() {
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}
  • 为什么是这两个数?

    选取 8682522807148012L 作为初始值和 181783497276652981L 作为乘子,大概率是实现者依据当时的研究资料选取的两个数。 其中 181783497276652981L 可能依旧出自TABLES OF LINEAR CONGRUENTIAL GENERATORS OF DIFFERENT SIZES AND GOOD LATTICE STRUCTURE。 但在该文中出现的是 1181783497276652981,细看少了最前面的 1,至于是不是大佬手误便不得而知了。

    但通过以下代码测试,以 8682522807148012L 作为初始值和 181783497276652981L 作为乘子,在 OOM 到达时 counter = 50331647,此时依旧 没有发生碰撞,表明这两个数周期远远超出五千万,事实证明这两个数是千挑万选而来的。

      long a = 8682522807148012L;
      HashSet<Long> set = new HashSet<>();
      for (int counter = 0; ;counter++) {
          if (!set.contains(a)) {
              set.add(a);
              a *= 181783497276652981L;
          } else {
              break;
          }
      }
    

    OOM

  • 为什么要使用 seedUniquifier()

    为了防止并发调用默认构造器时创建出两个状态相同的 Random 实例,自旋操作 + 长周期 + 异或运算使得发生这件事的概率变得几乎不可能。

  • 为什么自定义 seed 操作中不使用 seedUniquifier() 进行异或操作呢?

    线性同余方法产生的必定是伪随机序列,所以无论用不用 seedUniquifier() 最终的随机序列都是可预测的,而 seedUniquifier 的变更也是 可预测的,所以在 setSeed() 操作中加上 seedUniquifier() 实际上就是穿滑板鞋骑自行车,再怎么样也追不上开车的,还白费功夫。

    使用 seedUniquifier() 的目的时避免在多线程中出现状态相同的伪随机数生成器,这是在规避并发情况下的一些问题。但在某些 场景下我们需要获取多个初始状态相同的实例,以进行一些可以还原或者验证的操作。这个时候如果引入 seedUniquifier 非但没有任何作用,反而使得 同一 JVM 无法还原出相同初始状态的实例。

生成随机数

所有获取随机数的方法都是调用本方法,而后再进行其他操作。

同时约定 Random 的子类需要重写本方法,因为子类的随机数实现方式一般与父类不同。

/**
 * Generates the next pseudorandom number. Subclasses should
 * override this, as this is used by all other methods.
 */
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));
}

方法同样通过自旋的方式对 seed 进行更新,更新成功再通过位运算取出需要的位数。而 seed 的更新方法与我们上文推断的方程一致:

仅仅是最后使用与运算代替取模操作,实现效果相同,但是位运算速度大大快于多步骤的取模操作,位运算也是 Java 源码中常见的妙招。

  • 为什么是 int 返回类型?

    通过自旋更新后,注意到返回值类型是整型,这是因为 Random 中的线性同余发生器是 48 位周期的,最多生产 48 位整数,远远达不到长整型的完整长度,因此使用 整型作为返回值,至于怎么用整型生成长整型随机数,其实也简单,下文有所描述,此处略过。

  • 多出来的位数取高位还是低位?

    48 位较 32 位多出 16 位长度,next() 传入参数表示所需位数,根据传入的位数进行位移操作即可返回需要的随机数。如需要 32 位整数传入 32 即可, 48 - 32 = 16,舍弃 16 位数即可返回,最终返回 seed >>> 16。很显然 Java 取的是 seed 的高位。这是由于,线性同余发生器的一个缺点是,生成 伪随机数的低阶比特的周期会比较短,因此在能够选取比特区域的时候,优先舍弃掉低阶比特部分

其他方法

  • 获取随机整型

      public int nextInt() {
          return next(32);
      }
        
      public int nextInt(int bound) {
          if (bound <= 0)
              throw new IllegalArgumentException(BadBound);
        
          int r = next(31);
          int m = bound - 1;
          if ((bound & m) == 0)  // i.e., bound is a power of 2
              r = (int)((bound * (long)r) >> 31);
          else {
              for (int u = r;
                   u - (r = u % bound) + m < 0;
                   u = next(31))
                  ;
          }
          return r;
      }
    

    对于获取指定范围的整型,方法规定入参 bound 必须大于 0,返回参数值域为 [0, bound)。分几个步骤处理:

    1. bound 校验;

    2. 获取一个正整数 r = next(31),无符号右移 17 位,整型最高位必定为 0,为正整数;

    3. 判断边界是否为 2 的幂方

       int m = bound - 1;
       if ((bound & m) == 0)  // i.e., bound is a power of 2
           r = (int)((bound * (long)r) >> 31);
      

      使用位运算 n & (n - 1) == 0 来判断 n 是否为 2 的幂方,除此之外,常用判断 2 的幂方的还有 n & (-n) == n,原理如下:

      Judge the power of 2

      如果是 2 的幂方,则可以通过位运算代替取模操作,更快地计算结果。但是,为什么设计者不和 (ax + c) & (m - 1),一样直接进行与操作,而是 选择强转类型后再右移的操作呢?

      设计者在这一点上处理得非常巧妙,沿着之前的理念:在能够选取比特区域的时候,优先舍弃掉低阶比特部分。如果 bound 是 2 的幂方,那就表示 结果是 r 中连续的一段比特,按照该理念我们应该取 r 中最高位的那段,因此 java 设计者就使用了这么一段牛逼的位运算来实现这个操作:

       bound   = 00000000 00000000 00001000 00000000
       r       = 01001101 10110100 01001110 00111001
       (long)r = 00000000 00000000 00000000 00000000 01001101 10110100 01001110 00111001
       * bound = 00000000 00000000 00000010 01101101 10100010 01110001 11001000 00000000
       >>> 31  = 00000000 00000000 00000000 00000000 00000000 00000000 00000100 11011011
       int(r)  = 00000000 00000000 00000100 11011011
      

      二进制中,2 的幂方类似于十进制中 10 的幂方,会直接把与之相乘的数位数往高位推,效果等同于左移操作,左移位数等同于乘数最后 0 比特的个数。

      我们利用这个性质可以达到目的:假设 bound 后端 0 比特的位数是 n,因此我们返回的结果位数需要为 [0, n], 第一步先进行类型提升,因为左移后我们需要的位数都将溢出: (long)r。接着让 boundr 相乘左移 n 位:bound * (long)r。 由于 r 原本是整型,最高位为符号位固定为 0,为了保证随机性需要舍弃掉。因此我们进行无符号右移 31 位,此时 r 刚好保留了除原本符号位以外高位 的 n 个比特。

    4. 如果不是幂方,进行取模操作:

       for (int u = r;
            u - (r = u % bound) + m < 0;
            u = next(31))
           ;
      

      取模操作很简单,但是直接进行取模获得的结果并不是真正随机的。r = rand(31) 获得的值范围为 [0, 2147483647],当 bound 无法整除 2147483647 时,最终结果靠近 0 的数出现的概率就会比其他数大。如 bound = 100,如果 r∈[0, 2147483600),在这段范围内最终结果 [0, 100) 是等概率的, 如果加上 r∈[2147483600, 2147483648),那么 [0, 48) 这些数出现的概率会比 [48, 100) 稍微大些。

      u - (r = u % bound) + m < 0 这一步操作就是为了在这种情境下,跳过最终不符合公平的那些数。

      如果 u 是需要跳过的,那么

      那么

      ,所以

      所以 u - (r = u % bound) + m 会超出整型边界,变成小于 0 的数,如下图:

      Remove abnormal numbers

  • 获取 Byte 数组

    中间 for 将一个整型拆分成 4 个 byte 类型,勤俭持家

      public void nextBytes(byte[] bytes) {
          for (int i = 0, len = bytes.length; i < len; )
              for (int rnd = nextInt(),
                       n = Math.min(len - i, Integer.SIZE/Byte.SIZE);
                   n-- > 0; rnd >>= Byte.SIZE)
                  bytes[i++] = (byte)rnd;
      }
    
  • 获取 Long 类型

    it’s okay that the bottom word remains signed.

      public long nextLong() {
          // it's okay that the bottom word remains signed.
          return ((long)(next(32)) << 32) + next(32);
      }
    
  • 获取 Float 类型

      public float nextFloat() {
          return next(24) / ((float)(1 << 24));
      }
    
  • 获取 Double 类型

      public double nextDouble() {
          return (((long)(next(26)) << 27) + next(27)) * DOUBLE_UNIT;
      }
    

随机数破解与预测

根据线性同余发生器的原理,如果我们知道乘子、增量和模数,我们在知道随机种子的前提下,可以推断整个随机序列。

那么我们就可以通过随机序列中连续的两个随机数,推断回初始值,即原始随机种子。

Random 生成种子有两种方式,一种是无参构造 seedUniquifier() ^ System.nanoTime(),另一种是带参构造 (seed ^ multiplier) & mask, 对于纳秒数而言我们进行预测命中的概率非常低,对于带参构造在无法获取 seed 的前提下我们无法算出初始种子。

从上文我们知道 nextInt() 方法是通过调用 next(32) 实现的,next(32) 是通过种子取高位 32 位实现的。当我们获取到连续生成的两个随机数后, 我们可以获得前两个种子的高 32 位,而随机种子完整位数是 48 位,后 16 位未知,因此我们可以通过暴力遍历 0x000xFF 进行破解。 由于是暴力推断,有可能存在多解存在的情况,但刚好线性同余发生器所追求的是长周期,因此在已知 32 位的情况下,存在多解的概率非常低,因此我们可以忽略。

private static final long multiplier = 0x5DEECE66DL;
private static final long addend     = 0xBL;
private static final long mask       = (1L << 48) - 1;

private static long predictNextPRNGSeed(int val1, int val2) {
    long seed = ((long) val1 << 16);
    /* 暴力循环破解 */
    for (int i = 0x0000; i <= 0xffff; seed++, i++) {
        long nextSeed = (seed * multiplier + addend) & mask;
        if ((int) (nextSeed >>> 16) == val2) {
            return (nextSeed * multiplier + adden) & mask;
        }
    }
    return -1;
}

java.security.SecureRandom

显然,一个可以轻易破解的伪随机数生成算法无法满足我们的需求,在很多场景下我们都需要使用真正的随机数,以防攻击者预测和暴力破解。 对此我们需要考虑真正安全的随机数生成算法,java.security.SecureRandom 类为我们提供了该功能。

Any seed material passed to a SecureRandom object must be unpredictable, and all SecureRandom output sequences must be cryptographically strong

Java 文档中并没有说 SecureRandom 类是一个真随机数发生器,它只是强调,无论为 SecureRandom 注入什么种子,所生产出来的随机数必定是不可预测的。 且这些随机数必定是{强加密性}(cryptographically strong)的。

由此我们可以推断两点,一是 SecureRandom 的随机数并非完全依据随机种子生成,二是该生成后的随机数必定经过某种加密操作使其符合强加密性。

种子的生成

SecureRandom 生成的随机数必定是不可预测的,依据其文档中所描述的:

Many SecureRandom implementations are in the form of a pseudo-random number generator (PRNG), which means they use a deterministic algorithm to produce a pseudo-random sequence from a true random seed. Other implementations may produce true random numbers, and yet others may use a combination of both techniques.

有些实现是使用确定的伪随机数生成器,但以一个真随机数作为种子。而其他实现可能是通过产生真随机数的方式,这种方式类似于在对 seed 进行操作时,某个参数所使用的是真随机数, 这样所产生的随机数必定是无法预测的。甚至有的实现使用了二者结合的方式,使用一个真随机数作为种子,再使用一个参数不确定的算法。

以上几种方式都有一个共同的特点,那就是我们需要获得真正的随机数源,算法是通过特定的输入获取确定的输出的,因此我们无法在软件层面上获得真正的随机数, 那我们又该从哪获取呢?

真随机数

由于计算机的空间状态是固定的,因此我们要获取真正的随机数,必须借助外界的被我们所客观认定的随机事件, 像分子的热运动这种自然现象或者是我们人类的连续活动所宏观上构成的随机行为。

  • 硬件策略

    而对于计算机而言,最接近可获取的随机量就是集成电路中的原子的热运动所产生的噪声了,因此我们可以在 CPU 中借助放大器将噪声放大,并以此生成随机数, 这种硬件我们称之为 TRNG,但由于对噪声的处理、屏蔽等方式,带来的影响是 TRNG 生产随机数的频率太低,且多个 TRNG 占用 CPU 的空间太大。

    同时,CPU 中也存在着 PRNG,该随机数使用{线性反馈移位寄存器}(Linear feedback shift register, LFSR)生成。 可以理解为该寄存器从一个固定周期的 0/1 序列中,根据输入的参数获取特定位置的序列,其生成随机数的方式简单,因此 PRNG 生成随机数的频率非常高。

    实际上,由于 TRNG 的工作频率较低,CPU 会让它不断产生真随机数,每个生成的真随机数都会存储在维护的随机熵池中,当需要生产随机数时, 便从熵池中取出真随机数作为 PRNG 的参数,以高速生成随机数。

    除此之外的硬件策略有磁盘驱动器的旋转速度偏差、放射性物质的随机延迟。

  • 非硬件策略 - 宏观随机事件

    除了物理方式创造随机数之外,计算机的每一次 IO 时间差、每一次键盘输入信号、鼠标输入信号等等这些事件,我们在宏观上可以理解为随机的。 因此,操作系统一般都会将这些随机事件产生的参数收集起来,并丢入一个持续维护的随机熵池中,该熵池以虚拟设备的方式挂载在操作系统中, 初始的随机熵池采用计算机硬件上各种唯一的标识进行初始化,在不断地运行过程中,熵池的熵值会不断增大。在我们需要随机数的时候,只需要访问该设备, 即可轻松获取到随机的值。

    在 Linux 中,该熵池存储在设备文件 /dev/random 中,但由于每次重启过后熵池重置,熵值太低导致访问的时候往往会阻塞,以等待更多的随机事件发生。 因此 Linux 还维护了另一个设备文件 /dev/urandom,该文件在关机时并不会清空该熵池的状态,因此不存在重启之后获取随机数会阻塞的问题。

强加密性

In cases where a series of random quantities must be generated, an adversary may learn some values in the sequence. In general, they should not be able to predict other values from the ones that they know. –RFC 1750: Randomness Recommendations for Security.

对于随机数而言,强加密性的标准就是:攻击者在获取已有的随机数列的基础上,无法通过该随机数列推算出余下的随机数。对此需要有两个要求:

  1. 后生成的数与前面生成的数无关联性。
  2. 每一个生产的数应该尽可能少的表示出发生器的状态。

强加密性有不同的算法可以实现,选用哪种取决于 SecureRandom 的实现,本文更注重对于随机数的讨论,因此予以略过。但我们应该记住的是, SecureRandom 满足以上两个要求。

再谈随机

我们知道 TRNG 的产生有硬件策略和非硬件策略两种,但硬件策略的产生速度太慢,实际上我们所采用的随机种子, 其每一位元都有可能是经过多个 TRNG 进行各种操作后产生的。产生 TRNG 位元较少的生产策略无疑跟不上我们的需求。

就像纳秒数中的最后三位一样,在人类甚至目前的机器层面,取其二进制低 7 位我们可以视为 TRNG。但是,这对于攻击者而言是非常欣喜的一件事, 因为在已知毫秒的情况下,仅需花费 次尝试就可以推测出来。

但是,在不需要考虑安全性的前提下,我们要获取一个 0 或 1 的真随机数,纳秒数的二进制最低位就可以直接拿来用了。