Algebra / Cryptography?

Question

An RSA cipher is set up with the public keys n = 12091 (the modulus) and r = 3 (the exponent). The plaintext is m = 2107. Encrypt m.
Find the decryption key for the above cipher.
Plase show working as I am very confused. Thanks!!

Answer 1

In order to encrypt m using the RSA cypher, you simply raise it to the power r mod 12091. So the corresponding cyphertext would be 2107^3 mod 12091 = 7077.

In order to find the decryption key, it is necessary to find the totient of the modulus. In order to do this, we must factor it -- which is easy in this case, since the numbers are small. The factors are 107 and 113. Therefore φ(12091) = (107-1)(113-1) = 11872. To find the decryption key, we must compute the multiplicative inverse of r mod φ(n). We know that φ(12091) mod 3 = 1, so we have that:

11872 - 3*floor (11872/3)=1

So -floor (11872/3) is a multiplicative inverse of 3 mod 11872. But this is -3957, or finding the least residue mod 11872, d=7915. The decryption key is therefore (12091, 7915). And indeed, we have that 7077^7915 mod 12091 = 2107, giving us the original plaintext.