Python3 Simple RSA CTF Solver

rsa.py

# python3 -m pip install pycryptodome==3.4.3
from Crypto.Util.number import inverse, long_to_bytes
import decimal, binascii

# If you have the id_rsa.pub or equivalent
# ssh-keygen -f id_rsa.pub -e -m PKCS8 > id_rsa.pem

# If you have a private key (pem) file
# - http://certificate.fyicenter.com/2145_FYIcenter_Public_Private_Key_Decoder_and_Viewer.html
# -- Fill in n, e, d, p, q (Note: numeric values of n,d,p,q - Not displayed hex values)
# -- Convert hex to decimal over at: https://www.binaryhexconverter.com/hex-to-decimal-converter

n = 0 # Enter given n value here - Leave as 0 if not available
e = 0 # Enter given e value here - Required
c = 0 # Enter given c value here - Leave as 0 if not available (If 0, will assume you have a cipher file named cipher)
d = 0 # Enter given d value here - Leave as 0 if not available

# If you have n
# - Go to http://factordb.com/ and enter in n
# - Under "Number", p = left, q = right. If they have ^2 on them, add **2 to the end of the number

# If you have p and q, just enter them

p = 0
q = 0

###                             ###
### Do not edit below this line ###
###                             ###
if (n == 0):
  n = p * q

# Cubed Root Attack (Thanks John!)
if e == 3:
  decimal.getcontext().prec = 3000
  c_decimal = decimal.Decimal(str(c))
  m = c_decimal ** (decimal.Decimal('1') / 3)
  m = int(m) + 1
  result = long_to_bytes(m)
  print("Possible Solution: " + result.decode("utf-8"))

if p != 0 and q != 0:
  # They match - Different calc
  if p == q:
    phi = p * (p - 1)
  else:
    phi = (p - 1) * (q - 1)
  # Either solving for c or d
  if d == 0:
    d = inverse(e,phi)
  if c == 0:
    with open("cipher", "rb") as f:
      data = f.read()
    c = int(binascii.hexlify(data), 16)

  # We should have everything now
  m = pow( c, d, n )
  print(long_to_bytes(m))

Given n1, n2, c1, c2, e

Thanks To: H-mmer

from Crypto.Util.number import *

n1 = 0 # Insert n1 here
n2 = 0 # Insert n2 here
c1 = 0 # Insert c1 here
c2 = 0 # Insert c2 here
e = 0 # Insert e here - Probably 65537

###                             ###
### Do not edit below this line ###
###                             ###

p = GCD(n1,n2)
q1 = n1 // p
q2 = n2 // p

phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)
d1 = inverse(e,phi1)
d2 = inverse(e,phi2)

print(long_to_bytes(str(pow(c1,d1,n1)) + str(pow(c2,d2,n2))))

Given n1, n2, e1, e2, c1, c2, where n1 == n2 (Common Modulus Attack)

Thanks to: lossme

import gmpy2

n1 = 0 # Insert n1 here 
e1 = 0 # Insert e1 here  
c1 = 0 # Insert c1 here 
n2 = 0 # Insert n2 here 
e2 = 0 # Insert e2 here 
c2 = 0 # Insert c2 here

###                             ###
### Do not edit below this line ###
###                             ###

assert n1 == n2
assert gmpy2.gcd(e1, e2) == 1
n = n1
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
    s = -s
    c1 = gmpy2.invert(c1, n)
if t < 0:
    t = -t
    c2 = gmpy2.invert(c2, n)
plain_code = gmpy2.powmod(c1, s, n) * gmpy2.powmod(c2, t, n) % n
plain_code = int(plain_code)
b_plain_text = plain_code.to_bytes(plain_code.bit_length() // 8 + 1, "big")

print(b_plain_text)

Sometimes get p / q from n (Doesn't always work)

Thanks to: murtaza-u and tryhackme

#!/usr/bin/python3

# pip install gmpy2
# If that fails, sudo apt install libmpc-dev first

from gmpy2 import isqrt

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will always
    # be 2
    if (n & 1) == 0:
        return (n/2, 2)

    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    # n = (a - b) * (a + b)
    # n = a^2 - b^2
    # b^2 = a^2 - n
    while True:
        a += 1
        _b = a * a - n
        b = isqrt(_b)
        if (b * b == _b):
            break

    return (a + b, a - b)

n = 0 # CHANGE ME

ret = factorize(n)
print("p: " + str(ret[0]))
print("q: " + str(ret[1]))

Generate private key from n, p, q, and e

python3 rsatool.py -n CHANGEME -p CHANGEME -q CHANGEME -e CHANGEME(Probs 65537) -f PEM -o priv.key

chmod 600 priv.key