|
Symmetric cryptography |
|
|
|
Asymmetric cryptography |
|
|
Source: Sachi Mani’s blog67
As we have seen, one of the biggest problems of symmetric cryptography is how to share a key in the first place when all forms of communication are tapped. It is hard to be sure that you can share a decryption key with your friend without the eavesdroppers also getting that key. With public key cryptography, you broadcast your public key to everyone, not caring if the eavesdroppers can see it or not. Your friend then encrypts the message and sends it to you. Only you can decrypt it because only you have the private key. If an eavesdropper gets the encrypted message, they can’t decrypt it because they don’t have your private key. It is a beautiful system and a huge improvement over symmetric schemes because you never need to communicate a shared or common key.
What do keys look like? There are number of different schemes. PGP (Pretty Good Privacy) is a scheme originally developed in the 1990’s for encrypting, decrypting and digitally signing messages such as emails. This scheme was so powerful that the US Government didn’t like it and had it classified as Munitions, an ‘Auxiliary Military Equipment,’ meaning that anyone found exporting it from the US would be in deep trouble. Phil Zimmermann, the creator of PGP, found a way around this by publishing the source code as a hardback book using First Amendment protection of the export of books68. This marked the height of tensions between the US Government and individuals who are passionate, quite rightly so, about privacy. To learn about this story in depth, I recommend Steven Levy’s book Crypto which documents the history of PGP and the revolution of cryptography.
Back to public and private keys. I downloaded GPG Suite69, an open source and free set of tools that conforms to the OpenPGP standards, and I created a new keypair. Here is what the public and private keys look like:
Of course this specific keypair is useless now, as I have made both keys available to the public.
So that is PGP. Bitcoin uses a different scheme called ‘ECDSA’—Elliptic Curve Digital Signature Algorithm. It works like this:
•Pick a random number between 0 and 2256-1 (that, written out, has seventy-eight digits: 115, 792, 089, 237, 316, 195, 423, 570, 985, 008, 687, 907, 853, 269, 984, 665, 640, 564, 039, 457, 584, 007, 913, 129, 639, 935). This is your private key.
•Do some ECDSA maths on it to generate a public key. The ECDSA algorithms are well known and there are plenty of tools to help with the calculations.
That is it! You now have a randomly chosen private key and you have mathematically generated a public key from it. From your public key you can generate your Bitcoin address to tell the world, but make sure you don’t tell anyone your private key. Although it was easy for you to convert your private key into a public key by doing some ECDSA maths on it, it is mathematically impossible for someone to ‘work backwards’ and derive your private key from your public key.
For a real example, go to www.bitaddress.org and wiggle your mouse a bit to generate some randomness. I did it with the following result:
The Bitcoin address is derived from the public key. By pasting the private key into the ‘Wallet Details’ section of the website, you can see all of the gory details including the public and private keys in various formats:
Again, of course this keypair is useless now and I wouldn’t recommend sending any bitcoins to it!
So there you have it. Bitcoin addresses (accounts) are derivatives of public keys, and when you make a Bitcoin transaction, you use your private key to sign, or authorize, the transaction which moves bitcoins from your account to someone else’s. Most blockchain schemes operate this way. Digital assets are held in accounts made from public keys, and the respective private keys are used for signing outbound transactions.
A hash function is a series of mathematical steps or algorithms that you can perform on some input data, resulting in a fingerprint, or digest, or simply, a hash. There are basic hash functions (not used in blockchains) and cryptographic hash functions (used in blockchains).
We’ll need to understand basic hash functions before moving to cryptographic hash functions.
Basic Hash Function
A really basic hash function might be ‘Use the first character of the input’. So using this function you’d get:
Hash(‘What time is it?’) => ‘W’
The input to this function is ‘What time is it?’ and is sometimes called the preimage or the message.
The output of this function is ‘W’ and is called the digest, the hash value, or simply the hash.
Hash functions are deterministic because the output is determined by the input. If a function is deterministic, it always produces the same output for any given input. All mathematical functions are deterministic (adding, multiplying, dividing, etc).
Cryptographic Hash Functions
A cryptographic hash function is special and has some characteristics that makes it useful in cryptography and for cryptocurrencies, as we will see later. Wikipedia70 states that the ideal cryptographic hash function has five main properties (my comments in parentheses):
1.It is deterministic so the same message always results in the same hash
2.It is quick to compute the hash value for any given message (you can easily go ‘forwards’)
3.It is not feasible to generate a message from its hash value except by trying all possible messages (you can’t go ‘backwards’)
4.A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value (a small change makes a big difference)
5.It is not feasible to find two different messages with the same hash value (it is hard to create a hash clash)
What does this mean? The combination of properties 2 (you can easily go ‘forwards’) and 3 (you can’t go ‘backwards’) means that cryptographic functions are sometimes called ‘trapdoor function’. It is easy to create a hash from a message, but you can’t re-create the input from the hash. Nor can you guess or infer what the message may be by looking at the hash (property 4). The only way to go backwards is to try every possible combination of inputs and see if the hash value matches the one you are trying to reverse. This is called a brute force attack.
So would our previous hash function (‘Use the first character’) be a good cryptographic hash function? Let’s see:
1.Yes, it is deterministic. ‘What time is it?’ always hashes to ‘W’.
2.Yes, it is quick to compute the output, you simply take the first character.
3.Yes, by knowing only ‘W’ it is not feasible to guess the original sentence (but see 5).
4.No, a small change in the message doesn’t necessarily change the output. ‘What time is at?’ also hashes down to ‘W’.
5.No, we can easily create loads of inputs that will all hash down to the same output. Anything starting with ‘W’ will work.
So our earlier hash function is no good as a cryptographic hash function.
So what is a good cryptographic hash function? There are some established industry standard cryptographic hash functions that meet all of these criteria. They have names like MD571 (Message Digest) or SHA-256 (Secure Hash Algorithm), and they have an additional benefit in that their output is usually of a fixed length. This means that whatever you use as an input to the hash function, whether it is a sentence, a file, a hard drive, or an entire data centre, you will always get a short digest back.
Here is the kind of output you get:
MD5(‘What time is it?’) –> 67e07d17d43ee2e70633123fdaba8181
SHA256(‘What time is it?’) –> 8edb61c4f743ebe9fdb967171bd3f9c02ee74612ca6e0f6cbc9ba38e7d362c4d
You can even try this on your computer. If you have a Mac, run the Terminal application and type:
md5 -s “What time is it?”
or
echo “What time is it?” | shasum -a 256
You will see that your results are the same as mine. Of course, that is the whole point in a cryptographic hash—it is deterministic.
If you change the input slightly, you get a very different result:
SHA256(‘What time is it?’) –> 8edb61c4f743ebe9fdb967171bd3f9c02ee74612ca6e0f6cbc9ba38e7d362c4d
SHA256(‘What time is at?’) –> 2d6f63aa35c65106d86cc64e18164963a950bf21879a87f741a2192979e87e33
Hash functions can be used for proving that two things are the same without revealing the two things. For example, let’s say that you want to make a prediction and don’t want others to know the prediction, but you want to be able to reveal the prediction later. You’d write the prediction down privately, hash it, and display the hash to your audience. People can see that you’ve committed to a prediction but can’t back-calculate what your prediction is. Later, you can reveal the prediction, and others can calculate the hash and see that it matches the hash you published.
Cryptographic hashes, the output from cryptographic hash functions, are used in Bitcoin in a number of places:
•In the mining process
•As identifiers for transactions
•As identifiers for blocks, in order to link them in a chain
•Ensuring that data tampering is immediately evident
Digital signatures are used extensively in Bitcoin and blockchains for creating valid transactions ‘signing’ transaction messages to move coins from your account to someone else’s.
What are digital signatures, in a cryptographic sense? Well, we can afford to be a bit pedantic here. Digital signatures are a subset of electronic signatures, which can take a number of forms.
One form of electronic signature is as simple typing your name into a box:
|
Joe Bloggs |
This is an electronic signature but not a digital signature.
Another form of electronic signature is a picture that looks like a wet-ink signature, but inserted into a document:
This is also an electronic signature, but not a digital signature.
So what does a digital signature look like? I created a small message containing the text ‘Here is a message I want to sign’. and I signed it using the (private) PGP key I generated earlier. Here is what the signature looks like:
So that is a digital signature. Looks like gibberish. So what’s so special about it? What does it prove?
A digital signature is created by taking the message you want to sign and applying a mathematical formula with your private key. Anyone who knows your public key can mathematically verify that this signature was indeed created by the holder of the associated private key (but without knowing the private key itself).
So, anyone can independently validate that this piece of data was signed by the private key holder of this public key.
In essence:
Message + Private key -> Digital signature
Message + Digital signature + Public key -> Valid/Invalid
How is this better than a wet-ink-on-paper signature? The problem with a wet-ink signature is that it is independent of the data that is being signed, and this creates two problems:
1.There is no way of knowing if a document has been tampered after your signature is applied to the bottom.
2.Your signature can easily be copied and re-used with other documents, without your knowledge.
Your wet-ink-on-paper signature is your signature and doesn’t change based on the item being signed: when you sign a cheque, a letter, or a document, the whole point is that your signature looks the same. This is easy for other people to copy! This is really terrible security!
In contrast, a digital signature is only valid for that exact piece of data, and so it cannot be copied and pasted underneath another piece of data, nor can someone else re-use it for their own purposes. Any tampering with the message will result in the signature being invalidated. The digital signature is a one-time ‘proof’ that the person with the private key really did approve that exact message. No one else in the world can create that digital signature except you, unless they have your private key.
Now, just to explain one further step, the mathematical process of ‘signing’ a message with a private key is actually an encryption process. Remember that you encrypt data with a public key, and decrypt it with a private key? With some schemes you can also do it the other way around: you can encrypt data with a private key and decrypt it with a public key. So actually the validation process is taking the digital signature and decrypting it with the well-known public key, and seeing that the decrypted signature matches the message being signed.
But what if the message being signed is really big, like, say, gigabytes of data? Well, you don’t want a really long digital signature, as that would be inefficient. So in most signing schemes, it is actually the hash (fingerprint) of the message that is signed with the private key to produce a digital signature which is small, irrespective of the size of the data being signed.
There is a good summary on Microsoft’s Technet website72:
So digital signatures can be used to authenticate a transaction or message, as well as to ensure data integrity of the message. Also, unless a private key has been copied, it is impossible afterwards to say ‘it wasn’t me’—this property is called ‘non-repudiation’ and provides comfort for both parties to a transaction.
Digital signatures are used in blockchain transactions because they prove account ownership, and the validity of a digital signature can be proven mathematically and offline, without asking any other party. Compare this to traditional banking: when you instruct your bank to make a payment, you first authenticate yourself by logging in to the bank’s website, or showing your ID to a bank teller in person. If the bank believes that you are the account holder, then the bank executes your instruction on your behalf. In a blockchain system, where there is deliberately no organisation to provide or maintain accounts for you, your digital signatures are the critical piece of evidence that entitle you to make transactions.
In cryptography, it always seems to be Alice and Bob. Why? They are characters first used by Ron Rivest, Adi Shamir, and Leonard Adleman in their 1978 paper ‘A method for obtaining digital signatures and public key cryptosystems’73 instead of a drier ‘A’ and ‘B’. Since then, people use these characters as a nod to the inventors.
But wait, there’s more… Wikipedia74 has a list of commonly used characters, and here are a few I am fond of:
•Craig the password cracker
•Eve the eavesdropper
•Grace the government (generally characterised as anti-cryptography)
•Mallory the malicious man-in-the-middle
•Sybil the attacker who uses a lot of pseudonyms to overwhelm Alice and Bob
So there you go, that is why it is always Alice and Bob.