Enumerate all possible RSA plaintexts given a ciphertext, two primes p and q, and any integer e.

t.py

from Crypto.Util.number import GCD, bytes_to_long, long_to_bytes

class CRT:
    def __init__(self, p, q):
        self.p_p_inv = p * pow(p,-1,q)
        self.p_q = p * q
    def calc(self, a, b):
        x = a + (b - a) * self.p_p_inv
        return x % self.p_q

def factor(n):
    factors = []
    p = 2
    while n > 1:
        k = 0
        while n % p == 0:
            n /= p
            k += 1
        if k > 0:
            yield (p, k)
        p += 1

def primitive_nth_root(n, p):
    g_m = 1
    for l, n in factor(n):
        g = 2
        while pow(g, (p - 1) // l, p) == 1:
            g += 1
        g_m = (g_m * pow(g, (p - 1) // l ** n, p)) % p
    return g_m

def decrypt_all(c, e, p, q):
    """For RSA done mod p*q
    """

    # Create CRT context for combining
    crt = CRT(p, q)

    # Find the largest multiple m_p of e's factors that divides p-1
    phi_p = p-1
    m_p = 1
    while (gcd := GCD(phi_p, e)) > 1:
        phi_p //= gcd
        m_p *= gcd

    # Find the largest multiple m_q of e's factors that divides q-1
    phi_q = q-1
    m_q = 1
    while (gcd := GCD(phi_q, e)) > 1:
        phi_q //= gcd
        m_q *= gcd

    # Find one of the roots mod p and mod q
    r_p = pow(c, pow(e, -1, phi_p), p)
    r_q = pow(c, pow(e, -1, phi_q), q)

    # Then enumerate the rest of the roots by multiplying by the m-th roots of unity
    x = primitive_nth_root(m_p, p)
    y = primitive_nth_root(m_q, q)

    for _ in range(m_p):
        for _ in range(m_q):
            yield crt.calc(r_p, r_q)
            r_q = (r_q*y)%q
        r_p = (r_p*x)%p


def decrypt_all_prime(c, e, p):
    """For RSA done mod p
    """

    # Find the largest multiple m_p of e's factors that divides p-1
    phi_p = p-1
    m_p = 1
    while (gcd := GCD(phi_p, e)) > 1:
        phi_p //= gcd
        m_p *= gcd

    # Find one of the roots mod p and mod q
    r_p = pow(c, pow(e, -1, phi_p), p)

    # Then enumerate the rest of the roots by multiplying by the m-th roots of unity
    x = primitive_nth_root(m_p, p)

    for _ in range(m_p):
        yield r_p
        r_p = (r_p*x)%p


p = 327414555693498015751146303749141488063642403240171463406883 # 191 divides p-1
q = 693342667110830181197325401899700641361965863127336680673013 # 673 divides q-1
e = 191 * 673 * 11
c = 194186516353725635893223797231621259449401879863371122992551811855573257121740630993813847863192405635178789086158088709

for plain in decrypt_all(c, e, p, q):
    if (b := long_to_bytes(plain)).startswith(b"pwned"):
        print(b)
        break

p = 7852254689934457914164517553948728068824029461583663893319011306325520591196726981549767414709331981931824272592553540226726711107942021372932185197531771
q = 10802986030484856524163169767252165873196316662310116664453733294061231223500707432424304305590076669803179079841351119551371498782497659569244910738297053
e = 65537 * 2
c = 20903612714102789758649407391136063099919174985123402877724548219705409134699583479694897883341673282179825344048216674980935172475783460811985621595553597148312581359704003252759166734984407716458388015357930933477460942561005268250137704082994199952592028806536457220776000839961054398113943878100205467166

for plain in decrypt_all(c, e, p, q):
    if (b := long_to_bytes(plain//2)).startswith(b"pwned"):
        print(b)
        break


p = 158956010976836742521330254087275425096501583054825136137040889728364290468342445750425376148898452284963095323948276435573809460871703413808672473157217817381946017879464498512288960101002405275174672926496400917470509079465025417877720664744491054992376496575684398645703346912039046842844204816524282238459
e = 65536
c = 17696325213195819360084027228862087546075383230711834052302081670404491942278399339165629822030797913121661625273125782635636475385580385239446207346095935362399429412825040827923795088154904762207215060766109368707427481633970394393914176132798637385151502305355038711511174834777689397585730318578634645332

for plain in decrypt_all_prime(c, e, p):
    if (b := long_to_bytes(plain)).startswith(b"pwnEd"):
        print(b)
        break