What you need to know
3.5.1 Asymmetric keys and encryption methods
- show understanding of the terms: public key, private key, plain text, cipher text, encryption and asymmetric key cryptography
- show understanding of how the keys can be used to send a private message from the public to an individual/organisation
- show understanding of how the keys can be used to send a verified message to the public
Encryption Basics
When you encrypt something, the sender takes some legible data (plain text) and turns it into something illegible (cipher text) using a key. This key is then used by the person who receives it to turn the illegible data back into legible information.
The simplest encryption that is usually used when starting to learn encryption techniques is the Cesar Cipher. You can watch this video to see how this works.
The simplest encryption that is usually used when starting to learn encryption techniques is the Cesar Cipher. You can watch this video to see how this works.
|
This method was fine back in Caesar's day, but is not sufficient for modern day encryption. Having a single private key is too risky - if anyone else obtains the key they would be able to intercept and decrypt your data. This isn't including the fact that a Caesar Cipher is also easy to break using the most simple of cracking techniques - brute force (basically trying every possibility - there are only 26 in this method).
|
Symmetric Encryption
The Caesar Cipher is a very basic example of a symmetric encryption system. Some computer systems also use this technique - using a number of word to encrypt the data. This is the key to decrypt it too and is typically 128-bit or 256-bit which gives billions of possibilities. This means that breaking it via brute force would be very tricky (but not necessarily impossible by a computer). The biggest problem is the key has to be held by the receiver and transferring a secret key from the sender to the receiver is always taking a huge risk that it could be intercepted. Once someone has the key all further messages are compromised.
Activities
1. Research the Vigenere cipher - an example of a stronger symmetric encryption
2. Try and pass a secret message to someone else in the classroom using this technique
2. Try and pass a secret message to someone else in the classroom using this technique
Asymmetric Encryption
Asymmetric encryption is a much stronger form of encryption. In this method when an encryption is created, two keys are produced. One is a private key that the creator holds on to and the other is a public key that is released into the public domain. SSL certificates are an example of asymmetric encryption (what is an SSL certificate?).
Each key can only open messages that have been encrypted by the other. So the private key can open public key encrypted messages and the public key can open messages encrypted with the private key. This is beneficial in a number of ways:
Each key can only open messages that have been encrypted by the other. So the private key can open public key encrypted messages and the public key can open messages encrypted with the private key. This is beneficial in a number of ways:
- If you wish to send encrypted data to someone, you can use their public key to encrypt it and send it to them knowing that only the person with the private key can open it.
- The person with the private key can send a message, and whilst anyone with the public key can open it, it confirms the message has come from the correct location.
- A very secure way of sending a message is to encrypt it first with your private key and then with the other person's public key. This means that someone with just your public key can now not open it. Only the intended recipient can open it - first using their private key and then your public key to read the information.
Activities
Discrete Logarithms
Note: Activity taken from this website
Public key cryptography depends on the existence of a type of mathematical functions called trapdoor functions. Trapdoor functions have the property that they are very computationally easy to compute but are very difficult to invert. To invert a function means to figure out what you need to input into a function in order to get a desired output.
The following is a simple example of a function which is easy to compute, but more difficult to invert. Let's pick some prime number p = 19. The particular number doesn't matter so long as it's prime. The larger the prime number, the harder this function will be to invert. We will define our function as f(n) = 3n (mod) p . The (mod) p in this equations means the same thing as dividing by p and then taking only the remainder as your answer.
Trying to invert this function is known as the discrete-log problem, and no known efficient algorithm is known to solve this. If someone ever figures out a way to quickly compute discrete logs, public key cryptography depending on this trapdoor function will become insecure. However, it is thought by informed researchers to be an intractable problem, and it is unlikely that anyone will make such a mathematical break-through in the foreseeable future.
Public key cryptography depends on the existence of a type of mathematical functions called trapdoor functions. Trapdoor functions have the property that they are very computationally easy to compute but are very difficult to invert. To invert a function means to figure out what you need to input into a function in order to get a desired output.
The following is a simple example of a function which is easy to compute, but more difficult to invert. Let's pick some prime number p = 19. The particular number doesn't matter so long as it's prime. The larger the prime number, the harder this function will be to invert. We will define our function as f(n) = 3n (mod) p . The (mod) p in this equations means the same thing as dividing by p and then taking only the remainder as your answer.
- Find f(5).
- Is there an n so that f(n) = 17?
Trying to invert this function is known as the discrete-log problem, and no known efficient algorithm is known to solve this. If someone ever figures out a way to quickly compute discrete logs, public key cryptography depending on this trapdoor function will become insecure. However, it is thought by informed researchers to be an intractable problem, and it is unlikely that anyone will make such a mathematical break-through in the foreseeable future.
Exercise Exploring RSA
Note: Activity taken from this website
- Go to Herbert Hanewinkel's RSA page. (If that's down or missing, you can use this local copy.
- From the pulldown menu, choose a number of bits. This is the number of bits that n will be (approximately), and, because factoring n is the hard part, the bigger n, the stronger the encryption scheme.
- (FYI, 2048 bits is considered barely acceptable for commercial websites, but takes 90+ seconds to compute on my office desktop computer, whereas 1024 bits takes just 5 seconds.)
- click on generate key
- Notice how big the Public Modulo (p*q) is. This is the value of n. Imagine trying to factor that to get p and q!
- Skip down to below the solid line to the pair of boxes labeled plaintext and ciphertext in hex. (Notice how you now understand what hex means: since the encryption is going to be a long string of bits, hex is incredibly useful here..)
- Type in a message (plaintext) and encrypt it. Erase the plaintext and decrypt it.
Exercise Using the RSA Cipher
Let's make this a bit more realistic. Choose a partner (better if you can't easily look onto their monitor, though it doesn't really matter). One of you will be the sender and the other the receiver.
- The receiver uses this customized receiver version of Herbert Hanewinkel's form to create a key pair.q
- She transmits the public key to the sender. Specifically, she sends the last field of the form above the horizontal line, the input labeled OpenPGP Multi Precision Integer (MPI) of Public Key (base64). (This is an encoding of both e and n, in one relatively compact representation.)
- (For a less-realistic but faster short-cut, just use two different browsers on the same machine, say Chrome and Firefox. One is the sender and one is the receiver. You can then just copy/paste between browsers instead of using email.)
- The sender copies the packed public key into this customized public version of the RSA encryption form. She clicks on the button to unpack e and n from the public key.
- The sender encrypts her message. The message can be anything. It doesn't even have to be private. If you're feeling stumped, send the identity of the important character who dies in Harry Potter and the Half-Blood Prince and who kills him. This is an important secret; don't assume everyone has read the book.
- The sender then copy/pastes the ciphertext into an email message and emails it to the receiver.
- The receiver copy/pastes the ciphertext into the same RSA form, above (the one that knows the decryption key) and decrypts the message.
- Verify that the message was transmitted correctly and secretly.