RSA加密算法

参考资料：

RSA算法原理（一） - 阮一峰的网络日志 (ruanyifeng.com)

RSA算法原理（二） - 阮一峰的网络日志 (ruanyifeng.com)

欧拉定理 (数论) - 维基百科，自由的百科全书 (wikipedia.org)

扩展欧几里德算法详解_zhj5chengfeng的博客-CSDN博客_扩展欧几里得算法

RSA是目前使用最广泛的公钥密码之一，安全性基于大整数因子分解的困难性，这篇博客是我学习RSA算法的笔记，总结结合了网上的资料。

原理

前置知识1：模运算

模运算（mod）即求余运算，$a\ mod\ n$就是a除以n得到的余数，例如$8\ mod\ 3 = 2$。

若$(a\ mod\ n) = (b\ mod\ n)$，则定义a，b模n同余，即$a\equiv b\ (mod\ n)$，例如$21\equiv 11(\ mod \ 10)$。同余有以下性质：

• 自反：$a\equiv a\ (mod\ n)$
• 对称：若$a\equiv b\ (mod\ n)$，则$b\equiv a\ (mod\ n)$
• 传递：若$a\equiv b\ (mod\ n)$且$b\equiv c\ (mod\ n)$，则$a\equiv c\ (mod\ n)$
• 幂：若$a\equiv b\ (mod\ n)$，则$a^m \equiv b^m\ (mod\ n)$
• 若$a\equiv a_1\ (mod\ n)$且$b\equiv b_1\ (mod\ n)$，且$c,d$是任意整数，则$ac+bd \equiv a_1c+b_1d$，$abcd\equiv a_1b_1cd$。（同模下的式子可以互相加减乘，并且可以往$\equiv$两边加乘常数）

前置知识2：欧拉函数

欧拉函数$\phi(n)$表示小于等于$n$的正整数中，与$n$构成互质关系的数的个数，例如$\phi(8)=4$（分别是1 3 5 7）。

欧拉函数的计算方式：$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})$，其中$p_r$是质数且$\prod p_r=n$（$p_r$不重复）。例如$\phi(1323)=\phi(3^3\times7^7)=1323(1-\frac{1}{3})(1-\frac{1}{7})$。

欧拉函数的一些计算性质：

• 若n可以分解为两个互质整数之积：$n=p_1\times p_2$，则$\phi(n)=\phi(p_1)\phi(p_2)$。

前置知识3：欧拉定理

若正整数$a$和$n$互质，则$a^{\phi(n)}\equiv 1\ (mod\ n)$。例如$a=3,n=5时\phi(n)=4,3^4\equiv1\ (mod\ 5)$。

这个定理可以简化求大数幂的个位数，比如计算$7^{222}$的各位数时，可看做求$7^{222}$除以10的余数

• 因为7,10互质，所以$7^{\phi(10)}\equiv 1\ (mod\ 10)$。
• 所以$7^{222}=7^{4\times55+2}=(7^4)^{55}\times 7^2$
• 所以$(7^4)^{55} \equiv 1^{55}\ (mod\ 10)$
• 所以$(7^4)^{55}\times 7^2 \equiv 1^{55}\times7^2\ (mod\ 10)$
• 所以也就是$9$。

前置知识4：模反元素/乘法逆元

若$a,n$互质，则必有$b$使$ab\equiv 1(mod\ n)$，此时$b$是$a$的模反元素或乘法逆元。

乘法逆元的直观作用：$m$是一个很大的数，现要计算$c=m/a\ mod\ b$，若$d$是$a$的乘法逆元$ma\equiv1(mod\ n)$，则可用$d$代替计算：$c=md\ mod\ b$。

前置知识5：拓展欧几里得算法

欧几里得算法是求解$a,b$的最大公约数（记作$gcd(a,b)$）的一种递归算法，也叫辗转相除法：$gcd(a,b)=gcd(b,a\ mod\ b)$，一直到$gcd$参数有一个为0。

比如求14和45的最大公约数，即$gcd(45,14)=gcd(14,3)=gcd(3,2)=gcd(2,1)=gcd(1,0)=1$。

再比如求28和63的最大公约数，即$gcd(63,28)=gcd(28,7)=gcd(7,0)=7$。

我们已知$a,b$的最大公约数是$gcd$，那么一定会有$x,y$满足$ax+by=gcd(a,b)$，而扩展欧几里得算法就是找到$x,y$的方法。

• 用%表示求余，用//表示整除，假设上一步是$gcd(a,b)$，下一步是$gcd(b,a\%b)$
• 已知下一步的$x,y$满足$bx+(a\%b)y=gcd$
• 代入$a\%b=a-(a//b)\times b$，得到$bx+[a-(a//b)b]y=ay+b[x-(a//b)y]=gcd$
• 此时可以发现上一步的$x_1=y,y_1=x-(a//b)y$。
• 也就是说，假设$a>b$，上一步是$gcd(a,b)$对应$ax+by=1$，下一步是$gcd(b,a\% b)$对应$ay'+b(x'-ky')=1$。

前置知识6：用拓展欧几里得计算乘法逆元

$ab\equiv 1(mod\ n)$已知$a,n$求b，原式等价于$ab-kn=1,\ k未知$，而此时把b看作x，-k看作y，那么就是解一个拓展欧几里得的问题了。

RSA密钥生成

1. 选择两个不相等质数$p,q$。（p=61，q=53）

2. $n=p\times q$，$n$的二进制长度就是秘钥长度。n=（3233）

3. 根据性质，计算$\phi(n)=(p-1)(q-1)$。φ(n)=（3120）

4. 选择整数$e$，满足$1<e<\phi(n)$，且$e$与$\phi(n)$互质。假设选了1到3120之间的17

5. 计算$e$对于$\phi(n)$的模反元素$d$，即满足$ed\equiv 1 (mod\ \phi(n))$，也即$ed-1=k\cdot \phi(n)$。

   17d+3120k=1，用拓展欧几里得算法得到d=2753,k=-15

6. 将n和e封装为公钥，n和d封装为私钥

这个算法保证了已知n和e，无法推出d。因为$ed\equiv 1 (mod\ \phi(n))$需要知道$\phi(n)$，而$\phi(n)=(p-1)(q-1)$需要知道$p,q$，而$n=pq$，当$n$很大的时候，就无法因数分解。

# 重新整理一下
p,q（不相等大质数） n（无法因数分解的大数） e（和n组成公钥）d（和n组成私钥）φ(n)（算出来的）

RSA加密

设明文为$m$，$m$是一个小于$n$的整数。计算$c$，使$m^e\equiv c(mod\ n)$，则$c$为密文。

假如要加密m=65，则$\bold{65^{17}\ mod\ 3233=2790=c}$。

RSA解密

拿到密文$c$之后，$c^d\equiv\ m (mod\ n)$。

$\bold{2790^{2753}mod\ 3233=65}$。