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}`