Public Key Cryptography

Any discussion of cryptography needs to make mention of the number of people that need to work together and build upon each other's work in order to both create and break ciphers; and one process is constantly driving the other. One person needs to make a message secret, and so they create a way to encrypt it. Then another person wants to read it so they find a way to break it. So then a new method needs to be created to encrypt messages again, and a new method to break it, and so on, and so on… And methods are always building upon themselves, in fact you can see how the simple Caesar cipher can be found in every other process discussed here, including the ‘uncrackable’ Enigma.

We also need various methods of cryptography for different purposes. For example, while highly secure, one-time pads were awkward to use and not practical for day to day use and are now only used in a few situations. Enigma was highly secure but required large, bulky machines and operators, making them impractical in many situations. Yet, Caesar and Vigenère ciphers could be done with a piece of paper and knowledge of the shift or keyword, but could be easily broken. Different methods of cryptography therefore are used for different purposes and where they make the most sense.

Also, because of the inherent secrecy of cryptography, many methods of decryption, including the people who work on it, remain hidden and secret for many years after their work is done. For example, those who worked at Bletchley Park, including Alan Turing, returned home to be seen by friends and family as not contributing to the war efforts; and they were forbidden to speak of their work. Even the accomplishments of Flowers and his Colossus machine weren’t revealed to the public until decades later. In the case of Turing, he passed away before ever receiving recognition for his contributions.

It is believed that, even today, there are many government and private efforts to both protect and decrypt our data. But the people working on these efforts remain hidden and secret; just like the codes they are attempting to make and break!

RSA

You want to send a message to your friend, but your friend lives on the other side of the world. There are many ways you can send this message including: sending a letter through the mail, phoning them, or sending them an electronic message (like an email, text message, or message through social media or an app). If you want the message to not be read by others then you need to find some way to encrypt it. As we have seen in previous chapters cryptography requires two parts: an algorithm (a way to encrypt the information) and a key (a specific piece of information required to ‘crack the code’). In earlier times the key would often be written down and distributed to those exchanging messages. This could be done through code books, or by simply telling the other person the key directly. Cryptographers who intercepted these encrypted messages would look for ways to break them or, if they were lucky enough, would find these codebooks or intercept the keys in some way (a spy or someone who wasn’t careful keeping the key a secret - like writing it down) and then they would have access to all the hidden messages.

While the modern internet, and modern computers, have made communication across the world much faster and easier it has also presented new ways for information to be intercepted. Let’s say the message you want to send to your friend is supposed to be secret, but it gets intercepted along the way. If you were to use one of the methods of cryptography described earlier a modern computer could easily crack it by using the tricks and methods developed by people like Babbage, Rejewski and Turing; things like frequency analysis and investigating patterns within the encrypted code. It could also use a brute force attack with thousands of possibilities a second; much faster than cracking it by hand.

So you need to share a key first, but how can you do this safely? Let’s say you’re sending an email to your friend, how could you send the key?

Interactive Element: a drop down list of different options they could pick to send the key separate from the message and each selection would have a pop-up of the difficulties that method presents:

Method Issue Send another email If the email address has already been ‘hacked’ then the interceptor will have both key and message. Phone them They have to remember the key exactly; you might be more tempted to pick a really simple/easy to remember key for them; the phone could also be hacked; they could choose to write the key down on a piece of paper that could be found or on a file on their computer that could be seen if the computer and not the email was hacked Tell it to them in person Requires you both to be in the same place; hey have to remember the key exactly; you might be more tempted to pick a really simple/easy to remember key for them; they could choose to write the key down on a piece of paper that could be found or lost, or they could write it as a file on their computer that could be seen if the computer and not the email was hacked Send it to them over another form of communication (text message, social media, an app) Message could be intercepted by the phone company or by the company that owns the social media or app; if their computer is compromised the hacker might be able to see the key regardless of the way it is sent.

As you can see there are many ways that the key could be intercepted. So why not create a method to send a key publicly where it doesn’t matter if someone else gets it? That’s what RSA is.

From: https://en.wikipedia.org/wiki/RSA_Security

RSA is named after the co-founders of RSA Security: Ron Rivest, Adi Shamir and Leonard Adelman, and they named the encryption method the same. It uses a series of public (Definition: not secret, can be intercepted, and read by a third party freely) and private (Definition: only known by the recipient and kept secure on their system) keys, along with modular arithmetic, to encrypt messages being sent electronically and ensure that, even if they are intercepted, they can’t be cracked.

Prime Numbers

To explain how RSA encryption works we have to start with prime numbers (link to Prime Numbers module in Mathigon) and factors.

What are all the factors of 150? Input 1, 150, 2, 75, 3, 50, 5, 30, 6, 25, 15, 10

Now how about 151? Input 1, 151

151 is a prime number so there are only two factors. If you knew that 151 was a prime, getting the factors would be quite easy, but it becomes more work if you don’t know it’s a prime, as you have to test all the numbers in between 1 and 151 to see if 151 is evenly divisible by any of them.

Now there are some tricks that can simplify this such as any even number is divisible by 2, a number ending in 5 or 0 is divisible by 5, but for larger numbers it can be quite tricky. Imagine finding all the factors of 125728394792, it would take a while, even with the help of a computer.

Let’s go the other way now. What is 547 x 251? Input 137,297

Pretty easy to figure out (especially if you have a calculator or computer on hand). But what if I asked you what two numbers multiply together to get 262,319?

Interactive Element: an input box with an “HELP” button that gives the answer 947 and 277

947 and 277 are both prime numbers and so, when multiplied together, gives an answer that only has 4 possible factors, 1, 262319, 947 and 277. Now with the help of a computer you could determine this answer pretty quickly, it would be very difficult to figure it out by hand (but it could be done, especially if you knew it was the product of two prime numbers).

However, what if the prime number was longer, MUCH longer. In fact, in 2048-bit RSA encryption the number is 617 digits long. A number this long, with only 4 factors, would take a classic, modern computer about 300 trillion years to crack. So this is what RSA makes use of.

So how does knowing the factors of a number help secure information? It has to do with private and public keys. A public key is something that can be shared freely between people and it doesn’t matter if someone else intercepts it. Without the private key, which is stored only by the sender or the recipient (not both - they each have their own) then intercepting the message and the public key is not enough to decrypt the message. But when you pair the public and private key together, the message unlocks and can be read only by the intended recipients.

Generating the Keys

In order to generate our keys we need to pick two prime numbers that are big enough and far enough apart that they will work. The smaller the numbers and the closer together they are the Input (selection box “easier” or “harder” choices, correct answer is “easier”) they are to guess.

Interactive Element: this will be a multi-step process (it could be set up as a step by step slideshow with text and inputs) Step 1: Text: “first we choose two prime numbers Pop-up/side note: the actual numbers chosen for RSA are normally very large and a primality test (like the Rabin-Miller Primality Test) is used to ensure that they are actually prime numbers.” students will then choose two prime numbers (there needs to be instructions and a check that the primes are at least over 100 and they have to be primes). The two primes should be labelled “p” and “q” Step 2: Text: “next multiply your two primes together” students will then multiple the two numbers together to give “n” Step 3: Text: “now we need to find a number that will form an upper limit for our next step. This is done using Carmichael’s totient function: \lambda(n) = lcm(p-1, q-1), where lcm is the least or lowest common multiple (you can learn more about lcm here). However, because lcm requires finding prime factors and we are dealing with large numbers here’s a calculator to help you” Students will input their p-1 and q-1 numbers and then we will provide a calculator to determine the lcm for those numbers and show them their \lambda value (like this: https://www.calculatorsoup.com/calculators/math/lcm.php) Step 4: Text: “we now use this \lambda(n) value to find a value we can use to make up our public key called e” students will then be asked to pick a prime number (e) between 1 and \lambda(n). This could be an auto-generated list of prime numbers between 1 and their \lambda(n) and they click on what number they want to use. Step 5: Text: “we now have p, q, n, and e to work with, where our public key is a combination of e and n” These numbers should all be filled in, perhaps a labelled box with their various values. Step 6: Text: “so now it’s time to encrypt. Let’s start with a very simple message, a number (we’ll talk about text later), and call it m.” students pick a number between 1 and 9 (inclusive) and it gets labelled as m. Step 7: Text: “now we are going to use this equation to encrypt our message c = m^e mod n. Pop-up: this pop-up links to the below section on modular arithmetic” students will fill in the equation with the various parts to solve for c, this should be a calculator that shows the various steps (the m^e calculation and then finding out the mod n part). Step 8: Text: “so we now have our plaintext (the student’s m value) as a ciphertext (the student’s c value) that gets sent to the receiver.”

Pop-up on Modular Arithmetic (see above): In order to understand this method of encryption we have to understand the concept of modular arithmetic. In its most basic form modular arithmetic is like reading a clock where the ‘n’ in mod n determines how many ‘hours’ there are. Every time the clock reaches back to where it starts we restart our numbering (like when we go from 12:59 to 1:00 on a regular clock, we don’t go to 13 because there are only 12 numbers on the face).

Each time we go around the clock we return to our starting number. So if we were going on a trip and we left at midnight and it was going to take 18 hours to get to our destination, what time would it be when we get there? Input: 6:00 (this should be a drop down with options to avoid am, pm, or 24 hour time).

So you see, we went around the clock 18 ‘hours’ but ended up at the number 6. This is the basis of modular arithmetic. It’s how many times the number we are looking for goes into the mod evenly, and the remainder becomes the value we are looking for.

Let’s try an example: say we are looking at the number 13 in mod 5. Important note: unlike the clock above, we always start modular calculations with a 0 so the numbers go from 0 to n-1 (more on this in a minute). So to find 13 mod 5 we can simply count, starting at 0, 13 places, and then record where we end up Input 3.

So how do we do this for bigger numbers (because who wants to count something like 447 mod 5) and why do we start at 0? This is because modular arithmetic is based on integer division and remainders. So to calculate 447 mod 5 we divide 447 by 5 and then we look at the remainder Input 2. The reason we start at 0: because a number like 550 mod 5 would have a remainder of Input 0 not of 5.

How to calculate mods: the best way to do this is to practice long division and find the integer remainder of the number.

Interactive Element: have students calculate 134 mod 8. This should be set up as a long division question where they have to put an input at each step and they find the remainder to be 6. It should look something like this (where the blue boxes are input boxes and the text in them is the correct solution):

So 134 mod 8 = Input 6

For very large numbers however, we often use a mod calculator.

So now we have an encrypted message that we can send to a receiver. But we need to make sure they can read it. This is where the private key comes in.

A private key must work with the public key so we use the same e and n values. Neither the e or n value is particularly useful on its own, and remember, the n value is actually the product of two prime numbers, which we saw before were very difficult (if not impossible) to guess for large, far apart numbers.

So we send e and n out in the open and they are received by our intended recipient, and if someone else gets them in the middle it’s not going to be of much use.

To create the private key (called d) we use this formula:

d = 1/e mod \lambda(n)

Now it’s important to note that 1/e is not 1 divided by e but is instead the modular inverse of e. To solve for this we are going to use a calculator as finding this by hand involves the Extended Euclidean Algorithm, which is beyond the scope of this lesson but more can be found here https://www.extendedeuclideanalgorithm.com/index.php

So let’s take our e value Interactive Element: the e value from before and an inverse modular calculator like the one here (https://planetcalc.com/3311/) to give an answer.

We then use that information and the value of n Interactive Element: the value of n from above

To calculate d Interactive Element: the value of d

Voila! Our private key (d).

Now we can use our value of (d), the product of two primes (n), and our public key (c), to decrypt the message (m) as:

m = c^d mod n

Interactive Element: students will input their various values and the value of m will be calculated. It should be the same m value as what they chose in the previous step.

In our example we encrypted a number, but what about text or other information?

Well computers actually already convert input information into numbers and then into binary; and this is the information that gets encrypted and sent.

From: https://stillthere.co/encryption

Interactive Element: using a chart like this: https://www.asciitable.com students would either type in a word and an animation would show it being converted to ASCII or they would type in a word and then click on elements in the table to convert their message to ASCII. They would then see their word appear as a series of numbers.

As you can see your word (their word from above) has been re-written as (the ASCII text from above) and we know how to encrypt a series of numbers using RSA. The computer can then transform this into binary (Link to Mathigon section on Binary) and send the message through the internet; safe in the knowledge it is secure and unreadable by anyone without a corresponding key.

From: (not sure where this image is from but it’s just to show an interceptor of the messages)

The public and private key exchange used in RSA allows for users to keep parts of the key hidden and away from potential interceptors but to share a public aspect that is useless without the other part. This is what makes it possible to send encrypted, secret, message through insecure means without a worry that someone will be able to decrypt it.

By using the power of prime numbers, and the near un-guessability of the factors of a product of two large primes, we are able to keep messages safe as they travel through the internet.

Cracking RSA (P vs NP and Quantum Computers)

Whenever anyone comes up with a new way to secure and encrypt data following right behind them are the codebreakers, and RSA is no different. Currently there are two considerations for the long term usability of RSA encryption.

The first is linked to something called the P vs NP problem, which is one of the 7 Millenium Prize Problems (valued at $1 million to whoever can solve it) Link: http://www.claymath.org/millennium-problems. The question essentially sets P as ‘easy to find’ and NP as ‘easy to check’. It then seeks to ask if we can easily/quickly check a solution then can it also be solved quickly. In RSA, we can quickly check if a given solution is correct (we just see if the value for m we get out is correct), so if we are able to quickly solve it as well, then it would be easily cracked by modern computers.

The second deals with the development of newer and faster computers. As mentioned previously, a ‘classic’ modern computer would take about 300 trillion years to crack a 2048 bit RSA encryption; but, it did crack a 768 bit RSA in about 2 years. Still a long time, but it does mean it’s doable.

From: https://www.technologyreview.com/s/612844/what-is-quantum-computing/

Enter the quantum computer. A quantum computer works on the principles of superposition (Definition: we can add quantum states together and get a new quantum state) and entanglement (Definition: that two particles or groups are connected to each other in a way that you can’t change one without affecting the other). Quantum mechanics, and quantum computing, is a whole new way of looking at how we process information. In terms of RSA, unlike a modern ‘classic’ computer that would test every prime number until it found one that was a factor of n, a quantum computer could test all the primes nearly simultaneously and determine n in a matter of seconds (not years).

But, while many people are currently working on problems like P vs NP and quantum computers we are still a long way off. The most modern version of a quantum we have currently can only handle a 2-digit factor (remember, RSA 2048 uses 617 digits) so the solution is still a long way off. But, like any form of encryption, people will keep trying to break it. Luckily we can also use these new technologies to create newer, and more secure, methods of keeping our data safe as well!