RSA —— 经典的非对称加密算法_rsa加密算法

RSA —— 经典的非对称加密算法

一、加密算法基础知识

加密的密钥

    密钥是一种参数，它是在明文转换为密文或密文转换为明文时算法的输入参数。可以理解成密码的钥匙。

对称与非对称

    常见的数字加密方式分为两类：对称加密 和 非对称加密。

      对称加密，又称为私钥加密，指的是加密和解密使用同一个密钥的方式。其特点是加密和解密过程简单、快速，并且只需要一个密钥。常见的对称加密算法包括DES、AES等。然而，由于使用的是同一个密钥，如果密钥被黑客拦截，信息就很容易被破译。

       非对称加密，又称为公钥加密，是指使用一对非对称密钥进行加密的方式，其中一个密钥是公钥（可以公开的密钥），另一个密钥是私钥（只有密钥的持有者知道的密钥）。公钥可以用来加密信息，而私钥可以用来解密信息。因为使用的是两个不同的密钥，所以这种算法称为非对称加密算法。私钥不通过网络发送出去，所以非对称加密的安全性很高。最常用的非对称加密算法是RSA算法。

总结来说，对称加密和解密速度快，但安全性相对较低；而非对称加密虽然安全性高，但解密速度慢。在实际应用中，可以根据具体需求选择合适的加密方式。

二、RSA算法流程

（源于RSA —— 经典的非对称加密算法 - 知乎 (zhihu.com)）

2、（3）欧拉函数（在RSA算法中相当于算出有几组素数即公私钥的组合）

定义：

欧拉函数，记作φ(n)，在数论中表示小于n的正整数中与n互质的数的数目。

对于正整数N，少于或等于N的正整数中与N互质的正整数（包括1）的个数记作φ(n)。例如，φ(10)=10×(1-1/2)×(1-1/5)=4，其中p(1)=2，p(2)=5是10的所有质因数。

欧拉函数的性质包括：

1. 若N是质数p的k次方，则φ(n)= p^k - p^(k-1)。
2. 如果m和n互质，即GCD(m, n)=1，那么φ(m*n) = φ(m) * φ(n)。（换句话说，当我们把两个互质的数相乘时，与它们的乘积互质的数的数量是它们各自与自身互质的数的数量的乘积。

   这个性质对于互质的数来说是成立的，因为互质的两个数没有其他公约数除了1以外，所以它们的欧拉函数值是独立的。）

公式：

欧拉函数φ(n)的公式取决于n的质因数分解。
如果n是质数p的k次方，那么φ(n)= p^k - p^(k-1)。
如果n没有形如p^k的质因数，那么φ(n)= n*(1-1/p1)(1-1/p2)...(1-1/pk)，其中p1, p2, ..., pk是n的所有质因数。

2、（5）（逆元定理允许我们将公式（a/b）%c转换为乘法运算，从而避免由于b值过大而导致的精度问题。）

逆元是指一个可以取消另一给定元素运算的元素。在数学中，逆元素被广义化为加法中的加法逆元和乘法中的倒数。具体来说，如果存在一个数x满足ax%m=1，那么x就是a的逆元。逆元定理允许我们将公式（a/b）%c转换为乘法运算，从而避免由于b值过大而导致的精度问题。逆元有多个求法，包括费马小定理和欧拉定理等。每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1（mod n）。一个数有逆元的充分必要条件是gcd（a，n）=1，此时逆元唯一存在。

在RSA算法中，d是e的模φ(n)下的乘法逆元。这意味着e和φ(n)互素，并且因为模运算的性质，它的乘法逆元一定存在。d被称为私钥，而e被称为公钥。加密时，使用公钥e和模n对明文进行加密，得到密文。解密时，使用私钥d和模n对密文进行解密，得到明文。这种加密和解密的方式基于数论中的一些基本性质，可以提供一种安全的方式来保护信息。因此，在RSA算法中，计算逆元d是非常重要的。

模运算是一种数学运算，通常表示为“取模”或“模运算”。在计算机编程中，模运算被广泛应用于各种算法和数据结构中，因为它可以提供快速高效的整数除法操作。

模运算的基本概念是将一个数除以另一个数，并取余数。这个余数就是模运算的结果。例如，在计算a mod n时，表示将a除以n并取余数。同样地，在计算b mod n时，表示将b除以n并取余数。

模运算的性质包括：

1. 模运算具有反交换律和反结合律，即a mod n = b mod n当且仅当a=b（反交换律），以及(a+b) mod n = (a mod n + b mod n) mod n（反结合律）。
2. 模运算可以用于判断一个数是否是另一个数的倍数，即如果a mod n=0，则a是n的倍数。
3. 模运算可以用于实现循环移位操作，即将一个数循环右移或左移若干位。
4. 在计算机编程中，模运算被广泛应用于各种算法和数据结构中，例如快速排序、二分搜索、哈希表等。

c = pow(m,e,n)

m = pow(c,d,n)

三、工具

RSATool2v17.exe

注意：

1.辨别base10/16

• base10: 10进制
• base16: 计算机字节表示
• base64:含字母

2.e要转换为hex

四、RSA相关的数论知识

1. 一个大于1的整数p，若除1和起本身之外没有其他正整数因数（约数），称P为素数。

2. 若整数a和b最大公约数为1，则称a，b互素，记为（gcd（a，b）= 1）。

3. 设n为正整数，a和b为整数，若a和b被n除后所得余数相同，称a和b模n同余，记为a≡b（mod n）。此式被称为同余式。若n能整除a则同余式表示为a≡0（mod n）。

两个整数模n同余的等价说法有：a和b被n除余数相同。a-b被n整除。a和b在模n的同一个剩余类中。存在整数s使得a=sn+b。

4. 同余式的一些运算性质，

（1） 若a≡b（mod n），c≡d（mod n）则有ac≡bd（mod n）。特别的有，ka≡kb（mod n），k为任意整数。

（2） 若a≡b（mod n），d是a，b，n的公因数，则(a/d) ≡(b/d)（mod n/d）。特别的有an≡bn（mod n），n为正整数。[微软中国2]

（3） 若ka≡kb（mod n），且k与n互素时，有a≡b（mod n）。（同余式消去律）

5. 设n为正整数 ,则任何一个整数被n除 ,余数必为0,1,2,…,n-1中的某一个,把整数集中被n除余数相同的数分别归为一类,记为[0],[1],[2]…,[n-1],这样就按模是否同余把整数集分成n类,其中每一类都称为模n的一个剩余类。显然,每个整数必属于上述类中的一类,被n除余数不同的数必属于上述的不同类中。若a0,a1,a3…,an-1分别取自上述类的不同类中,称a0,a1,a3…,an-1为模n的一个完全剩余系,该剩余系中的数两两模n不同余。

6. 含有未知量的同余式称为同余方程。一次同余方程是最简单的一种,其一般形式为ax≡b（mod n）。若a，n的最大公约数d能整除b，则ax≡b（mod n）有解。且恰有d个解。若a，n的最大公约数d不能能整除b，则ax≡b（mod n）无解。例如同余方程7x≡1（mod 5）。7与5最大公约数为1，能被b=1整除，故有一个解。7x≡1（mod 5）≡6≡11≡21（mod5）。由于7与5互素有消去律得x=3。.[微软中国3]
一般地 解同余方程的步骤为 ①判断解的情况 ②当同余方程的a，b，n有公因数时 ,约去公因数化简方程 ③利用同余的定义和消去律求方程的解。

7. 费马小定理：设任意整数a和素数p互素[微软中国4] ，则ap-1 ≡1（mod p）。

8. 欧拉定理：若n,a为正整数，且n,a互质，(a,n) = 1，则a^φ(n) ≡ 1 (mod n)。

9. 模运算极其性质：

基本理论:

基本概念：

给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r ；

其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。

对于正整数p和整数a,b，定义如下运算：

取模运算：a % p（或a mod p），表示a除以p的余数。

模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。

模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。

模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。

说明：

1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。

2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

基本性质:

（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)

（2）(a % p)=(b % p)意味a≡b (% p)

（3）对称性：a≡b (% p)等价于b≡a (% p)

（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

     (a + b) % p = (a % p + b % p) % p （1）

     (a - b) % p = (a % p - b % p) % p （2）

     (a * b) % p = (a % p * b % p) % p （3）

     (a^b) % p = ((a % p)^b) % p （4）

结合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

     ((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

交换率： (a + b) % p = (b+a) % p （7）

     (a * b) % p = (b * a) % p （8）

分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

重要定理

      若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）

（取自RSA算法以及数学基础_rsa的加密过程和解密过程互逆吗-CSDN博客）

五、经典题型

1、已知 公钥（n, e） 和 密文 c  求 明文 m？

import libnum
from Crypto.Util.number import long_to_bytes
 
c = 0x6cd55a2bbb49dfd2831e34b76cb5bdfad34418a4be96180b618581e9b6319f86
n = 108539847268573990275234024354672437246525085076605516960320005722741589898641
#n = int("",16)
e = 65537
#e = int("",16)
q = 333360321402603178263879595968004169219
p = 325593180411801742356727264127253758939
 
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n)   # m 的十进制形式
string = long_to_bytes(m)  # m明文
print(string)  # 结果为 b‘ m ’ 的形式

2、欧几里得算法（n1、n2求n），c不相同，e相同，求明文

3、共模攻击（m，n相同；e，c不同，且e1 和 e2互质）

当题目给我们很多组c和e，但它们加密使用的模数n相同时，我们可以考虑共模攻击，当e1，e2互质，有gcd(e1,e2)=1，根据扩展欧几里得算法，一定存在整数x,y使得e1*x+e2*y=1。我们可以调用gmpy2.gcdext()来使用扩展欧几里得算法，以此求出x和y。

又根据加密过程，c1=pow（m，e1，n）、c2=pow（m，e2，n）。所以

(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)modn

又经过一堆化简之后就可以得到：m = (c1^x*c2^y)modn,得到明文。

gmpy2.gcdext( , )：

gmpy2.gcdext(e1, e2) 是 gmpy2 库中的一个函数，它用于计算两个整数 e1 和 e2 的扩展欧几里得算法（Extended Euclidean Algorithm）。这个算法不仅返回 e1 和 e2 的最大公约数（GCD），还返回两个额外的整数 x 和 y，它们满足贝祖等式（Bézout's identity）：

x * e1 + y * e2 = gcd(e1, e2)

4、低加密指数攻击（e很小）

适用情况：n很大但是e很小，一般e=3

n很大时我们就不能因式分解了，当然还有其他思路，例如当e很小时，比如e=3，有，我们可以对k进行爆破，直到可以开根，借此得到m。

gmpy2.iroot( , )

gmpy2.iroot(m, e) 是 gmpy2 库中的一个函数，用于计算整数 m 的 e 次方根。这个函数尝试找到一个整数 x 和一个整数 y（通常是 0），使得 x^e + y 尽可能接近 m，且 x^e 不超过 m。在大多数情况下，y 会是 0，除非你请求一个非常高的次方根且 m 不足以被完美地表示为某个整数的 e 次方。

函数的返回值是一个元组 (x, True/False)，其中 x 是 m 的 e 次方根（作为整数），而布尔值 True/False 表示 x 是否是一个完美的 e 次方根（即 x^e 是否严格等于 m）。

5.低解密指数攻击（e很大）wiener攻击

适用情况：e很大

和低加密指数攻击相反，当e很大的时候我们怎么办呢，这里就要用到低解密指数攻击。当e很大时，相对的d就会很小。这里我们用到github上一个wienerHacker脚本

 git clone https://github.com/pablocelayes/rsa-wiener-attack