Introduction

RSA is perhaps the most well known public public key cryptosystem out there. A lot of the problems on this site deal with RSA so if you aren't familiar with RSA consider this a short primer on the system. The basic idea behind public key cryptography is that there are two keys, a public key and a private key. The public key is used for encrypting and verifying messages and can be distributed to anyone whereas the private key is used for decrypting and signing messages and should be kept secret by the party that generated the keys. For the purposes of this problem we'll only concern ourselves with encryption and decryption.

RSA Basics

RSA is composed of three algorithms, namely $Key$ $Generation$ $(Gen)$, $Encryption$ $(Enc)$ and $Decryption$ $(Dec)$. In RSA the public key is a pair of integers $(e, N)$ and the private key is an integer $d$. The three algorithms are described below:

$Gen$

Pick two prime numbers of the same bit size, call them $p$ and $q$.

Let $N = p*q$ and let $\phi(N) = (p-1)*(q-1)$.

Choose an integer $e$ such that $gcd(e, \phi(N)) = 1$ (i.e. such that $e$ and $\phi(N)$ share no common factors).

Let $d = e^{-1} \text{ mod } \phi(N)$.

Output $(e, N)$ as the public key and $d$ as the private key.

$Enc$

To encrypt integer $m$ with public key $(e, N)$ calculate $c = m^e \text{ mod } N$.

Output $c$ as the encrypted message.

$Dec$

To decrypt integer $c$ with private key $d$ calculate $m = c^d \text{ mod } N$.

Output $m$ as the decrypted message.

If you're interested you can refer to this page for the proof of correctness that $Dec(Enc(m)) = m$.

Concrete Example

Let $p = 13$, $q = 17$, $N = p*q = 221$

Calculate $\phi(N) = (p-1) * (q-1) = 12 * 16 = 192$.

Let $e = 5$ (note that $gcd(5, 192) = 1$).

Calculate $d = e^{-1} \text{ mod } \phi(N) = 5^{-1} \text{ mod } 192 = 77$.

To encrypt $m = 100$ calculate $c = 100^5 \text{ mod } 221 = 172$,

To decrypt $c$ calculate $m = 172^{77} \text{ mod } 221 = 100$.

Some Details

Note that we can only encrypt integers smaller than $N$ with RSA as decryption will always yield a term less than $N$. Also note that if we wish to encrypt strings or other data types we must first convert them to integer form (e.g. by interpreting the datas binary representation as an integer). As long as after decryption we convert back from integer to the data type we originally had this is no problem. The security of the scheme comes from the difficulty of recovering $m$ given $c$ and $(e, N)$. We can try to compute the $e$th root modulo $N$ of $c$ to recover $m$, which is actually known as the RSA Problem and is conjectured (but not proven) to be computationally intractable. Another approach would be to compute $d$ from $(e, N)$ and then perform a decryption operation. This reduces to factoring $N$ into $p$ and $q$ which is again conjectured to be computationally intractable (for sufficient size $N$).

The Problem

Given the following public key, private key, and encrypted message ($c = m^e \text{ mod } N$), compute the original message ($m$). Submit your answer as a hex integer (no lead 0x, all lower case characters).

(e, N) = (0x3, 0x64ac4671cb4401e906cd273a2ecbc679f55b879f0ecb25eefcb377ac724ee3b1)
d = 0x431d844bdcd801460488c4d17487d9a5ccc95698301d6ab2e218e4b575d52ea3
c = 0x599f55a1b0520a19233c169b8c339f10695f9e61c92bd8fd3c17c8bba0d5677e

Solution