RSA Public Key Encryption – The Code that Secures the internet

Cracking RSA Code – The World’s Most Important Code? 

RSA code is the basis of all important data transfer.  Encrypted data that needs to be sent between two parties, such as banking data or secure communications relies on the techniques of RSA code.  RSA code was invented in 1978 by three mathematicians (Rivest, Shamir and Adleman).  Cryptography relies on numerous mathematical techniques from Number Theory – which until the 1950s was thought to be a largely theoretical pursuit with few practical applications.  Today RSA code is absolutely essential to keeping digital communications safe.

To encode a message using the RSA code follow the steps below:

1) Choose 2 prime numbers p and q (let’s say p=7 and q=5)

2) Multiply these 2 numbers together (5×7 = 35).  This is the public key (m) – which you can let everyone know. So m = 35.

3) Now we need to use an encryption key (e).   Let’s say that e = 5.  e is also made public. (There are restrictions as to what values e can take – e must actually be relatively prime to (p-1)(q-1) )

4) Now we are ready to encode something.  First we can assign 00 = A, 01 = B, 02 = C, 03 = D, 04 = E etc. all the way to 25 = Z.  So the word CODE is converted into: 02, 14, 03, 04.

5) We now use the formula: C = y^e (mod m) where y is the letter we want to encode.  So for the letters CODE we get: C = 02⁵ = 32 (mod 35). C = 14⁵ = 537824 which is equivalent to 14 (mod 35). C = 03⁵ = 33 (mod 35).  C = 04⁵ = 1024 which is equivalent to 09 (mod 35).  (Mod 35 simply mean we look at the remainder when we divide by 35).  Make use of an online modulus calculator!   So our coded word becomes: 32 14 33 09.

This form of public key encryption forms the backbone of the internet and the digital transfer of information.  It is so powerful because it is very quick and easy for computers to decode if they know the original prime numbers used, and exceptionally difficult to crack if you try and guess the prime numbers.  Because of the value of using very large primes there is a big financial reward on offer for finding them.  The world’s current largest prime number is over 17 million digits long and was found in February 2013.   Anyone who can find a prime 100 million digits long will win $100,000.

To decode the message 11 49 41 we need to do the following:

1) In RSA encryption we are given both m and e. These are public keys.  For example we are given that m = 55 and e = 27.  We need to find the two prime numbers that multiply to give 55.  These are p = 5 and q = 11.

2) Calculate (p-1)(q-1).  In this case this is (5-1)(11-1) = 40.  Call this number theta.

3) Calculate a value d such that de = 1 (mod theta).  We already know that e is 27.  Therefore we want 27d = 1 (mod 40).  When d = 3 we have 27×3 = 81 which is 1 (mod 40).  So d = 3.

4) Now we can decipher using the formula: y = C^d (mod m), where C is the codeword.  So for the cipher text 11 49 41:  y = 11³ = 11 (mod 55).  y = 49³ = 04 (mod 55). y = 41³ = 6 (mod 55).

5) We then convert these numbers back to letters using A = 00, B = 01 etc.  This gives the decoded word as: LEG.

If you enjoyed this post you might also like:

How Are Prime Numbers Distributed? Twin Primes Conjecture. Discussion on studying prime numbers.

Cracking ISBN and Credit Card Codes. The mathematics behind ISBN codes and credit card codes

Essential resources for IB students:

1) Exploration Guides and Paper 3 Resources

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations.  The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.