Skip main navigation

Hurry, only 9 days left to get one year of Unlimited learning for £249.99 £174.99. New subscribers only. T&Cs apply

Find out more

A worked example

A worked example of the RSA algorithm, to help ensure that you completely understand what's going on.
A hand about to write in an exercise book. A computer tablet is also on the table.
© University of York

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.

© University of York
This article is from the free online

The Mathematics of Cryptography: From Ancient Rome to a Quantum Future

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now