RSA加密和相关攻击

2024-03-07 10:07:32

涅普冬令营第五课--------rsa加密和攻击 入口

1.什么是RSA

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

对称密码

 非对称密码

单向函数

对每一个输入 x，函数值 f(x) 都很容易计算
对随机给出的函数值 f(x)，算出原始输入 x ，却比较困难
使用陷门信息 (trapdoor information) 则可以反逆

2.一点点数论基础

(1)同余

若a,b为两个整数,且它们的差a-b能被某个自然数m所整除,则称α就模m来说同余于b,或者说a和b关于模m同
余,记为:a≡b(modm)。它意味着:a-b=m*k(k为某个整数)。

性质
对于整数a,b,c和自然数m,n,对模m同余具有以下一些性质
1.自反性:a≡a(mod m)
2.对称性:若a≡b(mod m),则b≡a(mod m)
3.传递性:若a≡b(mod m)，b≡c(mod m),则a≡c(mod m)
4.同加性:若a≡b(mod m),则a+c≡b+c(mod m)
5.同乘性:若a≡b(mod m),则a * C≡b * c(mod m)
若a≡b(mod m),c≡d(mod m),则a * c≡b* d(mod m)
6.同幂性:若a≡b(mod m),则aⁿ ≡ bⁿ(mod m)
7.推论1:a * bmod k=( a mod k) * ( b mod k)mod
8.推论2:若a mod p =x,a mod q=x,p,q互质,则a mod p * q=x。
证明:因为 a mod p=x, a mod q=x,p,q互质
则一定存在整数s,t,使得a=S * p+x,a=t * q+x
所以,8 * p=t * q
则一定存在整数r,使S=r * q
所以,a=rpq+x,得出: a mod p * q=x

(2)模拟元

模逆元也称为模倒数。
一整数a对同余n之模逆元是指满足以下公式的整数b：
a^-1= b(mod n)
也可以写成以下的式子:
ab≡1(mod n)
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素,若此模逆元存在,在模数n下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。

可以使用Python第三方包Crypto的 inverse() 函数求模逆元。
from Crypto.Util.number import inverse
print(inverse(3, 7)) # 3 是要求逆元的数，7是模数
可以使用Python第三方包gmpy2的invert() 函数求模逆元。
from gmpy2 import invert
print(invert(3, 7)) # 3是要求逆元的数，7是模数
可以在SageMath中直接用 inverse_mod() 函数求模逆元。 inverse_mod(3, 7) #3 是要求逆元的数，7是模数

模运算

欧拉函数

Z_m内与m互素的整数的个数可以表示为Φ(m)
示例：
假设m等于6时,现在对应的集合为{0,1,2,3,4,5}
GCD(0,6)=6
GCD(1,6)=1--------互素
GCD(2,6)=2
GCD(3, 6)=3
GCD(4,6)=2
GCD(5,6)=1--------互素
由于该集合中,有两个与6互素的数字,即1和5,所以欧拉函数的值为2,即Φ(6)=2。

不难看出，如果数值非常大的话，将集合内的元素从头至尾都处理一遍并计算 gcd
的欧拉函数的计算方法会非常慢。实际上，使用这种最直接的方法计算公钥密码学中使
用的非常大的整数对应的欧拉函数是非常困难的。幸运的是，如果 m 的因式分解是已
知的，则存在一个更简单的计算方法，如下图所示。
假设m=240,240因式分解对应的素因数相乘形式为
m=240=16 * 15=2⁴ * 3 * 5
Φ(m)=23 * (2-1) * (3-1) * (5-1)=8 * 1 * 2 * 4=64
所以想要计算出一个合数的欧拉函数,需要先知道这个数
的因式分解,—些大整数的乘积难以被分解的特点也保证了RSA公钥加密的安全性

3.RSA 是如何加密和解密的

RSA加密中会出现以下几个参数
1.两个大的素数 p 和 q ,以及它们的积 n , n 是加解密过程中的模数
2.欧拉函数q(n)=(p-1) * (q-1)
3.加密指数 e ,和解密指数d= Invert(e,φ(n))
4.密文 c ,明文 m

4. Python 简单实现 RSA 算法

1)生成随机素数
getPrime()函数，括号里的参数意义为位长度，下面示例表示生成一个 512bits 的随机素数。

from Crypto.UtiL.number import *
p=getPrime(512)

getStrongPrime() 函数，括号里的参数意义为位长度，生成一个更安全的素数。

from Crypto.UtiL.number import *
p = getstrong Prime(512)

2)计算模逆元的两个函数的区别
使用 Crypto 包里的 inverse() 函数，两个参数不互素的时候返回的是除以最大公因数之后的逆元。互素的情况下和gmpy2的invert返回值相同。

from Crypto.UtiL.number import *
d= inverse(e,(p-1)*(q-1))

使用 gmpy2 包里的 invert() 函数，两个参数不满足互素时会报错，只有满足互素时正常求逆元。

from gmpy2 import invert
d= invert(e,(p-1)*(q-1))

3)判断素数
isPrime() 可以用来判断素数

from Crypto.Util.number import *
print(isPrime(7))

求最大公因数

from Crypto.Util.number import *
print(GCD(12, 18))    # 6

4)开 n 次方根
使用 gmpy2 的 iroot 函数，可以开 n 次方根，返回一个数字，一个布尔值。数字表示开根的结果，布尔值表示结果的 n 次方是否刚好等于原来的数。

from gmpy2 import iroot
print( root(4,2))     #表示对 4 开平方根

RSA加密

from Crypto.UtiL. number import *
m = 123456
e = 65537
p, g= getPrime(128), getPrime(128)
n =p * q
c= pow(m, e, n)
print(c)
#4644656753073432895689505062145185541306861424178348965758370527982913123577

RSA解密

from Crypto.Util. number import *
p = 307677955863441770267761398816442898269
q = 234956087764792853945937117492863651101
e = 65537
C = 25009787683260330186467878431892979552086452988450015957799934262727022882703
d = inverse(e,(p-1)*(q-1))
n = p * q
m = pow(c, d,n)
print(m)
#123456

现在 Alice 想要接收 Bob 的一串数字 123456，他们的通信线路是不安全的，可以被攻击者 Eve 窃听到，所以他们可以使用 RSA公钥加密算法，使信息安全的传输。
Alice 首先需要生成公钥 (e, n)，和不发送的私钥 d。Alice 会将 (e, n) 发送给 Bob：

from Crypto.Util. number import *
e = 65537
p, q = getPrime (128),  getPrime(128)
n = p * q
d = inverse(e, (p-1)*(q-1))
print( "n =",n）
print( "d =",d)
#n = 64119097861467025841314869723386401172380445670197869142261589855521615781313
#d = 34488339696882282190704342167311503848344429551595618555980250777974774475073

现在 Bob 接收到了 Alice 发送的公钥 (e, n)，他使用这组公钥加密自己的明文，并把密文 c 发送给 Alice：

from Crypto.Util. number import *
e=65537
n=64119097861467025841314869723386401172380445670197869142261509855521615781313
m=123456
c= pow(m, e, n)
print("c =",c)
#c = 35175839627001706475239565374293351303180888840171603334474497768320397005778`

Alice 接收到了 c，她还有之前生成的解密指数 d，她可以用私钥 (d, n) 解开密文：

from Crypto.Util. number import *
d=34488339696882282190704342167311503848344429551595618555980250777974774475073
n=64119097861467025841314869723386401172380445670197869142261509855521615781313
C=35175039627001706475239565374293351303180888840171603334474497768320397005778
m= pow(c, d, n)
print("m =”， m)
#m=123456

所以 Alice 最终得到了 Bob 的明文，并且他们在这条不安全的通信线路中传递了两次信息，这两次都被 Eve 成功窃听到。
那么 Eve 现在掌握的信息是：
• Alice 和 Bob 在使用 RSA 公钥加密算法传递信息。
• 窃听到了 Alice 发送的 e 和 n。
• 窃听到了 Bob 发送的 c。
Eve 想要窃取到明文 m，需要从这三个参数入手。
在很多 CTF 密码学题目中，我们解题就相当于 Eve 做的事情——攻击加密算法。

5.RSA 相关的攻击算法

1)分解素因数攻击

以上面的 Alice 和 Bob 泄露的信息为例，开始第一种攻击，我们现在已知的参数：

e = 65537
n =64119097861467025841314869723386401172380445670197869142261509855521615781313
c =35175039627001706475239565374293351303180888840171603334474497768320397005778

解密需要计算 pow(c, d, n)，所以我们需要知道 d，然而 d = invert(e, φ(n))，这个
式子中我们已知了 e 和 n，invert很好计算，就需要算 φ(n)，现在问题是如何计算 n 的
欧拉函数，我们需要知道 n 的素因数分解。
n 的数值很大，RSA中常用的数量级往往不能通过枚举的方法（试除法）分解因数。
但是如果生成的素数是不安全的，有可能导致 n 很容易被分解。
在这一个例子中，我们可以知道 n 是 256 位的，这种长度完全是不安全的（通常
生成的素数约 2048 位），所以我们尝试使用一些算法或工具来尝试分解 n。
整数分解
 整数因数查询

2)共模攻击

如果在 RSA 的使用中使用了相同的模 n 对相同的明文 m 进行了加密，那么就可以在不分解 n 的情况下还原出明文 m 的值。

通过扩展欧几里德算法，可以计算出：
这样就有：

但是 r 和 s 中必有一个是负数，所以需要用逆元来处理一下(假设s<0)：

3)已知 p+q 或 p-q

或者是题目给了其他的pq之间的关系，通过解方程组或推导来求出p和q。

p ∗ q = n
p + q = a

使用SageMath解方程组：
var(‘p q’)
solve([p*q == n, p+q == a], [p, q])

4)小公钥指数攻击

当加密指数 e 很小，比如 e = 3 时，c 可能不比 n 大很多（可能是 n 的几十倍或者几百倍，在可枚举的范围之内）。
这样就存在一个较小的可枚举的 k 满足：

m³ = c + k ⋅ n

尝试枚举 k 并开根，能刚好开根的就是解。

5)已知e，d 分解 n

ed≡1(mod Φ(n) )
ed=1+k * Φ( n ) , k < e

穷举k，计算出Φ(n):

Φ(n)=(p-1)(q-1)=n-(p+q)+1

解一个二元二次方程组:

p + q=n - Φ(n)+1
p * q=n

6)已知明文高位攻击

Coppersmith定理指出在一个 e 阶mod n的多项式f(x)中,如果有一个根小于n^1/e,就可以运用一个O(log n)的算法求出这些根
所以在e等于3,并且已知明文高位,可以尝试使用 Coppersmith攻击。

PR.< x > =
PolynomialRing(Zmod(n))
f = (m0 + x) ^ 3 - c
ans = f.small_roots(X=2 ^ 500)
m = ans[0]+m0

7)Partial p 攻击

PR.< x > = PolynomialRing(Zmod(n))
f = x + p0
roots = f.small_roots(X=2^256, beta=0.3)

8)RSA Last Bit Oracle Attack

假设存在一个 Oracle，它会对一个给定的密文进行解密，并且会检查解密的明文的奇偶性，
并根据奇偶性返回相应的值，比如 1 表示奇数，0 表示偶数。那么给定一个加密后的密文，
我们只需要 log(N) 次就可以知道这个密文对应的明文消息

C = P^e mod N
p^e * e^e=(eP)^e mod N

服务器会计算得到 2 P mod N
2P 是偶数，它的幂次也是偶数。
N 是奇数，因为它是由两个大素数相乘得到。
如果服务器返回奇数,即2 P mod N为奇数,则说明2P大于N,且减去了奇数个N,又因为2P < 2N,因此减去了一个N,即N/2 ≤ P < N,我们还可以向下取整。
服务器返回偶数,则说明2P小于 N。即0 ≤P<N/2,我们还可以下取整。
那么第i次时: