Public Key Cryptography - a very short introduction (Part I)
Intro to Cryptography
Cryptography (a word that can be interpreted from the Greek as “hidden writing” or “secret writing”) is the science and art of encoding, transmitting and decoding secret messages over an insecure channel. This is done so that only the sender and the intended receiver can understand what is being communicated, and third parties cannot eavesdrop, even if they manage to somehow intercept the message.
Why would someone go through any trouble just so they could do that? Well, historically, cryptography was mostly used for high-level, sensitive political and military communications, which could result in a major advantages for the opposing side should they manage to intercept and decipher them, though there is evidence private individuals also developed their own techniques, for reasons ranging from protecting themselves agains political or religious persecution to protecting their romantic correspondence while engaged in extraconjugal affairs. There is some evidence some people did it simply for fun or as an aesthetic exercise – for instance, a theory put forward to explain the famous Voynich Manuscript is that it in fact contains encrypted text [1].
In the simplest of terms, encryption is the act of taking any message, such as a physical letter, text file, video, email etc., and scrambling it up in such a way that it can’t be read anymore. In order to make it readable again, you need the key with which it was encrypted (think of it as a secret password). If you want to communicate securely with someone else, you encrypt all messages with your key and then give that person your key so when they arrive, they can make them readable again. This particular example is known as symmetric-key cryptography and has been known since Ancient times (one of the earliest well-known cyphers is called the Caesar Cypher [2]).
There is an issue however with this approach, namely that the key becomes a message in itself. How do you make sure the key arrives at your correspondent safely and unaltered? What happens if someone steals or destroys your key? Or even worse, copies it and then uses it to read your messages without anyone noticing (called a man-in-the-middle attack)? You could try to encrypt the key too, of course – but then you arrive at the same problem of how to send that key over, and so on and so forth. There really is no good answer to this question and, historically, numerous approaches were tried, with mixed results.
Public Key Cryptography
In order to address this issue, during the late 60’s and 70’s, a new approach was developed (though some of the underlying principles were known for quite some time – interestingly enough, the now often-overlooked early weird fiction writer William Hodgson described something very similar in his 1910 novel The Night Land, with relation to telepathic communication, of all things – perhaps this too warrants some discussion at one point in the future). It involves using not just one key, but a pair of two keys. These keys are in fact very large numbers that are mathematically related, but cannot be derived one from the other except by random guessing – and because of their large size, that would take so much time that any information hidden would be useless by the time it were cracked. One of them has to be shared with all participants, thereby becoming known as the public key, while the other has to be kept secret by its owner and is thus known as the private key.
If you wanted to send someone a message using such a system, first you would have to find out the public key of the recipient and use it to encrypt your message. Afterwards you would sign the message using your private key. Then you would take both pieces of information and send them over to your counterpart. What they would then do is use their own private key to decrypt the message you sent, and use it together with the signature they received and your public key to verify the message:
This signature verification step is essential because it ensures that:
-
The message truly came from you (Authenticity). Remember, anyone can encrypt a message with the recipient’s public key, so what is stopping a third party from encrypting messages and saying they were from you? The signature can only be created with your private key - if they don’t have it, they can encrypt messages but can’t sign them.
-
The message was not modified on the way to the recipient (Integrity). The signature is unique for each message, so if on the way some clever third party intercepted your data, changed the message, encrypted it back but kept the same signature as before since they couldn’t generate a new one, the recipient would know immediately that what they got was not what you sent.
-
You can’t say that it wasn’t you that sent the message (Non-repudiation). Since only you have access to the private key, it’s not possible to claim that a message that has been signed by you wasn’t also sent by you.
It is also often the case in real-world implementations that after a secure channel is established and both participants can send, verify and receive messages from each other, they can subsequently agree on a shared secret key that they will use from then on to switch over to a simpler, faster symmetric-key algorithm. This is still secure because the shared key was agreed on using an already-encrypted channel.
These are the basics of how public key cryptography works, and the real-world there are a few implementations, of which the most famous and most widely-used are RSA (Rivest-Shamir-Adleman, from the name of its inventors) and ECDSA (Elliptic-Curve Digital Signature Algorithm), and while they differ markedly in the mathematics of how they come up with the keys and what relationship there is between them, the general principles described above still apply.