A worked example

Now we have seen an outline of the mathematics behind RSA, let’s do a worked example.

Using the previous example, let’s say Alice’s public keys are (N=187) and (e=27).

Let’s say Bob wished to send Alice the message (m=10). He uses Alice’s public keys to calculate

[begin{split} C &= m^e text{ (mod }Ntext{)} \ &= 10^{27} text{ (mod }187text{)} \ &equiv 54 text{ (mod }187text{)}. end{split}]

Alice receives (C=54) and so she calculates, using her secret exponent (d=83) that we calculated in the last step,

[begin{split} C^d text{ (mod }Ntext{)} &= 54^{83} text{ (mod }187text{)} \ &equiv 10 text{ (mod }187text{)} end{split}]

which is – as expected – the message that Bob had sent.

Remark: In practice, no one would ever calculate (m^e) or (C^d) directly, as finding powers produces very big numbers, very quickly. There are much more efficient ways of exponentiation in modular arithmetic.

This clearly shows the trapdoor: if you know the secret primes, it’s very easy to find Euler’s totient function, and hence you can find (d). However, it is believed that knowing only (N) it is very hard to find the prime factors in general.

Your turn!

Try the following exercises, to check your understanding; use the comments to ask any questions you may have, but be careful not to give away the answers!

Some of these numbers can get very large, so you may wish to use a computer (rather than a pocket calculator) to help. Wolfram Alpha is an online advanced computer algebra system able to do these calculations with ease. For example, if you wished to calculate (54^{83} text{ (mod }187text{)}), type PowerMod[54,83,187]. A useful hint: if you wish to calculate the decryption key then typing PowerMod[(e),-1,(phi)] (with the appropriate choices for (e) and (phi)) will yield (d). One can check that PowerMod[27,-1,160]=83, as we saw in the previous step.

Let’s now say Alice’s public RSA keys are (N=551) and (e=17).

You wish to send the message (m=123) to Alice. What would your encrypted ciphertext message be?

Alice knows that (N = 19 times 29). What is her decryption exponent (d)?

Verify that she can correctly decrypt your ciphertext to obtain the plaintext message.