下面简单回顾一下RSA加密算法，以及解一道以RSA为背景的密码题。
温故而知新
RSA算法是1978年由Rivest、Shamir和Adleman提出的一种用数论构成的，也是迄今理论上最为成熟完善的公钥密码体制，该体制已经得到了广泛的应用。
算法过程
- 密钥生成
- \[genPrime(\kappa) \rightarrow p,q\]
- \[n=pq,\varphi(n)=(p-1)(q-1)\]
- \[pick\ e\ which\ 1<e<\varphi(n)\ and\ gcd(\varphi(n),e)=1\]
- \[pick\ d\ which\ d \cdot e \equiv 1 \bmod \varphi(n)\]
- \[pk = (n,e), sk = (n,d)\]
- 加密
- \[c = m^e \bmod n\]
- 解密
- \[m = c^d \bmod n\]
安全性假设
RSA问题是已知大整数\(n,e,y \in Z^*_n\)，满足\(1<e<\varphi(n)\)且\(gcd(\varphi(n),e)=1\)，计算\(y^{\frac{1}{e}}\bmod n\)。RSA的安全假设是没有概率多项式时间的算法可以解决RSA问题。
题目
题目经过稍微的改动，原版的题目没有标注出数据的含义。
e = 65537
n = 16969752165509132627630266968748854330340701692125427619559836488350298234735571480353078614975580378467355952333755313935516513773552163392952656321490268452556604858966899956242107008410558657924344295651939297328007932245741660910510032969527598266270511004857674534802203387399678231880894252328431133224653544948661283777645985028207609526654816645155558915197745062569124587412378716049814040670665079480055644873470756602993387261939566958806296599782943460141582045150971031211218617091283284118573714029266331227327398724265170352646794068702789645980810005549376399535110820052472419846801809110186557162127
sp = 1781625775291028870269685257521108090329543012728705467782546913951537642623621769246441122189948671374990946405164459867410646825591310622618379116284293794090970292165263334749393009999335413089903796624326168039618287078192646490488534062803960418790874890435529393047389228718835244370645215187358081805
c = 11588826164053103684105053949507314143838362216686131396614531602144164340874755771042442569843332513949079387700518619612476391873634554671189405869276286998180627668339128070840305225664281910233215119517273138645104156590566982031631267605876531617769309375563149920765623009579812597587268584833122934311693248766170572476577286820352353062871941566317501770242773809026514980363494835470731729133131972844317845045181594075500423720090746050727478550357408329556642662344658417335071111458489889492785702132022582841102141274600208615470737164247942620973262433902159096806966171422106366246640519086095837929475
# sp = d % (p-1)
思路
首先\(n\)的长度是2048bit，试图分解\(n\)是不可行的。这里给出的信息中除了公钥外还多了一个\(sp\)，显然是要从这里入手。
尝试对公式进行一些变换：
\[sp \equiv d \bmod (p-1) \tag{1}\] \[sp \cdot e \equiv d \cdot e \bmod (p-1) \tag{2}\]设\(x_1\)是一个未知数，我们有
\[d \cdot e = x_1 \cdot (p-1) + sp \cdot e \tag{3}\]根据RSA算法的定义，我们知道
\[d \cdot e \equiv 1 \bmod \varphi(n) \tag{4}\]将(3)、(4)式结合，得到
\[x_1 \cdot (p-1) + sp \cdot e \equiv 1 \bmod (p-1)(q-1) \tag{5}\]设\(x_2\)是一个未知数，将(5)式展开得到
\[x_1 \cdot (p-1) + sp \cdot e = x_2 \cdot (p-1)(q-1) + 1 \tag{6}\]化简(5)得到
\[sp \cdot e = (p-1) \cdot [x_2\cdot(q-1)-x_1] + 1\tag{7}\]我们用\(L=(p-1),R=x_2\cdot(q-1)-x_1\)对(7)式进行化简得到
\[sp \cdot e = L \cdot R + 1 \tag{8}\]由于\(sp = d \bmod (p-1)\)，也就是\(sp < L\)，那么我们可以推断出
\[R < e \tag{9}\]因为这里\(e=65537\)，数值比较小，因此我们可以尝试暴力破解出这个\(R\)。当\(R\)被求出的时候，那么我们就可以通过
\[L = (sp \cdot e - 1) / R \tag{10}\]来求解出素因子\(p = L + 1\)，注意到(10)式等式的右边部分都是已知的量，那么接下来的工作就是暴力破解这个\(R\)值。我们从\((1,e)\)间遍历这个\(R\)，结合(8)式判断下面等式是否成立
\[(sp \cdot e - 1) \bmod R \overset{?}{=} 1\]到这里已经可以解出两个素因子\(p,q\)，后面就没什么难度了。
代码
for R in range(1,e):
t = sp * e - 1
if t % R == 0 and n % (t//R + 1) == 0:
p = t // R + 1
q = n // (t // R + 1)
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi) % phi
# print("p: " + str(p))
# print("q: " + str(q))
# print("sp: " + str(d%(p-1)))
m = libnum.n2s(pow(c, d, n))
print(m)
结果
flag{R5A_i5_fun_U1S1}