# THE CRYPTOGRAPHY BEHIND BITCOIN

Bitcoin relies on cryptography to function, which is why it is sometimes called a *cryptocurrency.* But what role does cryptography play in Bitcoin, and why is it needed? We'll begin with a short introduction to some necessary cryptography concepts (if they are familiar to you, you can just skip to "The Reasons Bitcoin Needs Cryptography" on page 137), and then we'll explore the specific cryptographic methods used in Bitcoin.

If you flipped to this chapter only because you wanted to know whether the cryptography used by Bitcoin is safe, you can rest easy knowing that Bitcoin uses only tried-and-tested cryptographic techniques: All of the cryptographic methods used by Bitcoin have been widely used in the past by governments and major corporations to secure financial, medical, and other sensitive information, as well as personal identification data.

In fact, the cryptography in Bitcoin could be described as *boring,* simply because it relies on very conservative cryptographic algorithms. But in some fields of study, such as accounting and dentistry, boring is good; in the case of Bitcoin, conservative and well-established cryptography helps make it more secure. The interesting part is what Bitcoin *does* with cryptography.

Fortunately, as you'll see, although Bitcoin cryptography may be old hat to the experts, it is still immensely fascinating to a novice!

## A Brief Cryptography Overview

Historically, cryptography was used to send secret messages when necessary to protect information. Messages were systematically scrambled, or *encrypted,* in a way that hopefully only the recipient of the message knew how to *decrypt.* A well-encrypted message might be intelligible as battle plans to the intended recipient, but to anyone else it would just be a well-tossed word salad with a side order of alphabet soup. Historically, encryption and decryption were laborious tasks and were reserved only for secure clandestine communication (usually of a military or illicit romantic nature). With the advent of computers, which could do in milliseconds what used to take hours manually, cryptography is now used routinely by the masses to encrypt/decrypt very important (e.g., financial) and not-so-important (e.g., pay-per-view TV) communication. Perhaps surprisingly, the convenience and speed of computers has led to the adoption of cryptographic methods for more than just encrypting secret messages. Common examples include logging in to websites with a username and password combination and using a registration key to install software. Both use cryptographic methods, but no message encryption is involved in either case.

In addition to encrypting messages, modern cryptography is used to verify the validity of information (through *cryptographic hash functions)* and to prove one's identity (through *digital signatures).* For example, without modern cryptography, you wouldn't be able to distinguish between two identical websites that both claimed to belong to your bank. One might be phony and run by thieves to steal your money. But only your bank's website can provide the correct digital signature. Before we explain how digital signatures and cryptographic hash functions work, let's explore one-way functions, a feature that both rely on.

### One-Way Functions

*One-way functions* are mathematical functions that make it easy to calculate an output based on the input but difficult to do the reverse. A precise mathematical definition of what is easy or difficult doesn't exist but depends on the complexity of the calculation and the effort required to solve it.

A typical example is called *integer factorization,* which asks you to write an integer as the product of only prime numbers—for example, the factors of 6 are 2 and 3, which are both prime. Given the prime factors as input, it is easy to multiply them to produce an output integer, but the reverse is not true (at least for larger numbers). Given a large integer, finding its prime factors is very difficult. The only known methods involve systematically guessing different combinations of prime factors, but the amount of time required to find the right answer increases exponentially with the number of digits. Imagine trying to multiply 2 x 7 x 7 in your head. It is not that difficult to calculate the answer of 98; however, if you were given the number 98 and were required to find its prime factors, generating 2, 2, and 7 would be more difficult. A typical laptop can factor a 60-80 digit number in less than a second, but the required time grows exponentially: To factor a 300-digit number or greater would take a modern supercomputer decades.

Another one-way function, which is a bit more complicated but is commonly used in cryptography, involves the *discrete logarithm.* Consider a set of integers {0, 1, 2, 3, ... , *n* - 1} where *n* is a prime number and where we only use modular arithmetic with modulo *n:3*

hour hand on a clock once it moves past 12; instead of pointing to 13, it starts over and points to 1. However, whereas clocks start over at the number one, the common convention among mathematicians is to start over at 0. So 3 + 6 = 9, but 3 + 6 (mod 7) = 2 because after reaching 7, the next three numbers are 0, 1, and 2.

It is easy (as in, you can do it with a pocket calculator) to raise an integer, *a,* to the *k*th power to calculate the integer *b:*

However, the discrete logarithm, which is finding *k* given only *a, b,* and *n,* is difficult to calculate. The only known methods to find *k* are variations on trying to guess every value between 0 and *n* that satisfy the preceding equation. The larger the value of *n,* the harder it is (and the more time it will take) to calculate *k.*

In the early days of computers, people started applying the asymmetry in these one-way functions to build various classes of cryptographic algorithms, which is what we'll discuss next.