如何在pow(a,b,c)中反向求解b并还原未知TEXT？

核心思路 #

问题的关键在于利用PKCS#7填充的结构特性，避免直接求解1024位的离散对数（暴力破解TEXT完全不可行）。通过枚举填充长度p（仅256种可能），将原问题拆解为多个小规模离散对数求解，最终验证候选结果是否符合填充规则。

具体步骤 #

1. 利用费马小定理简化同余关系
   因为c是素数，根据费马小定理，2^(c-1) ≡ 1 mod c，因此原等式2^b ≡ y mod c可转化为：
   b ≡ log₂(y) mod (c-1)
   但我们不需要直接求解完整的离散对数，而是结合b的结构（b = 字节转长整数(pad(TEXT,256))）来缩小范围。

2. 枚举填充长度p
   PKCS#7填充规则是：填充p个字节，每个字节的值为p，其中1 ≤ p ≤ 256。对每个p执行以下操作：

   • 计算填充部分对应的数值：pad_num = p * (256^p - 1) // 255（这是p个值为p的字节转成的长整数）。
   • 将b = text_num * 256^p + pad_num代入原同余式，变形得到：
     (2^(256^p))^text_num ≡ y * 2^(-pad_num) mod c
   • 令A = pow(2, 256^p, c)，B = y * pow(2, (-pad_num) % (c-1), c) % c，此时问题转化为求解A^text_num ≡ B mod c——这是一个小规模离散对数问题（text_num对应TEXT的长度，远小于c的位数）。

3. 求解小规模离散对数并验证
   使用Baby-step Giant-step算法快速求解text_num，然后：

   • 计算候选b值：b_candidate = text_num * 256^p + pad_num。
   • 将b_candidate转换为大端字节串，验证是否符合PKCS#7规则：字节串长度是256的倍数，且最后p个字节全为p。
   • 验证通过后，用unpad去除填充得到TEXT。

实现代码 #

from Crypto.Util.number import *
from Crypto.Util.Padding import unpad

c = 178421928611071019360267030334948865864898765051649286940999740284901927205871904589008975999166343705176087678836390158248443701521112359395642244010241537603886223197773601996752130369527788156850561634811382810306708743274890833005691607859804295513120809249269263095276488896526807638635252842937565466271
y = 21343660735918737508327032642093044458513430667350324146942601945958232402677794381334538380151928312459028941815432844601005666496537855378093591308495810737072737197378249689765750242912228630158636001591313536255003252774830039438050786246884290993531824792273255248565666477421036484450980164795516106937

def baby_step_giant_step(a, b, p):
    # 求解 a^x ≡ b mod p
    m = int(p**0.5) + 1
    table = {pow(a, i, p): i for i in range(m)}
    a_m_inv = pow(pow(a, m, p), p-2, p)
    current = b
    for j in range(m):
        if current in table:
            return j*m + table[current]
        current = current * a_m_inv % p
    return None

for p in range(1, 257):
    # 计算填充对应的数值（模c-1避免溢出）
    pad_num = p * (pow(256, p, c-1) - 1) // 255
    # 构造A和B
    exponent = pow(256, p, c-1)
    A = pow(2, exponent, c)
    inv_pad = pow(2, (-pad_num) % (c-1), c)
    B = y * inv_pad % c
    # 求解text_num
    text_num = baby_step_giant_step(A, B, c)
    if text_num is None:
        continue
    # 生成候选b并转换为字节串
    try:
        padded_bytes = long_to_bytes(text_num * pow(256, p) + pad_num)
        # 验证填充规则
        if len(padded_bytes) % 256 != 0 or padded_bytes[-p:] != bytes([p])*p:
            continue
        # 去除填充得到TEXT
        text = unpad(padded_bytes, 256)
        print(f"还原得到TEXT: {text.decode('utf-8')}")
        break
    except (ValueError, OverflowError):
        continue

关键优势 #

• 枚举填充长度仅256次循环，计算成本极低。
• 将1024位的大离散对数问题转化为小规模离散对数求解，Baby-step Giant-step算法可快速完成。
• 通过PKCS#7填充规则验证，能直接过滤无效候选结果。

内容的提问来源于stack exchange，提问作者hexa