Question

Encrypt the message UPLOAD using the RSA system with $n=53\cdot 61\mathrm{and}\mathrm{e}=17$, translating each letter into integers and grouping together pairs of integers, as done in Example 8.

Short answer

The encrypted message is: $254527571211$.

Step-by-step solution

Step 1

UPLOAD

$2015111403$

To encrypt this message, first we have to find out the numeric values of each letter used throughout the message. In the English alphabet, and with RSA conventions, we find out that

$$\begin{gathered} U=20,P=15,\mathrm{L}=11,\mathrm{A}=0\mathrm{and}\mathrm{D}=3. \\ \mathrm{n}={53}^{\ast }61,\mathrm{e}=17 \\ \gcd (17,(52\ast 60\left)\right)=1 \end{gathered}$$

We then check out if our key is correct by calculating the gcd between the exponent $"\mathrm{e}"and\mathrm{n}={\mathrm{p}}^{\ast }\mathrm{q}$ which should be 1 .

Since it is 1 we can now proceed to encrypt the message.

Step 2

$$\begin{gathered} 2015-1114-0003 \\ {\mathrm{M}}_1=2015 \\ {M}_2=1114 \\ {M}_3=0003 \end{gathered}$$

We separate now out string in blocks of four digits (RSA convention), by doing some concatenation. Since out string leaves two digits, 0 and 3 , without the necessary digits to fill the $4-\mathrm{digit}$block, we add 0's to the n leftmost bits, this means that we will add two 0's before the concatenation "03" .

We assign a variable to each block.

$C_x=M_x^{\epsilon }(modn)$

Now, to encrypt each one of the three blocks we have, we use the following equation, where x represents the block we are working on, e represents the exponent and n is our modulus.

Step 3

$C_1={2015}^{17}(mod3233)$

For the first block, it follows that ${\mathrm{M}}_1=2015$, and $e=17,n=3233$(for every block).

$$\begin{gathered} {2015}^{17}={2015}^{16}\ast {2015}^1={2015}^8\ast {2015}^8\ast {2015}^1={2015}^4\ast {2015}^4\ast {2015}^4\ast {2015}^4\ast {2015}^1= \\ {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^2\ast {2015}^1 \end{gathered}$$To compute ${2015}^{17}$, we need to reduce the exponent so we can power $2015$with small numbers. Notice that ${2015}^{17}={2015}^{16}\ast {2015}^1$, but this is valid because

$\gcd (16,3233)=1AND\gcd (1,3233)=1$.

When doing this kind of process, we need to be aware of this.

So we find a larger, but powered-reduced expression for ${2015}^{17}$.

Step 4

$$\begin{gathered} {2015}^2(mod3233)=4060225(mod3233)=2810(mod32330) \\ {2015}^2\ast {2015}^2=1114 \\ {2015}^{17}={1114}^2\ast {1114}^2\ast {2015}^1 \\ {2015}^{17}={2757}^2\ast {2015}^1{2015}^{17}={266}^{\ast }{2015}^1 \\ {C}_1={2015}^{17}=2545(mod3233) \end{gathered}$$

We start by finding out ${2015}^2$, and then we square this result to obtain $1114$, which we then square two times, to obtain in each number $2757$. We are doing here pure powering of numbers and applying modulus $3233$TO EACH calculation. We keep doing this until we found a very easy expression for ${2015}^{17}$.

$$\begin{gathered} C_1=2545 \\ {C}_2=2757 \\ {C}_3=1211 \end{gathered}$$

We do this same process for the other two blocks and the concatenation of $C_1,C_2,C_3$is our encrypted message.