BBS(Blum-Blum—Shub)产生器

BBS算法是一种基于大质数的伪随机数生成器，由Ralph Blum、Yaacov Shapira和Michael Shub于1986年提出。

blum_blum_shub 函数接受四个参数：

  • p：一个大质数。
  • q：另一个大质数。
  • seed：用于生成伪随机数的种子。
  • n_bits：需要生成的二进制位数。

函数的主要逻辑是计算M = p * q，然后使用种子值seed计算x = (seed * seed) % M。

接下来，使用一个循环来生成n_bits个二进制位。在每次循环中，计算x = (x * x) % M，然后取模2得到一个二进制位b，并将其添加到结果字符串bits中。最后，返回生成的二进制字符串。

BBS算法的安全性取决于大质数p和q的选择。在实际应用中，需要确保p和q是足够大的质数，以防止攻击者破解生成的伪随机数。

代码部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def blum_blum_shub(p, q, seed, n_bits):
    M = p * q
    x = (seed * seed) % M

    bits = ""
    for _ in range(n_bits):
        x = (x * x) % M
        b = x % 2
        bits += str(b)

    return bits

# 使用示例
p = 23
q = 19
seed = 2
n_bits = 10
random_bits = blum_blum_shub(p, q, seed, n_bits)
print(random_bits)

实验结果

1
2
3
0010110010

Process finished with exit code 0