Series: Quadrans Essentials Presents The Beauty and Magic of Public-Key Cryptography
We land today on the third episode of the Series: Quadrans Essentials. Our journey continues as we delve into the technologies at the core of Quadrans Blockchain and their role within the Web3 Revolution and decentralised systems.
In the first episode of the series, we covered the rise of P2P networks and the sweeping changes they brought to all the industries that rely on them today. In the second episode we guided you through the history of Cryptography, from its origin to Post-Quantum Cryptography.
Today we continue to swim in the same sea — Cryptography is in fact such a broad and fascinating subject that it brings together math enthusiasts, spy story geeks and cryptocurrency nuts.
In this article we will focus on Public-Key Cryptography — a family of cryptographic algorithms with many possible applications.
Public-Key Cryptography algorithms are also referred to as asymmetric and as the name suggests they are meant to be set apart from their predecessors — the symmetric algorithms.
So let’s jump right in and see what makes asymmetric Public-Key Cryptography algorithms different from symmetric ones.
Encryption at a Glance
Usually, encryption makes secure communication between two or more parties possible in a hostile environment.
Do you remember Alice and Bob? These two need to communicate privately out in the open preventing a malicious third party, called Eve, from knowing what they are saying to each other. Encryption comes to the rescue, with its tools and algorithms.
Let’s see how with an example.
Alice wants to deliver the message ‘M’ to Bob, to do so she uses an encryption algorithm and a secret key ‘K’ which transforms her initial message ‘M’ into a seemingly random gibberish text — the result of the transformation is a new message ‘G’.
Alice can now send the message ‘G’ to Bob using any insecure channel, because even if Eve was ready to intercept it she could not trace the original message ‘M’ without the key ‘K’. Only Bob, who knows both the algorithm used by Alice and the key to read it, can recover the original message ‘M’ to the received message ‘G’.
Hurray for privacy!
Today we use encryption almost daily without even realising it: it’s embedded in our smartphones, the apps we use to chat, in banking apps, within the web, in payment systems and plenty of other examples.
In the Beginning it Was Symmetric
Historically, the first algorithms to be built were symmetric. Symmetric in this case denotes that the algorithm is reversible and can be run in either direction.
So in symmetric encryption an algorithm and a cryptographic key are used to transform the message ‘M’ into the message ‘G’ and, when the same algorithm is run backwards with the same encryption key, the message ‘G’ is recovered back into the message ‘M’.
An example you might already be familiar with is called “the letter transposition algorithm”.
This is an easy trick to pull off, imagine scrambling the letters of the alphabet and comparing the new scrambled alphabet with the regular one. Look at the image below. To compose your message, check which letter corresponds to the letter you want to use.
Using this scrambled alphabet we would exclaim “Vmzzd Oduzs!” instead of “Hello World!”
In this case, the algorithm used or more simply the rule used is “replace the letter” and the secret key is the encrypted alphabet we created by scrambling the alphabet — but note that the same approach can be used to create a different encrypted alphabet.
If we swapped the letters in one direction to encrypt your message, all we need to do to decrypt it is to swap them backwards. You played similar games in school, didn’t you?
We’re having fun with it, but it is clear that this encryption scheme is way too simple and easy to crack to be used for real life purposes: the encrypted words have the same number of characters as the original ones, and the frequency of the letters reveals too many clues. But for the argument’s sake let’s pretend this algorithm is extremely hard to break. Which other weaknesses can you find?
One of the main drawbacks of symmetric algorithms is that both parties need to know the key used before exchanging a message.
Take Alice and Bob, they have to agree on which key to use before exchanging their first encrypted message and have to do it in a secure way too. Do they have to first meet alone to share the key before using it in an insecure scenario? Yes, because other channels may not be secure at all.
Also, what if Eve breaks the key? Alice and Bob have to agree on another one — and that means meeting again, which may not be possible. This is all very inconvenient!
Such algorithms cannot be used in any of the applications that require encryption that we mentioned above: imagine how different texting on Whatsapp would be if you had to share a dedicated secret key with every person in your address book to use proper end-2-end encryption…That sounds like a nightmare!
Lucky for us all, a few decades ago mathematicians came up with a new class of encryption algorithms that provide an elegant solution to this problem and open up to a whole new set of possible applications.
Let’s Go Public
Let’s pretend that building some sort of digital safe is somehow possible. To use it, anyone can grab a copy, put their message inside it, and lock it.
The digital safe is then sent back to users with regular/insecure mail. Anyone could intercept the safe, but no one can unlock it since the digital safe is very secure and there is no way to tamper it or recover its combination.
Only you, the intended recipient of the message, have the combination to unlock the safe and retrieve the message locked inside. Wouldn’t that be great?
With this fancy method anyone could send a message securely in the digital safe, even in an insecure environment.
No need for a secure channel to communicate, no in-person meet-ups… things would roll much more smoothly. In a nutshell, this is exactly what Public-Key Cryptography algorithms do.
Let’s break it down: these algorithms work differently — instead of having one key, they actually have two. One key is called the “Private key” or ‘Pk’ and the other the “public key” or ‘pk’.
The public key is used to encrypt the message (i.e. it turns ‘M’ into ‘G’), while the private key is used to reverse the process and decrypt the ciphertext (i.e. it turns ‘G’ back into ‘M’).
Both Pk and pk are generated by one of the parties (Alice) who cleverly keeps her Private key for her eyes only, while sharing her Public key with anyone.
The best thing is that Alice can share her Public Key with no worries, since there is no practical way (as of today) to grab a copy of the Public key and guess/determine the corresponding Private key.
Thanks to Public-Key Cryptography Bob can use Alice’s public key and send her an encrypted message with the absolute certainty that only she can read it.
Asymmetric encryption algorithms are called so as they are not reversible and need two different keys to perform two different operations.
The Whatsapp nightmare scenario we imagined before is now solved: any contact can share their public key with the whole list of people they want to chat with and use end-2-end encryption.
These algorithms are also the ones that allow secure web connections via HTTPS between our browser and the bank’s server.
Most asymmetric encryption algorithms are based on difficult mathematical problems and operations that are easy to solve in one way but virtually impossible to be reversed.
Let’s peek at a couple of examples. One well- known algorithm is called RSA and leverages the factorisation of very large numbers into two very large primes. Another is called ECDSA or “Elliptic Curve Digital Signature Algorithm” and it is based on elliptic curves… These are very complex math problems that require expert knowledge — we won’t go into details in this episode. Just remember that Math is on our side.
Now you know what asymmetric algorithms are and can understand them in all their beauty.
But where does the magic lie?
Adding Magic
We said that public keys are used to encrypt messages and private keys to decrypt them. Truth is, it is not that simple.
In fact, public keys are also used to decrypt messages when they were encrypted using the same private key. Basically what one key does, the other undoes. But does this do any good?
If Bob encrypts a message for Alice with her public key, he is sure that Alice will be the only one able to read it.
But what if someone was impersonating Bob? How can we avoid that?
Let’s see the trick in all its steps:
Alice is certain that Bob sent the message, since he is the only one who has the private key — both the sender and the receiver are guaranteed.
Let us now have a closer look at an even better application: the digital signature.
Bob needs a signed document from Alice. Alice uses a hash function to obtain the digest.
N.B. Hash functions can be thought of as a way to fingerprint a file and create a short value (let’s say 32 bytes) which depends on every single bit of the document. Two “nearly” identical documents with as little as a single bit apart will have different fingerprints or digests.
Once Alice has the document digested, she encrypts it using her private key. The encrypted digest is nothing more than the signature that is sent to Bob along with the document.
Now Bob has received the document and signature, and can check them. He creates the document digest the same way Alice did, then decrypts the signature using Alice’s public key. Only if the two values match Bob can have a very high level of confidence that:
the message he received is from Alice
- Alice did create the digest of that precise document
- the document was not edited since Alice signed it
- Alice signed it since she’s the only one with the matching private key.
How cool is that?
Practical applications
Want to have fun with cryptographic algorithms? PGP (Pretty Good Privacy) and GPG (Gnu Privacy Guard) are two popular encryption programs that use Public-Key encryption.
You can start by generating your private/public keys and encrypt files with it to see how it works. Give your public key to your friends or just anybody!
Keybase.io is a website and smartphone app that allows you to share your public key and use it in a bunch of different ways like having your git repository encrypted or chat privately.
If you want to use Public-Key encryption to secure your emails, Mailvelope is a browser extension that integrates with Gmail web application and performs encryption and decryption of the email messages very easily.
How about Blockchain?
If you are a Blockchain or cryptocurrency enthusiast, you’ve undoubtedly heard about private keys and their extreme relevance.
Public-Key encryption is in fact one of the key components of Blockchain security that comes into play whenever a transaction is made. In fact, each transaction has to be signed to prove that the account or wallet making the transaction is the actual owner of the digital assets involved.
In other words, to manage your cryptocurrencies you must first prove that they are yours — and to do that you must prove that your digital signature matches that of the known owner.
As you can see, Public-Key Cryptography is a key component in every one’s security and privacy and we are currently using it daily.
