CTF中的RSA基本套路(3)

第三部分是基本的Coppersmith相关内容

依赖库：

• gmpy2
• pycrypto
• pwntools
• sage

引子#

$c=m^e \mod N$, 当 $|m| < N^{1/e}$时，我们能很快求得$m$的值

当$|m|>N^{1/e}$时，如果已知$m$的部分信息$m_0$，能不能恢复未知$x$的值，这就是$Corppersmith$ 要解决的问题

$$c = (m_0+x)^e \mod N$$

已知部分明文攻击#

引理1

假设$N$是一个未知因子组成的数，且存在一个因子$b \geq N^{\beta},0 \lt \beta \leq 1$,$f(x)$ 是一个一元$\delta$阶多项式，且$c \geq 1$，那么可以在$O(c\delta ^5 log^9(N))$复杂度内求解下列等式的所有的$x_0$

$$f(x)=0 \mod b, |x_0| \leq c N^{\beta ^2/\delta}$$

场景#

设$m=m_0 + x_0$，其中$x_0$是未知的，那么我们可以列出以下多项式

$$f(x)=(m_0+x)^e - c \mod N , f(x_0)=0$$

当$e$和$x_0$很小的时候，$Coppersmith$就能求出$x_0$的值

解法#

在这个场景中，我们知道$b=N,\delta=e,\beta=1$，设$c=1$，此时$|x_0| \leq c N^{\beta ^2/\delta} = N^{1/e}$，因此，为了求解$x_0$，我们需要知道原消息$m$至少(1-1/e)​*N.bit_length()比特的信息

碰到的最常见的是已知明文高位攻击，但其实未知的部分在哪里都可以，只要是连贯的，就能构造对应的$f(x)$进行求解

已知明文高位#

e = 
c = 
n = 
kbits = # x的未知bit数目
m0 =  #明文的高位信息
PR.<x> = PolynomialRing(Zmod(n))
f = (m0 + x)^e - c
f = f.monic()
x0 = f.small_roots(X=2^kbits,beta=1)[0] # 在0 - 2^kbits范围内求解小根，beta为1和上述分析的beta一致，也就是对应factor为N
print(x0)

已知明文低位#

将构造的函数改为以下即可

f = ((m0 + ZmodN((pow(2,m0.nbits())))*x)^e) - c

当然,如果是明文的中间部分bit未知，也是相同的去修改对应的多项式f(x)即可，具体题目见https://cryptohack.org/challenges/rsa/ 中的Null or Never题目（Coppersmith是该题的一种解法）

已知部分p攻击#

场景#

已知$p=p0+x$,且$|x|<N^{1/4}$时，也就是知道$p$的大约一半bits信息时，可以得到对应的$x$，从而对$N$进行分解

解法#

此时根据$p=p0+x0$我们知道$p0 = x0 \mod p$，所以可以列出多项式$f(x)= p0-x \mod p，f(x_0)=0 \mod p$

对应到引理中，显然$b=p$，由于在$RSA$中，$p和q$经常为同比特的素数，所以设置$beta=0.4，0.3$等都可

已知p高位#

n = 
p0 = # 已知的p的高位
kbits = 
PR.<x> = PolynomialRing(Zmod(n))
f = x + p0
f = f.monic()
x0 = f.small_roots(X=2^kbits, beta=0.3)[0] # beta=0.3表明存在factor 大于n ^0.3
print(x0 + p0)

已知p低位#

同样的，已知p低位或者中间部分未知，修改对应的f(x)的表达式即可，例如已知p低位，则

ZmodN=Zmod(n)
f(x) = x*ZmodN(pow(2,p0.nbits()))+p0

部分私钥暴露攻击#

场景#

当已知私钥的部分bit信息，私钥$d=d0+x$，$d0$ 的bit数目约为$d$的$1/4$时，可以恢复私钥$d$

解法#

根据论文《An Attack on RSA Given a Small Fraction of the Private Key Bits》

假设私钥$d$的bit数目为$kbits$,且已知的是私钥的低位

那么我们可以知道$d0 = d \mod 2^{kbits}$

所以有$ed0=1+k(N-s+1)\mod 2^{kbits},(s=p+q)$

所以我们可以通过解$ed0x-kx(N-x+1)= x \mod 2^{kbits}$ 得到可能的$s \mod 2^{kbits}$的值，继续通过求解$ p^2-sp+N=0 \mod 2^{kbits}$，就能得到$p \mod 2^{kbits}$的值了，进而把问题转换为已知部分$p$攻击。下面这个日本大哥的脚本是把1、2两步结合起来列式了，所以只求一个方程解出了部分$p$

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3，在实际使用脚本的时候可以自己手动改nbits等参数，理解了原理再看脚本就很清楚明了了
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n =
    e = 
    d0 = 
		kbits = # 未知的d的bits数目
    p = find_p(d0, kbits, e, n)
    print("found p: %d" % p)
    q = n//p
    print(inverse_mod(e, (p-1)*(q-1)))

如果将1、2两步分开列式，则修改函数find_p如下

def find_p(d0, kbits, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1)== X], 2^kbits)
        for x in results:
            s = ZZ(x[0])
            pvar = var('p')
            p_results = solve_mod([pvar*pvar-s*pvar+n==0],2^kbits)
            for p0 in p_results:
                p0 = ZZ(p0[0])
                p = partial_p(p0, kbits, n)
                if p:
                    return p

但是速度上好像慢一些。

同样的已知d高位等也可以进行求解，例如已知d高位，那么第一步解出来的其实是可能的p的低位，所以在解部分p时，修改f = (2^kbits)*x + p0即可

例题：2020 天翼杯 hardRSA#

题目脚本：

# chall.py
# flag{6809781d08e120627e623dcdafe26b8a}
p = getPrime(510)
q = getPrime(510)
r = getPrime(510)
e = 7
m = bytes_to_long(os.urandom(30) + flag)
n = p * q * r
d = invert(e, (p - 1) * (q - 1) * (r - 1))
c = pow(m, e, n)
print(n // p)
print(p)
print(c)
print(hex(d % (1 << 540)))

从题目看也是Coppersmith partial d的情况，只是这里由于$n$由$p、q、r$三个素数组成，因此需要我们重新推导同余方程

已知：$kbits = 540$、$p$、$qr$、$d_0$的值，$d_0 = d \mod 2^{kbits}$

推导如下：
$$
\begin{align*}
ed_0
& = 1 +k(p-1)(q-1)(r-1) \
& = 1+ k(pq-p-q+1)(r-1) \
& = 1+k(pqr-pr-qr-1-pq+p+q+r) \
& = 1+k(N-p(r+q)+s-qr-1) \
& = 1+k(N-p(r+q)+(r+q)+p-qr-1) \
& = 1+k(N-ps+s+p-qr-1) \
& = 1+k(p-1)(qr-s+1)\mod 2^{kbits},(s=q+r) \tag{1}
\end{align*}
$$
通过上式可以求得所有的$s \mod 2^{kbits}$的值，同时我们知道
$$
q^2-sq+qr = 0 \mod 2^{kbits} \tag{2}
$$
联立公式$1 \times q$和公式$2 \times k(p-1)$，可以得到公式

$$ed_0q = q + kq(p-1)(qr-s+1) \tag{3}$$

$$k(p-1)qr = kq(p-1)(s-q) \tag{4}$$

相加得到：

$$ed_0q + k(p-1)qr = q+kq(p-1)(qr-q+1)$$

即：

$$ed_0q + k(p-1)qr-k(p-1)q(qr-q+1) = q \mod 2^{kbits}$$

解上述同余方程，即可得到$q \mod 2^{kbits}$

由于$kbits=540$，而$q$只有$510 bits$，所以解出来的就是可能的$q$的值，再通过$qr % q==0$过滤即可

def find_q(d0, kbits, e, qr, p):
    X = var('X')
    for k in range(1, e + 1):
        temp = k*(p-1)
        results = solve_mod([e*d0*X+temp*qr-temp*X*(qr-X+1)==X], 2 ^ kbits)
        for x in results:
            q = ZZ(x[0])
            if qr % q == 0:
                return q
    return None


if __name__ == '__main__':
    qr = 6857671284539062742975668483013695756136974308830302383869017675211748459038460434623218652374536550644287079851235538790745857383008797698872874798021995947967308637270510423795384863442755166813716746318469915880844736019524077541319597047087620854791342900521099848683663304636436936596021386279685708537
    p = 2141698433991046082370939321691850154692026423424010392532982575546199921995522418737105878977898158159119041866620684371362271661642476751663585379591337
    c = 4329606906986929520922207896899782825966852252045645553852666134465727605375552409314262439896695961792039946511877813768609658516837096110397826574615865145364406310497152725490038135469839136190625952342503082553246584871237205558902774064100332461452316195663446307120094941991930964324406679011451626126064494215289724959537793057773764253924636259378833228904446486925068109314698993641720938647836132806653451109926428309922461595730642461604303078237048
    d0 = 0x8e6f66a517d9c8a610eb65dac5a613e72d47a29beaa5c77a9eb857e0db5d09eadf3a317776fdf27b0d85db0b6677afc8e0683d6dc2b4580281b6e99c3050f649213c37
    e = 7
    kbits = 540
    q = find_q(d0, kbits, e, qr, p)
    print(q)
    # q = 2505948797318027758820680066583904581437202552654881626817593379353882875609223855015707273771918291251411562855290697544161987271016184806489110771554269

short padding attack#

场景#

Short padding attack经常和 相关消息攻击结合(https://blog.ycdxsb.cn/2decc525.html#more)使用

我们已知$c_1 = m^e \mod n$，$c_2 = (m+padding)^e \mod n $，但我们不知道具体的padding值是多少

解法#

首先通过short padding attack 求出padding的值，然后再使用相关消息攻击求得消息$m$

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff
 
 
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

参考链接#

• https://github.com/mimoo/RSA-and-LLL-attacks
• http://inaz2.hatenablog.com/entry/2016/01/20/022936
• https://www.davidwong.fr/papers/david_wong_rsa_lll_boneh_durfee__2015.pdf
• https://zhuanlan.zhihu.com/p/161622928
• https://cryptohack.org/challenges
• https://link.springer.com/content/pdf/10.1007/3-540-49649-1_3.pdf
• https://crypto.sqrt-1.me/