RSA Public-Key Encryption: Upper Secondary Mathematics

The idea behind every encryption system is to make communication between two parties secure and secret. The systems we have looked at this week involve a method, or algorithm, and a key; sometimes the encryption and decryption keys are the same, sometimes different. The task of anybody trying to intercept the communication is to try to discover both the algorithm and the encryption/decryption keys.

In 1977 a counter-intuitive discovery was published: that it was possible to devise a system where the encryption key was made public with only the decryption key kept private. This became known as RSA Public-Key Encryption and is still in use today.

Rather than thinking about it in terms of keys, imagine we have a lock-and-key system. Zeta receives all her communication via a courier system that places every message inside a box, locks it and then sends it to her. Zeta has created many copies of her private lock and distributes them throughout the world. Anybody who wishes to communicate with her places their message in a courier box, finds one of Zeta’s special locks and then closes the box securely using that lock. Anybody can do this, but only Zeta holds the key that unlocks the box! The encryption locks are public but the decryption key is private.

The mathematics behind this system involves knowledge of prime numbers and modular arithmetic. Let me go through one example, then you can try a similar question.



Example

Zeta wishes to set up a public key so that friends may communicate with her securely. (Note that for Zeta to reply securely, her friends also need to establish a public key that she can use in her reply.) Let’s go through Zeta’s process step by step. We shall use rather small prime numbers to make the calculations easier to do by hand. In reality, computers use very large prime numbers and cryptography is one reason why the search for massive primes is an active area of research.

1) Zeta picks two (large) prime numbers p and q and calculates their product n = pq. In this case, let p=17 and q=29, hence n=493.

2) Then she calculates m = lcm(p-1, q-1), the lowest common multiple of one subtracted from each of the two primes. In this case, m = lcm(16, 28) = 112.

3) She then picks a number r such that it is relatively prime to m. Let’s keep things simple and pick r=5.

4) Now she calculates the value of s such that rs = 1 (modm). In this case, we have 5s = 1 (mod112). This is equivalent to 5s = 112k + 1, with s and k as positive integers. This gives us s=45 as the smallest value.

5) Zeta then publishes the values of n and r as her public key, but keeps p, q and s private.

6) Now, Adam wishes to send a message M to Zeta. Again, let’s keep this simple; he sends her a single letter that has been encoded into its decimal place N in the alphabet. Adam firstly checks that his N is coprime with n – notice that because of our small primes Adam’s message cannot be “Q”. (What would happen if he tried to encrypt the message “Q”?) He also needs to check that 0 < N < n. Then he calculates N^r (modn). He gets the answer 333 and sends this encrypted message to Zeta.

7) Now Zeta needs to decrypt the message. She does so by calculating (N^r)^s (modn). In this case, she gets 333⁴⁵ (mod493). What is the value of this, and hence what is the letter that Adam sent to Zeta?

Although we have used very small prime numbers and so finding the original p and q is very easy, even by hand, this last step shows how big the numbers can get. A standard calculator will probably overload and, although most computers can just about handle this, some programs cannot – worse, some programs will give the wrong answer rather than an error message. Now, imagine if the primes p and q had hundreds of digits!


Question

Adam wishes to send Zeta a message with no more than three letters. Adam encodes the message into decimal digits, for example, CAT becomes 030120 (or just 30120 removing the leading 0). Zeta has published her public key as n=479719 and r=2111. Adam encrypts his message M using M^r (modn) and obtains the result 408174.

You have intercepted Adam’s message and you know Zeta’s public key. Find the original message M.

You may wish to consult a list of prime numbers to help you. Although this may sound slightly masochistic, try to do as much of the question by hand, without a computer – it will give you a better sense of how much work is needed, even with primes that are very small for the computer to handle. If you are feeling exasperated, Wolfram Alpha is your friend.

Notice also that if n were really huge then you could be spending years factoring it! Here is a small value, n=3640043777446155573176670087704698887395105733551. Find the primes p and q.

Feel free to comment, ask questions and even check your answer in the comments box below powered by Disqus Google+.

If you enjoy using this website then please consider making a donation - every little helps :-)

You can receive these questions directly to your email box or read them in an RSS reader. Subscribe using the links on the right.

Don’t forget to follow Gifted Mathematics on Google+, Facebook or Twitter. You may add your own interesting questions on our Google+ Community and Facebook..

You can also subscribe to our Bookmarks on StumbleUpon and Pinterest. Many resources never make it onto the pages of Gifted Mathematics but are stored in these bookmarking websites to share with you.