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