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

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

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

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

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

Last updated