RSA 密码算法是使用最为广泛的公钥密码体制。该体制简单且易于实现，只需要选择 5 个参数即可（两个素数$p$和$q$、模数$N=pq$，加密指数𝑒和解密指数𝑑）。设𝑚为待加密消息，RSA 体制破译相当于已知$𝑚^𝑒 \pmod 𝑁$，能否还原𝑚的数论问题。目前模数规模为 2048 比特的RSA 算法一般情况下是安全的，但是如果参数选取不当，同样存在被破译的可能。
有人制作了一个 RSA 加解密软件（采用的 RSA 体制的参数特点描述见密码背景部分）。已知该软件发送某个明文的所有参数和加密过程的全部数据（加密案例文件详见附件 3-1）。Alice 使用该软件发送了一个通关密语，且所有加密数据已经被截获，请问能否仅从加密数据恢复该通关密语及 RSA 体制参数？如能请给出原文和参数，如不能请给出已恢复部分并说明剩余部分不能恢复的理由？
- 每个使用者，任意选择两个大素数𝑝和𝑞，并求出其乘积$N=pq$
- 令$𝜑(𝑁) = (𝑝 − 1)(𝑞 − 1)$，选择整数𝑒，使得$GCD(𝑒,𝜑(𝑁)) = 1$，并求出𝑒模𝜑(𝑁)的逆元𝑑，即$𝑒𝑑 ≡ 1 mod 𝜑(𝑁)$.
- 将数对(𝑒, 𝑁)公布为公钥，𝑑保存为私钥。
Bob 欲传递明文𝑚给 Alice，则 Bob 首先由公开途径找出 Alice 的公钥(𝑒, 𝑁)，Bob 计算加密的信息𝑐为：$𝑐 ≡ 𝑚^𝑒 \pmod 𝑁$。
Bob 将密文𝑐传送给 Alice。随后 Alice 利用自己的私钥𝑑解密：$𝑐^d ≡ (𝑚^𝑒 )^𝑑 ≡ 𝑚^{𝑒𝑑} ≡ 𝑚 \pmod 𝑁$。
1） 模数𝑁 = 𝑝𝑞规模为 1024 比特，其中𝑝，𝑞为素数；
2） 素数𝑝由某一随机数发生器生成；
3） 素数𝑞可以随机选择，也可以由 2) 中的随机数发生器产生；
4） 可以对文本加密，每次加密最多 8 个明文字符；
5） 明文超过 8 个字符时，对明文分片，每个分片不超过 8 个字符；
6） 分片明文填充为 512 比特消息后再进行加密，填充规则为高位添加 64 比特标志位，随后加上 32 比特通信序号，再添加若干个 0，最后 64 比特为明文分片字符对应的 ASCII 码（注：填充方式参见加密案例，但注意每次通信的标志位可能变化）；
7） 分片加密后发送一个加密帧数据，帧数据文件名称为 FrameXX，其中 XX 表示接收序号，该序号不一定等于通信序号；
8） 帧数据的数据格式如下，其中数据都是 16 进制表示，结构如下 $$ 1024bit模数N | 1024bit加密指数e|1024bit密文m^e \pmod N $$
9） 由于 Alice 初次使用该软件，可能会重复发送某一明文分片。
RSA 的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题。数域筛法是目前 RSA 攻击的首选算法。在 1999 年，一台 Cray 超级电脑用了 5 个月时间分解了 512 比特长的密钥。在 512 比特 RSA 算法破解 10 年之后,即 2009 年 12 月 9 日，768比特 RSA 算法即 232 数位数字的 RSA-768 被分解。分解一个 768 比特RSA 密钥所需时间是 512 位的数千倍，而 1024 比特所需时间则是 768比特的一千多倍，因此在短时间内 1024 比特仍然是安全的。除此之外，目前对于 RSA 算法的攻击主要有以下方式:选择密文攻击、公共模数攻击、低加密密指数攻击、低解密指数攻击、定时攻击等等，详细的 RSA 安全分析参见有关文献。
首先用现有的分解大整数的方法对所有的模数进行测试
费马分解法用于p与q相近的n，注意到$(p+q)^2-4n=(p-q)^2$，那么我们可以得知$(p+q)/2$与$\sqrt{N}$接近，，通过爆破这个差值能够容易地计算出p+q，从而分解n。
from Crypto.Util.number import *
from gmpy2 import iroot
nec = open(f"./Frame14",'r').read()
n = int(nec[:len(nec)//3],16)
e = int(nec[len(nec)//3:len(nec)//3*2],16)
c = int(nec[len(nec)//3*2:],16)
a = iroot(n,2)[0]+1
for i in range(a,a+100000000):
if iroot(i**2 - n,2)[1]:
b = iroot(i**2 - n,2)[0]
p = (i+b)
q = (i-b)
print(p)
print(q)
break
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)).split(b'\x00')[-1])Pollard's p − 1 算法由John Pollard在1974年提出。这个算法要求N一个因子是$p-1$光滑的，即$p-1$是一些小于$B$的因子的乘积。令整数$a$与$p$互素，根据费马小定理：
即$\gcd(a^{k(p-1)}-1,n)$如果不是$1$或者$N$,则一定是$p$的倍数。又因为$p-1$光滑，那么存在$M=\prod_{q\leq B}q^{\left \lfloor \log _q B\right \rfloor}$使得$(p-1)|M$。在算法中，考虑$M=N!$既能满足条件又能方便计算。
Alg 1. Pollard p-1算法
Input: $N$
Output:
-
$a=2,x=2$ -
while True:
$a=a^x \pmod N$ $res=\gcd(a-1,N)$ if
$res \neq 1$ and$res \neq N$ : return$res$ $n=n+1$
这个算法的时间复杂度是$\mathcal{O}(B \log B \cdot \log^2 n)$，选取更大的$B$需要更长的运行时间，更可能成功分解$N$。
# python2
from Crypto.Util.number import long_to_bytes
import gmpy2
nec = open(f"./Frame6",'r').read()
n = int(nec[:len(nec)//3],16)
e = int(nec[len(nec)//3:len(nec)//3*2],16)
c = int(nec[len(nec)//3*2:],16)
def Pollard_p_1(N):
a = 2
while True:
f = a
for n in range(1, 200000):
f = gmpy2.powmod(f, n, N)
if n % 2 == 0:
d = gmpy2.gcd(f-1, N)
if 1 < d < N:
return d
print(a)
a += 1
p = Pollard_p_1(n)
q = n // p
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)
m = long_to_bytes(gmpy2.powmod(c,d,n)).split(b'\x00')[-1]
print(m)
'''
2: b' That is'
6: b' "Logic '
19: b'instein.'
'''尝试因数碰撞法，即对每一个n计算公因数，若能够计算出非0公因数则能够直接将两个n进行分解。
from Crypto.Util.number import *
from gmpy2 import invert
nec1 = open(f"./Frame1",'r').read()
n1 = int(nec1[:len(nec1)//3],16)
e1 = int(nec1[len(nec1)//3:len(nec1)//3*2],16)
c1 = int(nec1[len(nec1)//3*2:],16)
nec = open(f"./Frame18",'r').read()
n = int(nec[:len(nec)//3],16)
e = int(nec[len(nec)//3:len(nec)//3*2],16)
c = int(nec[len(nec)//3*2:],16)
p = GCD(n1,n)
q1 = n1 // p
q = n // p
d1 = invert(e1,(p-1)*(q1-1))
d = invert(e,(p-1)*(q-1))
print("1:",long_to_bytes(pow(c1,d1,n1)).split(b'\x00')[-1])# frame 1
print("18:",long_to_bytes(pow(c,d,n)).split(b'\x00')[-1])# frame 18
'''
1: b'. Imagin'
18: b'm A to B'
'''对于使用了相同的n相同m，不同e所对应的两个密文，我们可以通过共模攻击在不分解n的前提下求解出m。 $$ c_1= m^{e_1}\pmod n\ c_2=m^{e_2}\pmod n \ $$ 已知以上信息，我们可以通过扩展欧几里得的方法求出$xe_1+ye_2=\gcd{(e_1,e_2)}$的方法，使得模数变小，而一般gcd等于1时，直接求得就是m了即$c_1^xc_2^y=m^{xe_1+ye_2}\pmod n=m$。
from Crypto.Util.number import *
from gmpy2 import gcdext
nec = open(f"./Frame0",'r').read()
n = int(nec[:len(nec)//3],16)
e1 = int(nec[len(nec)//3:len(nec)//3*2],16)
c1 = int(nec[len(nec)//3*2:],16)
nec = open(f"./Frame4",'r').read()
n = int(nec[:len(nec)//3],16)
e2 = int(nec[len(nec)//3:len(nec)//3*2],16)
c2 = int(nec[len(nec)//3*2:],16)
g,a,b = (gcdext(e1,e2))
m = (pow(c1,a,n) * pow(c2,b,n))%n
print(long_to_bytes(m))
'''
0:b'My secre'
4:b'My secre'
'''对于e=3与5的几个密文，如果他们所对应的明文相同，则可以通过小指数广播攻击来求解出m。用这种方法只求解出了e=5的5个密文对应的明文，求不出e=3对应的明文，原因是e=3的三个明文不同，而e=5时五个明文相同。
使用中国剩余定理，我们可以解出一个$C = c_i \pmod{n_i}$，而这个$C = m^5 \pmod {n_1n_2...n_5}$，又因为$m<n_i$ ，所以$C < n_1n_2...n_5$，所以该式在ZZ上成立，直接对C开5次方根即可求出m。
from Crypto.Util.number import *
from gmpy2 import invert,iroot
from functools import reduce
nlist=
clist=
index=[3, 8, 12, 16, 20]
def CRT(mi, ai):
M = reduce(lambda x, y: x * y, mi)
ai_ti_Mi = [a * (M // m) * invert(M // m, m) for (m, a) in zip(mi, ai)]
return reduce(lambda x, y: x + y, ai_ti_Mi) % M
def small_e_boardcast_attack(nlist , e , clist):
m = CRT(nlist , clist)
tmp = iroot(m , e)
if tmp[1] == 1:
return tmp[0]
else:
return 0
m = small_e_boardcast_attack(nlist,5,clist)
print(long_to_bytes(m).split(b'\x00')[-1])
'''
b't is a f'
'''Coppersmith在1996年给出了一种单变元模多项式方程求小值解的结论后，经过Howgrave-Graham等人完善、改进逐渐成熟。
Howgrave-Graham引入了一个十分重要的引理简化了Coppersmith的证明过程。
Howgrave-Graham 引理1 设$g(x)$为一个具有$\omega$项的单变量多项式，m为一个正整数，若同时满足以下两个条件： $$ g(x_0) \equiv 0 \mod{N^m},,,|x_0| \leq X \notag\ | g(xX) | \leq \dfrac{N^m}{\sqrt{\omega}} \notag $$ 则$g(x)=0$在整数上成立。
定义 格(Lattice)：格
$$
\mathcal{L} ( \boldsymbol{B} ) = \biggl{ \sum{i=1}^{n} x_i \boldsymbol{b}_i \mid x_i \in \mathbb{Z}, i=1,2\dots n \biggr} \notag
$$
其中，$m$是格的维数，$n$是格的秩，通常我们只考虑满秩，即$m=n$的情况。一组线性无关的向量
受高斯在二维格中做格基约简的思路启发，Lenstra、LEnstra、Lov'asz三人将其思路拓展到高维，并在1982年共同提出著名的LLL格基约简算法[LLL82]，任意给定一组格基，此算法可在多项式时间内将其转化为正交性较好的优质基。
**定义 (LLL算法}：**设
定理
设格
Size条件: $$ | u_{i,j} | = \dfrac{| \boldsymbol{v}_i \cdot \widetilde{\boldsymbol{v}}j|}{|\widetilde{\boldsymbol{v}}j |^2} \leq \dfrac{1}{2} \quad \forall 1 \leq j < i \leq n \notag $$ Lov'asz条件: $$ |\widetilde{\boldsymbol{v}}i + \mu{i,i-1}\widetilde{\boldsymbol{v}}{i-1}|^2 \geq \dfrac{3}{4}|\widetilde{\boldsymbol{v}}{i-1}|^2 \notag $$ 令$\mathcal{L}$表示一个维数是$n$的格，则$\mathcal{L}$的任意一组LLL约简基$\boldsymbol{v}_1,\boldsymbol{v}_2 \dots \boldsymbol{v}_n$具有如下两条性质:
$$ \prod_{i=1}^n |\boldsymbol{v}_i| \leq 2^{\frac{n(n-1)}{4}} \det (\mathcal{L}) \notag\
|\boldsymbol{v}_j | \leq 2^{\frac{i-1}{2}} |\widetilde{\boldsymbol{v}}_i | \quad \forall 1 \leq j < i \leq n \notag
$$
除此之外，LLL的初始向量，即得到的近似最短向量满足:
$$
|\boldsymbol{v}_1| \leq 2^{\frac{i-1}{4}} |\det(\mathcal{L})|^{\frac{1}{n}},,,\text{且}|\boldsymbol{v}_1| \leq 2^{\frac{i-1}{2}}\min|\boldsymbol{v}|
$$
LLL算法具体步骤：给定整数格基
其中SizeReduce即对Gram-Schimt正交化中每个$j\in[2,n],i\in[j-1,1]$，$v_{j}=v_{j}-\lfloor \mu_{i,j}\rceil \cdot{v_{i}}$，$ u_{i,j} = \dfrac{| \boldsymbol{v}_i \cdot \widetilde{\boldsymbol{v}}_j|}{|\widetilde{\boldsymbol{v}}_j |^2}$
由Howgrave-Graham引理，假设$F(x) = \sum_{i=0}^{d} a_i x^i \in \mathbb{Z}[x],,,x_0 \in \mathbb{Z}$是$F(x) \equiv 0 (mod ,N)$的一个小根，且$|x_0|<X,,X\in \mathbb{N}$，定义如下行向量：
$$
\boldsymbol{b}F = (a_0,a_1X\dots a{d-1}X^{d-1},a_dX^d)
$$
如果$|\boldsymbol{b}_F| < N/\sqrt{d+1}$，那么$F(x_0) = 0$。依据此结论构造多项式
令
因此我们需要将rsa上的问题转化为一个求解模方程的小解的问题。当e=3时，虽然m本身较大，但是m的上半部分我们已知，未知仅有一个序号与8字节(64bit)的明文，序号可以直接爆破。而8字节的未知数是一个很小的数字，可以构造出一个以该8字节数为根的函数，通过调用coppersmith的求根法来解决问题。
设f = (app + m)^3 - c (mod n)，app为m的高位已知数，则我们可以通过coppersmith算法来求解出m
from Crypto.Util.number import *
def GetPrefix(i):
res = '9876543210abcdef' + hex(i)[2:].rjust(8 , '0') + '0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000' + 16 * '0'
return int(res , 16)
nlist =
clist =
index = [7, 11, 15]
e = 3
for j in range(3):
PR.<x> = PolynomialRing(Zmod(nlist[j]))
for i in range(21):
a = GetPrefix(i)
f = (a + x) ^ e - clist[j]
x0 = f.small_roots(X = 2^64 , beta = 1)
if len(x0) != 0:
print(index[j], i ,long_to_bytes(int(x0[0])))
'''
7 2 b'amous sa'
11 3 b'ying of '
15 4 b'Albert E'
'''Frame0: b'My secre'
Frame1: b'. Imagin'
Frame2: b' That is'
Frame3: b't is a f'
Frame4: b'My secre'
Frame5:
Frame6: b' "Logic '
Frame7: b'amous sa'
Frame8: b't is a f'
Frame9:
Frame10: b'will get'
Frame11: b'ying of '
Frame12:b't is a f'
Frame13:
Frame14: b' you fro'
Frame15: b'Albert E'
Frame16: b't is a f'
Frame17:
Frame18: b'm A to B'
Frame19: b'instein.'
Frame20: b't is a f'
找到有意义的内容之后回复出来明文是
final_secret =
"My secret is a famous saying of Albert Einstein. That is \"Logic will get you from A to B. Imagination will take you everywhere.\""
[1] Dan Boneh et al. Twenty years of attacks on the rsa cryptosystem. Notices of the AMS, 46(2):203–213, 1999. 2.1
[2] Don Coppersmith. Finding a small root of a univariate modular equation. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 155–165. Springer, 1996.2.2.1
[3] Nicholas Howgrave-Graham. Finding small roots of univariate modular equations revisited. In IMA International Conference on Cryptography and Coding, pages 131–142. Springer, 1997. 2.3
[4] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefffficients. Mathematische annalen, 261(ARTICLE):515–534, 1982. 2.2.1
[5] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. 2.1
[6] H. P. Williams. Integer and combinatorial optimization. Journal of the Operational Research Society, 41(2):177–178, 1990. 2.3