You're in a bar. The year is 2017.
Some slick looking tool wearing sunglasses indoors who probably owns way too many fidget spinners downs his last drink, draws a smug smile, and pulls out a phone with a QR code on it. Judging from his demeanor, you'd bet your left pinkie finger he's tried pulling this off before. Oh brother, you may think to yourself. Just because Captain Snazzy-Pants over here saw that somebody ordered a pizza with Bitcoin, he thought he'd go from bar to bar every night preaching the gospel of encryption in a fruitless attempt to pay off his tab, fully expecting to be tossed out or arrested, thus vindicating him as a rebel and an outcast of the system.
It's around this moment you doubtless pay off your dues with fiat and excuse yourself before the argument with the bartender gets too heated -- or worse, you have to listen to Captain Snazzy-Pants explain cryptocurrency with less nuance or accuracy than your local Boy Scout Troop Leader could. And you know full well he hasn't touched a computer without dial-up since before dial-up was even a thing.
And yet, as you stroll out of the bar, there's a very real possibility that the question hasn't yet left your head -- just how was that man planning on making a transaction happen? And more to the point, how exactly is it that some stupid bastard with more neopets than a Toys R' Us able to hold on to money without it being stolen?
Because there's something incredibly powerful about encryption. Be it currency, messages, or sensitive documents, it matters not. If encryption is performed correctly, absolutely nobody can break it. Not you, not me. Not the US government. Not China. Not Russia. Not any organization, public or private. Even if each of them were to conspire unanimously against you, cooperating perfectly since the dawn of the solar system to break into your encrypted data, they could not.
I think there's something beautiful about encryption. It may just be that I'm a mathematician with a passing interest for number theory, but I rather like the idea that -- by using nothing more than a fundamental understanding of the integer numbers -- anybody can produce a document or a transmission that no law, no policy, no force of nature short of the very rarest sliver of unadulterated bad luck can ever crack.
Except for you.
But how does it work? How does encryption allow us to see how much a particular wallet carries without being able to access it? How does encryption allow for anybody to encode a message while only allowing select few to decode it?
The Mathematics Behind Encryption:
Cryptocurrencies like Bitcoin or Etherium use what's known as asymmetrical public-private key cryptosystem. This means that if somebody posts their address on their websites, they can receive donations by anybody as though it were the tool of a libertarian OnlyFans account -- but only those who holds the private key are able to withdraw them.
The history of asymmetric public-private key cryptosystem is a fairly recent advent, in the grand scheme of computer science, even though it's built off of theorems dating back centuries. The first publicly revealed asymmetric public-private key cryptosystem was released in 1977, and dubbed after the initials of the three primary figures behind its inception: Ron Rivest, Adi Shamir, and Leonard Adleman. Although an equivalent system was developed by the British three years earlier by a man named Clifford Cocks, RSA would go on to become the norm for computerized encryption. It's so robust, in fact, that it's largely unchanged and still used today in applications everywhere: from messages in Telegram, to the web browser you're reading this essay on, to the cryptocurrency you hold in your wallet.
So without further ado, why don't we take a closer look at exactly how this fundamental encryption process works -- and how it applies to other uses.
Step One: Produce Some Prime Numbers
Here are a couple of four digit primes, along with their product. For rigorous security, it's important to have really really big prime numbers, but for the sake of this example, I chose a few that were a little bit more manageable. It's also good to have prime numbers that are of a different order of magnitude -- that is, I did an oopsie by making both my primes four digits in length.
The product of these two primes, "n" can be released to the public. It's a part of the public key.
Step Two: Find the Least Common Multiple of Each Number, Minus One
You're welcome to ignore the lambda (or "Half-Life 3 Confirmed" symbol, if you prefer) for now. It simply refers to the Carmichael function, which states that ?(n) is the smallest positive integer "m" such that am ? 1 (mod n) is satisfied. For those of you who are unfamiliar with modular arithmetic, you really aren't -- it's simply not framed in a context you're familiar with. If I asked you how tall somebody would be if they were 4ft 14 inches, you'd know immediately that they were actually 5ft 2 inches. That is, 14(mod12) ? 2.
Or rather, 22 o' clock military time is 10pm, since 22 ? 10(mod 12). (Let's use clocks for our examples, shall we?)
So why does our Carmichael Function for "n" produce the same result as the least common multiples of (p-1) and (q-1)? Well, it has partially to do with the nature of primes. Let's build some wacky clocks with more than twelve hours on them, and get to work on seeing what happens when we try to apply our primes.
Suppose we had some sort of clock that had seventeen hours on it -- a prime number -- instead of twelve. Let's start at midnight and jump forward some number of hours. Say seven hours.
You might notice that something especially peculiar happens to clocks with a prime number of hours to them. We're really used to the idea that if you wait six hours after midnight, and then wait another six hours, it'll be midnight again. Not so for a prime-number houred clock. In fact, as you might very well suspect, the only way to guarantee that this seventeen-hour clock will fall to midnight again is to skip forward seven hours seventeen times.
You're more than welcome to count the number of lines. And I'd certainly encourage you to try it for other numbers besides just seven and seventeen -- mostly just because I think the patterns they make are really pleasant to look at. But I can guarantee you, no matter how many hours we choose to skip ahead each time, so long as it's less than seventeen, it will always take seventeen cycles to return to midnight. This is because the number of, well, numbers that are less than seventeen but are relatively prime to seventeen are sixteen. Whenever you have a prime number "q", there will always be (q-1) numbers before it that share no multiple in common.
This least common multiple of (p-1) and (q-1) is incredibly special -- and as a result, must be kept secret. This is because it describes the amount of numbers less than one of our primes relatively prime, multiplied by the amount of numbers less than our other prime that are relatively prime. And so, for our number "n", there are (p-1)*(q-1) numbers that are relatively prime to it. This is also true of the least common multiple of (q-1) and (p-1) -- we're only choosing to use it here since it saves our brains, physical and computerized, a little bit of hassle. The product of ?(n) = (p-1)*(q-1) was actually the method described in the original RSA paper. But any miner out there will know of the importance of using an efficient algorithm.
Step Three: Pick some number "e" that is relatively prime to ?(n), but still smaller than ?(n)
We've come up with two prime numbers, determined the amount of numbers prior to each that are relatively prime, and found the least common multiple of these two new numbers. Now, we need to find another number between one and ?(n) (or ?(n) if you're old school) that is also relatively prime to ?(n) . I chose 47. Now, let n=5,654,399 and e=47 become public knowledge, broadcast to all Cryptocurrency Public Address systems, and pasted on donation pages.
Step Four: Find some number "d" that is the modular inverse of "e"
Imagine an even bigger clock. Not one with 17 hours, but with 2,824,620 hours. Since 47 is relatively prime to 2,824,620 -- that is, it has no multiple in common but 1 -- we could keep going around 47 hours at a time and not once fall back to midnight until we've gone around 2,824,620 times.
Now let d = 600,983. It should be noted that when we multiple 47*600,983, we get 2,824,621 -- just one greater than ?(n).
Now pretend you never saw the "d," because d is our private key. With it, you can decode any message provided by the prime numbers we've selected, and all of our encryption becomes entirely worthless.
Step Five: Encoding and decoding messages
Whenever we want to encode a message (represented by a string of numbers) we simply multiply it by itself 47 times and take whatever remainder we have left after we keep subtracting 5,654,399. This is our encoded message.
To decode a message, we take what's encrypted, multiply it by itself 600,983 times and take whatever happens to be left after we keep subtracting 5,654,399.
Here's a simple encoded and decoded message I did with my cousin. The letters used were simply converted to numbers (a = 01, b = 02, ... , z = 26) and most importantly, each encoded segment did not surpass seven digits in length. For extra security, we conveniently forgot that the letter M is not the same as the letter L, and the letter O was not the same as the letter P.
You know, totally intentional stuff.
And this will always work, too. And if somebody doesn't know your private key, they (or their computer) will be forced to do a lot of multiplying and subtracting, multiplying and subtracting to find the right answer.
How much multiplying, you might ask? How many guesses will it have to make?
Cryptocurrencies like Bitcoin and Etherium aren't secured with RSA. But they still rely on an asymmetric public-private key cryptosystem. The receiving end is the "public key" and the sending end is the "private key". These are actually rather well illustrated, I think, on a paper token. While they don't use RSA exactly, they're secured with a not-dissimilar but far more rigorous cryptographic hash function called SHA-256. This means the results of the private key takes the form of a number, converted to binary, and represented as a string of 2256 ones or zeros.
In other words, they'll be making about...
57,896,044,618,658,097,711,785,492,504,343,953,926,634,992,332,820,282,019,728,792,003,956,564,819,968 guesses.
I don't think it's too much to say that 2256 is quite frankly a ridiculous amount of guesses. If your computer did one guess a second (it does slightly more than that) then it might take 18,822,840,140,793,441,047,579,032,883,486,772,370,030,623,287,563,814,118,981,738,973,404 centuries to find the right answer. And the fact that those two numbers don't look meaningfully different to me in length is some cause for concern. At least for hackers. It's reassuring to me. To say that never in a hundred-billion years would somebody be able to steal my cryptocurrencies is an optimistic understatement.
You're free to stop reading my crazy ramblings here and go on to more important business, such as trading coins or drawing cool patterns in circles. I might certainly be content with this explanation. But you might be unsatisfied with the amount of hand-waving I'm providing. Some may demand proof. Why is it that this works? And why haven't I heard anything about a French Lawyer yet?
Well, say hello to Pierre de Fermat. He was a French Lawyer of Parlement in Toulouse.
I rather like how he's rocking the bib. Go ahead and try to find a picture of him without it, I dare you.
Fermat produced a wealth of mathematical discoveries, in fields ranging from probability, optics, and perhaps most notably, number theory. He produced a little theorem, and titled it as much. I'm of the mind to think that if there were ever a reason to mint physical tokens of cryptocurrencies, at least one of them ought to have Fermat little theorem engraved upon it. Here is it now.
a^p? a (mod p)
So what is this saying? In short: for any clock with a prime number of hours -- such a 17 -- if you were to take any number of hours and skip forward that many hours seventeen times in a row, then your clock would land back on exactly the same number you started on.
There's a direct corollary to this, of course. If you take the number you landed on when you finished and went back one step, you'd end up at "midnight"
a^(p-1)? 1 (mod p)
Think back to our encrypted message, (m)^e. We can reason that (m)^(e*d) ? m(mod p*q) since taking the encrypted message and applying our private key, "d," decrypts it.
Now the least common multiple, lcm(p-1, q-1) is by definition something that's divisible by both (q-1) and (p-1). It has to be, otherwise it wouldn't be a common multiple, much less to say the least common multiple. This means, for some non-negative integers a and b,
e*d-1 = a(p-1) = b(q-1)
Now to ensure that I'm not blowing smoke and that I mean it when I say that (m)^(e*d) and m are on the same place on our "clock," we can check to see that the same follows for clocks with q or p hours on them. For this, we have two possibilities.
- If "m" is zero, then there you go. "m" is a multiple of p. So is (m)^(e*d), whoop dee doo.
- If "m" is not zero, then (m)^(e*d) = (m)^(e*d-1)*m = (m)^(a*(p-1))*m = ((m)^(p-1))^(a) m= (1)^a * m
And since 1 times itself any number of times is equal to one, we can conclude that m ? m(mod p).
You're welcome to do the same exact thing for q and a, and I guarantee you the exact same result. For any integer m, and integers e, d such that ed ? 1 (mod ?(p*q)), we will always have (m)^(e*d) ? m(mod p*q)
It's for this reason, because of this little theorem, that you and I are able to exchange cryptocurrencies. Because of this individual, we can send encoded messages to one another, and not a single other person could determine what we were saying.
Because of Fermat, secure banking, online privacy, drug trades, safety from domestic abuse, terrorism, whistle-blowing, and journalism in totalitarian nations are all possible.
Thank you, Fermat. I appreciate it.
