安全随机数生成

在密码学中，随机性是不可或缺的一个角色。许多密码学算法都要求使用一个不可预测的随机数，只有在生成的随机数不可预测时，这些算法才可以保证足够的安全性。例如MAC 算法中的 key，ElGamal，ECC算法的k。

另外许多高性能算法如快速排序，布隆过滤器都依赖于随机性，如果随机性可以被预测，或者能够找到特定的输入值使这些算法变慢，那么黑客就有攻击可循。

python随机数

在python中最简单方便的是使用random生成随机数。

#需要的库
import random
import string

#random.randint(a,b) 在[a,b]内生成随机数
random.randint(1,50)#随机生成最小值为1，最大值为50的整数（可以等于上下限）
random.randint(20, 20)  #上下限一样时结果永远是20 

#random.randrange(a, b), random.randrange([start], stop[, step]), [a,b)
random.randrange(0, 101, 2)

#0-1之间的随机浮点数
random.random() #用于生成一个0到1的随机符点数: 0 <= n < 1.0

#随机浮点数：random.uniform(a, b)
random.uniform(1, 10)  #随机生成1到10之间的浮点数，可等于1或10
random.uniform(10, 1)  #随机生成1到10之间的浮点数，可等于1或10

但很显然，这种随机数生成的方式并不安全。

PRNG 伪随机数生成器

Pseudo-Random Number Generators(PRNG) 是一种数字序列的生成算法，它生成出的数字序列的统计学属性跟真正的随机数序列非常相似，但它生成的伪随机数序列并不是真正的随机数序列！因为该序列完全依赖于提供给 PRNG 的初始值，这个值被称为 PRNG 的种子。

PRNG的算法流程如下，每次迭代都会生成一个新的伪随机数。

实际上目前也有所谓的「硬件随机数生成器 TRNG」能生成出真正的随机数，但是因为 PRNG 的高速、低成本、可复现等原因，它仍然被大量使用在现代软件开发中。

PRNG 的实现

import hmac, hashlib
def random_number_generator(seed: bytes, max_num: int):
  state = seed
  counter = 0

  while True:
    state = hmac.new(state, bytes(counter), hashlib.sha1).digest()    
    counter += 1

    # 这里取余实际上是压缩了信息，某种程度上说，这可以保证内部的真实状态 state 不被逆向出来
    yield int.from_bytes(state, byteorder="big") % max_num

# 测试下，计算 20 个 100 以内的随机数
gen = random_number_generator(b"abc", 100)
print([next(gen) for _ in range(20)])

如果初始的 PRNG 种子是完全不可预测的，PRNG 就能保证整个随机序列都不可预测。

因此在 PRNG 中，生成出一个足够随机的种子，就变得非常重要了。

CSPRNG

Cryptography Secure Random Number Generators(CSPRNG) 是一种适用于密码学领域的 PRNG，一个 PRNG 如果能够具备如下两个条件，它就是一个 CSPRNG:

能通过「下一比特测试 next-bit test」：即使有人获知了该 PRNG 的 k 位，他也无法使用合理的资源预测第 k+1 位的值
如果攻击者猜出了 PRNG 的内部状态或该状态因某种原因而泄漏，攻击者也无法重建出内部状态泄漏之前生成的所有随机数

有许多的设计都被证明可以用于构造一个 CSPRNG:

基于计数器(CTR)模式下的安全分组密码、流密码**或**安全散列函数的 CSPRNG
基于数论设计的 CSPRNG，它依靠整数分解问题（IFP）、离散对数问题（DLP）或椭圆曲线离散对数问题（ECDLP）的高难度来确保安全性
CSPRNG 基于加密安全随机性的特殊设计，例如 Yarrow algorithm 和 Fortuna，这俩分别被用于 MacOS 和 FreeBSD.

大多数的 CSPRNG 结合使用来自 OS 的熵与高质量的 PRNG，并且一旦系统生成了新的熵（这可能来自用户输入、磁盘 IO、系统中断、或者硬件 RNG），CSPRNG 会立即使用新的熵来作为 PRNG 新的种子。这种不断重置 PRNG 种子的行为，使随机数变得非常难以预测。

python中可以使用secrets模块来实现CSPRNG

secrets模块：

python的secrets库是在Python 3.6中引入的，它提供了生成加密安全随机数的函数。其中包括下面的几个函数：

secrets.token_bytes(nbytes=None)：返回一个指定长度的随机字节数组。
secrets.token_hex(nbytes=None)：返回一个指定长度的随机十六进制数字符串。
secrets.token_urlsafe(nbytes=None)：返回一个指定长度的随机URL安全的Base64编码字符串，去掉了’='字符。

这些函数的实现使用的是安全的随机数发生器，因此生成的随机数可以用于密码学应用程序等需要高安全性的场合。

#生成一个指定长度的随机十六进制数字符串
import secrets

print(secrets.token_hex(16))  # 生成一个16字节的随机十六进制数字符串

使用 Python 实现一个简单但足够安全的随机密码生成器：

import string
import secrets

# 定义密码生成函数
def generate_password(length: int) -> str:
    # 定义所有可用的字符集合
    alphabet = string.ascii_letters + string.digits + string.punctuation

    # 使用 secrets 模块生成随机密码
    password = ''.join(secrets.choice(alphabet) for i in range(length))

    return password

# 调用函数生成密码
password = generate_password(16)

print(password)