比较浅显的理解，主要是对RSA算法有一些数学上的认识。
1. 数学原理
1.1 质数很容易生成
给定一个长度，很容易找到符合这个长度的一个随机质数。这个结论依赖两点：
- 质数在任意长度内都广泛存在；
- 即使数很大(比如4096位)，也很容易判断它到底是不是个质数。
要生成一个质数，先随机生成一批给定长度的数字，然后判断它们是不是质数。根据Prime Number Theorem，找到一个质数，需要判断的候选数字个数在$\ln(x)$的阶上($O(\ln(x))$???), $x$是给定的长度。
之前判断一个数是不是质数需要找它所有的因子，看是不是只有1和它本身，如果是那就是质数。现在的方法是判断一个数是不是有质数的一些性质。如果不能很快判断一个数是不是质数，现代的很多公钥算法就很难实际应用了。
1.2 乘法很容易计算
有两个很大(512位以上)的质数$p, q$, 很容易算出他们的乘积$n = pq$。
1.3 因式分解很难
尽管经过几百年的研究，现在因式分解的方法比一个个查找的方法快很多(现在最快的能接近$\sqrt{n}$)，但还是很慢，非常慢。
1.4 幂的模很容易计算
给定$n, m, e$, 很容易算出来$c = m^e \text{ mod } n$
1.5 如果给出因子，很容易计算出模的根
给定$n, e, c$，还有$n$的质数因子$p, q$, 很容易计算出$c = m^e \text{ mod } n$中的$m$
方法就是存在$d$满足$m = (m ^ e) ^ d \text{ mod } n = c^d \text{ mod } n$
其中d按如下方法计算：
$L = LCM(p-1, q-1)$，LCM是$p-1,q-1$的最小公倍数，$d$是所有满足 $d \cdot e \text{ mod } L = 1$的数，也就是说，$d$和$e$是关于$\text{ mod } L$的倒数，$e$跟$p-1$和$q-1$互质保证了$d$一定存在。模倒数可以用扩展欧几里得算法很容易算出来。
1.6 如果不给出因子，计算模的根很难
如果只给出$n, e, c$，不给出n的因子$p, q$，就很难计算出$c = m^e \text{ mod } n$中的$m$。
要恢复$m$，需要先找到$d$，事实上，任何确定d的方法都会转到因式分解$n$的路上。
2. RSA加解密
有了以上的基础，现在可以描述一下RSA密钥对儿的生成步骤了。
加密系统中的公钥包含$n$和$e$，$n$叫*模数(modulus)，$e$叫公钥指数(public exponent)。私钥包含$n$和$d$，$d$叫私钥指数(private exponent)*。
生成步骤如下：
- 生成一对儿很大的随机质数$p,q$
- 计算模数$n = pq$
- 在[3,n-1]之间挑选一个奇数$e$, 作为公钥指数，并保证$e$和 $p-1、q-1$互质。
- 用$e, p, q$计算私钥指数$d$。 先算$L = LCM(p-1, q-1)$, LCM是$p-1$和$q-1$的最小公倍数，$d$满足$d \cdot e \text{ mod } L = 1$， 可以用扩展欧几里得算法算出来。
- $(n, e)$就是公钥， $(n, d)$就是私钥。
加密操作：
$$c = m^e \text{ mod } n$$
解密操作:
$$m = c^d \text{ mod } n$$
签名操作：
$$s = m^d \text{ mod } n$$
验签操作：
$$m = s^e \text{ mod } n$$
我们常数的RSA 4096指的是$n$的位数，表示RSA算法一次可以加密多少位的数据。
3. openssl相关的几个问题
RSA_size()和RSA_bits()的返回值RSA_size()返回的是rsa->n的字节数，这个值乘8就是期望的1024, 2048, 4096等值。RSA_bits()返回的是rsa->n的有效位数，这个值不一定就是1024这些值，因为最高有效位可能是0。(其实openssl内置的rsa密钥生成函数中，保证了n的最高4个有效位必须在[0x9, 0xf]之间)。
参考
- 讲RSA非常好的一个，基本是这篇的摘要: The Mathematics of the RSA Public-Key Cryptosystem