zer0pts CTF 2022 | Anti Fermat

#zer0ptsCTF2022

from Crypto.Util.number import isPrime, getStrongPrime
from secret import flag

def next_prime(n):
    n += 1
    while not isPrime(n):
        n += 1
    return n

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m.bit_length() < n.bit_length()
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

RSA で Suspicious Primeな問題。具体的には という形になっている