In order to demonstrate private and public key encryption, it is best to have a cast of characters.
Meet Alice, Eve, and Bob.
Alice wants to send Bob some sensitive information.
Eve has been trying to get this information from Alice.
She has been watching her communications in anticipation.
How can Alice send this information to Bob without Eve seeing the information?
Let’s assume that Alice and Bob are not able to meet in-person, so physically handing off the information is not an option.
Symmetrical Key Encryption
If this were a physical box containing sensitive information, then Alice could simply use a padlock and give Bob an exact copy of her key with which to open the box.
This tried-and-true concept is the foundation of symmetrical encryption keys. Rather than a set of physical keys the encryption might be a string of characters or a mathematical equation.
The problem is that Alice needs to securely give the duplicate key to the trusted individual, Bob, who has permission to access the information. Remember that Alice cannot meet Bob and hand him the key, so she could first send the key to Bob and send the locked box later; but, this would not protect the key from Eve, who has been watching Alice’s communications. All Eve needs to do is intercept the key, make a copy, and send it on to Bob, who would be none the wiser and repeat the interception when the information is sent.
Given the appropriate circumstances, symmetrical key encryption is a secure and adequate solution to the problem of communicating sensitive information. In fact, it was used throughout World War I and II in the form of Trench Codes and other ciphers. The weaknesses of symmetrical keys became more apparent as ciphers were broken by enemy spies and the advent of computers accelerated mathematical computations. It was not until the 1970s that the necessity of a more secure form of encryption led to a different way of looking at cryptographical methods.
James H. Ellis formulated the basis of a new form of encryption in 1970. Going back to our example, Bob could keep the key and send Alice an unlocked box. She could then put her sensitive information into the box, lock it, and send it back to Bob. The idea is simple. It makes sense when imagining the packet of information to be a physical one, but the mathematical representation of this idea was not realized until Clifford Cocks invented public key cryptography in 1973.
Cocks split a single key into a public key (the lockbox) and private key (the key) and relied on prime factorization to make the mathematical formula behind the key sufficiently difficult to solve. While an eavesdropper may gain access to the public key and the encrypted information, they will not be able to crack the code without the private key. This is known as a trapdoor function in the realm of cryptography and characterized as being easy to solve in one direction but near impossible to solve in the other direction. The idea is that, even with the lighting fast mathematical skills that computers possess, it would take so long to solve for the unknown variable that by the time the computer solves the equation, the information is no longer relevant or the hacker is dead and gone.
Cock’s encryption was classified but was rediscovered by Ron Rivest, Adi Shamir and Leonard Adleman in 1978 and given the name RSA (Rivest-Shamir-Adleman). If you want to learn more about how it works I’d recommend perusing the Wikipedia page or watching “Public Key Cryptography: RSA Encryption Algorithm” from Art of the Problem on YouTube. I will not go any further into the math behind this encryption because there is no appropriate way to make it simple enough to understand while still explaining the mathematical complexity. I will say that even if all of the public keys are intercepted, it would take hundreds of years to decrypt a message that uses RSA with a sufficiently large prime.
While RSA is the most utilized form of public key encryption, it is not the only one. Other techniques include Diffie-Hellman key exchange, DSS, ElGamal, and Cramer-Shoup. These all rely on sufficiently complex private keys, which is the greatest strength of any asymmetrical cryptology.
To sum it up: asymmetrical encryption relies on prime numbers, a private key, a public key, and a sufficiently complex mathematical trapdoor function; but the development of quantum computing may render all private keys obsolete.
Traditionally, computers communicate in bits that represent 1s and 0s, where 1 would represent on and 0 would represent off. Anything and everything on a computer is merely a string of 1s and 0s rendered in such a way as to be understandable by humans. In the first computers (and most likely on the device that you are using right now), these bits are sent and interpreted one at a time, but the theory behind quantum computing is that a bit could be programmed to be both a 0 and a 1 at the same time. These are called quantum bits (qubits) and utilize a superposition of state, entanglement, and tunneling.
Quantum mechanics came about when physicists started looking at light very closely. Light was thought to behave as a wave until experiments found that on a small enough scale it behaved like a particle. This gave way to the discovery of photons and thusly the field of quantum mechanics. Photons have a superposition property so that the net response caused by two or more stimuli is the sum of the responses that would have been caused by each stimulus individually.
Scientists also found that photons operate in the buddy system, which is formally called entanglement. When you look at one photon you change the behavior of its “entangled” partner. This happens regardless of the distance that separates the two particles (Einstein called this “spooky action at a distance”).
They also discovered that particles on the atomic scale operate in a probabilistic world. So, while it is most probable that an electron will be in one location, but there is a possibility of it being in another and that other place is “more desirable” to the electron, then you may very well see the electron in the least probable place. This rather unfathomable concept is known as quantum tunneling. Imagine a boy skateboarding on a half-pipe. In traditional physics, if he were to start at the top of one side of the half-pipe he would only go to that height on the other side – even if the other side went higher than the starting side. If the skateboarder were an electron and the other side of the half-pipe a barrier, there is a chance that you will find the electron anywhere on the half-pipe, regardless of its energy potential.
Eventually, scientists worked out that the inherent properties of photons could be harnessed to create quantum computers that are able to solve hundreds of mathematical computations at the same time. Computers with that much computation power would have little trouble decrypting those difficult trapdoor functions that rely on prime factorization because a solution that may have taken a hundred years to solve can now be cracked in minutes.
With the creation of working quantum computers, cryptologists are racing to get ahead these private-key-cracking supercomputers that would crack RSA in an afternoon. Their solution: quantum cryptology.