RSA加密系统

RSA公钥加密系统中，公钥和密钥的产生：

1. 随机选取两个大质数p和q，使得p ≠ q。
2. 计算n=pq。
3. 选取一个与$\phi (n)$互质的小奇数e，其中$\phi (n)=(p-1)(q-1)$
4. 对模$\phi (n)$，计算出e的乘法逆元d的值。即$ed\equiv 1\pmod {\phi(n)}$
5. 将$p=(e,n)$公开作为RSA公钥
6. 将$s=(d,n)$公开作为RSA密钥

假设密文为 c ，明文为 m

RSA的加密过程为：$c = m^e\pmod n$

RSA的解密过程为：$m = c^d\pmod n$

这里是公钥加密，私钥解密。

如果用于数字签名，则与之相反，即私钥加密公钥解密。

如何获取大质数

素数分布函数$\pi(n)$描述了小于或等于n的素数的数目。例如$\pi(n) = 4$，分别为$2,3,5,7$

素数定理

$\lim \limits_{n \rightarrow \infty}\frac{\pi(n)}{n/\ln n} = 1$

对于较小的n，近似式$n/\ln n$能精确的给出$\pi(n)$的估计值，如：$n=10^9$，误差不超过6%

为了找一个长度与n相同的质数大概需要在n的附近找大约$\ln n$个数，如找一个1024位长度的质数，大约需要测试$\ln 2^{1024} \approx 710$个随机选取的长度为1024位长的整数素性。

// rand big prime in 2^15
ll rand_prime(ll rd) {
    ll prime = time(NULL) * rd % (2LL << 15);
    while (!miller_rabin(prime, 10)) {
        prime++;
        // cout << prime << endl;
    }
    return prime;
}