​

Boneh-Durfee攻击是一种针对RSA加密算法的数学攻击方法，专门用来破解私钥指数d选得太小的情况。这个比起维纳攻击有更高的上限【winner攻击条件是d < 1/3 * N^(1/4)】

=========================================================================

💡核心思想：

RSA 的安全前提是 d 够大，如果 d 太小，就可以被猜出来。而 Boneh 和 Durfee 就提出了一种数学技巧，可以在 d < n^0.292 的时候用格子（lattice）算法暴力破解私钥 d！

目标： 给定一个公钥（大数 N和指数 e），想找到私钥 d

格（lattice）： 是个高维空间的格点集合，这脚本通过构造一个特殊矩阵（基矩阵），然后用 LLL算法 这个“格基约简神器”来找出很小的向量。

这个“很小的向量”其实对应于原始多项式的解，也就是RSA里的私钥d。

=========================================================================

这里是github开源的原脚本

下面来看sagemath的具体实现：

from __future__ import print_function
import time

############################################
# 配置
##########################################

"""
将 debug 设置为 True 会显示关于格、界限、向量等更多信息
"""
debug = True

"""
将 strict 设置为 True 会在行列式上界不正确时停止算法（并返回 (-1, -1)）。注意这并不一定意味着找不到解，因为理论上界通常远大于实际结果。因此建议使用 strict = False。
"""
strict = False

"""
这是实验性的，但目前效果显著。它会尽可能地减少格的维度，同时保持效率。我认为没有理由不用这个选项，但如果有问题可以尝试关闭。
"""
helpful_only = True
dimension_min = 7 # 如果格的维度达到该值则停止移除

############################################
# 函数
##########################################

# 显示有用向量的统计信息
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print(nothelpful, "/", BB.dimensions()[0], " 个向量无用")

# 用 0 和 X 显示矩阵结构
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

# 尝试移除无用向量
# 从 current = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 递归终止条件
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # 从末尾开始检查
    for ii in range(current, -1, -1):
        # 如果是无用向量：
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # 检查是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果影响了其他向量：
                # 计数加一
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # 如果没有其他向量受影响
            # 直接移除
            if affected_vectors == 0:
                print("* 移除无用向量", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # 如果只影响了一个，检查它是否影响其他向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果影响了其他向量
                    # 放弃移除
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受影响，且该有用向量不够有用
                # 相比于无用向量
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* 移除无用向量", ii, "和", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # 没有发生变化
    return BB

"""
返回：
* 0,0   如果失败
* -1,-1 如果 strict=True 且行列式不受界
* x0,y0 为多项式 pol 的解
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh 和 Durfee 改进算法（Herrmann 和 May 版本）
    
    如果满足以下条件则能找到解：
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    只要 delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # 替换（Herrman 和 May 方法）
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-偏移
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-偏移的单项式列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-偏移（Herrman 和 May 选择）
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # 替换
    
    # y-偏移的单项式列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # 构造格 B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # 格降维原型
    if helpful_only:
        # 自动移除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print("失败")
            return 0,0

    # 检查向量是否有用
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # 检查行列式是否受界
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print("行列式未受界，可能找不到解。")
        print("尝试更大的 m 和 t。")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("行列式与理论界的差值 = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n)（很好！如果存在小于 N^delta 的解，将会被找到）")

    # 显示格基
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print("通过 LLL 优化格基，这可能需要较长时间")

    BB = BB.LLL()

    if debug:
        print("LLL 完成！")

    # 将向量 i 和 j 转换为多项式 1 和 2
    if debug:
        print("在格中寻找线性无关向量")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # 对于 i 和 j，创建两个多项式
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # 计算结果子式
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # 这些多项式是否合格？
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("找到合适向量，使用", pol1_idx, "和", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print("未找到线性无关向量，这种情况极少发生...")
        return 0, 0
    
    rr = rr(q, q)

    # 求解
    soly = rr.roots()

    if len(soly) == 0:
        print("你的 delta 预测太小")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

def example():
    ############################################
    # 如何使用本脚本
    ##########################################

    #
    # 需要解决的问题（编辑下方数值）
    #

    # 模数
    N = 0xc2fd2913bae61f845ac94e4ee1bb10d8531dda830d31bb221dac5f179a8f883f15046d7aa179aff848db2734b8f88cc73d09f35c445c74ee35b01a96eb7b0a6ad9cb9ccd6c02c3f8c55ecabb55501bb2c318a38cac2db69d510e152756054aaed064ac2a454e46d9b3b755b67b46906fbff8dd9aeca6755909333f5f81bf74db
    # 公钥指数
    e = 0x19441f679c9609f2484eb9b2658d7138252b847b2ed8ad182be7976ed57a3e441af14897ce041f3e07916445b88181c22f510150584eee4b0f776a5a487a4472a99f2ddc95efdd2b380ab4480533808b8c92e63ace57fb42bac8315fa487d03bec86d854314bc2ec4f99b192bb98710be151599d60f224114f6b33f47e357517

    # 对私钥的假设（可调整，理论最大值为 0.292）
    delta = .18 # 即 d < N^delta

    #
    # 格参数（可调整）
    #

    # 可调整（首次运行后可递增，直到找到解）
    m = 4 # 格的维度（越大越慢/越好）

    # 需要精通格理论才能调整
    t = int((1-2*delta) * m)  # Herrmann 和 May 的优化
    X = 2*floor(N^delta)   #这里可能会很大
    Y = floor(N^(1/2))    # 若 p, q 大小接近则正确

    #
    # 以下内容无需修改
    #

    # 问题转为方程
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # 开始求解！
    #

    # 检查参数界限
    if debug:
        print("=== 检查参数 ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* e 的位数:", int(log(e)/log(2)))
        print("* N 的位数:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== 运行算法 ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # 找到解了吗？
    if solx > 0:
        print("=== 找到解 ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("找到私钥:", d)
    else:
        print("=== 未找到解 ===")

    if debug:
        print(("=== %s 秒 ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()

下面是参数调整建议：

​