Determine the factors p and q of an RSA modulus n (=p×q) given the values of n and p XOR q

rsa-pq-xor-crack.py

# Given a semiprime n and the xor product of
# its two factors p and q, calculate p and q

def rsa_xor_crack(n, pxq, k, start, p0):
    # n: the semiprime we are trying to factorize (=p*q)
    # pxq: the XOR product of n's two prime factors (= p^q)
    # k: the number of bits to extract per iteration
    # start: the first unknown bit we want to find
    # p0: a tentative value for the first start bits of p
    bit_mask = (1 << start + k) - 1
    for i in range((1<<k)):
        # Guess next {k} bits of p
        p1 = (i << start) | p0
        if p1 * p1 > n:
            # Fail. End recursion here
            return False
        # Calculate corresponding bits of q
        q1 = (p1 ^ pxq) & bit_mask
        n1 = p1 * q1
        if n1 == n:
            # Success
            return (p1, q1)
        if n1 & bit_mask == n & bit_mask:
            # Calculate next chunk by recursion
            result = rsa_xor_crack(n, pxq, k, start + k, p1)
            if result:
                return result
    # Nothing found
    return False

# Example:

n = int('aeae14ec2a0d2fe313e5db9b0e88639567da43e276bc4a798bf44eea046f772ede1d'+\
        '56ab80486c978268614a8e8887acd627a163a2753a97f757acd10b63375ff70cbb9d'+\
        '8b7e74b96550bdb4ee7c9bf2a6209eacf25732eeb09ac2b6ab4322da64da4dfa578d'+\
        'b00923280cb0a741301e166000ac2dbd83c108c2ab112aafa4fd', 16)
pxorq = int('164c05bbe5c199f396590c61c99d60625bdc212cf71ac44c40a8c4ba83497d94'+\
        'ee4863042aa5415922629d7e72f24f5ec489d911a7cf520dc9ed6f3324473c7c', 16)
rsa_xor_crack(n, pxorq, 4, 0, 0)