0
$\begingroup$

I am stuck on a problem using RSA encryption. We are encoding the message WELCOME.

$W= 23$ $E= 5$ $L= 12$ $C= 3$ $O= 15$ $M= 13$ $E= 5$

$n =77$ $\text{and}$ $e =31$

I've come up with a couple that are the same values as they were before encoding. Here's an example of $W$ and my approach to each letter.

$23^1\pmod{77}=23$

$23^2\pmod{77}=67$

$23^4\pmod{77}=23$

$23^8\pmod{77}=67$

$23^{16}\pmod{77}=23$

After which I multiply the values: $23*67*23*67*23=54617663$

$54617663/77 = 709320.2987$

$54617663-(77*709320)=23$

Is $23$ the correct encoded value? I've done a few others and had $L$ and $C$ end up with the same values as well. What am I doing wrong?

$\endgroup$
2
$\begingroup$

You are nont soing anything wring in the calculation. It is just that the modulus and exponent are suboptimal for cryptographic purposes. While it is clear that $n=7\cdot 11$ must be composed of very small primes if one wants such an exercise to be feesible for manual calculation. But as direct consequence we'd have an immediate problem with the relatively many message numbers that fail to be coprime to the modulus, such as $G=7$, or $K=11$, or $N=14$ - which just happen not to be among the input. But apart from this, also the exponent $e=31$ is not good. Note that for primes $p$ we have $x^p\equiv x\pmod p$ ("little Fermat"), and likewise $x^{k\cdot (p-1)+1}\equiv x\pmod p$, specifically $x^{5\cdot 6+1}\equiv x\pmod 7$ and $x^{3\cdot10+1}\equiv x\pmod{11}$. By the Chinese Remainde Theorem we conclude $x^{31}\equiv x\pmod {77}$, so your encryption is just a fancy way of sending cleartext.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.