Since my last posts explaining how Bitcoin works were a bit of a success, I figured I would continue the series. So far we’ve discussed Bitcoin mining, the incentives and the cryptography used in the protocol. However, I glossed over a key element in the Bitcoin ecosystem — digital signatures. This was partly because my goal in the previous posts was only to introduce you to mining, but also because digital signatures are important enough that they deserve their own post. If you’re reading this, I’m going to assume you have limited knowledge of cryptography. So instead of jumping right into digital signatures, I’m going to start by providing a broad introduction to cryptography. Hopefully you’ll learn not just how Bitcoin works, but also how to stay safe on the internet by keeping your private information away from prying eyes.
“There are two kinds of cryptography in this world: cryptography that will stop your
kid sister from reading your files, and cryptography that will stop major governments
from reading your files.” —Bruce Schneier
Obviously, we’re going to concern ourselves with the latter. Cryptography is the science of using mathematics to encrypt and decrypt data so that we can either store it or transmit it to someone so that only the intended recipient can read it. In practice we take plaintext (the unencrypted data) and encrypt it using a cipher, a mathematical algorithm used to securely encrypt and decrypt data, to produce ciphertext (unreadable encrypted data). In conventional cryptography the same key is used to both encrypt and decrypt the data. This practice is called symmetric-key cryptography.
One of the earliest and most well know ciphers was a Caesar’s cipher, used by Julius Caesar to protect his military correspondence. This particular cipher was a substitution cipher. Each letter in the message was substituted with the letter that was three spaces to the left in the alphabet. The key in this case was simply to shift to the right by three. Caesar ciphers were even used by the Russians in WWI after their troops failed to master more complicated ciphers. German and Austrian cryptanalysts had no trouble cracking it, however.
Another popular cipher was Little Orphan Annie’s decoder ring. :o
Today, the most widely used symmetric-key cipher is the Advanced Encryption Standard (AES). AES was established in 2001 by the US Government’s National Institute of Standards and Technology after it held an open competition to create a replacement for the cracked Data Encryption Standard (DES). Fifteen designs were submitted by cryptographers from around the world. The list was narrowed down to five finalists: Rijndael, Serpent, Twofish, RC6, and MARS. Ultimately, Rijndael, developed by two Belgian cryptographers, was selected as the cipher for AES.
The AES algorithm is part of the public domain. That means it’s not only free for anyone to use, but also that it has undergone an enormous amount of cryptanalysis. As of today there are no known feasible attacks. The NSA has even approved AES for use in the encryption of Top Secret classified information. You can take that as a bit of a vote of confidence. You can find various implementations of AES to use for encrypting your files simply by googling around.
It should be noted that, given enough time, any cipher can be broken by a brute-force attack. A brute-force attack is where an attacker tries to decrypt the data simply by trying different keys over and over again. However, the time it takes to execute such an attack increases exponentially as the length of the key increases. To date the largest key found with a brute-force attack was a 64-bit RC5 key. Finding it took a total of 331,252 computers and over 1,757 days. The three versions of AES use keys of 128-bits, 192-bits, and 256-bits — well out of range of any brute-force attack. In fact, if every one of the 7 billion people on Earth had 10 computers testing 1 billion key combinations per second, it would take the entire population 77,000,000,000,000,000,000,000,000 years to find a single 128-bit AES key!
What about quantum computers? Could they brute-force an AES key? Well, I’m not an expert, but from what I’ve read quantum computing would likely double the size of a key that could be effectively brute-forced. That might cause AES-128 to fall, but AES-192 and AES-256 should still be safe.
Needless to say, if you’re going to crack AES, a brute-force isn’t going to do it. You’re going to have to find some kind of weakness in the algorithm. How about the NSA and it’s $52.9 billion black budget? What are the chances that it’s had some sort of cryptographic breakthrough that the public or academia is currently unaware of? Well, it’s plausible, but it’s unlikely that such a breakthrough would allow them to actually view the plaintext. When DES was broken, the best attack didn’t reveal the plaintext, it just shortened the effective strength of the encryption key by about 17 bits, making it easier to brute-force. Even then, the attack required something like 70 terabytes of ciphertext to analyze. You’re not going to get that much ciphertext from an average user. So to the extent that the NSA does have a crack of AES that nobody knows about, it’s unlikely it will actually allow them to decrypt anything. Most of their time is likely spent finding bugs in AES implementations, bad passwords, or performing traffic analysis. The fact that they pressured companies like Google, Apple, Microsoft etc, into giving them backdoors into their systems is prima facie evidence that they can’t break modern commercial encryption systems.
While symmetric-key encryption works well for encrypting data on your computer or on a server, it isn’t that great for communication. Since it uses the same key for both encryption and decryption, two parties that wish to communicate with each other need some way to agree on a key. Obviously, the whole reason you are encrypting your communications to begin with is that you don’t believe your communication channel is secure. You just can’t send an encryption key in an email or text or phone call since it will be intercepted. Short of meeting in person, it can be difficult for two parties to securely share an encryption key. Imagine the plight of Edward Snowden trying to send top secret files to Glenn Greenwald without having previously shared an encryption key.
Now there does exist a method for securely communicating an encryption key called Diffie-Hellman key exchange. This method allows users to communicate over an insecure channel to establish a shared secret. The below picture provides a nice visual how it works. Of course, in the real world the exchange is done with math rather than gallons of paint.
Key exchange works well enough, but there are a couple inconveniences. First, you have to take extra precaution to make sure you are establishing a shared secret with the person you actually want to communicate with and not some spook posing as the other party. Second, you both have to sign online at the same time so there can be a “handshake”. This is fine if you are communicating in a real-time chat. In fact, the popular Off-the-Record messaging protocol uses this practice. For sending an encrypted email, say, that someone can decrypt and read at their own convenience, it doesn’t work so well.
Public-key cryptography represents an advance over symmetric-key cryptography as far as communications are concerned. Instead of using a single key for both encryption and decryption, separate keys are used for both. A user generates a pair of keys that are mathematically linked to each other. One key (the public key) is used for encryption and the other (the private key) is used for decryption. The algorithm is designed in such a way that it is infeasible for an attacker to derive the private key from a given public key.
Using this scheme, a person can share his public key, usually by posting it on a keyserver or a website, and anyone can download it and use it to encrypt files to send to him. Once encrypted, they can only be decrypted with the corresponding private key.
The most popular implementation of public-key encryption is Pretty Good Privacy (PGP) and its free open source counterpart the GNU Privacy Guard (GPG). You can download a Windows version with the Kleopatra GUI here.
A PGP public key will look something like this:
-----BEGIN PGP PUBLIC KEY BLOCK----- Version: GnuPG v2.0.17 (MingW32) mQMuBFG3x4URCACZ/c7PjmPwOy2qIyKAYRftIT7YurxmZ/wQEwkyLJ4R+A2mFAvw EfdVjghAKwnXxqeZO9WyAEofqIX5ewXD9J4H6THaWNlDeNwnIUhbVsSEgT6iwGEG arXvkrMyy+U5KA0x2dcsYRKAPMM1db+4zSQkWTWzufLU7lcKi3gU3pNTxSA0DjCn wfJQspiyWchSfgZ59+fKaGZJVSElrS2i2ok5mK3ywCXRWvnAC/VxA3N6T4jvkX/+ 1gS/oUgdocP31TeV0L20JH9QgmFYC3jMbErAATo2x9Y8g4NofdvSnntbZk9Giycc cgOWsa8aFtTjvcBp8hkCl3dK5xTZiY0gLSaDAQCXSHI7zw4LiNFfCV+PbO9BEqDA i4JFV/qX7TgfBNX7nwf/fEFu18V16lVCsRzeuhMsHHzAQ7PZJfdfhyOubq0fnjkk 2RdcleosnP22zP5LoRs1fvIDdL3wnkg1ZUwfICP0HWRzRYcVBaIv9HcqSVBWriJj uscni5QtX3fIU2wqSyP90wquWPkO7jObT0hWihhWPFXiFA6996i/rTZiJH+eFPSW afxVlRAqH4kaUBen5fSMbBSsfc+GkuuQH7gIYQC2k88soPLuFZGsibDwBqvdUqFG S39ifNf/2MUx8DrM8bbIPPwiuTelAFVPu7GGzyzAF3yhk/Cdd/YmWlwrwAd4Psev WpXNSApzSgh/HhY3wVdj9skItQBISXJSVkMD4DLvhwgAh/Ur5JEgtx5dYGpU/nEr LGEDUgPeBnewReA8wurAnYeOHGVSu84kXceO2tJvnbLn5y1L0dML/u3+S9pDXOfR 1TR9QxWd3QIBUY68lfa+DiXHSVcfrTPz3q+CHMLj7917hfATWwRTemccp6n8al68 tfGXih9t+lAwuq4KuRk0NkGEKrqeRU3sdGVLdIZ8IteikyYgWcZTYG7oxcj7qpif ixl0DsI1HXfXQrFVnjOyQuiS8z06+ZuC/8dgi7UBpUkgQLZYosE0fUAdeiAVPGv0 LanXwHRQPDlmBiorge1c1jpbna2K9EyQ1Jbkyn6nkg8OaetO9brLBMk916mn6mQD ebQfQ2hyaXMgUGFjaWEgPGN0cGFjaWFAZ21haWwuY29tPoh6BBMRCAAiBQJRt8eF AhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAKCRC4lW2/7nwQXJ/dAP42O7se mHDqZnxl4Slrf8AxgCI0DowpBcNxWRM8hNHS2QD/TkbCvy4QNq2QNrP26m183eJM y6PNCncuwsB5TdoLgYq5Ag0EUbfHhRAIAIPrWRsRVTt3nhJ+0dygQjQsywx9wMMX ELOdpOmWz838kufR02789b5DTRP2qEm+hymfebd42kgam2CLPBt3F6je4ZHP1iaW BnsihKJBC4Oha+b3Wj8UGpH+t6ti8voQhQgKK7HNokedMVRQdW3nzBT1p7KbTyLH pdT+O8KUXdh5hMBPrxgPdB3GFH3QAO3hgsWXkZfMHNAx24AG/oimtW5gGLzDvBQ0 wQFfWmsiy+ah8QhoUd1R0UItD6vD9p2I8MAPnheDO4E16wdy/An/5k1yoqxBd+pA ACnoDJpTwR/P2y7FoO5aCXMWz5ZeKobiTOxKxRfoaZlm72FKpLBTI68ABAsH+wet wHpRPqU9ajhSExUD1d9JL20GyDM+9MgLq1AQ0U0UOC+OQ51L2bq0tFKI653M7niu rB7n3bCnSNAysRtkRDs/YWeuPjaGUcwfnGArdIPdzN1rYN87esdavDMBI7hXGjtI EypYdXykoO3FflWJtJzKO/5DoLqVcbXMuubXuhDOigLUQroKgXmPxcSlzRuLabPi m88Jg6uRuZQGTix95FZkicTh3U6/48D5R56vCfgGJVwDRCTJmxt7OhGn9v3bvBQM uNNuVFD2XS7CQTNxyqCKke5bJdk/XAgfVJ+H15RfGsW+z6I0TumOvHX0lLaN1LGV xETuDbVSNCE9LoS14fiIYQQYEQgACQUCUbfHhQIbDAAKCRC4lW2/7nwQXEI4AP49 Se5zeNswzCcaACkA76fh93RK2VWO4SfKh3hlWxMVhgD/exv41oZehRIOzNrzjFkQ uRkFDPE1NWJAngLobMUo93s=
That’s my public key by the way. Feel free to test it out by encrypting something and sending it to me.
There is also a PGP plugin for Mozilla’s Thunderbird email client that is a great way to combine the benefits of public-key encryption with ordinary email. Of course your metadata (your email address and who you’re sending the email to) isn’t hidden. Only the body of the email will be encrypted.
Now, if you’ve stuck around this far you’re probably asking what does all this have to do with Bitcoin?
Public-key cryptography has a second benefit beyond just the encryption and decryption of data. It can be used to create something called a digital signature which can be used to simultaneously provide authentication, data integrity, and non-repudiation, all of which are critical to Bitcoin’s operation.
A digital signature is generated by combining a user’s private key with the data he wishes to sign in a mathematical algorithm. Once the data is signed, the corresponding public key can be used to verify that the signature is valid.
The following is what a signed message looks like in PGP. Notice the digital signature attached to the bottom.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 This is an example of a PGP signed message. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.17 (MingW32)iF4EAREIAAYFAlIqmD0ACgkQuJVtv+58EFzNTgD/b9tS8CCqnmnKpvR+ZNwr2lGP bb5Ld3ZLPG/91VJ1udgA/1PI30He1e3F6Dj88wssnrMq0jpSOC+kFuxLnpPZxF83 =p9Ov -----END PGP SIGNATURE-----
Now one of the features of a digital signature is that the signed data is actually an integral part of the signature. If the data (the message in this case) is altered in even the slightest way, the signature will show as invalid when checked. This feature allows for the secure transfer of data while ensuring that nobody can just taken the signature and attach it to another file in an attempt to forge a signature.
Let’s return to Edward Snowden. Suppose he were to send the Top Secret files to Glenn Greenwald, but the NSA were to intercept them. They might want to remove the classified information from the files and replace it with disinformation before forwarding them along to Greenwald. However, if they did this, it would invalidate the digital signature. Upon checking the signature, Greenwald would see that it doesn’t match public key Snowden provided him with.
This is how digital signatures are used in Bitcoin. When your wallet creates a new Bitcoin address, what it is really doing is creating a new public-private key pair using the Elliptic Curve Digital Signature Algorithm (ECDSA). The public key is hashed several times until it looks like the familiar Bitcoin address.
In geek speak, a Bitcoin address is technically a base58 encoded RIPEMD160 hash of a SHA-256 hash of 256-bit public key of an Elliptic Curve Digital Signature Algorithm key pair concatenated with a checksum.
If you haven’t read Part 2 where I discussed hash functions, all you need to know is that the public key is run through a number algorithms until a Bitcoin address spits out the other side. The private key is stored in your wallet and needs to be kept safe for reasons you will see in a second.
Before I continue, let me mention that many beginners have an image of a “bitcoin” as some kind of digital file that gets transferred from one person to another. That’s not really how it works. Bitcoins are nothing more than a balance in the public ledger (the block chain). If you want to figure out how many bitcoins you have in your wallet, you can just scan the block chain and record all the inflows and outflows from your address, then simply subtract the outflows from the inflows. That’s it. That’s really all a “bitcoin” is — just a balance in a ledger.
When you make a transaction, all you are doing is telling the rest of the users in the network to add a transaction to the ledger transferring n number of bitcoins from address 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM to address 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T. This effectively just reduces your balance in the ledger while increasing the other person’s. This is really no different that how a check works at your bank. When you write a check to someone, your bank just simply goes into its records and reduces the balance in your account while increasing the balance in the check recipient’s account. The only difference is that Bitcoin’s ledger is public and an electronic transaction performs the same functions as a check.
So when you create a transaction, it is signed with your private key before it is broadcast to the rest of the network. The peers in the network that receive the transactions will then check the digital signature to verify that it matches the public key of the address from which the bitcoins are being sent. If it does, the transaction is considered valid and it is relayed to other peers, ultimately ending up in the block chain. Obviously, only the person in possession of matching private key could have produced a valid signature.
If someone were to try to create a bogus transaction sending funds from an address they don’t own, the signature will show as invalid and the transaction will be rejected. If a malicious peer were to try to alter your transaction by, say, removing the output address and substituting one of their own or by changing the amount sent, this would also invalidate the signature. Remember a property of digital signatures is that if the signed message is altered in the slightest way it will invalidate the signature.
And of course digital signatures also make Bitcoin transactions (or any other data signed with a digital signature) non-repudiable. Once you sign something, you can’t later claim that you didn’t since you are the only one in possession of the key. Of course, if your key gets lost or stolen then you will lose your bitcoins.
So to sum up. Digital signatures are the key ingredient in Bitcoin that allows only the owner of a particular Bitcoin address, and no one else, to publish a transactions to the block chain transferring bitcoins from that address to another.
Ok that wraps up Part 3. Hope it was worth your while reading to the end. If you think this post will be of use to others feel free to share!