加密 RSA 使用位掩码查找 p 和 q

Question

我是加密货币新手，我陷入了这个挑战，我需要能够以某种方式提取 p 和 q。

您将获得一个Python脚本和一个带有ecnrypted标志和其他相关元素的output.txt 这是给您的脚本：

from Crypto.PublicKey import RSA

RSAkeys = RSA.generate(2048)
p = RSAkeys.p
q = RSAkeys.q
n = RSAkeys.n
e = RSAkeys.e
m = b"LetsCTF{<REDACTED>}"
c = pow(int.from_bytes(m, "big"), e, n)

mask = int("55" * 128, 16)
r = p & mask
mask = mask << 1
r += q & mask

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"r = {r}")

问题是我无法从“n”，“e”，“c”和“r”中提取p和q 我理解 RSA 背后的概念，但我仍然无法解决它。

到目前为止，我已经尝试制作一个脚本并尝试从 r 获取 p 和 q 。

mask = int("55" * 128, 16)

之后的初始掩码的形式为 0101 0101 ... 0101（一系列二进制 5）。那么此时的r：

r = p & mask

就是p的偶数位组成的整数。将掩码向左旋转后，q 的奇数位被添加到 r 中。那么r是一个整数，其偶数位是q的偶数位，其奇数位是q的奇数位。

我编写这个脚本是为了获得 p 和 q 的近似值（每个位的一半）：

pa = ""
qa = ""
i = 0
for elem in bin(r).lstrip("0b"):
    if i % 2 == 0:
        pa+= elem
        qa+= '0'
    else:
        qa+= elem
        pa+= '0'
    i += 1


pa = int(pa,2)
qa = int(qa,2)

r 的偶数位分配给 pa（p 的近似值），qa 分配为 0，奇数位则相反。

到目前为止我还没能完成pa和qa到p和q。我知道 pq 等于“n”，但我不知道如何修改 pa 和 qa 以便 paqa 转换为 n。 感谢您的关注，并为我糟糕的英语感到抱歉。

Answer 1

这是一个程序，演示了一种恢复 RSA 模数 n = p * q 的未知素因数 p 和 q 的方法。

基本思想是问题中的

r

值为我们提供了 p 的所有其他位和 q 的所有其他位。假设我们知道 p 和 q 的低位 B 位。然后我们可以写 p = p₁2^B + p₀ 和 q = q₁2^B + q₀，所以 n = pq = p₁q₁2^2B + (p₁q₀ + p₀q₁)2^B + p₀q₀,其中 mod 2^B 等于 p₀q₀。换句话说，n的低阶B位仅取决于p和q的低阶B位。该算法在每次迭代时将 p 和 q 的已知部分的大小增加 2 位。

# https://stackoverflow.com/q/78578789/238704
import math
import random
import time

_PRIME_SIZE_BITS = 1024
_PRIME_SIZE_BYTES = _PRIME_SIZE_BITS // 8


def create_ctf_instance():
    primes = []
    while len(primes) < 2:
        prime = random.SystemRandom().getrandbits(_PRIME_SIZE_BITS) | 1
        if pow(2, prime - 1, prime) == 1 and pow(3, prime - 1, prime) == 1:  #  good enough for RSA-sized primes
            primes.append(prime)
    p, q = primes
    n = p * q
    e = 65537
    m = b"LetsCTF{<blah, blah, and blah>}"
    c = pow(int.from_bytes(m, "big"), e, n)
    mask = int("55" * _PRIME_SIZE_BYTES, 16)
    r = p & mask
    mask = mask << 1
    r += q & mask
    return n, e, c, r


def find_factors(n: int, cheat: int) -> tuple[int, int] | tuple[None, None]:
    """
    Assume n is the product of two primes p and q, each no larger than _PRIME_SIZE_BITS.
    Using the "cheat" value `cheat` which gives us 1/2 of the bits, find the unknown
    # 1/2 of the bits and return p and q.
    :param n:
    :param cheat:
    :return:
    """
    mask = int("55" * _PRIME_SIZE_BYTES, 16)
    survivors = {(1, 1)}
    current_bit_length = 0
    low_order_bitmask = 0x3
    #
    # build the prime factors of n, p and q, from the low-order bit to the
    # high-order bit two bits at a time. One of those bits for each prime
    # is provided by `cheat` and one we have to guess. We check our guess by
    # multiplying these low-order bits together and verifying that they
    # match the low-order bits of n
    #
    while current_bit_length < (n.bit_length() + 1) // 2:
        next_survivors = set()
        while survivors:
            p_start, q_start = survivors.pop()
            # place the next cheat bits into each prime candidate
            p_start |= (cheat & mask) & low_order_bitmask
            q_start |= (cheat & (mask << 1)) & low_order_bitmask
            # now guess the unknown bit in each of p and q and check the guess
            for next_p_bit in range(2):
                p = p_start | next_p_bit << (current_bit_length + 1)
                for next_q_bit in range(2):
                    q = q_start | next_q_bit << current_bit_length
                    if (p * q ^ n) & low_order_bitmask == 0:
                        next_survivors.add((p, q))
        survivors = next_survivors
        current_bit_length += 2
        low_order_bitmask = (low_order_bitmask << 2) | 0x3
    for p, q in survivors:
        if p * q == n:
            return p, q
    return None, None


def main():
    n, e, c, r = create_ctf_instance()
    start = time.process_time()
    p, q = find_factors(n, r)
    elapsed = time.process_time() - start
    if p is None:
        print("No factors found")
    else:
        print(f'found factors: \n\t{p}\n\t{q}\nin {elapsed} seconds')
        # compute d
        car_lam = math.lcm(p - 1, q - 1)
        d = pow(e, -1, car_lam)
        m = pow(c, d, n)
        print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode())


if __name__ == '__main__':
    main()