Public Key Encryption
Modern cryptographic techniques move well beyond the simple modular arithmetic ciphers of the Ancient Greeks and Romans. Although their functionality and security are more robust, basic mathematical ideas still underpin their algorithms.
Aside from Gandalf in the Lord of the Rings, people do not use passwords to open doors.
Instead, we Muggles use keys. Encryption algorithms use keys as well — mathematical keys. In Unit 1: Encryption, you discovered the use of the Cæsar cipher. In this type of encryption, the number of times the characters are shifted could be considered the key. In that case, there were only 26 possible keys, and so if someone knew the algorithm, they could break the code quickly and easily. The security was in hiding how the encryption was performed.
Modern systems do not rely on this assumption. A quick search of the Web reveals many different algorithms for encryption. In fact, many businesses actually advertise which algorithm they use to indicate the strength of their security protocols. Instead of the classical system's reliance on ignorance of the encoding process, modern encryption schemes rely on the complexity of the keys used to secure information.
Early key systems relied on the fact that the both the sender and the recipient had the same key. One could use the key to encrypt the message, and the other could use it “in reverse” to decrypt it. These symmetric key systems have a major flaw — How are the keys themselves securely exchanged? Are there ways that the sender and the recipient can have separate keys (only known to themselves), and exchange information securely?
Notice that each of these encryption methods relies on restricted knowledge.
With the Caesar cipher, anyone who knows the algorithm and the offset can decrypt the message. However, we have seen that even if you know just the algorithm, it is not hard to decrypt without also knowing the offset—there are only 25 possibilities. With the Vigenère cipher, anyone who knows the algorithm and the key can decrypt the message. It is much more difficult to decrypt the message without the key than before because patterns in the text are less obvious, and there are many more possibilities than 25.
However, what if someone obtains the key?
Let’s consider some possible scenarios:
Alice sends Bob a locked box with her message inside. Although it gets passed through many hands before reaching Bob (e.g., the courier system), it is locked and so Bob receives it securely. However, to unlock it, he needs the key. How does Alice send Bob the key in a secure way?
Alice sends Bob a locked box with her message inside. When it reaches Bob, he put his own lock on it and sends it back. Then Alice removes her lock, and sends the box back to Bob. When Bob receives the box, it is locked only with the lock that he put on it. He unlocks it and retrieves Alice’s message—or does he?
Bob has invented a special lock. It is special because it costs nothing to duplicate and send, and it is virtually impossible to analyze the lock and create a key. The key and the original lock must be created at the same time. He sends out his locks to anyone who wants to send him a message. Alice locks her box with one of Bob’s special locks and sends it to him. When he receives it, he unlocks it with his special unique key and reads the message.
The third scenario is actually how modern secure message passing happens. This is called Secure Sockets Layer (SSL) and is typically indicated by a padlock icon in the browser’s address bar. SSL is considered an asymmetric key system. Certificate authorities (CAs) issue digital certificates that validate the ownership of encrypted keys used in secured communications and are based on a trust model.
Imagine a system in which the sender could send anybody (or everybody) copies of a lock he had the only key to open. Beyond that, there is no way that someone could practically figure out how to reproduce the key to match the lock no matter how they examined the lock itself.
How Can We Make Such a Lock?
The trick to accomplishing this feat lies in the fact that some things are much more difficult to do in reverse. For example, driving in reverse for long distances is untenable because cars were designed to better accommodate forward motion. The steering mechanism is located in the front (near the driver) to facilitate ease and reliability of control.
Crypto-keys can be designed in much the same way mathematically by the use of a one-way function. A one-way function is a mathematical function that is relatively easy to apply, but difficult to invert (i.e., undo). Common public key cryptosystems rely on the fact that multiplying two numbers together is easy to do, but once the product is obtained, it is difficult to retrieve the original factors by applying the inverse operation, division.
A simplified description of the algorithm is as follows:
|Begin with two large prime numbers p and q. Note: These two numbers are prime, so they do not have any factors other than themselves and 1. Consider why this may be important.||
Prime p: 9689
Prime q: 9697
|Multiply them together to determine their product, n.||
n = p × q
n = 9689 × 9697
n = 93954233
|n is the key that “locks” the message (public key). Anyone can have the public key and encrypt messages with it, but they will not be able to decode messages. p and q comprise the private key. p and q cannot be trivially determined from n. As long as p and q are kept only by the person meant to decode message encrypted with n, the message is secure.||Lock n: 93954233|
|The plaintext “hello” can now be encoded using the lock, but must first be numerically encoded. We can use the ASCII representation:||
Plaintext = hello
ASCII-encoded plaintext = 104 101 108 108 111
|Multiply the encoded plaintext and lock n to encrypt the message.||104101108108111 × 93954233 = 9780739766747650083863|
This is a simplified version of RSA encryption methodology. For more information about RSA encryption visit https://brilliant.org/wiki/rsa-encryption/.