> For the complete documentation index, see [llms.txt](https://ret2basic.gitbook.io/ctfnote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ret2basic.gitbook.io/ctfnote/crypto/rsa/prime-factors.md).

# Prime Factors

## FactorDB

Always try factoring the modulus `N` using `factordb-python`:

```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`.

```python
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`.

```python
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:

{% embed url="<https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-4/>" %}
Twin primes
{% endembed %}

```python
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:

```python
#!/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.