RSA加密方式及常见攻击手法

RSA_0">RSA：

RSA_2">RSA加密操作流程：

第一步：选取一对不相等且足够大的质数，记做p和q；

第二步：计算p和q的乘积n；n=pq;

第三步：计算欧拉函数：phi(n)=(p-1)(q-1)

第四步：选一个与phi(n)互素的整数e，1<e<phi(n)

第五步：计算出e对phi(n)的模反元素d，de mod phi(n)=1;

第六步：公钥—K1=(e,n);

第七步：私钥—K2=(d,n);

加密：明文M: M^e mod n = C

解密：密文C: C^d mod n = M

RSA_22">RSA普通破解方式

RSA_24">1.RSA安全位数：

RSA算法的安全性取决于其底层的数学难题—大整数因数分解问题的难度。目前最新的大整数分解的世界记录为829-bits().

请添加图片描述

2.直接分解：

对于一些不安全/位数比较小的素数（N），以当前的算法和算力很容易将其分解。通常在300bits以下的模数均可在较短的时间内被分解，一些不安全的素数也会很快被特定的算法所分解掉

CTF中常见的分解手法：

在线网站：factordb.com（类似于一个映射表，存放前人已经分解过的大素数的分解结果，然后根据你的输入进行查找）

在线网站：https://www.alpertron.con.com.ar/ECM.HTM（运行ECM分解算法来计算）

工具:yafu

SageMath内置的factor函数：

操作：

1.判断n的位数：

python">n=0x564656435135468436651321354368368154136547683543n.bit_length()

2.求p和q

因为n的位数比较小直接通过在线网站可以获取到n的分解结果p和q

3.求解明文m

之后的步骤相当于已知p和q，c求明文m

#n，p和q已知可推出
#公钥e，密文c知道from Crypto.Util.number import *
d=inverse(e,(p-1)*(q-1))
m = pow(c,d,n)long_to_bytes(m)
print(long_to_bytes(m))

3.p,q相近：

在计算RSA模数的时候，生成两个素数靠的很近，这个时候也很不安全的。

例如生成：

生成代码：

p和q相近的情况：

python">from Crypto.Util.number import getPrime,isPrimedef nextPrime(p):p=(p+2)|1 #一般p是一个素数while not isPrime(p):p+=2return pdef genKey(bits):p=getPrime(bits)q=nextPrime(p)e=65537n=p*qreturn n

这样的话一般来说生成的两个数p和q相差仅仅不过几百或者几千

破解原理：

此时，会有如下关系：
$p^2 < n <q^2$
如果对n开近似平方根：

$p < \sqrt n < q$
则近似平方根必然落在p和q之间，并且距离p和q很近，可以通过穷举的方式找到p和q。

4.（模不互素）

当两个模数共有一个素数时，有如下关系：

n1=p*q1

n2=p*q2

可以对n1和n2求最大公约数（gcd），这两者的最大公约数即为其中的一个素因子p，从而可以分解为这两个模数。

python">#案例代码：
p=getPrime(1024)
q1=getPrime(1024)
q2=getPrime(1024)n1=p * q1
n2=p * q2#解题代码from Crypto.Util.number import GCDp=GCD(n1,n2)
q1=n1 // p	#整除
q2=n2 // p

5.共模攻击：

两个用户使用相同的模数，不同的私钥，加密同一明文消息时存在“共模”

python">#案例代码p = getPrime(512)
q = getPrime(512)
n = p*q
e1 = getPrime(64)
e2 = getPrime(64)
m = bytes_to_long(flag)c1 = pow(m,e1,n)
c2 = pow(m,e2,n)

RSA解密可以看作是，对C开e次方根；或者说是，找到一个d，使得
$m^e)^d≡m^1(mod n)$
目的是为了让m右上角的指数变成1。

这在只有一个 $c≡m^e(mod n )$ 时是很难得的，因此也被称为RSA Problem

目前已经有了两组这样的关系：

m^e1≡c1(mod n )

m^e2≡c2(mod n )

可以通过扩展欧几里得算法计算出

re1 + se2 = 1

从而有：

C1^r * C2^s ≡ m^(re1 + se2)≡m^1(mod n )

使得右上角的指数变成1

python">def egcd(a, b):'''Extended Euclidean Algorithm.returns x, y, gcd(a,b) such that ax + by = gcd(a,b).'''u, u1 = 1, 0v, v1 = 0, 1while b:q, r = divmod(a, b)u, u1 = u1, u - q * u1v, v1 = v1, v - q * v1a, b = b, rreturn u, v, ar, s, _ = egcd(e1, e2)
if r < 0:r = -rc1 = inverse(c1, n)
else:s = -sc2 = inverse(c2, n)m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(m))

RSA_239">RSA指数相关利用手法：

1.小公钥指数的利用:

1.引言：

RSA算法通过模幂运算对明文信息加密，当指数逐渐增大时，模运算将会发挥作用，将整数的幂运算的结果截断到有限的范围内。

但是当指数太小时，模运算还未发挥作用，幂运算就已经结束了。此时的加密结果并没有被解截断，即是原本的幂运算，此时就不存在“加密”效果了。
$C≡m^e (mod n ) ==> c =m^e$

2.什么情况下会发生小公钥指数利用？

当m较小时，即m^e < n时，就会存在这种利用。

另外，即使m^e稍比n大一点点，也可以通过穷举的方式对其尝试开根。

$\equiv m^e \pmod{n} \Rightarrow c = m^e - k \cdot n$

可以从0开始穷举k，并对k·n+c尝试开e次方根，若可以开出来根，则说明成功解密。（对于正常的RSA加密，k一般很大，无法被穷举）

3.代码：

python">from sympy import nth_root# 假设这些值是已知的
c = 123456789  # 密文
e = 3          # 公钥指数
n = 323         # 模数# 尝试穷举k来破解RSA加密
for k in range(0, 1000000):tmp = k * n + croot = nth_root(tmp, e, 1)[0]  # 计算e次方根if root.is_integer and root > 0:  # 检查根是否为正整数print(f"成功解密: 明文m = {int(root)}")break
else:print("在给定的范围内未能成功解密。")

2.已知e和d分解n

RSA算法若能够知道加密指数e和解密指数d，则可以完成对n的分解。

根据e和d的关系有

$\cdot d \equiv 1 (\text{mod} \phi(n))$

同样可以化为

$\Rightarrow e \cdot d = 1 + k \cdot \phi(n)$

其中 $\phi(n)$ ，因此必有 $k < e = 65537$ ，k可以穷举，从而可以得到 $\phi(n) = (p - 1) \cdot (q - 1)$ 。

得到 $\phi(n)$ 后，根据 $\phi(n)$ 的表达式有

$\phi(n) = (p - 1) \cdot (q - 1)$

再结合n的表达式

$\cdot q$

可以组成一个二元二次方程，解出这个方程，就可以得到 p和 q，从而分解n。

from sympy import symbols, solve# 已知的RSA参数
e = 65537  # 公钥指数
d = 123456789  # 私钥指数，这里只是示例，实际情况下d是保密的
n = 1234567890123456789  # 模数，这里只是示例# 穷举k的值来找到φ(n)
for k in range(1, e):if (e * d - 1) % k == 0:  # k可以整除ed-1phi = (e * d - 1) // k# 检查是否满足欧拉定理if pow(123, phi, n) == 1:# 定义变量p和qp, q = symbols('p q')# 解方程组solution = solve([p * q - n, (p - 1) * (q - 1) - phi], (p, q))if solution:print("分解结果:", solution)break

3.Wiener利用

利用条件：

当d比较小（d<1/3*N^(1/4)）时，对手可以使用Wiener利用来获取私钥d。

特征：（加密指数e和模数N差不多长度的情况下，可以使用这种手段破解）

通常出题人为了要使得生成的私钥d比较小，通常会先生成一个比较小的d，然后再去求e，从而使得e的取值范围位于（1，Φ）之间，会导致e看起来很大。

从φ(n)和e、d的关系式出发，有

$\dot{=} 1 + k \cdot \phi(n)$

代入 $\phi(n)$ 的表达式（拆开）

$\phi(n) = (p - 1) \cdot (q - 1) = n - (p + q) + 1$

有

$\cdot (n - (p + q) + 1)$

两边同时除以nd，可得（近似表示）\delta很小无限接近于零

$\frac{e}{n} = \frac{k}{d}(1 - \delta)$

对于该式子左边均已知，右边均未知。

右边的比值和左边的比值非常接近，这种情况可以使用连分数来将左边的比值展开，在连分数的展开式中，很大概率存在k和d。从而可以求出私钥d，进行解密。

python">from sympy import symbols, solve, convergents, is_squaredef recover(e, N):cf = convergents(e / N)G = symbols('x', integer=True)for index, k in enumerate(cf[1:]):d0 = k.denominatork = k.numeratorif k != 0 and (e * d0 - 1) % k == 0:phi = (e * d0 - 1) // ks = (N - phi + 1)f = x**2 - s * x + Nb = f.discriminantif b > 0 and is_square(b):d = d0roots = list(zip(*f.roots()))[0]if len(roots) == 2 and prod(roots) == N:print("[x] Recovered! \\d = %0x" % d)return delse:continueprint("[] Could not determine the value of d with the parameters given. Make sure that d < 1/3 * N^0.25")return -1# 示例使用
# 假设e和N是已知的RSA参数
e = 65537
N = 323  # 这里只是一个示例值，实际中N会是一个非常大的数# 调用recover函数尝试恢复私钥d
recover(e, N)

RSALSB_409">RSA-LSB利用手法

LSB Oracle Attack

假设现在有一个oracle（预言机），它会对一个给定的密文进行解密，但并不会直接返回解密结果，而是检验解密的明文的奇偶性，并根据奇偶性返回相应的值，比如1表示奇数，0表示偶数，即最低位（LSB, least significant bit）。

那么给定任意一个消息被加密后的密文，只需要log(N)次oracle询问，就可以解密出明文消息。（例如当N是1024位时，只需要大约1024次左右的oracle询问，就可以解密出明文。）

请添加图片描述

预言机（Oracle）端代码：

python">#这行代码提示用户输入一个加密后的消息，并使用raw_input函数获取#输入。输入的字符串通过strip()方法去除首尾的空白字符，然后通过#int()函数转换为整数。这个整数代表加密后的消息。
cc = int(raw_input('Your encrypted message: ').strip())
mm = k.decrypt(cc)#检查mm的最低位,最低位是1，mm是一个奇数。
if mm & 1 == 1:print('The plain of your decrypted message is odd!')
else:print('The plain of your decrypted message is even!')

攻击方式：

RSA_436">RSA的积性（乘法同态）:

数学原理：

两个明文乘积的加密等于两个明文加密的乘积

$\operatorname{Enc}(P_1 \cdot P_2) = \operatorname{Enc}(P_1) \cdot \operatorname{Enc}(P_2)$

证明：

$(P_1 \cdot P_2)^e = P_1^e \cdot P_2^e \pmod{n}$

利用这个性质，可以选择一个s，并计算 $\equiv c \cdot s^e \pmod{n}$ ，将 $c^{'}$ 发送给服务器，服务器会返回c’解密结果 $\cdot s$ 的奇偶性。通过不断巧妙地继续选取s，就可以恢复出m。

攻击手法（二分思想–缩小m范围）：

假设我们现在已经获取到了明文m加密所得的密文c。

第一次选择s=2，并向服务器发送

$\equiv c \cdot 2^e \pmod{n}$

服务器解密得到

$\equiv 2 \cdot m \pmod{n}$

并会返回 $\cdot m \pmod{n}$ 的奇偶性。

由于 $m < n$ （解密的时候m是余数，所以m一定小于n的），所以 $2\cdot m \pmod{n}$ 有两种情况：

没有被mod n，就是 $2\cdot m$ ，此时服务器会返回“偶数”。这说明 $2\cdot m<n$ ，即 $\leq m < \frac{n}{2}$ 。

被mod n了，解密结果为 $2\cdot m - n$ ，由于 $2\cdot m$ 为偶数且 n为奇数，因此服务器必然会返回“奇数”。这说明 $2\cdot m > n$ ，即 $\frac{n}{2} < m < n$ 。

第二次选择s=4，并向服务器发送

$\equiv c \cdot 4^e \pmod{n}$

服务器解密得到

$\equiv 4 \cdot m \pmod{n}$

并会返回 $\cdot m \pmod{n}$ 的奇偶性。

在这里插入图片描述

(乘以x个2表示移动2x步)
如果 $\leq m < \frac{n}{2}$ ：

服务器返回“偶数”，说明没有被mod n，有 $\cdot m < n$ ，也就是说 $\leq m < \frac{n}{4}$ 。
服务器返回“奇数”，说明这说明 $\cdot m > n$ ，只有 $\frac{n}{4} < m < \frac{n}{2}$ 。

如果 $\frac{n}{2} \leq m < n$ ：

服务器返回“偶数”，说明 $\cdot m - 2 \cdot n < n$ ，即 $\frac{n}{2} \leq m < \frac{3n}{4}$ 。
服务器返回“奇数”，说明 $\cdot m - 3 \cdot n < n$ ，即 $\frac{3n}{4} < m < n$ 。

小结：

通过上述方法，可以将m的取值范围缩小一半。

之后，仍然可以继续类似的操作，通过选取 $s=2^i$ ，服务器会返回 $\cdot 2^i$ 的奇偶性，从而可以不断地将范围缩小一半，直至最后范围缩小到1，即为正确的m。

python">def oracle(cc):# 这里是模拟oracle的行为，实际情况下，你需要替换为实际的oracle函数# 假设oracle函数返回cc解密后明文的奇偶性，1表示奇数，0表示偶数decrypted = pow(cc, d, n)  # 假设d是私钥指数，n是模数return decrypted & 1# 初始化
L, H = 0, n
t = pow(2, e, n)  # e是公钥指数，n是模数
cc = c  # c是密文# 二分搜索解密
for _ in range(n.bit_length()):cc = (t * cc) % nif oracle(cc) == 0:H = (L + H) // 2else:L = (L + H) // 2print(L, H)m = L  # 得到m的一个近似值# 由于结果可能不精确，需要在附近寻找正确的m
for x in range(-1000, 1000):if pow(x + m, e, n) == c:print(x + m)  # 打印出正确的mbreak

RSACoppersmith_542">RSA-Coppersmith相关利用手法

1.coppersmith定理

1996年，Don Coppersmith借助LLL算法构造格子，发现了一种可以求解任意多项式“小”根的算法，即Coppersmith定理。

Coppersmith将这个算法应用在了RSA上面，从而打开了RSA的一个新的利用面，可以在已知某些关键信息（例如明文的部分bit、p的部分bit）的情况下，实现对RSA的破解（解密密文/分解模数），这种利用手法被称为Coppersmith利用。

假设N为一个未知分解情况的合数，并定义 $a_{k-1}x^{k-1} + \cdots + a_2x^2 + a_1x + a_0 \pmod{N}$ 为一个最高次数为k的整系数多项式。

假设这个多项式存在一个根 $x_0$ ，即

$p(x_0) = 0 \pmod{N}$

满足 $x_0| < N^{1/k}$ 。

Coppersmith给出了一个算法，可以很快地求出这个“小”根。

(N为1024bit， $k = 3$ 时， $x_0$ 小于341bit)

Coppersmith定理

令 $p (x)$ 为一个最高次数为k的首一多项式，N为一个未知其分解情况的正合数， $\varepsilon > 0$ 为一个极小的量。那么在多项式时间（算法复杂度较低）内，我们可以找到 $p (x)$ 的整数解 $x_0$ ，满足

$\left|x_0\right| < \frac{1}{2} N^{(\frac{1}{k})-\varepsilon}$

（证明过于复杂，涉及到格构造、LLL算法等知识点）

sagemath（数学软件系统）代码：

sage: N = 100001
sage: K = Zmod(10001)
sage: P.<x> = PolynomialRing(K)
sage: f = x^3 + 10*x^2 + 5000*x - 222
sage: f.small_roots()//获取小根

代入RSA的情景：

如果我们可以获得到2/3的明文信息 $m^{'}$ ，并且RSA的加密指数 $e = 3$ ，加密结果为c，现在需要求解另外1/3的明文信息，从而恢复出整个明文信息。

假设未知明文信息为x，那么根据

$m^3=c \pmod n$

即：

$\left(m'+x\right)^3=c \pmod n$

借助Coppersmith的算法，可以将这个多项式中的未知量x（小根）很快地求解出来。

2.已知m高位

题目：

假设模数n为1024bit，e=3，现在已知m的高位m0，只有低72位未知，未知量符合小根的条件（小于341bit）。

设未知量为x，构造如下mod n的多项式：

$f=\left(m_0+x\right)^3-c\pmod{n}$

使用Coppersmith定理即可求解出x。

请添加图片描述

除了已知m的高位这种利用场景，Coppersmith还适用于很多其他场景：

已知p的高位
已知d的高位
Padding过短
…