Cryptography Crash Course

Morning, everyone. Or, good afternoon. Happy midnight? Close enough.

I've been sitting here at my computer for about two weeks now, on and off, just keyboard smashing all sorts of content out for the site. My fingers feel like they're about to fall off, but right now I have this wave of motivation to make content which I know doesn't come often. I want to take advantage of the situation, as I know I won't have time to write once classes start, so for now I'm cool being planted at my desk during my free time.

Some of the articles I'm working on right now have sections that focus on some pretty advanced cryptography, which I feel needs plenty of explaining and background to make them easier to understand. I found that when I included crash courses in each of my articles to bring readers up to speed, the word count quickly skyrocketed to unacceptable levels. I still believe that a solid background is necessary to truly understand some of these topics, so I decided to splinter the crash courses off into their own post to give crypto the room it needs to breathe.

With that said, this is my crash course on cryptography! Most of the basics and some intermediate topics from my cryptography classes are covered. If you're able to understand the concepts in this article, then I believe that you're roughly about the same level of understanding as a typical computer science undergrad. Hopefully, this understanding will make my other posts easier to parse. I hope you enjoy!

Basic Terminology

Before we go any further, here are some basic terms you'll need to know. These are fairly common phrases in the cryptography scene, so knowing them will be extremely useful:

• Plaintext - Ordinary, readable data before it is converted into ciphertext, or after being converted back from ciphertext.
• Ciphertext - The encoded version of a plaintext message.
• Encryption - The process of converting plaintext into ciphertext.
• Decryption - The process of restoring the plaintext from the ciphertext.
• Cipher - Another term for an algorithm used to encrypt/decrypt information.

Symmetric Encryption

First off, people have been using ciphers to encode information since way before cryptography was even a concept in most people's minds. The oldest known cipher, the Caesar Cipher, was developed around 100 BC, which is well over 17 centuries before the term "cryptography" was even coined. For almost as long as major civilization itself has lasted, the ability to securely communicate has been desired.

Back then, all ciphers were symmetric. A symmetric cipher has only one key, which is used in both the encryption and decryption processes of the cipher. (Think: passwords.) In the aforementioned Caesar cipher, the key is the number of shifts each character in the message makes while encoding or decoding.

For example, the image above describes shifting all characters in the alphabet three spaces to the left. Now, any letter E in our plaintext would become a B in the ciphertext; D would become A, C would become Z, and so on. Following this process, "Hello World!" would now be encrypted as "Ebiil Tloia!"

However, this cipher has one major flaw that make it pretty weak. There are only 26 possible permutations of any given message, as there are only 26 shifts we can make before the letters line up again. Therefore, it's trivial to decrypt any Caesar cipher by just trying to calculate all of the possible versions and seeing which one is legible. (i.e. Brute-force attack)

We can use another cipher like ROT13, a mono-alphabetic cipher, to tackle this issue. Where the Caesar cipher introduces the idea of transposition (i.e. shifting), ROT13 introduces substitution.

Instead of just shifting the alphabet, how about we create a mapping of characters to each other, and use that as a key to encrypt our message? ROT13 uses a standard arrangement, but if we make a random mapping, then our number of possible keys goes from a measly \(26\) to \(26!\), roughly equal to 403 septillion possible keys.

However, mono-alphabetic ciphers aren't bulletproof either. Due to the way that the English language has developed, certain letters appear more commonly than others. We can use this knowledge to attack the mono-alphabetic cipher. Take a look at the graph below:

This graph depicts the relative frequency of each letter within all of the words in the English dictionary. We can see that the letter E seems to be the favorite letter, while Z and Q are the least favorite. Likewise, if you look at any ciphertext encoded using a mono-alphabetic cipher, you'll probably see that certain letters appear more than others as well. We can compare these two graphs to try and find out a key.

For example: If you see the letter T shows up the most in your ciphertext, you can infer that it's is probably mapped to E. Inversely, if you see that F is the least common, you can probably infer it's mapped to Z or Q. Using this trick, in combination with identifying ciphered forms of frequently used common letter combinations ("th", "the"), you can slowly whittle down the possible plaintexts into a set that can be easily brute forced.

Over the many centuries that symmetric encryption was king, many ciphers would take a stab at combining both transposition and substitution to make a secure cipher. There was Playfair, Vignere, One-Time Pad, and the infamous Enigma Machine just to name a few. Unfortunately, each of these would grow to have design inconsiderations or mathematical loopholes that would be revealed and make them vulnerable or infeasible.

Nowadays symmetric encryption is still used, but its security is mainly a game of cat and mouse between the mathematicians who design the symmetric algorithms and the computer engineers who build systems powerful enough to break them. There are many ciphers that are currently considered secure; AES and ChaCha20 are two examples. These ciphers still have their uses, mainly when it comes to securely storing or transmitting large amounts of data, but they're not infallible by themselves.

The most notable vulnerability of every symmetric encryption scheme doesn't even involve the algorithms themselves. Kerchoff's assumption states that we should assume any adversary already knows the entire system used for encryption, minus the secret key. If this key were to be compromised, then the entire system would fail. Therefore, distribution of the key now becomes the most crucial part of symmetric encryption.

If we were to tell the other party our key in person, who's to say there isn't an eavesdropper? Through the mail? Someone could open our letter, read it, then reseal it in an identical envelope. Telephone? Could be wiretapped. Over the internet? Given the key must be transferred in plaintext, a man-in-the-middle attack can intercept it.

What if we encrypt the key using another scheme before transferring it over the internet? Then our system now becomes dependent on how secure this other scheme is, because once that other scheme gets cracked, then it can be used to decrypt this key and all of its data too. And if this other cipher's key is also subject to the same vulnerable means of transmission as the original, then what's the point?

We need a better way of deriving these shared keys. Hold that thought!

Asymmetric Encryption

Fast forward to the 1970s, and the idea of asymmetric cryptography is introduced. This system works by issuing not one, but two keys to each user in a given environment. Each key pair is also derived in such a way our system now meets 3 criteria:

1. Encryption and decryption now become one-way processes
2. Any data encrypted using one key can only be decrypted via the other key in its pair.
3. It's impossible to glean any information about one key by looking at the other in the pair

Essentially, this means that we now have one key to encrypt, and another to decrypt. A common analogy used to describe this kind of system: The encryption key is a lock, and the decryption key is... well, the key. You and anyone else can attach the lock to any data you want, but only you— the key holder— can unlock it.

Condition 3 of the list above also tells us something indirectly: our metaphorical lock contains no information that can be used to figure out what the key is. Therefore, it is totally safe to can hand out copies of this lock to everyone we know! By doing this, we've now created a public key cryptosystem, and we're able to do a lot of cool things with it!

RSA Deep Dive

Let's briefly take a look at a public key cryptosystem in detail. An common public key cryptosystem used nowadays is the Rivest-Shamir-Adleman cryptosystem. RSA makes major use of modular arithmetic; if you're unfamiliar with the subject, here's a good Khan Academy article on the basics.

Essentially, RSA works due to the premise that we can derive two integers \(e\) and \(d\), such that if we raise some message \(M\) to the power of \(e\) and \(d\), then find the remainder when it's divided by some number \(N\), the remainder will be equivalent to \(M\). Essentially, RSA implements the following equation:

\[(M^e)^d \equiv M (\bmod N)\]

I won't get into key derivation today, but in case you're interested, I'd suggest watching this extremely informative 2-part series from YouTube math teacher Eddie Woo. It seriously helped me understand how RSA works. For now, all you need to know is that keys in RSA are distributed as a pair of numbers, called the exponent and the modulus. In most documentation, you'll commonly see these notated in the format \((e, M)\) or \((d, M)\).

Enough lore, time for the example. Given a properly derived key pair, the diagram below steps through the encryption and decryption processes within RSA:

It's important to note that in practice, these numbers must be extremely large to be secure. All RSA keys must have moduli and private exponents with at least a 1024-bit length, with most keys now opting for 2048 bits or higher.

Quick Aside: RSA in Practice

For the technically inclined, let's take a look at how these keys are actually created and stored on most systems. For those of you who don't care to know technical details, go ahead and skip to the next section.

Start by logging into a Linux environment and generating a new key using the ssh-keygen commend line tool. For the sake of example, we'll be making a 1024-bit RSA keypair called test_rsa:

$ ssh-keygen -t rsa -b 1024 -m PEM
Generating public/private rsa key pair.
Enter file in which to save the key (/home/azure/.ssh/id_rsa): test_rsa
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in test_rsa
Your public key has been saved in test_rsa.pub
# ... snip ...

Take note of the -m PEM flag there, as that means we would like to store our key it in the PEM (PKCS#8) format, rather than OpenSSH's own key format. We do this because the PEM format allows our keys to work interoperably with OpenSSL's tools, which we'll now use to see what the contents of our key file are:

$ openssl rsa -inform PEM -in test_rsa -noout -text
RSA Private-Key: (1024 bit, 2 primes)
modulus:
    00:bb:6e:61:36:11:9f:5c:c7:9b:67:a8:16:f9:fb:
    cb:c1:5d:9b:8d:27:ba:e4:cb:d0:8c:a0:e8:e9:b9:
    ef:b5:65:ab:dc:3a:76:ae:e7:d0:1e:4d:58:12:e9:
    69:61:50:b4:5a:4b:2b:dc:e1:89:8a:a5:40:4e:49:
    21:90:90:11:26:36:d8:37:d8:15:e9:3b:c6:09:de:
    a8:89:4e:77:dd:61:c3:05:d6:74:d5:0e:9d:0e:c8:
    d0:58:a9:48:c4:58:30:34:7e:d5:a6:3a:7f:01:9b:
    b8:92:81:94:39:f8:70:cf:34:b7:8c:b9:0a:2e:e0:
    fc:dd:e9:05:b9:56:23:fe:c7
publicExponent: 65537 (0x10001)
privateExponent:
    00:ba:76:2f:03:89:38:8f:26:8c:b5:ec:85:1f:20:
    9e:2d:ba:20:3b:a7:20:c8:e8:f2:8a:54:b2:21:83:
    36:b3:b1:77:ed:d9:c3:a4:71:3d:9c:47:b9:ac:e6:
    c4:4d:69:ea:62:41:92:5b:65:8c:5d:7f:d4:9f:8d:
    25:75:19:bd:d4:1e:2a:a0:fe:5e:48:17:96:a4:b0:
    18:99:d8:e2:e7:4c:b6:b2:74:a1:b9:ab:2d:8d:08:
    9b:dc:29:5b:03:5d:6b:8b:75:a3:fe:71:a1:c7:af:
    85:e4:36:c2:4f:1a:d3:ee:44:69:fa:05:e3:d8:64:
    92:87:24:ce:5d:dc:fd:1a:11
# .. snip ...

Our key, when read out, has a 129 byte modulus. If we get rid of any leading zeroes, we're left with 128 bytes, or exactly 1024 bits. We can analyze what our modulus's numerical value is by converting the number from hex into decimal.

Sure enough, there is our 1024-bit modulus in decimal form, and it sure is uncountably long! If you want, you can repeat this same python decoding procedure with our private exponent value as well. You'll probably find it's just as long.

Now that we've analyzed the private key, let's repeat the process on our public key. First off, the .pub file that is generated for us is not in a standard format, so we'll need to re-derive our public key file in PEM format. We can achieve this using our private key. Then, we'll analyze our public key as we did with the private key, this time adding the -pubin flag to let OpenSSL know we're parsing a public key.

$ openssl rsa -in test_rsa -pubout > test_rsa.pub
writing RSA key
$ openssl rsa -inform PEM -in test_rsa.pub -noout -text -pubin
RSA Public-Key: (1024 bit)
Modulus:
    00:bb:6e:61:36:11:9f:5c:c7:9b:67:a8:16:f9:fb:
    cb:c1:5d:9b:8d:27:ba:e4:cb:d0:8c:a0:e8:e9:b9:
    ef:b5:65:ab:dc:3a:76:ae:e7:d0:1e:4d:58:12:e9:
    69:61:50:b4:5a:4b:2b:dc:e1:89:8a:a5:40:4e:49:
    21:90:90:11:26:36:d8:37:d8:15:e9:3b:c6:09:de:
    a8:89:4e:77:dd:61:c3:05:d6:74:d5:0e:9d:0e:c8:
    d0:58:a9:48:c4:58:30:34:7e:d5:a6:3a:7f:01:9b:
    b8:92:81:94:39:f8:70:cf:34:b7:8c:b9:0a:2e:e0:
    fc:dd:e9:05:b9:56:23:fe:c7
Exponent: 65537 (0x10001)

As you can see, our public key only contains the modulus and the public exponent, but none of the other information that our private key contains. Having these two components makes our key sufficient for either encryption or decryption, but not both. Because our public key is missing the last part of the puzzle, the private exponent, this file is safe to distribute.

Cool, we now know how asymmetric cryptosystems work! Now, what can we do with our keys?

Putting Our Keys To Use

The usages of public and private keys in cryptography are still being discovered nowadays, but the three main functions we can use them for are secure communications, message validation, and key derivation. We'll briefly go over each in this section.

Using public keys, we can ensure that a message is securely sent to a recipient of our choice. This is done by encrypting our message with their public key. Once they receive our encrypted message, they can decrypt it using the Private key which only they have, and receive the original message. The image below describes this process:

Another use for public keys is message validation. If we wanted to prove we wrote something, we can attach a encrypted thumbprint of the text to the original. This thumbprint is usually calculated using something called a hash algorithm, and we'll encrypt the result with our private key before attaching it.

Now, if anyone stumbles upon our post and wants to verify that it was us who wrote it, they can hash the post themselves, separately decrypt the attached thumbprint with our public key, then check if the two match up. If so, then they can confirm that we were the author who wrote the original message!

One of the coolest and most frequently used components of public key cryptosystems is called the Diffie-Hellman Key Exchange (DHKE), named after the two people who created it.

Recall the point we made earlier, which stated that symmetric cryptosystems all have one main vulnerability because there isn't any classical method of communication secure enough to handle transmitting our keys. DHKE fixes that problem.

DHKE works due to a particularly cool concept within asymmetric cryptosystems that allows users to generate shared keys without ever having to communicate over an insecure channel during the negotiation process. If symmetric cipher keys are derived using DHKE, then our modern symmetric ciphers are secure!

At face level, DHKE works by taking your private key and combining it with your target's public key. If your target also combines their private key and your public key, you will both end up with the same shared key. This shared key can then be used for symmetric encryption or further key derivation.

Here's a little diagram that explains how this process works in greater detail:

Note how in the diagram above, we never transmit any information that we could consider insecure. Private keys never leave the hands of the issuer, and the shared key that we derive is at no point transmitted over the internet! Now, we can use these keys in combination with our favorite symmetric ciphers like AES to quickly encrypt and decrypt large amounts of data, faster than we would be able to using pure asymmetric systems, and without having to deal with the hassle of transmitting a key.

Tools That Use Asymmetric Crypto

These concepts of secure communication, message validation, and key derivation make public key cryptosystems extremely powerful, so it's no surprise that they're now being used as frequently as they are to help drive security further. Many popular apps and protocols now incorporate asymmetric crypto into their platforms to increase security. Let's take a glance at some of them to see how this tech is used.

First, and probably the most common example, is the Secure Shell Protocol. SSH is commonly used to remotely connect to computers or servers you control, and allows you to issue commands to them remotely. The most common implementation of SSH is OpenSSH, which uses Diffie-Hellman to generate a shared key that is used with either AES or ChaCha20 to encrypt the connection each way.

Another example is your web browser! Transport Layer Security (TLS) also uses Diffie-Hellman to derive a shared key, but the algorithms it uses have a special focus on ephemerality. This means that they do not commit these keys to disk and will try not to persist keys any longer than absolutely needed in memory. This increases security by lessening the chance of a memory leak potentially disclosing any keys which could be used to decrypt previous conversations.

A newer standard that's on the rise is WebAuthn! WebAuthn aims to replace passwords with private keys stored on a hardware authentication device you must physically have access to. Instead of asking for a password when you log in, the server will send your browser a string that was encrypted using your public key, and ask you to decrypt it. You'll be prompted to plug in your hardware authenticator, which will then use the private key stored on it to decrypt the string and send it back. If the server sees that the string was decrypted properly, the server authenticates you and logs you in!

Conclusion

The field of cryptography is one that is very complex but also very interesting. By using concepts like ciphers, modular arithmetic, and public/private keys, we can now secure data in ways that were previously inconcieveable. Symmetric and asymmetric cryptographic systems each have their own unique uses, and can be combined to create systems that provide increasing levels of security in an ever-connected world. This article only barely scratches the surface, and the field is still growing at a rapid pace, but hopefully this is enough to teach you the basics. (And here's hoping this content is still revelant in a few years!)

I hope you all found this work useful and that it gave you some insight into how modern cryptography works. If you enjoyed, be sure to comment or share this with a friend! A special shout out to any students who found their way here; I know when I was going through my classes at uni, I would have killed for a reference on Diffie-Hellman like this. If this helped you in your classes, be sure to leave a comment below! And as always, feedback is welcome!

Until next time!