Question

What is the original message encrypted using the RSA system with $n=43\cdot 59and\mathrm{e}=13$if the encrypted message is $066719470671$? (To decrypt, first find the decryption exponent d which is the inverse of $\mathrm{e}=13modulo42\cdot 58$).

Short answer

SILVER

Step-by-step solution

Step 1

Given encryption: $066719470671$.

$$\begin{gathered} n=43\cdot 59=2537 \\ e=13 \end{gathered}$$

Since $n=42\cdot 58=2436,n=42\cdot 58=2436$d is then the inverse of$13modulo243613mod2436=1$ (which means $13\mathrm{mod}2436=1$and d integer with $0\le d<2436$).

$d=937$

Decrypt each block using the mapping $M_1=C^{d}mod2537$.

$$\begin{gathered} M_1={0667}^{937}mod2537=1808 \\ {M}_2={1947}^{937}mod2537=1121 \\ {M}_3={0671}^{937}mod2537=0417 \end{gathered}$$

Thus, the message is then:

$180811210417$

Let

$$\begin{gathered} \mathrm{A}=00,\mathrm{B}=01,\mathrm{C}=02,\mathrm{D}=03,\mathrm{E}=04,\mathrm{F}=05,\mathrm{G}=06,\mathrm{H}=07,\mathrm{I}=08,\mathrm{J}=09,\mathrm{K}=10,\mathrm{L}=11 \\ \mathrm{M}=12,\mathrm{N}=13,\mathrm{O}=14,\mathrm{P}=15,\mathrm{Q}=16,\mathrm{R}=17,\mathrm{S}=18,\mathrm{T}=19,\mathrm{U}=20,\mathrm{V}=21,\mathrm{W}=22,\mathrm{X}=23,\mathrm{Y}=24,\mathrm{Z}=25. \end{gathered}$$

SI LV ER

Rewriting the blocks such that English words form:

SILVER.