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.
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.
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 Nr (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 (Nr)s (modn). In this case, she gets 33345 (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!
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 Mr (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.
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.