X-NUCA 2020 密码题

2020/11/02 CTF

这周末我看见群里有同学参加X-NUCA 2020比赛,其中我拿到了一道密码题的代码,花了一天时间没有解决出来,赛后与西电一个本科学弟交流,最终求解出flag,这个过程中学习到不少东西,感谢shallow同学的分享。

题目描述

点击这里获取题目的源文件。题目的大意是对一个64 bytes长度的flag进行加密,已知参数\(e, N\)和密文,求出明文flag。

密钥生成

下面是代码中的密钥生成的函数:

def key_gen(bits):
    while True:
        p = random_prime(2**bits)
        q = random_prime(2**bits)
        if p % 4 == 3 and q % 4 == 3:
            break
    if p < q:
        p, q = q, p
    N = p * q
    while True:
        x = getrandbits(bits // 2)
        y = getrandbits(bits // 2)
        if gcd(x, y) == 1 and (x * y) < (int(sqrt(2 * N)) // 12):
            e = randint( 
                int(((p + 1) * (q + 1) * 3 * (p + q) - (p - q) * int(N**0.21)) * y / (x * 3 * (p + q))), 
                int(((p + 1) * (q + 1) * 3 * (p + q) + (p - q) * int(N**0.21)) * y / (x * 3 * (p + q))) )
            if gcd(e, (p + 1) * (q + 1)) == 1:
                k = inverse_mod(e, (p + 1) * (q + 1))
                break
    return (N, e, k)

结合题目我们可以知道\(N\)的长度是2048 bits,参数\(e\)的选取很特别,它满足下面的式子:

\[\frac{(p+1)(q+1)y}{x} - \frac{p-q}{p+q} \times \frac{y}{x} \times \frac{N^{0.21}}{3} < e < \frac{(p+1)(q+1)y}{x} + \frac{p-q}{p+q} \times \frac{y}{x} \times \frac{N^{0.21}}{3}\]

因此可以得出参数\(e\)在\(\frac{(p+1)(q+1)y}{x}\)附近。

题解

这道题目的解题过程分为两步,第一是分解大整数\(N\),第二是求解出\(e\)的逆元。

分解大整数

由密钥生成环节我们可以知道:

\[e \times \frac{x}{y} \approx (p+1)(q+1)\]

如果我们能求出\((p+1)(q+1)\)的近似值\(t'\),那么我们可以解出其中一个素因子的近似值:

\[t = t'-N-1\] \[p = \frac{\sqrt{t^2-4N} + t}{2}\]

此时求解出的\(p\)近似值与真正的\(p\)存在高位相同(Factoring with high bits known)的情况,通过使用coppersmith算法可以快速求出真正的\(p\),进而将大整数\(N\)分解。

思路已经有了,但问题是\((p+1)(q+1)\)的近似值\(e \times \frac{x}{y}\)怎么求解出来?

定义1 设\(a_1, a_2, ..., a_n\)是不为零的实数,当分数

\[a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{...}}}\]

有意义时,称为有限连分数,简记\((a_1,a_2,...,a_n)\)。

定义2 设\(a_1, a_2, ..., a_n\)是不为零的实数,记

\[\frac{p_n}{q_n}=(a_1,a_2,...,a_n)\]

如果

\[\lim\limits_{n\to\infty} \frac{p_n}{q_n}=A < \infty\]

那么称连分数\((a_1,a_2,...,a_n)\)等于\(A\),并且

\[\frac{p_k}{q_k}=(a_1,a_2,...,a_k)\]

是\(A\)的第\(k\)个渐进分数。

定理1 设\(a,b,c,d \in N\),假设\(gcd(a,b)=gcd(c,d)=1\),并且

\[\lvert \frac{a}{b} - \frac{c}{d} \rvert < \frac{1}{2d^2}\]

那么有\(\frac{c}{d}\)是\(\frac{a}{b}\)的渐进分数。

定理2 \(\frac{y}{x}\)是\(\frac{e}{N}\)的第\(k\)个渐进分数。

证明 由定理1可知,我们只需要证明下列不等式成立:

\[\lvert \frac{e}{N} - \frac{y}{x} \rvert < \frac{1}{2x^2}\]

已知

\[xy < \frac{\sqrt{2N}}{12}\]

下面给出不严谨的数学证明

\[\begin{align} \frac{e}{N} - \frac{y}{x} &< \frac{y}{x} \times (\frac{(p+1)(q+1)}{N} + \frac{p-q}{p+q} \times \frac{N^{0.21}}{3N}) - \frac{y}{x} \\ &= \frac{y}{x} \times (\frac{p+q+1}{N} + \frac{p-q}{p+q} \times \frac{N^{0.21}}{3N})\\ &< \frac{\sqrt{2N}}{12x^2} \times (\frac{p+q+1}{N} + \frac{p-q}{p+q} \times \frac{N^{0.21}}{3N})\\ &< \frac{\sqrt{2N}}{12x^2} \times (\frac{p+q+1}{N} + \frac{N^{0.21}}{3N})\\ &= \frac{1}{2x^2} \times \frac{3 \sqrt{2N} (p+q+1) + \sqrt{2} N^{0.71}}{18N}\\ \end{align}\]

推导到这一步不容易继续逼近到一个紧界,通过计算机多次演算发现后面的

\[\frac{3 \sqrt{2N} (p+q+1) + \sqrt{2} N^{0.71}}{18N} < 1\]

结合这个结果我们可以得出上面的定理2。

下面的代码可以求出所有的渐进分数,分解结果见附录。

class ContinuedFraction():
    def __init__(self , numerator, denumerator):
        self.numberlist = []
        self.fractionlist = []
        self.GenerateNumberList(numerator , denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self,numerator,denumerator):
        while numerator != 1:
            quotient = numerator//denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder
    
    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0] ,1 ])
        for i in range(1,len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i-j-1]
                denumerator = temp
            self.fractionlist.append([numerator,denumerator])

求解逆元

观察代码片段(修改了一部分方便显示):

# 2000 years later...:)
for _ in range(e):
    t = ct[0] * pt[0] * ct[1] * pt[1]
    ct = ( 
        int((ct[0] * pt[1] + ct[1] * pt[0]) * inverse_mod(1 + d * t, N) % N), 
        int((ct[1] * pt[1] + d * ct[0] * pt[0]) * inverse_mod(1 - d * t, N) % N) 
    )

首先这个循环肯定是有问题的,循环次数\(e\)这么庞大,怎么可能算出来。这个地方很容易误导我们去尝试求解通项公式,事实上它的含义是曲线上的点加加法。

定义3 扭曲爱德华曲线的表达式是

\[E_{E,a,d} : ax^2 + y^2 = 1 + dx^2y^2\]

定义4 扭曲爱德华曲线上两个点\((x_1,y_1)\)、\((x_2,y_2)\)的相加法则是

\[(x_1,y_1)+(x_2,y_2) = (\frac{x_1y_2+y_1x_2}{1+dx_1x_2y_1y_2}, \frac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2})\]

上面这段代码的含义其实就是对于曲线上的点\(P=pt\),求出\(Q=ct\)满足:

\[Q=eP\]

不难得出题目中使用的曲线是

\[E_{E,-d,d} : -dx^2 + y^2 = 1 + dx^2y^2\]

又因为

\[d = \frac{y^2-1}{(y^2+1)x^2}\]

因此这里的\(d\)可以通过密文求出:

d = (((ct[1])**2 - 1) * inverse_mod(((ct[1])**2 + 1) * (ct[0])**2, N)) % N

那么现在问题好理解了,已知\(eP\)、\(e\),可以求出

\[P = e^{-1} \cdot (eP)\]

这里的\(e^{-1}\)其实就是代码生成密钥过程中的\(k\),它满足

k = inverse_mod(e, (p + 1) * (q + 1))

解题

简单回顾下,现在我们已经分解出了\(p、q\),求解出\(d\)与\(e\)的逆元\(e^{-1}\)。flag分为两个32 bytes部分作为曲线上点的x和y坐标,即点\(P\),现在我们已知这个点\(eP\),需要求出点\(P\)。

首先我们需要实现扭曲爱德华曲线的加法和乘法:

def add(ct, pt):
    t = ct[0] * pt[0] * ct[1] * pt[1]
    return (            
        int((ct[0] * pt[1] + ct[1] * pt[0]) * inverse_mod(1 + d * t, N) % N), 
        int((ct[1] * pt[1] + d * ct[0] * pt[0]) * inverse_mod(1 - d * t, N) % N)
    )

def mul(a, pt):
    kt = (0, 1)
    rt = (k0, k1)
    while(a):
        if a%2 == 1:
            kt = add(kt, rt)
        rt = add(rt, rt)
        a = int(a/2)
    return kt

稍作整理带入上述参数,有

def to_bytes(n, length):
    return ''.join(chr((n >> i*8) & 0xff) for i in reversed(range(length)))

# N = p * q
# ct = (k0, k1)
d = (((k1)**2 - 1) * inverse_mod(((k1)**2 + 1) * (k0)**2, N)) % N
pt = mul(inverse_mod(e, (p+1)*(q+1)), (k0, k1))
print(to_bytes(pt[0], 32) + to_bytes(pt[1], 32))

得出flag是X-NUCA{Youve_Forg0tt3n_th3_t4ste_0f_Rea1_h0ney_6f36940f714710af}。

附录

p=132160284144608950019816194803720605665582054407890340625286428343034451279699999656554400403442321672129341860427814515935184696844617907072796285688260865300923112869612920717393389100962210593903755734372629195470923938634371604924606564978967830639867288297401137624219856087339978669043930742514051454567

q=47829272736370744941064080734743479304288408291473409399482548765113703743397570463891897033407890596083892483228736317455296323399119244525315723144198082570139949182368719337284186973129859443768772812543803355101589217576041098514209516628934034418753338483083765911640872414369956826177554268635530233379

Search

    Table of Contents