RSA剪枝攻击技术详解

1. 基础剪枝攻击

1.1 基本概念

剪枝攻击是一种针对RSA密码系统的攻击方法，当攻击者获得部分关于私钥的信息时，可以通过逐步排除不可能的解空间来恢复完整的私钥。

1.2 简单剪枝案例

给定条件：

• p*q = n
• p^q = xor_result

对于每一位p^q的结果，可能的组合有4种：

1. 1^0
2. 0^1
3. 1^1
4. 0^0

1.3 搜索策略

1. 从低位开始搜索：从最低有效位(LSB)向最高有效位(MSB)逐步构建p和q的值
2. 剪枝条件：
   • 将p和q剩余位全部填充为1时，必须满足p*q > n
   • 将p和q剩余位全部填充为0时，必须满足p*q < n
   • p和q的低k位乘积的低k位必须等于n的低k位

1.4 示例脚本框架

def simple_prune(n, xor_result):
    # 初始化p和q的可能值
    p_candidates = [0]
    q_candidates = [0]
    
    for bit_pos in range(xor_result.bit_length()):
        new_p = []
        new_q = []
        current_bit = (xor_result >> bit_pos) & 1
        
        for p, q in zip(p_candidates, q_candidates):
            # 尝试所有可能的组合
            for p_bit in [0, 1]:
                for q_bit in [0, 1]:
                    if (p_bit ^ q_bit) == current_bit:
                        temp_p = p | (p_bit << bit_pos)
                        temp_q = q | (q_bit << bit_pos)
                        
                        # 剪枝条件检查
                        if check_prune_conditions(temp_p, temp_q, n, bit_pos):
                            new_p.append(temp_p)
                            new_q.append(temp_q)
        
        p_candidates, q_candidates = new_p, new_q
    
    return p_candidates, q_candidates

def check_prune_conditions(p, q, n, bit_pos):
    # 填充剩余位为0检查
    p_min = p
    q_min = q
    if p_min * q_min > n:
        return False
    
    # 填充剩余位为1检查
    p_max = p | ((1 << (n.bit_length() - bit_pos)) - 1)
    q_max = q | ((1 << (n.bit_length() - bit_pos)) - 1)
    if p_max * q_max < n:
        return False
    
    # 检查低k位乘积
    mask = (1 << (bit_pos + 1)) - 1
    if (p * q) & mask != n & mask:
        return False
    
    return True

2. 首尾剪枝攻击

2.1 基本概念

当给定p^q_rev（p与q的反方向二进制异或值）和n=p*q时，可以从两端向中间同时搜索。

2.2 搜索策略

1. 从两端向中间搜索：同时考虑最高位和最低位
2. 当前位分析：
   • 如果当前最高位为"1"：
     • p该位为1，q对应低位为0
     • p该位为0，q对应低位为1
   • 如果当前最高位为"0"：
     • p该位为0，q对应低位为0
     • p该位为1，q对应低位为1

2.3 剪枝条件

1. 将p、q未搜索到的位全填0，乘积应小于n
2. 将p、q未搜索到的位全填1，乘积应大于n
3. p、q低k位乘积的低k位应与n的低k位相同

2.4 示例脚本框架

def bidirectional_prune(n, xor_rev_result):
    bit_length = n.bit_length()
    # 初始化候选对，包含高低位
    candidates = [{'high_p': 0, 'high_q': 0, 'low_p': 0, 'low_q': 0, 'mask': 0}]
    
    for step in range((bit_length + 1) // 2):
        new_candidates = []
        current_high_bit = (xor_rev_result >> (bit_length - 1 - step)) & 1
        current_low_bit = (xor_rev_result >> step) & 1
        
        for cand in candidates:
            # 处理高位
            high_options = []
            if current_high_bit == 1:
                high_options.extend([(1, 0), (0, 1)])
            else:
                high_options.extend([(0, 0), (1, 1)])
            
            # 处理低位
            low_options = []
            if current_low_bit == 1:
                low_options.extend([(1, 0), (0, 1)])
            else:
                low_options.extend([(0, 0), (1, 1)])
            
            # 组合所有可能性
            for (hp, hq) in high_options:
                for (lp, lq) in low_options:
                    new_high_p = cand['high_p'] | (hp << (bit_length - 1 - step))
                    new_high_q = cand['high_q'] | (hq << step)
                    new_low_p = cand['low_p'] | (lp << step)
                    new_low_q = cand['low_q'] | (lq << (bit_length - 1 - step))
                    new_mask = cand['mask'] | (1 << step) | (1 << (bit_length - 1 - step))
                    
                    # 构建完整的p和q候选
                    temp_p = new_high_p | new_low_p
                    temp_q = new_high_q | new_low_q
                    
                    # 剪枝检查
                    if check_bidirectional_conditions(temp_p, temp_q, n, new_mask, bit_length):
                        new_candidates.append({
                            'high_p': new_high_p,
                            'high_q': new_high_q,
                            'low_p': new_low_p,
                            'low_q': new_low_q,
                            'mask': new_mask
                        })
        
        candidates = new_candidates
    
    return candidates

def check_bidirectional_conditions(p, q, n, mask, bit_length):
    # 计算未确定的位数
    unknown_mask = ((1 << bit_length) - 1) ^ mask
    
    # 填充0检查
    p_min = p
    q_min = q
    if p_min * q_min > n:
        return False
    
    # 填充1检查
    p_max = p | unknown_mask
    q_max = q | unknown_mask
    if p_max * q_max < n:
        return False
    
    # 检查已知位乘积
    known_mask = mask | ((1 << (bit_length // 2 + 1)) - 1)
    if (p * q) & known_mask != n & known_mask:
        return False
    
    return True

3. p^(q>>kbits)攻击

3.1 思路一：高位向低位搜索

条件：

• n = p*q
• leak = p^(q>>kbits)

搜索策略：

1. p的高kbits位可以从leak的高kbits位直接获得
2. 从第kbits位后开始搜索：
   • 如果leak的当前位为1：
     • p为1，q为0
     • p为0，q为1
   • 如果leak的当前位为0：
     • p为1，q为1
     • p为0，q为0

剪枝条件：

1. 将p和q剩余位全填1，必须满足p*q > n
2. 将p和q剩余位全填0，必须满足p*q < n
3. 结束条件：n mod p == 0

示例脚本框架：

def high_to_low_prune(n, leak, kbits):
    # 提取p的高kbits位
    p_high = leak >> (leak.bit_length() - kbits)
    p_high <<= (n.bit_length() - kbits)
    
    candidates = [p_high]
    
    for bit_pos in range(n.bit_length() - kbits - 1, -1, -1):
        new_candidates = []
        current_bit = (leak >> bit_pos) & 1
        
        for p in candidates:
            # 尝试两种可能性
            for p_bit in [0, 1]:
                temp_p = p | (p_bit << bit_pos)
                
                # 推导q的对应位
                q_bit = (p_bit ^ current_bit)
                
                # 剪枝检查
                if check_high_low_conditions(temp_p, n, bit_pos):
                    new_candidates.append(temp_p)
        
        candidates = new_candidates
    
    # 检查有效解
    for p in candidates:
        if n % p == 0:
            return p, n // p
    
    return None, None

def check_high_low_conditions(p, n, bit_pos):
    # 填充剩余位为0
    p_min = p
    q_min = 0
    if p_min * q_min > n:
        return False
    
    # 填充剩余位为1
    p_max = p | ((1 << bit_pos) - 1)
    q_max = ((1 << (n.bit_length() - p.bit_length())) - 1)
    if p_max * q_max < n:
        return False
    
    return True

3.2 思路二：迭代恢复法

算法步骤：

1. 从leak的高kbits位得到p的高kbits位
2. 用n除以p的高kbits位得到q的高位估计
3. 利用q的高位和leak恢复p的下kbits位
4. 重复这个过程直到恢复完整的p和q

示例脚本框架：

def iterative_recovery(n, leak, kbits):
    p = leak >> (leak.bit_length() - kbits)
    p <<= (n.bit_length() - kbits)
    
    recovered_bits = kbits
    while recovered_bits < n.bit_length():
        # 估计q的高位
        q_high = n // (p >> (p.bit_length() - recovered_bits))
        
        # 从leak恢复p的下kbits位
        next_p_bits = (leak >> (recovered_bits - kbits)) ^ (q_high >> (q_high.bit_length() - kbits))
        next_p_bits &= (1 << kbits) - 1
        
        # 更新p
        p |= (next_p_bits << (n.bit_length() - recovered_bits - kbits))
        recovered_bits += kbits
    
    if n % p == 0:
        return p, n // p
    return None, None

4. nextprime剪枝攻击

4.1 特殊条件

1. p和q的关系：q = nextprime(reverse(p))
2. 已知n = p*q
3. 可能已知q的低位信息

4.2 攻击步骤

第一步：爆破低6位

1. p*q的低6位必须等于n的低6位
2. 爆破p的低6位，计算对应的q的高6位

第二步：爆破高6位

1. 由于q = nextprime(reverse(p))，且nextprime偏移通常<2000
2. 从q的低6位可以推断p的高6位的逆序
3. 爆破依据：
   • p高6位后填0，q高6位后填0，乘积 < n
   • p高6位后填9，q高6位后填9，乘积 > n

第三步：中间位搜索

1. 从两端向中间搜索十进制位
2. 每次搜索10×10种可能（0-9）
3. 剪枝条件：
   • 未搜索位填0，乘积 < n
   • 未搜索位填9，乘积 > n
   • 低k位乘积的低k位 = n的低k位

4.3 示例脚本框架

def nextprime_prune(n, q_low_bits, p_low_bits=None):
    # 第一步：爆破p的低6位
    if p_low_bits is None:
        for p_low in range(10**6):
            # 计算q的高6位
            q_high = n // p_low
            q_high = int(str(q_high)[:6]) if q_high > 0 else 0
            
            # 检查低6位乘积
            if (p_low * q_high) % 10**6 == n % 10**6:
                break
    
    # 第二步：爆破p的高6位
    for offset in range(-2000, 2000):
        q_low = q_low_bits + offset
        if q_low < 0:
            continue
        
        p_high_rev = q_low
        p_high = int(str(p_high_rev)[::-1])
        
        # 剪枝检查
        p_test_min = p_high * 10**(p_low.bit_length())
        q_test_min = q_high * 10**(q_low.bit_length())
        if p_test_min * q_test_min > n:
            continue
            
        p_test_max = (p_high + 1) * 10**(p_low.bit_length()) - 1
        q_test_max = (q_high + 1) * 10**(q_low.bit_length()) - 1
        if p_test_max * q_test_max < n:
            continue
        
        # 找到可能的p高6位
        break
    
    # 第三步：中间位搜索
    candidates = [{'high': p_high, 'low': p_low}]
    total_digits = len(str(n)) // 2
    known_high_digits = len(str(p_high))
    known_low_digits = len(str(p_low))
    
    for pos in range(known_high_digits, total_digits - known_low_digits):
        new_candidates = []
        
        for cand in candidates:
            for d_high in range(10):  # p的下一个高位数字
                for d_low in range(10): # p的下一个低位数字
                    new_p_high = cand['high'] * 10 + d_high
                    new_p_low = cand['low'] + d_low * (10 ** (pos + known_low_digits))
                    
                    # 计算对应的q
                    p_rev = int(str(new_p_high).zfill(pos + known_high_digits + 1)[::-1] + 
                               str(new_p_low)[known_low_digits:])
                    q_cand = nextprime(p_rev)
                    
                    # 剪枝检查
                    p_min = new_p_high * (10 ** (total_digits - pos - 1)) + new_p_low
                    q_min = q_high * (10 ** (total_digits - pos - 1)) + q_low
                    if p_min * q_min > n:
                        continue
                        
                    p_max = (new_p_high + 1) * (10 ** (total_digits - pos - 1)) - 1 + new_p_low
                    q_max = (q_high + 1) * (10 ** (total_digits - pos - 1)) - 1 + q_low
                    if p_max * q_max < n:
                        continue
                    
                    # 检查已知位乘积
                    known_mask = 10 ** (pos + known_low_digits + 1)
                    if (p_min * q_min) % known_mask != n % known_mask:
                        continue
                    
                    new_candidates.append({'high': new_p_high, 'low': new_p_low})
        
        candidates = new_candidates
    
    # 验证候选
    for cand in candidates:
        p = cand['high'] * (10 ** (total_digits - known_high_digits)) + cand['low']
        if n % p == 0:
            return p, n // p
    
    return None, None

5. 实际应用案例

5.1 帕鲁杯"江枫渔火对愁眠"

问题特点：

• 混淆了按位或(|)和按位异或(^)操作
• 需要正确识别leak1^leak2=p^q

解决方案：

1. 确认实际是异或操作
2. 应用常规剪枝方法

5.2 DASCTF 2023 ezRSA

问题特点：

• 求出的n结尾是2且长度不足
• 实际n应该是计算结果加上N

解决方案：

1. 识别n可能被模减过
2. 恢复完整n = 计算结果 + N
3. 使用Franklin-Reiter攻击解flag

6. 总结与最佳实践

1. 正确识别操作：确认给定的信息是异或(^)还是或(|)操作
2. 搜索方向选择：
   • 从低位向高位：适合简单剪枝
   • 从两端向中间：适合首尾剪枝
   • 从高位向低位：适合p^(q>>kbits)情况
3. 剪枝条件：
   • 始终检查填充0和填充1的边界条件
   • 验证已知位的乘积匹配
4. 特殊关系处理：
   • nextprime关系需要十进制处理
   • 逆序关系需要调整搜索策略
5. 调试技巧：
   • 记录搜索过程中的候选数量
   • 设置合理的递归深度限制
   • 对中间结果进行验证

通过掌握这些剪枝技术，可以有效地解决多种RSA变体问题，特别是在CTF竞赛中遇到的部分密钥泄露场景。