RSA加解密专题 - Coppersmith 相关攻击一

Coppersmith 攻击是一种针对 RSA 加密算法的攻击方法，主要用于在特定条件下恢复 RSA 私钥或解密 RSA 密文。该攻击方法由 Don Coppersmith 在 1996 年提出，利用了 RSA 加密算法中的数学结构和性质。

这里我们并不会深入到 Coppersmith 攻击的数学细节，但我们会介绍一些相关的攻击场景和原理，以帮助你理解 Coppersmith 攻击的基本思想和应用。

部分明文泄露攻击 😋

单一变量的情况下，我们主要关注构建一个多项式方程，并使用 Coppersmith 方法来寻找小根。这种方法可以在某些特定条件下成功，例如当明文的某些部分已知或满足特定的数学关系时。

最简单的情况莫过于明文的某些部分已知，不管是哪一种泄露直接套用加密的方程就好：

$\begin{align*} (m_h + x)^e &\equiv c \pmod{n} \\ (m_h + x \ll m_l.\text{nbits}() + m_l)^e &\equiv c \pmod{n} \\ (x \ll m_l.\text{nbits}() + m_l)^e &\equiv c \pmod{n} \end{align*}$

其中 $m_h$ 是已知的明文部分，$x$ 是未知的部分，$e$ 是公钥指数，$c$ 是密文，$n$ 是模数。

部分明文泄露攻击例题

部分明文泄露攻击例题下载

from Crypto.Util.number import *
from secret import m

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 5
m_h = (m >> 72) << 72
c = pow(m, e, n)
print("n =", n)
print("c =", c)
print("e =", e)
print("m_h =", m_h)

# n = 71406081470098943664147354595360130965949415477183415925937691459300487381042569174133696785917044437192425109528474145856370063591801161214117594482262437036039582313557538014983339960352144743243869648717280156439092931956094810765560689842129272908038382363737252851872602935800129772310097494871743999683
# c = 60258767266725462475089309010639723372675479396874103345307979963872676339512613518477686690014996946520051358953694535853808486956187104018894409809787475031000910824770481120529345447944422364229572306876886435743357596246183561495740412854973420619617616182147277760953828917472063677119186309853762339354
# e = 5
# m_h = 777244835068427274667156821981506353228924473235252582307290753380891138229664743424

在这个例题中，我们生成了一个 RSA 密钥对，并加密了一个明文消息。我们知道明文的高位部分 $m_h$，并且我们有密文 $c$ 和公钥指数 $e$。使用 Coppersmith 方法，我们可以尝试找到未知的部分 $x$，从而恢复完整的明文消息。

解题代码示例：

from sage.all import *

n = 71406081470098943664147354595360130965949415477183415925937691459300487381042569174133696785917044437192425109528474145856370063591801161214117594482262437036039582313557538014983339960352144743243869648717280156439092931956094810765560689842129272908038382363737252851872602935800129772310097494871743999683
c = 60258767266725462475089309010639723372675479396874103345307979963872676339512613518477686690014996946520051358953694535853808486956187104018894409809787475031000910824770481120529345447944422364229572306876886435743357596246183561495740412854973420619617616182147277760953828917472063677119186309853762339354
e = 5
m_h = 777244835068427274667156821981506353228924473235252582307290753380891138229664743424

P.<x> = PolynomialRing(Zmod(n))
f = (x + m_h)^e - c
roots = f.small_roots(bound=2^72, epsilon=1/32)
for r in roots:
    flag = long_to_bytes(int(r + m_h))
    print(flag)
# b'flag{the_leaked_flag_is_not_secure}'

模数部分泄露攻击 😎

在某些情况下，攻击者可能会获得 RSA 模数 $p$ 的部分信息，例如知道 $p$ 的高位或低位。这种信息泄露可以被利用来构建多项式方程，并使用 Coppersmith 方法来寻找小根，从而恢复完整的模数 $p$。

模数相关的方程构建直接使用 $n$ 的定义就好，高位泄露和低位泄露都是一样的思路：

$\begin{aligned} (p_h + x)q &\equiv 0 \mod n \\ (x \ll p_h.nbits() + p_h)q &\equiv 0 \mod n \end{aligned}$

其中 $p_h$ 是已知的模数部分，$x$ 是未知的部分，$q$ 是另一个素数。

模数部分泄露攻击例题

模数部分泄露攻击例题下载

from Crypto.Util.number import *
from secret import m

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
p_h = (p >> 128) << 128

c = pow(m, e, n)
print("n =", n)
print("c =", c)
print("e =", e)
print("p_h =", p_h)

# n = 148343204993341213021619313428058654106890149696397492706333896400186219477227728301676148709241129304306574087724304991489318859287047163276539541481697268017678181261322191026527154404707813733872358303403566566327058403912886903786387007581372068922650740322771090553555674369191355108765322667860494558677
# c = 39156544505474625229023477922212602423468384619737085007608097248472070125608788562256041364458195493803172264223273233547146479148821267828148585094956004078892557930333392606045896106072959524844360325819706205800762438141913680222858798397571618769159479716837722530469152413770655154791443613805271743833
# e = 65537
# p_h = 12734678186795088622000398950939657451514087254410587977928786315334611555210018653020273683790430319996027334767103524767798553242990607416419371588780032

在这个例题中，我们生成了一个 RSA 密钥对，并加密了一个明文消息。我们知道模数 $p$ 的高位部分 $p_h$，并且我们有密文 $c$ 和公钥指数 $e$。使用 Coppersmith 方法，我们可以尝试找到未知的部分 $x$，从而恢复完整的模数 $p$，进而解密消息。

解题代码示例：

from sage.all import *

n = 148343204993341213021619313428058654106890149696397492706333896400186219477227728301676148709241129304306574087724304991489318859287047163276539541481697268017678181261322191026527154404707813733872358303403566566327058403912886903786387007581372068922650740322771090553555674369191355108765322667860494558677
c = 39156544505474625229023477922212602423468384619737085007608097248472070125608788562256041364458195493803172264223273233547146479148821267828148585094956004078892557930333392606045896106072959524844360325819706205800762438141913680222858798397571618769159479716837722530469152413770655154791443613805271743833
e = 65537
p_h = 12734678186795088622000398950939657451514087254410587977928786315334611555210018653020273683790430319996027334767103524767798553242990607416419371588780032

P.<x> = PolynomialRing(Zmod(n))
f = x + p_h
roots = f.small_roots(bound=2^128, beta = 0.4, epsilon=1/32)
for r in roots:
    p = int(r + p_h)
    q = n // p
    phi = (p-1)*(q-1)
    d = inverse_mod(e, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(flag)
# b'flag{the_leaked_p_is_not_secure}'

私钥低位泄露攻击 🧐

在某些情况下，攻击者可能会获得 RSA 私钥 $d$ 的部分信息，例如知道 $d$ 的低位。这种信息泄露可以被利用来构建多项式方程，并使用 Coppersmith 方法来寻找小根，从而恢复完整的私钥 $d$。

这个时候就好灵活构建方程了，要先认识到低位，可以理解成原来的方程在取模时的值，这样在取模后就可以达到一个未知数暂时不参与的效果。

私钥低位泄露攻击例题

私钥低位泄露攻击例题下载

from Crypto.Util.number import *
from secret import m

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
d = inverse_mod(e, (p-1)*(q-1))
d_l = d & ((1 << 512) - 1)
c = pow(m, e, n)
print("n = ", n)
print("e = ", e)
print("c = ", c)
print("d_l = ", d_l)

# n = 78036226711261137562635523171733270722300007283095085193438779642343110620250804479566251132258821498672359932995596424916036883417080280241580905118033281785063140297467453715900194715947245388137276189087436097121831057248623061596822311980543096721479575328572293908180835278420031510114830258210990389017
# e = 3
# c = 4458558515804294040125006969671194268520221962979792020774793426952905371959925004280044612155954386479615226026601709155668384798849357146766830652052906333248686079022711702984275745125
# d_l = 1548125634003834517457946342794474179624692403859149914470848791910513316602949323478233517628159099938386644246361533546700081991087641483936928476761795

根据RSA相关参数我们可以知道的是 $e \cdot d = k \cdot \phi(n) + 1$，其中 $k$ 是一个整数。我们设 $s = p + q$，则有 $e \cdot d = k \cdot (n - s + 1) + 1$。

重点来了，已知 $d$ 的低位部分 $d_l$，我们可以直接将方程取模 $2^{512}$，得到：

$\begin{aligned} e \cdot d_l = k \cdot (n - s + 1) + 1 \mod 2^{512} \\ s \equiv n + 1 - (e \cdot d_l - 1) \cdot k^{-1} \mod 2^{512} \end{aligned}$

然后联系根为 $p$ 和 $q$ 方程 $x^2 - s \cdot x + n = 0$，我们就可以构建一个关于 $x$ 的多项式方程，并使用贪心加剪枝的方法求解 $512$ 位的 $p$ 和 $q$。如果 $p$ 和 $q$ 都大于 $512$ 位，那么我们可以通过 Coppersmith 方法来寻找小根。

解题代码示例：

from sage.all import *
from Crypto.Util.number import *

n = 78036226711261137562635523171733270722300007283095085193438779642343110620250804479566251132258821498672359932995596424916036883417080280241580905118033281785063140297467453715900194715947245388137276189087436097121831057248623061596822311980543096721479575328572293908180835278420031510114830258210990389017
e = 3
c = 4458558515804294040125006969671194268520221962979792020774793426952905371959925004280044612155954386479615226026601709155668384798849357146766830652052906333248686079022711702984275745125
d_l = 1548125634003834517457946342794474179624692403859149914470848791910513316602949323478233517628159099938386644246361533546700081991087641483936928476761795

def recover_p_general(d_l, e, n):
    d_l_sage = Integer(d_l)  # 转换为Sage的Integer类型
    known_bits = d_l_sage.nbits()  # 现在可以正常调用nbits()

    for k in range(1, e + 1):
        A = e * d_l - 1
        if A % k != 0: continue

        # 1. 也是算出只模已知位数的 s_mod
        s_mod = (n + 1 - (A // k)) % (2**known_bits)

        # 2. 也是逐位解 x^2 - s_mod*x + n = 0
        res = [1]
        for i in range(1, known_bits):
            next_res = []
            for r in res:
                for b in (0, 1):
                    x = r | (b << i)
                    if (x**2 - s_mod*x + n) % (2**(i+1)) == 0:
                        next_res.append(x)
            res = next_res

        # 3. 对每一个得到的部分低位 p_low 使用 small_roots 求高位
        for p_low in res:
            # 如果碰巧拿到全量位了，直接除除看
            if n % p_low == 0 and p_low != 1 and p_low != n:
                return p_low

            # 如果没拿到全量，用 small_roots 把剩下高位求出来
            PR.<x> = PolynomialRing(Zmod(n))
            f = x * (2**known_bits) + p_low    # p = x * 2^m + p_low
            f = f.monic()

            # X是预估未知高位的值域上限，假设 p 大约在靠近 sqrt(n) 附近
            n_sage = Integer(n)
            unknown_bits = (n_sage.nbits() // 2) - known_bits
            X_bound = 2**(unknown_bits + 5)   # +5 留一点余量

            if X_bound > 2: # 也就是确实有未知位需要求
                try:
                    # beta=0.4 反映了我们要找的 p 的位数约占总位数的比例（略小于一半）
                    roots = f.small_roots(X=X_bound, beta=0.4)
                    if roots:
                        p = int(roots[0]) * (2**known_bits) + p_low
                        if n % p == 0:
                            return p
                except Exception as e:
                    pass
    return None

p = recover_p_general(d_l, e, n)
q = n // p
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'flag{the_leak_of_d_is_bad}'

Håstad 广播攻击扩展 🤠

前面我们提到过 Håstad 广播攻击，而 Coppersmith 方法也可以被用来扩展 Håstad 广播攻击的适用范围。在 Coppersmith 方法的帮助下，我们可以将问题推广到更一般的情况，就是加密的不再是相同的 $m$，而是具有线性关系的 $m_i$。

Håstad 广播攻击扩展例题

Håstad 广播攻击扩展例题下载

from Crypto.Util.number import *
from secret import m

p1 = getPrime(256)
p2 = getPrime(256)
p3 = getPrime(256)
q1 = getPrime(256)
q2 = getPrime(256)
q3 = getPrime(256)
n1 = p1*q1
n2 = p2*q2
n3 = p3*q3
e = 3
c1 = pow(m, e, n1)
c2 = pow(m+1, e, n2)
c3 = pow(2*m+2, e, n3)
print("n1 = ", n1)
print("c1 = ", c1)
print("n2 = ", n2)
print("c2 = ", c2)
print("n3 = ", n3)
print("c3 = ", c3)

# n1 =  7436297924479111288858365740455970275623094012645820223363041858682843243234345296777579027762343770914910949000282160537982015904948267903325514335621283
# c1 =  4325495502980350621916618330673099516626441599498586125877854511173538779941000124091552361831740416431308367276617945025243861814840900084833354971434577
# n2 =  6456104243856281808527299663033415352202343985414289970319782054731415622452561418810434572150687245284010827848197758737921807475656221001397521660559891
# c2 =  2003003821228318250607284803400253958526269528049733743569235891789477388365756120493530569516748649272916121719028297249295064499105886124376055740719578
# n3 =  8769049710633699648972640916530598241721246817703490720809168840216439564713379108405895103749642237199313984669343902262587767037986004793227502470940611
# c3 =  7583851145248429122395092819244845051341655099143487890806191663124326571012675198159624097396942593587956402263246628310823739943969343448935180194204

这一题我们使用 CRT 构造一组标准基向量，通过线性组合正确合并三个多项式：

$l_i \equiv \begin{cases} 1 \pmod{n_i} \\ 0 \pmod{n_j} (j \neq i) \end{cases}$

后面用 $F = l_1f_1 + l_2f_2 + l_3f_3$ 就可以把三个方程合成一个方程，使得满足 $F \equiv 0 \pmod{n_i}$。剩下的就是求这个方程的整数根了。

解题代码示例：

from Crypto.Util.number import *
from sage.all import *

n1 =  7436297924479111288858365740455970275623094012645820223363041858682843243234345296777579027762343770914910949000282160537982015904948267903325514335621283
c1 =  4325495502980350621916618330673099516626441599498586125877854511173538779941000124091552361831740416431308367276617945025243861814840900084833354971434577
n2 =  6456104243856281808527299663033415352202343985414289970319782054731415622452561418810434572150687245284010827848197758737921807475656221001397521660559891
c2 =  2003003821228318250607284803400253958526269528049733743569235891789477388365756120493530569516748649272916121719028297249295064499105886124376055740719578
n3 =  8769049710633699648972640916530598241721246817703490720809168840216439564713379108405895103749642237199313984669343902262587767037986004793227502470940611
c3 =  7583851145248429122395092819244845051341655099143487890806191663124326571012675198159624097396942593587956402263246628310823739943969343448935180194204

N = n1*n2*n3
R_mod.<m> = PolynomialRing(Zmod(N))
f1 = m**3 - c1
f2 = (m+1)**3 - c2
f3 = ((2*m+2)**3 - c3) * inverse_mod(8, N)

c_1 = crt([1, 0, 0], [n1, n2, n3])
c_2 = crt([0, 1, 0], [n1, n2, n3])
c_3 = crt([0, 0, 1], [n1, n2, n3])

F_mod = c_1 * f1 + c_2 * f2 + c_3 * f3
F_mod = F_mod.monic()
X = 2**256
roots = F_mod.small_roots(X=X, beta=1.0)
flag = long_to_bytes(int(roots[0]))
print(flag)
# b'flag{coppersmith_is_very_useful}'

上一章：RSA加解密专题 - 公私钥格式相关攻击 👈
下一章：RSA加解密专题 - Coppersmith 相关攻击二 👈
回到开始：关于我 👈

相关链接：
密码学算法 - 中国剩余定理CRT 👈