rand 解析
#2023#Golang#rand 2023-08-26

rand 解析

随机数在开发的应用比较广泛，在不同的安全级别下应该采用不同的生成方案。

伪随机数

在人类“一眼看上去”是随机的，实际上是用算法产生的一列被认为具有随机性的数字，常常叫伪随机数。

在安全敏感度不高的情况下，生成伪随机数可以满足大部分需求。

LCG(线性同余生成器)

这是 Golang 生成伪随机数的方案，叫线性同余法。

直接说一下 Golang 的生成公式，如下：

1
next = (seed * 48271) % 2147483647

其中，seed 是当前的种子（初始种子由调用者设置），next 是生成的下一个伪随机数。48271 和 2147483647 是预定义的常量，用于执行乘法和取模操作。

48271 是生成器定义的常数。

214748364 是 2 ^ 31 - 1 ，通过对它取模确定随机数的范围在 int32 的范围内。

Golang 伪随机数的代码实现

从一个例子开始

rand.Seed()

1
2
r := rand.New(rand.NewSource(time.Now().Unix()))
fmt.Println(r.Intn(10))

第一行，将现在时间的时间戳作为种子传入 rand.NewSource()，然后将它返回的 Source 传给 rand.New，rand.New 返回一个结构体指针 *Rand

rand.NewSource()

1
2
3
4
5
6
7
8
// NewSource 返回一个新的带有给定值的伪随机源。
// 与顶级函数使用的默认源不同，此源对于多个协程并发使用不安全。
// 这意味着我们不能多个 goroutine 同时使用这一个源
func NewSource(seed int64) Source {
	var rng rngSource
	rng.Seed(seed)
	return &rng
}

可以看到在 rand.NewSource 中，首先创建了一个名为 rng 的 rngSource 结构体实例。然后，使用 Seed 方法将给定的种子值传递给该实例，以初始化随机数源的状态。最后，通过返回 &rng ，将初始化后的随机数源返回。

其中，返回类型 Source 是一个接口类型。其定义如下

1
2
3
4
type Source64 interface {
	Source
	Uint64() uint64
}

Seed

关键的种子处理函数 Seed 具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Seed 使用提供的种子值将生成器初始化为确定状态。
func (rng *rngSource) Seed(seed int64) {
	rng.tap = 0
    // feed 下一次生成随机数时应该使用的输入位置。
    // rngLen 是随机数序列的长度
    // rngTap 是一个常量，表示计算中的偏移量。
	rng.feed = rngLen - rngTap

    // 这里是对种子进行一些处理与校正
    // int32max 是常量，表示 2^31 - 1 ，int32 最大的值
    // 这个操作是用来保证这个种子的范围在 int32 范围内
	seed = seed % int32max
	if seed < 0 {
		seed += int32max
	}
	if seed == 0 {
        // 这是默认的非零种子值
		seed = 89482311
	}

    // 将种子的值赋给 x
	x := int32(seed)
    // 开启一个循环
	for i := -20; i < rngLen; i++ {
		x = seedrand(x)
        // 处理后将元素放入到 rng.vec 数组中
		if i >= 0 {
			var u int64
			u = int64(x) << 40
			x = seedrand(x)
			u ^= int64(x) << 20
			x = seedrand(x)
			u ^= int64(x)
            // 这个数组用来存储预先计算好的种子值。
            // 这些种子值被用来初始化随机数生成器，以便生成伪随机数序列。
			u ^= rngCooked[i] 
			rng.vec[i] = u
		}
	}
}

seedrand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1)
func seedrand(x int32) int32 {
	const (
		A = 48271
		Q = 44488 // x 的 商
		R = 3399 // x 的 余数
	)

	hi := x / Q
	lo := x % Q
	x = A*lo - R*hi
	if x < 0 {
		x += int32max
	}
	return x
}

rand.New

至于 rand.New ，作用就是将 rand.Source 得到的接口类型给到它，然后赋值并返回一个指针。

1
2
3
4
func New(src Source) *Rand {
	s64, _ := src.(Source64)
	return &Rand{src: src, s64: s64}
}

第二行，传入需要生成随机数的范围最大值 max + 1，然后通过 rand.Intn 生成一个随机数。

rand.Intn

1
2
3
4
5
6
7
8
9
10
11
// Intn 以 int 形式返回半开区间 [0,n) 中的非负伪随机数。
//如果 n <= 0，则会 panic。
func (r *Rand) Intn(n int) int {
	if n <= 0 {
		panic("invalid argument to Intn")
	}
	if n <= 1<<31-1 {
		return int(r.Int31n(int32(n)))
	}
	return int(r.Int63n(int64(n)))
}

可以看到在 n 的大小在 int32 范围内时，会调用 Int31n

Int31n 的具体实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (r *Rand) Int31n(n int32) int32 {
	if n <= 0 {
		panic("invalid argument to Int31n")
	}
    // 如果为 0，可以作为掩码
	if n&(n-1) == 0 { // n is power of two, can mask
		return r.Int31() & (n - 1)
	}
    // 计算出 n - 1 的值
	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    // 生成随机数
	v := r.Int31()
	for v > max {
		v = r.Int31()
	}
    // 取模保证大小不会超过要求的
	return v % n
}

生成随机数的核心时调用了 Int31

1
2
// Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }

可以看到是调用了 Int63 这个方法然后取它的高32位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
func (rng *rngSource) Int63() int64 {
	return int64(rng.Uint64() & rngMask)
}

// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64.
func (rng *rngSource) Uint64() uint64 {
    // 计算时的偏移量
	rng.tap--
    // 如果 < 0 则加上 rngLen，即随机数序列的长度
	if rng.tap < 0 {
		rng.tap += rngLen
	}

    // 上面说过 feed 是下一次生成随机数时应该使用的输入位置
	rng.feed--
	if rng.feed < 0 {
		rng.feed += rngLen
	}

    // 随机数生成，通过设置种子时得到的 vec 数组，获得它们的和。
	x := rng.vec[rng.feed] + rng.vec[rng.tap]
    // 将数组的该位置重新设置成 x，目的是提高随机性。
	rng.vec[rng.feed] = x
	return uint64(x)
}

如果是Int64 的范围，本质上也是调用 Uint64 这个方法

至此，伪随机数的生成过程总结如下：

  1. 通过 rand.NewSource 设置种子
  2. rand.NewSource 将种子进行处理，并通过线性同余法的计算公式得到一个随机数数组 vec。
  3. 调用生成随机数的函数，本质上是调用 rngSource 的 Uint64() 方法，取 vec 中 的两数和。

真随机数

根据密码学原理，同时满足随机数的随机性检验的三个标准的，可称为真随机数。

需要注意的是，真随机数的生成涉及到操作系统底层，对性能的影响较大，非必要不用。

Golang 真随机数的实现

使用及源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import (
	"crypto/rand"
	"fmt"
	"math/big"
)

func main() {
	max := new(big.Int)
	max.SetString("100000000000000000000000000000000", 10)

	n, err := rand.Int(rand.Reader, max)
	if err != nil {
		fmt.Println("随机数生成失败，err:", err)
		return
	}

	fmt.Println(n)
}

可以看到关键函数是 rand.Int

具体实现代码在 crypto/rand 下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Int 返回 [0,max) 范围内的随机数，如果 max < 0 则 panic
func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
	if max.Sign() <= 0 {
		panic("crypto/rand: argument to Int is <= 0")
	}
	n = new(big.Int)
    // 将 n 的值设为 max - 1
	n.Sub(max, n.SetUint64(1))
	// bitLen 是 < max 的值所需的最大位长度。
	bitLen := n.BitLen()
	if bitLen == 0 {
		// 只有一个有效的结果就是 0
		return
	}
	// k 是 < max 值所需的最大字节长度。
    k:= (bitLen + 7) / 8
    // b 是 max-1 的最高位字节的位数。
    b:= int(bitLen % 8)
	if b == 0 {
		b = 8
	}

	bytes := make([]byte, k)

	for {
        // 从随机数生成器 rand 中读取随机字节序列，并将其存储在 bytes 中
        // 这个字节序列就是从不同的操作系统中获取到的真随机数字节序列
        // 直到抛出错误或者生成了符合条件的随机数
		_, err = io.ReadFull(rand, bytes)
		if err != nil {
			return nil, err
		}

		// 清除第一个字节中的高位以增加概率
		// 候选值 < max。
		bytes[0] &= uint8(int(1<<b) - 1)

		n.SetBytes(bytes)
		if n.Cmp(max) < 0 {
			return
		}
	}
}

每个操作系统下，对应的真随机数获取流程不太一致，大体差不多。

值得一提的是使用了 go 编译标签( build tag) 来实现不同操作系统不同操作流程。

Windows

在Windows系统中，crypto/rand 包使用 RtlGenRandom 函数来获取随机数。RtlGenRandom 是Windows提供的一个使用操作系统内部的随机数生成器来生成真随机数的函数。

Linux

在Linux系统中，crypto/rand 包使用 /dev/urandom 设备来获取随机数。/dev/urandom 是一个特殊的设备文件，通过读取该文件可以获取系统内核中的随机数池。