【密码学】一文读懂RSA的随机数生成器
![%}LAL4H8}@USBB83LJ1]KT0.jpg](https://ucc.alicdn.com/pic/developer-ecology/7edc546815574ba787da3ff9fd53d8ce.jpg?x-oss-process=image/resize,w_1400/format,webp "%}LAL4H8}@USBB83LJ1]KT0.jpg")
RSA随机数生成器
本文接着来聊一个比较轻松的内容，再来说一个随机数生成器，对于这个随机数生成器呢，这里和之前讲到过的BBS有一些类似，直接来看具体的内容蛤。
这个随机数生成器的结构是真的简单，如果有实现好的大数运算的语言，基本上就只有一行核心的代码，相信各位读者看完我的代码实现之后，就会明白了。
算法过程
设p、q为两个k/2 bit长的素数，计算 ，随机选择一个b使得b满足 ，其中n和b是公开的，p和q是保密的。
在这里我们简单的来回顾一下rsa加密的过程，首选选取两个大素数p和q，然后计算 ，之后选取e满足 其中(n, e)作为公钥，这一块过程和RSA加密算法非常相似，因此呢，这个随机数生成器的名字就是这么来的。
好了，回忆完成RSA的加密算法，我们回过头开看随机数是怎样生成的，首先在 选择一个k比特长度的数字 作为种子。对于 定义如下的递推公式:
然后定义随机比特生成的函数:
其中:
这里，整个随机数生成器的过程就完成了，最后来一张简单的处理过程图吧。
RSA随机数生成器
代码实现
这里回归一下，因为算法比较简单，咱们还是用两种语言来实现
package rsa import "math/big" type RSAPRNG struct { p big.Int q big.Int b big.Int s0 big.Int n big.Int } func New(p, q, b, s0 big.Int) *RSAPRNG { n := new(big.Int) n.Mul(&p, &q) return &RSAPRNG{p, q, b, s0, *n} } func (r *RSAPRNG) PRNG() big.Int { r.s0.Exp(&r.s0, &r.b, &r.n) return r.s0 }
回归我的老本行语言，咱们再来rust来实现一下
use num_bigint::BigUint; struct RSAPRNG { p: BigUint, q: BigUint, b: BigUint, s0: BigUint, n: BigUint, } impl RSAPRNG { pub fn new(p: &BigUint, q: &BigUint, b: &BigUint, s0: &BigUint) -> RSAPRNG { let n = p * q; RSAPRNG { p: p.clone(), q: q.clone(), b: b.clone(), s0: s0.clone(), n } } pub fn next(&mut self) -> BigUint { self.s0 = self.s0.modpow(&self.b, &self.n); self.s0.clone() } }
