一道RSA密码题

2020/08/15 CTF

下面简单回顾一下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}

Search

    Table of Contents