【密码学】一文读懂BBS
之前聊过不少非密码学安全的伪随机数生成算法，这次呢，咱们来聊一个密码学安全的伪随机数生成器 「BBS」 ，这个是三位设计者的首字母: Blum、Blum 和 Shub。
生成器结构
BBS结构
首先BBS需要选择两个素数p和q，并且使得
简单解释一下上面这个式子吧，也就是说p和q同余与4模3，大白话就是p和q在除以4的时候余数都是3。
然后，令 ，之后选择一个随机数s作为种子，这里对于种子有个要求，要求s和n互素。
然后按照如下的方式产生随机序列:
好了，这篇文章依然很短，因为这个算法结构实际上并不复杂，如果想去看原理的，可以去参考文末参考资料当中的paper。
代码实现
这个代码实际上写起来也比较简单，这里我偷懒了，没用大数，直接用的uint
Go
package bbs type BBS struct { p uint q uint x uint n uint } func New(p, q uint) *BBS { return &BBS{ p, q, 0, p * q, } } func (b *BBS) Seed(seed uint) { b.x = (seed * seed) % b.n } func (b *BBS) Rand() uint { x := (b.x * b.x) % b.n return x }
Rust
struct BBS { p: u32, q: u32, x: u32, n: u32, } impl BBS { pub fn new(p: u32, q: u32, seed: u32) -> BBS { let n = p * q; let x = seed.wrapping_mul(seed) % n; BBS { p, q, x, n } } pub fn rand(&mut self) -> u32 { self.x = self.x.wrapping_mul(self.x) % self.n; return self.x; } }
