Tyler's Site

Abstract

Cryptography is a field that sits between multiple fields of study, most obviously mathematics and computer science. Historically, cryptography was largely used for purposes of military or espionage operations, however, in modern times much of the ways that we interact with the digital world has a fundamental reliance on strong cryptography. This cryptography allows for anything from private and secure communication between two or more people, as well as authenticating communications between entities.

This blog post is intended to be an extremely simplified view into the very, very basic concepts of cryptography, and is being written by someone who is not an expert in the field. That being said, I will do my best to give information that is accurate and to cite sources where necessary, but ultimately there is a decent chance that there will be something in this post that is not 100% accurate. So, if you are interested in this field, please go and do your own research. In the resources section of this post, there is an Introduction to Cryptography playlist given to university students that will be much more reliable and accurate than this. If there is one lesson to be learned from this, or any other resource on Cryptography for that matter, DO NOT MAKE YOUR OWN CRPTO! New crypto algorithms are extremely difficult to make securely, however, are extremely easy to create insecure algorithms while thinking it is a secure algorithm. When a new algorithm is proposed, it is done in such a way that asks people to attack and try to break it; they are proposed this way because the only way to ensure something is secure, is for people to continuously fail to break it. When this process is not followed, the security is not proven, then serious security vulnerabilities are found after the algorithm is in production, such as with the case of every version of SSL. So, I want to stress again, DO NOT MAKE YOUR OWN CRPTO, the chances that you get it wrong are extremely high, and that is even more true if you do not understand the field and are not doing the mathematical calculations for the algorithms in use currently. Leave the optimiations and tweaking of these algorithms to the experts in the field.

What is Cryptography?

In short, cryptography is the practice of securily communicating over unsecure channels; the general method of doing this is by algorythmically scrambling the message in such a way that it become unreadable without the key. This is a practice that has existed for thousands of years and has been used in a variety of settings. The algorithms that handle the scrabling of the original message are called ciphers and will take clear text (sometimes also called “Plain Text”) to turn it into encrypted text. One of the most basic and well known examples of this is the simple Ceaser cipher. Essentially the method of “encrypting” the message is to shift the letters by some number. For example, take the message “The less you say the more you hear” and shift the letters by five so the ‘T’ becomes a ‘Y’, the ‘h’ becomes an ‘m’ and so on, the encrypted message would be “Ymj qjxx dtz xfd ymj rtwj dtz mjfw”.

This is an achient cryptography method that does not even come close to modern cryptography standards, but it is an easy to understand primer for those unfamiliar with the topic. There are many systems that have existed before the age of modern computers that provided varying degrees of security for encoding information. While those are interesting on their own, they have little to do with the modern standards of cryptography and thus will largely be skipped over. Let’s instead look at the concepts that lay the foundation for modern crptography.

Fundamental Concepts

While the mathematics and calculations that make the various crptographic algorithms function in a secure manner are rather complicated, most of them involve a few basic concepts that are much easier to understand.

Prime Numbers

Prime numbers, for those that are unaware, are numbers that can only be divided by 1 and themselves, such as 13. Most if not all crptographic algorithms require large prime numbers (somewhere in the range of 2768 bits or larger) to function properly. The main reason for this is that the prime numbers are often used as a sort of key or key generator; these prime numbers are often processed in such a way that becomes practically impossible to find the original prime number with the number that is available to a threat actor. A simple example of this is finding the factors of a large semiprime number, however, that is certainly not the only way prime numbers are used in cryptography.

Modulus Math

Modulus math is something that most people are generally familiar with, even if they have not heard of it by that name. Essentially, it is division but the only answer we are concerned with is the remainder. For example, take the equation 6 ÷ 26, most people would be able to answer with “4 remainder of 2”. Well, in modulis math, the answer would just be the remainder, or ‘2’, these equations are represented as: 6 mod  24 = 2. It is notable that modulus math has non-unique answers, meaning that the equations 19 mod  3 and 37 mod  3 are equivalent (with the answer being 1). This property is useful to increase the performance of decryption as we do not actually have to divide by a huge number, but rather just find the modulo of that number compared to another. It is also worth noting that in the world of computers, everything is going to be set to modulo 2 (remember everything is either ‘0’ or ‘1’), so no matter what values are brains are dealing with, the computer only understands and performs mathematical operations on bits of 0 and 1.

Entropy

Entropy, also referred to as randomness, is an important part of the key generation process. Without a good amount of entropy in the system, it would be easy for attackers to systematically guess what the key is. There are two major categories of random number generators (RNGs):

The unpredictability of these random number generators is one of the key points to help cryptography stay secure. If the key is supposed to be a “random” prime number above so many bits, but the PRNG has been compromised to only give one of a handful of numbers, then there are many fewer keys to check against, thus reducing the security of the entire system dramatically. Having sufficient entropy in a system is highly important if the security of the system relies on randomness, such as with PID randomization.

Basics of Cryptography

Now that the foundational concepts that modern cryptography relies on, we can start discussing the general methodologies for encrypting information. As stated in earlier sections of this blog post, many historic methods would process the letters of the language’s alphabet in various ways to encrypt the information. However, modern computers do not understand human language, rather simply numbers that represent the characters drawn on our screen.

Symmetrical

A symmetric encryption algorithm is a system in which the key can be used to both encrypt and decrypt the message. An example of this might be the Ceaser cipher from our earlier example; the number ‘5’ was the key and could be used to encrypt and decrypt (just move the letters by five each time). In the modern world, the symmetric encryption algorithms are much more complex and robust as well as can be used as a stream cipher or a block cipher. A stream cipher is a cipher in which the bits are encrypted one by one as they come across the wire, alternatively a block cipher will encrypt a fixed length of bits at a time, even padding the data to meet the required length if necessary.

One of the biggest issues with symmetrical encryption is securely establishing a key, as both the sender and receiver must use the same key. There are several methods to securely establish a key, depending on what the situation calls for. Transferring the key can be done by using something like public/private key pairs, communicating the key via a secure channel (like meeting in real life and physically giving a key), or, more commonly, using something like Diffie-Hellman key exchange. The Diffie-Hellman is one of the most common methods to exchange keys between a client and server, and is often used in conjunction with AES encryption to secure web traffic. While I probably could explain the specifics of how Diffie-Hellman works, Computerphile has a video on it that explains it much better than I will probably do in this blog post.

Symmetrical encryption is one of the most widely used forms of encryption, as AES is the foundation of many of the protocols that we use today including HTTPS, WPA2, WPA3, and various other applications. Similar to Dillie-Hellman key exchange, I am not going to cover the specifics of how it works because computerphile did that one too, and I feel like they will do a much better job explaining how it works than I am going to be able to. The last thing of note is that while AES might be the most popular (at least symmetrical) encryption algorithm, there have been quite a few that have come before including, but not limited to:

Asymmetrical

Asymmetrical encryption is pretty much the opposite of symmetrical encryption, where the key for encryption and the key for decryption are different. There are many different examples of algorithms that use this basic idea for the cipher including, but not limited to:

Asymmetrical keys are often used to communicate symmetric keys more securely, however, asymmetrical keys tend to be more vulnerable being broken by quantum computers. At the time of writing though, quantum computers have not been able to break strong strong modern encryption (such as 4096 bit RSA or 768 bit ECC algorithms). Though, a quantum computer with sufficient qubits would be able to break modern RSA and ECC algorithms much more easily than classical computers (more resources on that later), nothing of that sort has happened yet, and I personal suspect we are at least 10 years from that becoming reality.

Another problem with some asymmetrical algorithms is the “web of trust”. This is specifically a problem with things like PGP keys and other asymmetrical cryptographic infrastructure such as certificate authorities. While the idea of creating a giant web of connections that allows every person to trust every other person via proxy connections is great, this idea falls apart when you start thinking about it in the real world. How many of your friend’s friends would you trust? If somehow that is the case, you either have an awesome friend or you are hopelessly naive. In the more likely case that you would not trust all of your friend’s friends, then you see the problem of the web of trust. Just because you trust one guy, doesn’t mean you trust the people he thinks is okay. If you cannot trust your friend’s friends, then the idea of the web of trust completely falls apart.

The two most commonly used asymmetric algorithms right now are RSA and ECC. These algorithms are not terribly difficult to understand the basics of, and often have good resources to explain it. That is what I am going to provide for learning these, as it will be much easier than poorly explaining it in this blog post. Eddie Woo has two videos (RSA Part1 and RSA Part 2) describing how RSA works, and computerphile has one on ECC.

Making Cryptography Secure

This is the section that will hopefully go more in-depth on why it is likely a bad idea to roll your own crypto for production use. I want to point out that attempting to create a crypto system for educational purposes is fine, but do not expect it to be secure. Cryptography something that is very easy to make something that looks secure, but is very difficult to make something that is secure. Thus, came about Kerckhoffs’s principle. The origins of this principle came from a list of six rules that military ciphers should follow published in the Journal of Military Science, which are:

  1. The system must be practically, if not mathematically, indecipherable;
  2. It should not require secrecy, and it should not be a problem if it falls into enemy hands;
  3. It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
  4. It must be applicable to telegraphy communications;
  5. It must be portable, and should not require several persons to handle or operate;
  6. Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.

While some of these rules did not age very well, rule number two is still relevant, and is now referred to as Kerckhoff’s principle. This principle ensures security through testing the standards by battle rather than by hiding; this will allow researchers to attempt to break the proposed cipher to see how well it fares against common attacks against crypto systems. These attacks using things like pattern recognition in the output vs what is known about the input; additionally attacks using poorly implemented RNGs can be used to gain some influence or insight as to what the key might be for the computer.

A great method of seeing the results of what rolling crypto in house is like, look no further than the Secure Sockets Layer (SSL) vulnerabilities. Modern day Transport Layer Security is not perfect, but it is at least not horribly vulnerable to man in the middle attacks. Most crypto systems that have not be exposed to the general public for a vetting period, likely cannot withstand the abuse that they will see in the real world. Which is why the advise is to never roll your own crypto.

Quantum Resistant Cryptography

The last part is the part that we have not actually approached in history yet, however, advancements are working towards breaking several encryption algorithms that would be detramental to the foundations of the Intenret. Many people are aware of this fact, but misunderstand the reasoning behind it. While quantum computers do out perform classical computers in certain workloads, they are highly specific. The reason for that is rather complicated, but has to do with the way that information is processed in a quantum computer; where classical computers have bits (0’s and 1’s), quantum computers have qubits. Qubits are able to take advantage of several quantum mechanic concepts that classical computers are not able to access, one of the most notable of these mechanics is quantum super position, that will allow quantum computers to out perform classical ones in things like Shor’g algorithm.

Using shor’s algorithm, we are able to break things like RSA encryption in a fraction of the that classical computers take. This is the “privacy ending” vulnerability that quantum computers expose. I use quote there, because it will take a long time before anyone will be able to beat modern encryption with quantum computers for one target, let alone generally doing this for all the data across the whole Internet. However, this is a problem that does need to be solved quickly to give the Internet an opportunity to adopt the quantum resistant tech. At the time of writing the National Institute of Standards and Technology (NIST) has found that the following encryption algorithms are sufficiently secure against quantum computers:

With the mention of the NIST, I would be doing a disservice if I failed to mention the controversies surrounding them as well. While the NIST holds the responsibility of promoting strong cryptography both in the public and governmental sectors within the United States, they do have a least one controversy in which the NIST allegedly allowed a standard (SP 800-90) to be published and promoted for cryptographic security, when there was a potential backdoor in the standard’s PRNG (some allegations say it was put there by the National Security Agency (NSA)). That standard was quickly revoked due to the backlash it was causing the NIST, however, that situation also weakened their trust for a lot of people. So, certainly do your own research on who to trust, and whether that situation is enough for you to distrust the NIST.

Resources

Cryptography is a huge field of study that I have barely done justice on getting a write-up published. As such, I wanted to make sure to leave some good primer material in this section. There are many other good places to start as well, but most people can follow along with YouTube videos easily enough and the creators do a good job of breaking it down in easy to understand pieces.