RSA加密算法

参考资料：

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

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

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

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

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

前置知识1：模运算

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

若(amodn)=(bmodn)，则定义a，b模n同余，即a≡b(modn)，例如21≡11(mod10)。同余有以下性质：

• 自反：a≡a(modn)
• 对称：若a≡b(modn)，则b≡a(modn)
• 传递：若a≡b(modn)且b≡c(modn)，则a≡c(modn)
• 幂：若a≡b(modn)，则am≡bm(modn)
• 若a≡a1(modn)且b≡b1(modn)，且c,d是任意整数，则ac+bd≡a1c+b1d，abcd≡a1b1cd。（同模下的式子可以互相加减乘，并且可以往≡两边加乘常数）

前置知识2：欧拉函数

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

欧拉函数的计算方式：ϕ(n)=n(1−1p1)(1−1p2)…(1−1pr)，其中pr是质数且∏pr=n（pr不重复）。例如ϕ(1323)=ϕ(33×77)=1323(1−13)(1−17)。

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

• 若n可以分解为两个互质整数之积：n=p1×p2，则ϕ(n)=ϕ(p1)ϕ(p2)。

前置知识3：欧拉定理

若正整数a和n互质，则aϕ(n)≡1(modn)。例如时a=3,n=5时ϕ(n)=4,34≡1(mod5)。

这个定理可以简化求大数幂的个位数，比如计算7222的各位数时，可看做求7222除以10的余数

• 因为7,10互质，所以7ϕ(10)≡1(mod10)。
• 所以7222=74×55+2=(74)55×72
• 所以(74)55≡155(mod10)
• 所以(74)55×72≡155×72(mod10)
• 所以也就是9。

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

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

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

欧几里得算法是求解a,b的最大公约数（记作gcd(a,b)）的一种递归算法，也叫辗转相除法：gcd(a,b)=gcd(b,amodb)，一直到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的方法。

欧几里得算法的停止状态是a=gcd,b=0，此时有a×1+b×0=gcd(a,b)，我们计划从这个状态反推到初始状态。

用%表示求余，用//表示整除，假设上一步是gcd(a,b)，下一步是gcd(b,a，已知下一步的x,y满足bx+(a。代入a，得到bx+[a−(a//b)b]y=ay+b[x−(a//b)y]=gcd。此时可以发现上一步的x1=y,y1=x−(a//b)y。

用28和63举例，gcd(28,7)是上一层，则x1=y=0,y1=x−(28//7)×y=1。gcd(63,28)是上一层，则x2=y1=1,y2=x1−(63//28)×y1=−2。

RSA密钥生成

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

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

3. 根据性质，计算ϕ(n)=(p−1)(q−1)。φ(n)=（3120）

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

5. 计算e对于ϕ(n)的模反元素d，即满足ed≡1(modϕ(n))，也即ed−1=k⋅ϕ(n)。

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

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

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

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

RSA加密

设明文为m，m是一个小于n的整数。计算c，使me≡c(modn)，则c为密文。

假如要加密m=65，则\bold6517mod3233=2790=c。

RSA解密

拿到密文c之后，cd≡m(modn)。

\bold27902753mod3233=65。