# Values from the challenge
n = 1079
e = 43
p = 13  # Smaller prime
q = 83  # Larger prime
c_list = [996, 894, 379, 631, 894, 82, 379, 852, 631, 677, 677, 194, 893]
 
# Step 1: Calculate Phi(n)
phi = (p - 1) * (q - 1)
 
# Step 2: Calculate the private key 'd' 
# Using pow() with -1 calculates the modular multiplicative inverse
d = pow(e, -1, phi)
 
# Step 3: Decrypt each character
plaintext = ""
for c in c_list:
    m = pow(c, d, n)
    plaintext += chr(m)
 
print(f"Private Key (d): {d}")
print(f"Decrypted Message: {plaintext}")
 

IyBWYWx1ZXMgZnJvbSB0aGUgY2hhbGxlbmdlCm4gPSAxMDc5CmUgPSA0MwpwID0gMTMgICMgU21hbGxlciBwcmltZQpxID0gODMgICMgTGFyZ2VyIHByaW1lCmNfbGlzdCA9IFs5OTYsIDg5NCwgMzc5LCA2MzEsIDg5NCwgODIsIDM3OSwgODUyLCA2MzEsIDY3NywgNjc3LCAxOTQsIDg5M10KCiMgU3RlcCAxOiBDYWxjdWxhdGUgUGhpKG4pCnBoaSA9IChwIC0gMSkgKiAocSAtIDEpCgojIFN0ZXAgMjogQ2FsY3VsYXRlIHRoZSBwcml2YXRlIGtleSAnZCcgCiMgVXNpbmcgcG93KCkgd2l0aCAtMSBjYWxjdWxhdGVzIHRoZSBtb2R1bGFyIG11bHRpcGxpY2F0aXZlIGludmVyc2UKZCA9IHBvdyhlLCAtMSwgcGhpKQoKIyBTdGVwIDM6IERlY3J5cHQgZWFjaCBjaGFyYWN0ZXIKcGxhaW50ZXh0ID0gIiIKZm9yIGMgaW4gY19saXN0OgogICAgbSA9IHBvdyhjLCBkLCBuKQogICAgcGxhaW50ZXh0ICs9IGNocihtKQoKcHJpbnQoZiJQcml2YXRlIEtleSAoZCk6IHtkfSIpCnByaW50KGYiRGVjcnlwdGVkIE1lc3NhZ2U6IHtwbGFpbnRleHR9IikK