The evolution of cryptography part 3: Putting the crypto into cryptocurrency
This is the third in our series of articles looking back at the evolution of cryptography – from simple displacement systems used to conceal messages, to elaborate digital protocols that have facilitated a financial revolution.
In the first two parts of this series, we covered the evolution of cryptography from basic substitution ciphers to astounding feats of engineering. However, though their methods may have grown increasingly complex, cryptographers remained firmly focused on obscurity rather than the mathematically-rigorous work we see today.
This all changed in WW2, when there were huge steps forward made in the world of computing. These technological advances introduced incredible power to crypto-analysis and ushered in a new era – one firmly focused on mathematical processes. The era of classical ciphers was over.
The father of mathematical cryptography
The era of modern cryptography really kicked off with Claude Shannon, known by some as ‘the father of mathematical cryptography’.
Shannon first achieved a measure of celebrity for defining in mathematical terms what information is and how it can be transmitted in the face of noise. Shannon’s informational entropy is the number of binary digits required to encode a message. Today, that might sound an obvious way to define how much information is in a message, but in 1948, simply digitising information was seen as revolutionary. It is also believed that his paper was the first to use the word “bit” as a shortening for binary digit.
Arguably his most important contribution to cryptography, though, came in 1949 with the publishing of ‘Communication Theory of Secrecy Systems’ in the Bell System Technical Journal. In the paper, Shannon proved that unbreakable cryptography was possible and thereby laid the foundation for the development of modern cryptography.
The scheme that Shannon proved unbreakable was the ‘one-time pad’, also known as the Vernam Cipher (so-called after its creator, Gilbert Vernam). In Vernam’s cipher, each plaintext character from a message is ‘mixed’ with one character from a key stream.
Image courtesy of cryptomuseum.com
The idea is to encode the message with a random series of digits – the key – so that the encoded message is itself completely random. This random key must therefore be as long as the message to be encoded and the keys can’t be used twice. If the key was completely random, the cryptanalytic difficulty would be equal to attempting every possible key.
A secret-key cipher obtains perfect secrecy if for all plaintexts (x) and all ciphertexts (y), it holds that Pr(x) = Pr(x|y). In other words, if a ciphertext (y) gives no information about the plaintext. To this day, no other encryption scheme is known to be unbreakable.
Cryptography for the masses
With the outbreak of the cold war, cryptography more or less disappeared from the public eye and moved into the basements of secretive government communications organisations. This lasted until roughly the mid 70s, when everything changed and extensive open academic research into cryptography began.
The main problem with the Vernam cipher and other private key ciphers was that they relied on keeping the key 100% secret. Somehow, both parties needed to get hold of the key, which would potentially involve some sort of courier (better known as ‘a security risk’). Furthermore, since it is not recommended to reuse secret keys, the number of keys that need to be distributed is proportional to the amount of data that need to be secured. This was exploding at an unprecedented rate.
In 1976, Diffie, Hellman & Merkle solved this problem by developing the first ever asymmetric cipher and thereby discovering public-key cryptography.
An asymmetric cipher is one that doesn’t use the same key for encryption and decryption. Therefore, it doesn’t need to be distributed. The way they did this was surprisingly simple. They split the key in two: a public key and a private key.
A public key system depends on relatively simple mathematical operations that are easy to perform and easy to reverse if you have the key information, but extremely time consuming and difficult to reverse engineer without it. The difficulty you would have reverse engineering these operations means the key that encodes the material can be shared on insecure channels. Using the public key, anyone can encode information and send it on, but only the holder of the private half of the key could decrypt it. Just one year later, Rivest, Shamir & Adleman published the first implementation of their work – the now-famous RSA algorithm.
Putting the crypto into cryptocurrency
Today, public-key cryptography is the basis for many of the systems that makes it possible for the internet to operate securely. It’s built into the internet protocols SSL/TSL, as well as encryption systems, such as PGP, that are necessary for internet users to send secure messages online.
In 2008, Satoshi Nakamoto applied the principles of public key cryptography in a way that hadn’t been done before – to money.
The idea of digital cash was not new in 2008. However, its previous iterations had all failed because they didn’t solve a key issue that’s common to all digital goods – they are infinitely copyable.
Think of a bank cheque. This needs your signature. For this signature to be considered secure, it must be verifiable as your own signature, counterfeit-proof so it cannot be forged, and impossible to deny by the signer later on.
Cryptocurrencies fulfil these requirements through the use of cryptographic techniques and encryption keys. They ensure the authenticity of the transaction and participant, like a real-world signature. They also make it so that only those for whom the data or transaction is intended for, can receive, read and process it.
The key technology that Nakamoto created to achieve this is known as blockchain. This underpins Bitcoin and the majority of other cryptocurrencies. The cryptography used in blockchain technology (specifically Bitcoin) uses public key cryptography for digital signatures and cryptographic hash functions. The cryptographic algorithm used for Bitcoin is called SHA-256 (Secure hashing function 256).
SHA-256 is used in several different parts of the Bitcoin network: Mining uses SHA-256 as the proof-of-work algorithm and it is used in the creation of bitcoin addresses to improve security and privacy.
SHA-256 in Mining
In order to find the hash number, Bitcoin miners use the SHA-256 Cryptographic Hash Algorithm. The data that a miner inputs into the SHA-256 hash function include all the current transactions which fit into the block’s size limit, the previous block’s hash result, and the nonce. The nonce is a random value the miner changes with each hash attempt to get a new output. Even a tiny change in input produces a completely different output.
Bitcoin miners are looking for an output with a certain number of zeroes. Today, Bitcoin miners have to find a hash which starts with nineteen zeroes. To get this number requires many, many attempts. Once the hash is found, the block is closed and it is added to the blockchain. After successfully mining a block, miners are rewarded with newly-created Bitcoins and transaction fees.
SHA-256 in private and public keys
The SHA-256 algorithm is also used to create private keys – a 256 bit-long string of numbers and letters used to prove ownership of Bitcoin. A private key is your way of saying “This address is mine, and I have access to it” It’s important to note that coins are stored on the blockchain and not within your private key. Keys are stored in wallets and therefore, coins are not stored in a cryptocurrency wallet.
A private key allows a user to authorise a transaction on the network. A private key that is an input for that algorithm will always produce its corresponding public key. For every private key that exists in Bitcoin, there is a 1:1 relationship with a public key. So every public key is also 256 bits long. The final hash (your wallet address) is 160 bits long.
In Bitcoin, private keys produce a public key via an Elliptical Curve Digital Signature Algorithm, or ECDSA. As it is an asymmetric cipher, the public key cannot be reverse-engineered to produce its corresponding private key. This is what makes it so secure.
The future of cryptography and cryptocurrency
Bitcoin is an incredible development in cryptography and an amazing application. But it is not the end. Cryptography will continue to evolve as the threat from code-breakers mutates. The next big threat is likely to be quantum computing. Google has a quantum computer that is 100 million times faster than any classical computer in its lab, which should give you some idea of its power and ability to overcome supposedly unbreakable codes.
However, cryptographers are constantly working to overcome these threats to security. Today, advances are being made in areas such as Zero-Knowledge Protocols, which are already being integrated into different coins. As we have seen across this series, cryptography is in a constant state of evolution. What comes next will be even more ingenious.
Do you have questions about blockchain and Bitcoin? Let us know on Twitter.