Prime Factors

FactorDB

Always try factoring the modulus N using factordb-python:

from Crypto.Util.number import inverse, long_to_bytes
from factordb.factordb import FactorDB

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------FactorDB--------#

f = FactorDB(N)
f.connect()
factors = f.get_factor_list()

#--------RSA decryption--------#

phi = 1
for factor in factors:
    phi *= factor - 1

d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

print(flag)

Modulus Itself is a Prime

• If the modulus $N$ is a prime, then we can directly compute $\phi = N - 1$.

• How to verify whether $N$ is a prime or not? Use sympy.ntheory.primetest.isprime.

from Crypto.Util.number import inverse, long_to_bytes
from sympy.ntheory.primetest import isprime
from sys import exit

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Primality test--------#

if isprime(N):
    print("N is a prime.")
else:
    print("N is not a prime.")
    exit()

#--------RSA decryption--------#

phi = N - 1
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

print(flag)

Repeated Prime Factor

• If the modulus is a perfect square of some prime $p$, i.e. $N = p^2$, then we can simply compute $p = \sqrt{N}$.

• If $p$ is found, then we have $\phi = p \cdot (p - 1)$.

• How to verify whether $N$ is a perfect square or not? Use sympy.ntheory.primetest.is_square.

from Crypto.Util.number import inverse, long_to_bytes
from sympy.ntheory.primetest import is_square
from sympy import root
from sys import exit

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Perfect square test--------#

if is_square(N):
    print("N is the square of some prime p.")
else:
    print("N is not a square.")
    exit()

#--------RSA decryption--------#

p = int(root(N, 2))
print(f"{p = }")
phi = p * (p - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

print(flag)

Twin Primes

"Twin primes" means $N = p \cdot q$ and $q = p + 2$. The value of $p$and $q$can be easily computed using quadratic formula. The detailed derivation can be found here:

Attacking RSA for fun and CTF points – part 4BitsDeep

Twin primes

from Crypto.Util.number import inverse, long_to_bytes
from math import sqrt

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Twin primes--------#

p = abs(int(sqrt(N + 1)) - 1)
q = abs(int(-sqrt(N + 1)) - 1)

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

print(flag)

Multi-prime

If the modulus $N$is the product of multiple primes, it is possible to factor it in a short amount of time:

#!/usr/bin/env sage
from Crypto.Util.number import inverse, long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Multi-prime--------#

primes = ecm.factor(N)

phi = prod(p - 1 for p in primes)
d = inverse(e,phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

This factorization can be done with the ecm.factor() function from Sage.