Exercise: Break RSA!

Consider the RSA public key given by

In [ ]:
n = 194274643231062691639385358112415982451463622172113143877512004427914261025147048739356361887575532773667861593051354629764405946743284497286723965324741156978690684829554458173152778310374159011721000570585940777404127368513940684751750910776238483500360184414065484071342966288566487689480824777449462799007

and $e=3$. Use an attack on RSA to compute the decryption exponent $d$ and use it to decrypt the ciphertext

In [ ]:
c = 54860562824715822168825232480964011986219163719726350974576005312399951585888845531002720741951998061282263360346959802670217808873962937389593437552745761216513573991088162768419980444289236920498215809444798924231024339878965264258629142507614163256681604408539934842940257453724759816370758908769625403060

and then recover the orginal message $m$.

Interpret $m$ as a base 27 number with $\mathtt{A} = 1$, $\mathtt{B} = 2$, etc. Once you find $m$ you can convert it to a base-27 integer with the Sage command m.digits(base=27) and then discard the $0$s used to pad the message. What is the secret message?

Hint: The public key was chosen to be vulnerable. Try the $p-1$ factoring method.