Encryption is a fun and useful tool. It’s not magic; it’s just math. If you’re reading this content directly from my web site, you’re reading it over an encrypted connection. The words started out on my web server, got encrypted, sent over the Internet where many different servers and people could be listening, and ended up in your browser. Yet because of encryption, only you can read the words.

I have tremendous respect for United States legislators, especially at the Federal level; however, I wonder if perhaps they sometimes attempt to pass ill-conceived laws before understanding the situation into which they’re legislating and the implications of their legislation. Consider the recent Compliance with Court Orders Act of 2016, sponsored by Senators Richard Burr (R-NC) and Dianne Feinstein (D-CA), the chair and vice-chair respectively of the Senate Select Committee on Intelligence. An article in The Hill quotes Senator Feinstein as follows:

I think this world is really changing in terms of people wanting the protection and wanting law enforcement, if there is conspiracy going on over the Internet, that that encryption ought to be able to be pierced.

Normally I find myself in general agreement with Burr and Feinstein on most issues, and I respect both of them because they seem to me to both genuinely care about the real safety and security of the United States. They both put reality above politics. Unfortunately, this bill and Senator Feinstein’s quote demonstrate how little they understand about encryption.

Encryption is Not Magic

Encryption is not magic. Encryption is just math. Math is a pesky thing, immutable by law. You can’t pass a law that makes 6 times 9 equal to 42 (at least in base-10). Math is an idea, and you can’t realistically make math or an idea about how to use math illegal. That is to say, you can’t pass a law that bans an idea about how to use math and expect everyone to play along.

Ever since I was a small child, maybe sometime in elementary school, I’ve loved playing around with “encryption,” encoding and decoding content. It started with the equivalent of the secret decoder ring solution, then progressed through symbolic substitution, pattern overlays, and even hiding messages in semantic calligraphy. I learned about the Enigma machine and how Bletchley Park hacked it. It wasn’t until I was working with computers in a major way before I really dove into real encryption.

I’m no math wizard. Far from it. I’m a pretty good software engineer, but it turns out you don’t need to be either to make use of encryption. To help prove my point, let’s encrypt and decrypt some data using the RSA cryptosystem.

The RSA Algorithm

The RSA cryptosystem is one of the older systems, if not the oldest public/private key encryption system. A public/private system starts with the creation of a public encryption key (used to lock things by encrypting them) and a private decryption key (used to unlock things that are encrypted). You can freely pass around the public key because it can only lock things, it can’t unlock things. Only the private key, which you keep secret, can unlock things.

The RSA algorithm may seem at first to non-math people (myself included) to be complex, but it’s really not. We can walk through the whole thing using simple calculations we can do with pencil, paper, and a calculator. At the same time, I’ll write some (very simple, non-strict) Javascript to demonstrate how software might implement (in a very basic way) the algorithm.

In practice, we’d never do this; we’d use a software library, because the numbers get very large very quickly. They get so large that our hand-held calculator and even the Javascript language itself can’t natively handle the math without resorting to some computer science tricks which would make the Javascript examples I’ll provide no longer simple. The goal in going through this is to just demonstrate that encryption is just an idea about how to use math.

Creating a Public/Private Key Pair

The first thing we need to do is create a public and private key pair, which is the most difficult part of the process. The actual encryption and decryption thereafter is easy. To start, we need to pick some prime numbers. The larger the prime numbers, the better. You can find some good prime numbers on the University of Tennessee’s web site. However, we need to pick very small primes to make the math work. For our paper solution, let’s pick 3 and 11. Our Javascript to pick primes might look like this:

primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ];

p = primes[ Math.floor( Math.random() * primes.length ) ];
q = 0;

while ( q == 0 || q == p ) {
    q = primes[ Math.floor( Math.random() * primes.length ) ];
}

We’re going going to allow selection of primes up to and including 29 because even if we pick 23 and 29 as our two primes, this Javascript should work properly in common browsers. Beyond 29, the math gets too large without some trickery. Also, if you don’t understand that whole Math.floor( Math.random() * primes.length ) thing, don’t worry. It just means, Pick at random one of the entries in the array.

Product and Totient of the Primes

Now we need to calculate the product and totient of the two primes we picked. As a non-math person, I asked, “Um, what does that mean?” A product is just multiplication. A totient is a term that refers to Euler’s totient function. Here’s the Javascript:

n = p * q;
t = ( p - 1 ) * ( q - 1 );

So for our paper version, we’ll get an n of 33 and a t of 20.

Pick a Coprime Integer

Next, we need to pick an integer that’s bigger than 1 and less than t. The integer we pick needs to also be coprime to e. The coprime concept just means the two numbers share no common factors.

For our paper version, picking is easy. We can just walk through the numbers between 1 and t non-inclusive, testing for values that are coprime. We can pick 7, 11, 13, 17, or 19. We can’t pick 5, for example, because 20 is divisible by 5. To keep things simple, we should pick the smallest number, which is 7.

For the Javascript, we could implement the same test as our paper version, but for larger primes, the work required of the computer gets large. So we can use a side-step. We can use the extended Euclidean algorithm. This is what it looks like in Javascript:

e = 2;
while (true) {
    e++;

    _e = e;
    _t = t;
    if ( _e > _t ) {
        _t = e;
        _e = t;
    }

    while ( _t % _e != 0 ) {
        a = _t % _e;
        _t = e;
        _e = a;
    }

    if ( _e == 1 ) break;
}

The while (true) bit means run the code inside the curly brackets over and over forever. We end up breaking out of this infinite loop when _e is 1 because of the if ( _e == 1 ) break line.

With this part accomplished, we’re done with the work needed to create a public key. Our public key is a combination of n and e.

Calculate the Private Key

The private key is just another number, but it’s a bit more complicated to calculate. We need to calculate d to satisfy the congruence relation d * e % t = 1. If you’re not familiar with the % thing, it’s not a percentage. It means the modulus of two numbers. In other words, if we take 11 and divide by 5, we get 2 with a remainder of 1. Therefore, 11 % 5 = 1.

So let’s solve d * e % t = 1 with e of 7 and t of 20. If we pick 3 for d, then d * e is 21, which divides into t once with a remainder of 1. The remainder of 1 is what we’re looking for, so we’re good with d being 3.

To do this with Javascript is fun. There are smarter/faster/better ways to do this than what I’ll show you here, but this is probably the easiest to read and understand for non-developers.

u1 = 1;
u2 = 0;
u3 = t;

v1 = 0;
v2 = 1;
v3 = e;

while ( v3 != 0 ) {
    _q = Math.floor( u3 / v3 );

    t1 = u1 - _q * v1;
    t2 = u2 - _q * v2;
    t3 = u3 - _q * v3;

    u1 = v1;
    u2 = v2;
    u3 = v3;

    v1 = t1;
    v2 = t2;
    v3 = t3;
}

d = ( u2 < 0 ) ? u2 + t : u2;

The Math.floor method is Javascript's way to round-down a number. So if you have 2.7, it becomes 2.

Now we're done with the work needed to create a private key. Our private key is a combination of n and d.

Encrypting and Decrypting

Let's pick some data to encrypt. Data can be any integer, but we're limited to integers that are less than n. In our paper example, we have an n of 33, so let's pick 14 as our message. To encrypt our payload, we use the following formula: message ^ e % n. This gives us a value of 20, which is our encrypted content.

In Javascript, we can't use the little hat symbol for to-the-power-of. We have to use a function that does the same thing.

encrypted = Math.pow( message, e ) % n;

To decrypt, we use a similar formula: encrypted ^ d % n. In Javascript, this is:

decrypted = Math.pow( encrypted, d ) % n;

Slightly More Complicated

For the on-paper example, this is sufficient to describe the process. However, there are some edge-cases in the Javascript solution where this breaks down. So here's some example Javascript for randomly selecting a data payload, encrypting it, and then decrypting it. This will always work provided we pick primes at and below 29.

message   = Math.floor( Math.random() * ( n - 2 ) ) + 1;
encrypted = Math.pow( message, e ) % n;
decrypted = ( d % 2 == 0 ) ? 1 : encrypted;
for ( var i = 1; i <= d / 2; i++ ) {
    decrypted = ( ( ( encrypted * encrypted ) % n ) * decrypted ) % n;
}

Don't Do This in Reality

This is all presented just to demonstrate how the math works at a basic level. You'd never, ever want to actually encrypt or decrypt data this way for a variety of reasons. In practice, you'd want use large primes, not small primes, because doing so significantly increases the difficulty of cracking the encryption with brute-force attacks. You're going to want values of n that are very large because it means you can encrypt larger payloads. You're going to want a means to break apart content that's larger than n, encrypt each part, then merge the parts together. All of this and much more are critical considerations for a real-world encryption algorithm.

That said, in principle, this is how the bare or core part of the encryption process works.

The Point... Finally

My point here is that it doesn't take a genius to implement basic encryption. There are numerous public, free, and open-source software libraries that provide the means for software engineers. For everyone else, there are numerous public, free, and open-source applications you can download and use safely.

Legislation that attempts to force the creation of "backdoors" to encryption or to, in Senator Feinstein's words, "pierce" encryption will only result in some applications that have a way for the United States Federal government to decrypt content. There will always be public, free, and open-source applications that don't comply. To borrow part of the quote from Senator Feinstein, "if there is conspiracy going on over the Internet, that encryption" won't use applications that have a government "backdoor" included.

Legislation that attempts to force these things is similar to legislation that bans people talking about Star Trek. To quote the Borg, "Resistance [to encryption] is futile."

To be fair, the Compliance with Court Orders Act of 2016 doesn't outlaw encryption that doesn't include a government backdoor. What it does is even less rational. It says that a company like Apple, Microsoft, IBM, or HP must help the government crack the encryption of any device that government wants cracked if asked to do so by a court order. The problem is that software can run on devices from Apple, Microsoft, IBM, or HP that use a clean implementation of the RSA algorithm, making it no more possible for Apple, Microsoft, IBM, or HP to crack the encryption as compared with the government.

You can't outlaw an idea. Math is an idea. Encryption is math.