RSA Solver

rsa_solver.py

# Sources
# https://stackoverflow.com/questions/4643647/fast-prime-factorization-module
# https://stackoverflow.com/questions/49856115/inverse-of-a-powa-b-n-function-in-python-decryption-code
# Solutions on cryptohack.org

## Imports
import binascii
import base64
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
from sympy.ntheory import factorint


## Set Vars HERE

cipher_text = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
e = 65537
#n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
P = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
Q = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591



def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

# d3CrY9t0r
def decrypt_it_all(encrypted_message, e):

    # Get our intercepted message into integer form
    #decoded_intercepted_message = base64.b64decode(encrypted_message)
    #decoded_text_integer = textToInteger(decoded_intercepted_message)

    
    ## If you need to factor N (please check factordb first) then you can do that here...
    # Factor n
    #factor_list = factorint(n)
    #factor_obj = [i for i in factor_list]
    #P = factor_obj[0]
    #Q = factor_obj[1]

    gcd, x, y = egcd(e, (P-1)*(Q-1))
    #D = x + (P-1)*(Q-1)

    if P != Q: # One would hope this is normally the case...
        n, phi = P * Q, (P - 1) * (Q - 1)
    else:
        n = P
        phi = (P - 1) * (Q - 1)
    
    D = inverse(e, phi)

    return pow(encrypted_message, D, n)


message = decrypt_it_all(cipher_text, e)
readable_message = long_to_bytes(message)

print(readable_message)