RSA 算法
前言
本来以前就想学习一下非对称加密算法中，大名鼎鼎的 RSA 算法，但是奈何本人当时不会数论，完全看不懂那些讲解。并且那些讲解往往都没有说清楚每一步在干什么，所以自然也没能理解 RSA 算法。
近日看了一个关于 RSA 算法的讲解视频，茅塞顿开，明白了 RSA 算法的基本原理。在这里就来记录一下自己对 RSA 算法的理解。
公钥和私钥
公钥和私钥都由一对数字组成，这里可以假定公钥为 $(N,e)$，私钥为 $(N,d)$。其中两个 $N$ 是相等的。
使用公钥加密的内容可以用私钥解密，使用私钥加密的内容可以用公钥解密。不过由于公钥是公开的，因此私钥加密一般用于数字签名。公钥和私钥这一对密钥实际上没有什么本质的区别。区别仅在于一个是公开的，一个是不公开的。
加密和解密
加密
假设有明文 $x$，使用公钥对数据进行加密的过程，相当于将明文 $x$ 幂上 $e$ 并取除以 $N$ 的余数。这里加密所得的密文 $c$ 满足： $$ c=x^e \bmod N $$
解密
解密的过程实际上与加密是一样的，只不过使用的是私钥。使用私钥对数据进行解密的过程，相当于将密文 $c$ 幂上 $d$ 并取除以 $N$ 的余数。这里解密出的明文 $x'$ 满足： $$ x'=c^d \bmod N=x^{ed} \bmod N=x $$
这里可以发现密钥对是满足 $x^{ed} \bmod N =x$ 的，因此重点是需要找到一组数字 ${N, e, d}$ 满足上述情况。
样例
例如有这么一对密钥，公钥为 $(33, 3)$，私钥为 $(33, 7)$。
- 加密时，假设有明文 $x=25$ 需要加密，那么就将数据幂上公钥中的 3，得到密文 $c=x^3 \bmod 33=16$。
- 解密时，就将密文幂上私钥中的 7，得到明文 $x'=c^7 \bmod 33=25$。
生成密钥对
生成一对密钥首先需要两个质数 $p,q$，将这两个质数相乘即得到了 $N$。
这里还需要求出 $\varphi(N)$ 的值，这里设为 $T$，根据欧拉函数的积性特征可得： $$ T=\varphi(p)\cdot \varphi(q)=(p-1)\cdot(q-1) $$ 而此时就可以开始计算公钥和私钥了，公钥 $e$ 和私钥 $d$ 满足： $$ ed \equiv 1 \pmod T $$ 这里需要先选择出这个密钥对中的其中一个密钥 $e$，这里可以随便选，但选择出的密钥需要与 $T$ 互质，并且 $1<e<T$，这样才能保证能找到另一个密钥 $d$。当选出密钥 $e$ 之后就可以很容易地计算出另一个密钥 $d$ 了。
最后将 $N,e$ 封装成公钥，$N,d$ 封装成私钥，然后销毁掉 $p, q, T$ 这三个数字。
如果 $p,q$ 取得足够大，那么其乘积 $N$ 也会变得非常大。想要找到一个大数的两个质因数十分困难，因此保证了 RSA 算法的安全性。
欧拉定理
互质情况
解密时： $$ x^{ed}=x^{k\varphi(N)+1}=x(x^{\varphi(N)})^k $$ 根据欧拉定理，若 $x$ 与 $N$ 互质，则： $$ x^{\varphi(N)}\equiv1 \pmod N $$ 可得： $$ x^{ed}\equiv x(1)^k \equiv x \pmod N $$
不互质情况
若 $x$ 与 $N$ 不互质，不妨设 $x=ap$，$ed-1=b(q-1)$，则可得： $$ x^{ed}=ap^{ed}\equiv 0\equiv ap\equiv x \pmod p $$ $$ x^{ed}=x(x^{ed-1})=x(x^{b(q-1)})=x(x^{q-1})^b=x(x^{\varphi(q)})^b\equiv x(1)^b \equiv x \pmod q $$ 整理后即是： $$ x^{ed}\equiv x \pmod p $$ $$ x^{ed}\equiv x \pmod q $$ 因此可以证明得到 $x^{ed} \equiv x \pmod N$。
样例
- 先选择两个质数 $p=11,q=17$。
- 可以计算得到 $N=pq=187,T=(p-1)(q-1)=160$。
- 随便选出一个公钥 $e=19$，计算可得私钥 $d=59$。
- 假设有数据 $x=114$ 需要进行加密，那么 $c=x^{19} \bmod 187=113$。
- 解密时 $x'=c^{59} \bmod 187=114$。