Cryptographic Methods Used in Bitcoin
Public key cryptography is a high-level framework that can be implemented many different ways. You learned how the RSA method, using integers factored into large prime numbers, could be used to implement digital signatures. But how are digital signatures implemented in Bitcoin? Many different cryptographic hash functions exist, and although the MD5 method mentioned earlier is widely used, it is not sufficiently secure for a cryptocurrency (collisions have been detected in MD5, resulting in two different inputs leading to the same output).
SHA256 and RIPEMD160 are the two cryptographic hash functions used in the Bitcoin protocol.
Cryptographic Hash Functions: SHA256 and RIPEMD160
Secure Hash Algorithm (SHA) was developed by the US National Security Agency (NSA). Race Integrity Primitives Evaluation Message Digest (RIPEMD) was designed in the academic community by Hans Dobbertin, Antoon Bosselaers, and Bart Preneel at the Katholieke Universiteit Leuven.
The prefixes SHA and RIPEMD refer to the underlying algorithms, and the numerical suffixes 256 and 160 refer to the bit-length of the output. A spectrum of other SHA functions, like SHA224 and SHA512 output other bit-length hashes as well.
Both SHA256 and RIPEMD160 are widely used, but the SHA methods are more popular and have undergone a higher degree of scrutiny from cryptographers. At the time of this writing, nobody has detected a collision in either SHA256 or RIPEMD160, which is an important measure of the security of a cryptographic hash function.
In the Bitcoin protocol, SHA256 and RIPEMD160 are used together to protect the public key used in digital signatures. The SHA256 method is also used for the proof-of-work function in Bitcoin mining and as part of the digital signature algorithm. Here are some examples of encrypting a sentence with a slight variation in both SHA256 and RIPEMD160 (all of the following outputs are in base 16 format):
A completely different result is produced with a single character change:
The same happens using RIPEMD160:
This hash is completely different:
As you'd expect and appreciate in an effective hash function, a minor change to the text (capitalizing the word Island) completely changes the resulting hash value in both methods.
Now that you understand the hash functions Bitcoin uses, let's discuss the algorithm Bitcoin digital signatures use.
Crowley and the Unfortunate Jelly-Filled Donut Incident
For the remainder of this chapter, we'll discuss the details of elliptical curve cryptography (ECC). But before we delve into the details of this algorithm, and to help you understand the basic concept behind it, let us tell you a story.
One day Crowley was driving through Cryptoville in his car, minding his own business, when suddenly, BAM! His car was thrown into the air!
He had been driving by a donut shop that was trying to beat the world record for the largest jelly-filled donut. Unfortunately, the bakers miscalculated the correct pressure of jelly to inject into the donut, causing the explosion.
After tumbling through the air, Crowley landed safely and was relieved to realize he wasn't hurt. However, he was a bit shaken from this frightful incident, and his car was covered in jelly. Because he had tumbled through the air, he was lost and no longer knew where he was in Cryptoville. What was he going to do now?
Suddenly, Satoshi stepped out of a nearby house. Quite by accident, Crowley had found out where the secretive Satoshi lived!
Crowley proceeded to explain to Satoshi what had happened to him and his car. Satoshi was concerned to hear that Crowley was lost but also a bit relieved because it meant that his home address was still a secret.
Crowley asked Satoshi to give him a ride home or call a tow truck. But Satoshi refused, saying, "If I do either of those things, you'll be able to figure out where you are in Cryptoville, and then you'll be able to figure out my secret home address. Luckily I have another idea: Why don't you come into my home as a guest and enjoy a cup of coffee as you regain your wits from your harrowing experience today. I'll be back in a couple of hours and will then share my plan to get you and your car home again."
Sure enough, Satoshi returned to the house after a while carrying an iPod, of all things. "OK, Crowley, here's what I did. I just drove to your house with my own car. While doing so, I recorded my drive on this iPod and recorded every action as I drove along. When I turned the steering wheel 10 degrees to the left, I said this on the recording. If I accelerated from 20 mph to 40 mph, I recorded this as well. Everything I did I recorded at the exact time I did it."
Crowley then understood the plan: Even though his car was covered in jelly and it was impossible for him to see through the windows, he could still follow the simple instructions on the tape. After all, his car motor still ran fine, and he could see the speedometer on his car's dashboard. Satoshi added, "It'll be very hard for you to reverse engineer the exact physics of how the car was driving based solely on the instructions I recorded on the iPod. Therefore, the location of my home will remain unknown to you. However, to make it extra hard, I also took a very circuitous route, driving through almost all of Cryptoville along the way to your house!"
But sure enough, using Satoshi's iPod, Crowley was able to drive his car back home without being able to see a thing through his car windows. He simply followed the instructions, and when the recording finished, he was back home. He still didn't have the slightest clue where Satoshi lived, and he miraculously avoided hitting any pedestrians or other cars in the process!
To thank Satoshi for helping him, Crowley sent Satoshi an email inviting him to lasagna at Crowley's house on Saturday night and asking him to suggest a time for dinner. Here is the email Satoshi wrote back:
Thanks Crowley—Dinner sounds great, and I love lasagna! Let's meet at 9:25 p.m.
Oh, and to prove that this email is legit, I can tell you that I was on the 300 block of Main Street driving north at exactly 38.7 mph when the iPod displayed 9 minutes and 25 seconds.
Being a stickler for verifying identities, Crowley tested this fact: He first had his car (still covered in jelly) towed to the location mentioned in the email and then started the iPod at the 9 minute and 25 second mark. Following the instructions on the iPod explicitly until they completed, he once again stepped out of the car and found he was back at home!
This silly parable is meant to give you a rough outline of one way you could create a digital signature: Imagine that Satoshi's home address is Satoshi's private key, and Crowley's home address is the public key. The instructions on an iPod are a one-way function that's difficult to reverse. Using this information, you could sign an arbitrary message (in this case the number 925, which corresponds to the meeting time). Only the person who knows the private key (Satoshi's home address) could generate this signature.
As you'll see, with ECC, we'll instead "drive around town" by jumping between points on a special two-dimensional curve, which makes it even harder to reverse engineer the directions. However, the overall process will remain roughly analogous to that in the story.
-  Hans Dobbertin, Antoon Bosselaers, and Bart Preneel, "RIPEMD-160, a strengthened version of RIPEMD," in Fast Software Encryption, ed. Dieter Gollmann (Berlin: Springer-Verlag, 1996), 71-82.