Category: Crypto
Points: 30
Description: I found this flag somewhere when I was taking a walk, but it seems to have been encrypted with this Really Secure Algorithm!

So for this challenge we are given the RSA values [p, q, e, c]. p, q and e is enough for us to create the private key to decrypt c. So following the wikipedia crypto system and implementing in python I came up with this really simple code.

# This function is from https://gist.github.com/JonCooperWorks/5314103
def multiplicative_inverse(e, phi):
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_phi = phi
    
    while e > 0:
        temp1 = temp_phi/e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2
        
        x = x2- temp1* x1
        y = d - temp1 * y1
        
        x2 = x1
        x1 = x
        d = y1
        y1 = y
    
    if temp_phi == 1:
        return d + phi

# This function was from https://ehsandev.com/pico2014/cryptography/rsa.html which is a similiar problem
def int2Text(number, size):
    text = "".join([chr((number >> j) & 0xff)
                    for j in reversed(range(0, size << 3, 8))])
    return text.lstrip("\x00")

p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349

n = p * q 
phi = (p - 1) * (q - 1)
d = multiplicative_inverse(e, phi)

message = pow(c, d, n)

print(int2Text(message, 100))

FLAG:

actf{really_securent_algorithm}

Leave a Reply

Your email address will not be published. Required fields are marked *