Introduction to Cryptography with Coding Theory, 3rd Edition

9.8 Exercises

1. The ciphertext 5859 was obtained from the RSA algorithm using $n=11413$ and $e=7467$. Using the factorization $11413=101\cdot 113$, find the plaintext.

2. Bob sets up a budget RSA cryptosystem. He chooses $p=23$ and $q=19$ and computes $n=437=pq$. He chooses the encryption exponent to be $e=397$. Alice sends Bob the ciphertext $c=123$. What is the plaintext? (You know $p$, $q$, and $e$).

3. Suppose your RSA modulus is $n=55=5\times 11$ and your encryption exponent is $e=3$.

   1. Find the decryption exponent $d$.

   2. Assume that $gcd(m\text{,}55)=1$. Show that if $c\equiv m^3(\text{mod}55)$ is the ciphertext, then the plaintext is $m\equiv c^d(\text{mod}55)$. Do not quote the fact that RSA decryption works. That is what you are showing in this specific case.

4. Bob’s RSA modulus is $979=11\times 89$ and his encryption ...