In the first episode of Tech & Savvy, Emily and April talk about the evolution of encryption, from the Caesar cipher, to the current AES (Advanced Encryption Standard), to a glimpse into modern quantum-secure algorithms.
Follow Tech n' Savvy!
Hey everyone, welcome to Season One episode one of Tech & Savvy. I'm April and I'm Emily and today Emily is going to talk to us about cryptography. We're going to go through its history and its modern applications today.
So, we'll start from the beginning, really looking back 2000 years ago at the origins of cryptography. So even if you're not familiar with cryptography or this is the first time, you're hearing about it, I hope to really explain what cryptography is and how it came about. But then we'll go through the history and actually come out to where we are today in cryptography.
How it's being used and what we're looking for towards the future of post quantum cryptography and how quantum computing will affect cryptography.
Alright, so let's get into it.
Can you give us an example of like an early implementation of cryptography?
Sure. So, one of the early forms of cryptography was the Caesar cipher, and it's named after Julius Caesar because he used it with his army to communicate. And basically, if you're going to send someone a message, you just shift every letter over by some amount. So, if you wanted to put in the letter A, you might instead encode it at C, and then B. Would it be encoded as D? That would be shifting it over by two.
And Caesar actually used a shift three to communicate with his army. So, what that meant is he would shift every letter over by three and then whoever he received it knew to shift it back. Today, that's obviously not secure, especially with computers or even if you just knew that somebody was using the Caesar shift. You could probably just look at it, try to find patterns and actually be able to decode it. Or you could just try every possible shift, right? That's very doable also.
Since the Caesar shift cryptography has advanced greatly and in World War Two the Germans used the Enigma machine.
Oh, I think I saw that in The Imitation Game.
Yeah, so that was used by the Germans to encrypt messages that they could then broadcast on the radio an even if someone was intercepting or listening in on the message, they wouldn't be able to know what it meant. So the Enigma machine, it's an actual machine. It looks like a typewriter, and what you do is you type the message that you want to send and then it scrambles the letters and then it gives you the letters. These scrambled letters that you'll then send. So instead of sending your actual message, you send this encoded message, and then the person receiving it also has an Enigma machine, and they're able to decipher it with that.
Interesting, so how are they able to decipher it? When you're talking about Caesar, clearly his generals knew that he was using shift three. So how was the enigma decryption communicated? Or what type of ways were the messages decrypted?
So just by having the Enigma machine, you couldn't decipher the messages. Because otherwise anyone who had the machine would be able to. So, what it was is that you actually could change the settings on the machine and that would actually determine how the letters were scrambled. So before actually broadcasting this information, there had to be some pre-established settings that you were going to use beforehand.
OK, and then how so? How do you get those settings though? Do you get it by pigeon?
Yeah, so that comes into the idea of key distribution, so you actually had to somehow in person or in some other way communicate what the settings you were going to use. So, I believe they would actually send someone, and that person would have written down what the settings were going to be every day for the next month. Then they would know OK. Today we're using this setting. They would both adjust their machines so that they were the same, and then they could send the messages.
What I find really fascinating about that, though, is that our mechanisms for communicating the ways of decrypting our messages doesn't seem like it had changed that much from Caesar to World War II. We were still dependent on someone bringing those keys to us.
Yeah, that's exactly right. And that's because both the Caesar shift and the cryptography produced by the Enigma machine are both what's called symmetric cryptography. So symmetric cryptography means that you have one shared key, and you can use that key both to encrypt and to decrypt the information. What that means is you must have some pre-established knowledge and currently, our symmetric cryptography that we use is called AES or the Advanced Encryption Standard.
And so while the Enigma machine, if you-
Spoil alert, should I say it? If you watch it. The Imitation Game, they break the enigma. But not to worry. Symmetric encryption has improved greatly since then, and it had to because modern computers could now break these older encryption algorithms so easily. So nowadays AES uses more advanced mathematical substitutions and shuffling more so than those older forms. AES encryption is very secure
So, you're saying AES encryption is the modern version of symmetric cryptography, but it kind of takes out that human factor?
It actually doesn't take out the human factor. But it does something else. It really is, like you said, just the more modern version of these older ciphers which aren't even considered cryptography by our standards today. But it's the same idea of you have some pre-established information. The secret key and you use that to encrypt more messages that you can send. But what you're bringing up is one of the main areas of cryptography which is the question of how you get those initial keys. How do you distribute them?
Exactly. So, if we still need that pre-established knowledge, how are we getting that pre-established knowledge Especially considering there's so many people on the Internet today and we're all communicating with each other. So how? How is it that everyone is communicating securely?
Yeah, and just like you said, it would be crazy to actually have somebody writing down keys and sharing them, right? I mean, every time you go to an HTTPS website that is secured because of AES, the messages going back and forth between client and server are encrypted with AES and those aren't even really people in a sense, communicating right. It's these different parties, so a client isn't actually going to walk over to server and say, “hey, here's a shared key”, right? So how do you actually distribute the keys? So that's where public key cryptography comes into play.
Can you explain a little bit more about that?
Sure. So, imagine that we're here and we want to have a secret conversation. Just the two of us, and we're smart, I think.
No, you know we’re smart!
So, we're going to use AES encryption to send encrypted messages back and forth. But Abdel is sitting right next to us, so there's no way that we could establish that shared secret right now. If we were to whisper close to each other, he would hear. So how do we actually establish that shared secret? That's where public key cryptography comes in, and it's pretty amazing how it works, because what it says is that you and I could be speaking at a level where Abdel, for instance, can hear everything we're saying. And yet we can establish a shared secret piece of information.
So, without us knowing anything about what we're going to talk about, we can just come up with our own secret key.
Exactly everything is out in the open, so before I even know what I want to encrypt, I already have a key ready exactly, so it's pretty. It's powerful, amazing. Cool to just think about it, like think about sitting within a room with people and you come up with this shared secret and everyone can hear everything you're saying. And yet somehow, we agree on the shared secret.
And you actually do this with mathematics. So, we talked about symmetric cryptography through the years. This is often called asymmetric cryptography, because asymmetric because there is actually a different key to encrypt than to decrypt. There are a few different variants, and they came out in the 70s. Some of the earliest ones. So, think about it for thousands of years we had symmetric cryptography, and it wasn't until the 20th century, late 20th century, that we came up with RSA and Diffie Hellman, which are both still used today and the idea with public key cryptography is that there is a public key that everyone can know, and there's also a private key that only one person knows.
I come up with this key, which is some string of characters and I want to send it to you secretly. So, what happens is you generate the keys you generate a public key and a private key and the public key. You're going to tell me, and anyone can hear it. That's OK, everyone can know the public key, but the private key you'll keep for yourself. So now I use that public key that you gave me to encrypt this secret message, and then I send you this encrypted message. And you use your private key to decrypt it and no one else can decrypt it because they don't have your private key.
Interesting. OK, so really, it's a matter of everyone has their own personal encryption and decryption key. The decryption key is what stays private to you, but you can send anyone your public key and get those secure messages back. Kind of like if you had like a secure text messaging service. I'm sending a message to you and it's somehow being decrypted and then you're sending something back to me, but neither of us know each other's decryption mechanism.
Exactly, and you could do it like that where you could just use public key cryptography, which is what you're describing. We could continue to send each other messages, right? You always encrypting with my public key. I'm encrypting with your public key and that is totally doable. What usually happens in practice is because public key cryptography is asymmetric. So, one way and often slower that we just use public key cryptography once. So only one person has to do the encryption and only one person has to do decryption, because once you've decrypted this secret that I came up with, we have a shared secret, so we can go back to using AES or another symmetric algorithm.
OK alright. So just one person, whoever basically makes the first communication, that's the key we use.
Yep, that's exactly right. And again, I just think it's truly amazing and it's only possible with mathematics and the only-
Emily loves math by the way.
I do I love math!
I love it more than anything.
Um, it's only possible with mathematics and this mathematics can be based on a lot of things. Initially it was based off of problems like factoring a number into two large primes. So, you might have heard cryptography prime numbers, and that's because to actually break this public key cryptography, they would actually have to factor a large number into two primes, if you're talking about RSA. And so public key cryptography is heavily based off of hard math problems. But keep in mind, not every hard math problem makes good cryptography. The key ingredient of it is it's a problem that's really hard to solve in one way and easy in the other. So, if you have two large numbers, you could probably multiply them fairly easily.
But how would you actually take one number and factor it into the components? And so, factoring basically means you take a number, and you break it into 2 numbers that multiply together. For instance, you have the number 15. You could factor that into 3 * 5. Factoring is a great example, and these problems are harder to come by than you would think. Actually, problems that are easy in One Direction harder the other.
And those are the problems that we look for in public key cryptography.
Yeah, that's exactly right.
We've gone through a lot of material so far. Let's summarize. In the beginning of this, we talked about how the purpose of cryptography is really surrounding secure communication. We talked about two different branches of cryptography, symmetric cryptography, an asymmetric cryptography 2 examples we talked about in regards to symmetric cryptography where Caesar cipher, which was a simple mechanism of shifting the letters that you were using in your message, and then we talked about the Enigma machine, which was used by the Germans in World War Two. The real similarities between these methods were that both of them had particular keys that had to be predetermined and pre communicated before anyone could actually decipher that message. So, Caesar's generals needed to know that he was shifting his messages by three letters and then the anyone who was using the Enigma machine actually had to know the settings of that machine for that particular day in order to decrypt that message. Then we moved over to asymmetric cryptography which we talked about with public key cryptography, in particular, in which a user- Actually, our two users have a public key and a private key. The public key can be communicated to anyone to encrypt a message and you have your own private key. In order to decrypt the message, you get back and no one knows about your private key. And that kind of takes away the middleman of having to have predetermined information ahead of time because you know the predetermined information is something that you created yourself and you're just communicating that, but you don't need to know the other person's side. You just need to know your side of the story.
Now we're looking in the late 20th century and we have AES, which we're using as our secure symmetric cryptography. And we have RSA or Diffie Hellman, which we're using as our asymmetric or public key cryptography. There's actually a lot more to public key cryptography that we're not going to dive into too deeply in in this episode, but I just want everyone to be aware that in addition to just encrypting messages so people can't read them and their private, there's also these two other main components, which is integrity, knowing that the message hasn't been changed, an authentication, knowing that it came from the correct party.
OK, so now that we've dove a little bit more into like you said cryptography of the late 20th century. Where are we today with cryptography?
We talked about how we use symmetric encryption like AES to encrypt messages and send them back and forth. We also talked about how that requires some shared secret information, a key, and we use public key cryptography like RSA or Diffie Hellman to actually establish that shared key. And we also talked about how we use public key cryptography as well for integrity and authentication. So public key cryptography is a very important part of the story and we talked about how it's based off of hard math problems. And these math problems have to be very hard for computers to solve and problems like factoring are very hard for our current computers. However, there is this new form of computing that's being developed called quantum computing and quantum computing can actually solve some of these problems easily that are very hard for our current computers.
So, these quantum computers are essentially supercomputers that can do things our current computers can't.
The interesting thing about quantum computing is that it really is a completely different way to do computing. So, it's not even that they're just more powerful innately. It's just that they have a completely different way of doing computation, and we can actually use that to solve these problems. So classical computers are based off of classical physics. Whereas quantum computers are based off of quantum physics, so a classical computer has a fundamental unit called a bit, and that bit could be either zero or one. But quantum computers, their fundamental unit is something called a qubit or quantum bit, and that can actually be any linear combination of zero and one, which means it's not necessarily zero or one. It can be somewhere in between that's called a superposition, there's a lot of different quantum processes that we can actually harness to solve these problems in a completely new way and problems like factoring that we use for our current public key cryptography will actually be able to be broken once we have a powerful enough quantum computer developed.
So how long do we actually have before these computers start breaking all the security?
How long until the end of the world?
Exactly how long before terminators?
Definitely good news. Right now, we have the algorithms you know, we actually know how to break our cryptography, but we don't actually have the machines to run the algorithms. So, there are very different estimates as to when quantum computers will be able to break our current cryptography. There is a lot of variables at play. And one is that quantum computing is just this new technology that we don't quite understand how to use it in the best way. I would say 10 years is a good estimate. Some people say as long as 30 years until it breaks it. So, it is a long time from now, but there's a lot of reasons that we should already be thinking about it. The first reason is we want to have our secure cryptography in place before quantum computers, so we want to fix this problem before it's a problem. Another is that we have to come up with new cryptography because clearly the cryptography we have right now isn't sufficient. So, we have to come up with this new cryptography, implement it everywhere before the quantum threat comes.
You're preparing for the inevitable, essentially. It is inevitable, right? You know.
So, there are some people who say it's not inevitable while we have the algorithms. Some people doubt that we will build a powerful enough quantum machine to run this. But based on the progress that quantum computers have been making and the various approaches that are going all over the world and the progress we've made from quantum computers were just this theory years ago, and now we actually do have quantum computers, just not powerful enough ones yet. I would say that it is inevitable, but you never know to some extent.
OK, so for those, those of us who understand that it's something that will happen in the future what what's currently being done to combat quantum computers.
The quantum computing. We talked about can break our public key cryptography, so we need new public key cryptography. And there's two types of our new public key cryptography. There is quantum cryptography and the interesting thing about quantum cryptography is that it's a way to do the key distribution that we talked about on a quantum computer. Because of that, it's actually very secure. Quantum computing is the problem. In some cases. It can also be the solution. There's also post quantum cryptography and post quantum cryptography actually doesn't use a quantum computer, it's called Post Quantum because it means after quantum, so it's secure against quantum computers. So, it's really just like our current cryptography in that you can run it on a classical computer. Like RSA, it's based off of some hard math problem, it's just that the math problem is much, much harder.
And how do we determine those math problems?
So currently NIST, the National Institute of Standards and Technology, is having a competition for the new post quantum cryptography. It started a few years ago with around 70 submissions of people coming up with new cryptography algorithms. And it's a very exciting time for cryptography because it's since been narrowed down to only seven algorithms. And that's including both the encryption algorithms, of which there are four and the signature algorithms, of which there are three.
Do we know when we'll find out who's the winner? Or is that still a couple of years away from now?
I think the estimate is in a year or two, but the algorithms that were left we already can talk a lot about what post quantum cryptography is going to look like just from these algorithms.
And how do we determine which algorithms to eliminate and which ones to keep?
There are some main factors. The first one, of course, is security, so we have to make sure that these cryptosystems are secure. And the way we do that is we show that the math problems that they are based on are very hard to solve, both for classical and quantum computers. We do something called security proofs which can sound a little bit like it's an absolute proof that this is secure. It's actually impossible to prove for sure that post quantum cryptography can never be broken, because it is this math problem. So, in a sense you don't know, but you can show that it's as hard as breaking an NP hard problem, which is very hard to do. And keep in mind that. Our current cryptography does not have these security proofs.
We're trying to make this cryptography much more secure. OK, so security is the first one, but also efficiency is very important, so we have to make sure that the algorithm can run quickly. We have to make sure that the key sizes aren't too big. There's a lot of things that go into it. We have to make sure that it's easy enough to implement that it's flexible. So, there's many factors that go into deciding.
Yeah, that's actually really exciting. So, we're living in a time in kind of like a revolution of cryptography in in, really, how people's privacy is going to be secured over the next couple of decades.
Yeah, I like that term revolution I. I mean you're right like our cryptography hasn't really changed that much in about 50 years. We've added new algorithms for sure. But our public key cryptography, we still use RSA that is still considered secure after 50 years. That's a very long time. So, although there are some other algorithms and have been other algorithms, elliptic curve cryptography for example, has become much more widely used, but also faces the same challenges. It's not until recently that we've realized we need to actually change our public key cryptography.
Now that we've talked about Asymmetric cryptography. And you know that means AES and versus RSA and Diffie Hellman. We've now dove into what can actually break the cryptography we have today, which is quantum computing. Our cryptography today is able to solve hard math problems. But we've been able to start developing computers that can solve. Even harder math problems and basically break the security standards and crypto standards that we built over the past couple of decades. And essentially, even though we don't have supercomputers and they're really not common place, we’re preparing for what some would say is the inevitable which could be anywhere from 10 to 30 years that our encryption becomes breakable and we need to battle that. That's where post quantum cryptography comes in, and this is actually a really exciting time because nothing has actually been standardized within post quantum cryptography, and there's a competition going on with NIST in order to kind of determine what algorithms are we going to use in order to battle the quantum computers that don't exist yet but will exist soon in the future. It's like a what came first the chicken, or the egg and its post quantum needs to be there before quantum is even a thing.
Quantum computing is able to break our current cryptography. How does that affect our different mechanisms we're using today, like AES and RSA are those going to become obsolete?
All of our current public key cryptography like RSA Diffie Hellman and also slightly newer elliptic curve cryptography, Quantum computers can break them, and there isn't much we can do to save those algorithms. So you're right, they will be obsolete and that is why we have the post quantum algorithms to replace them.
AES actually will not be obsolete against quantum computers. As far as we know now because AES is symmetric cryptography. In a sense, I like to think of it as the math problem isn't as important with AES because you have to have that pre shared information. So public key cryptography, I think of it as coming up with something from nothing. Establishing secure communication in a completely insecure environment. We have to have very specific hard math problems for that. And that's what public key cryptography is and that's why quantum computers can break them because they rely so much on just this hard math problem. Whereas the symmetric algorithms like AES don't rely as much on one hard math problem. There's a lot more to it in terms of shuffling, scrambling the messages, that quantum computers won't actually be able to break. As far as we know right now, actually, the best we can do against AES is a quadratic speedup.
This means that for AES we just have to double the length of the keys to get the same security we already have. So yes, AES will be affected by quantum computers, but there is a misconception that it will be broken. It won't be broken; we just have to use a stronger variant, meaning longer keys, to be still secure against quantum computers. But just using longer keys will not work for our public key cryptography. That is obsolete.
And so, you would say within the next 10 years this could be a real threat? Should, you know, places that are using AES or anything else really, start looking into quantum and post quantum in preparation for this kind of new wave of security and cryptography.
Definitely. As we mentioned, quantum computers do exist. They're already being developed at this point. I want to say they have 50 cubits. There's a really a lot that goes into quantum computing and I feel like we should have a whole episode just really diving into quantum to see where we are at. There are so many applications of it, even outside cryptography. But to get back to just cryptography, how we should start preparing with AES. Currently AES 128 bit key and 256 bit key are standard AES. 128 bit that is considered secure against classical, but it's not secure against quantum, whereas 256 bit is secure against both quantum and classical. AES 256 bit against the quantum computer has the same security that AES 128 bit has against a classical computer. So, in terms of how we can start preparing, if you have information that you want to be encrypted long-term, you don't want to wait 10 30 years later, when a quantum computer can break it. So, you want to be using AES 256 bit. And you also want to be looking at some of these new post quantum algorithms.
OK, so now we know how to prepare for Quantum. Can you tell us a little bit more about these algorithms that we should be watching out for?
There are seven algorithms that have made it through a series of rounds through the NIST Post Quantum competition. But we can actually break this down into 3 general types of math problems that they're based off of, so five out of the 7 remaining algorithms are actually based off of lattice cryptography. A lattice is an object in math, and you can think of it as you have some piece of paper and then you put a grid over it. Now pretend you're in 3D and you just see the grid in three dimensions everywhere. That grid is a lattice. In math we actually look at lattices in N dimensions and that could be 100 or 1000 dimensions. So, we can't really visualize this, but we can actually use this to do hard math problems. An example of this is the shortest vector problem. So, a vector is just connecting one point to another point on the lattice, and the shortest vector problem is finding the shortest vector on the lattice.
Without going into too much detail about lattice cryptography, I just want to emphasize that it is very likely going to be our new form of cryptography and I highly suggest looking into it if you're interested in post quantum.
But what about the other side? You know if I'm looking if I'm rooting for the underdog, who's the underdog in this situation?
The 4th encryption algorithm, so three of them are lattice based, the 4th one remaining is based on code-based cryptography which is based on error correcting codes and surprisingly this was actually developed in the 1970s, around the same time that RSA was. But it did not receive a lot of attention, and that's because it used enormous key sizes which at the time were beyond just impractical. They were inconceivable to have that large key sizes. And the other reason is that, compared to RSA, RSA was very simple and easy to understand. Code-based cryptography was hard to understand, longer key sizes. It just wasn't practical, and now it's kind of interesting that it's come back into our sight because RSA, you know? Back then we weren't expecting quantum computers. RSA was terrific and now that we have quantum computers, we're actually looking at code-based cryptography in a new light because not only do we have this new quantum threat against RSA, that seems to not be a threat against code-based, but we also have better computers. So those large key sizes, which back in the 70s were impossible, are not actually impossible.
So, another type is multivariate, and this is based off of solving a system of equations and multiple variables. multivariate is the remaining signature algorithm out of the three types that's there. So those are three of the main types of cryptography. Again, I really suggest looking into them more, but if you want to just focus in on one, I think lattice based is very prevalent.
So, we basically made it. We made it to 2020. We know we know where we are now, or we at least know what path we're on for the future. Can you give us, you know, for those of us who skipped to the end or might have forgotten where we came from, can you give a quick summary of what we learned today?
Sure, so we talked about starting all the way back 2000 years ago with the Caesar cipher as our initial form of cryptography of just shifting over letters. We built that up all the way to World War II using the Enigma machine to have basically harder to crack codes, and this was eventually cracked.
And we talked about how these are actually all the beginnings of what today we call symmetric cryptography, and our current symmetric cryptography is AES encryption, which we used to encrypt basically everything we want to encrypt and share or not share anything you want to encrypt so that other people can't read it.
We also talked about how AES needs a shared secret, which you get from public key cryptography and public key cryptography is very amazing. I think really just a brilliant transition from symmetric cryptography to public key cryptography where you can actually establish a shared secret with somebody in a completely public environment. And we talked about RSA and Diffie Hellman as our classical public key cryptography. And then we got into quantum computing. This new form of computation that's being developed that will actually be able to break RSA in our other current public key cryptography. So that then poses the questions of 1st, when will this happen, which we said we think 10 to 30 years. I wouldn't quote myself on that one.
And we also got into the question of, well, what do we do? How do we stay secure? And we talked briefly about the two different modern forms of cryptography. There is quantum cryptography which actually uses a quantum computer to run.
And this is.
Provably secure, which is pretty amazing, but it requires everyone to have a quantum computer, so not necessarily practical in every application.
And then we talked about post quantum cryptography, which is just like our current cryptography, except that it is secure against quantum computers. At least we believe it is. When I say believe, we have very strong reasons to say that it is secure. And where we are today is, we've narrowed it down to 7 algorithms, primarily based on lattice cryptography. And we're trying to decide what is going to be our new standard for public key cryptography. And then we'll just have to implement that.
Wow, well I know I, for one, am very interested in learning more about quantum and post quantum. So, I'm looking forward to one of our future episodes where we kind of do a deep dive into that.
Definitely! Thank you April and I'm very happy that you're as excited- almost as excited as me about cryptography. I think it's a very exciting time to be involved.
I agree and everyone, like Emily said, you should do your own research and also look more into quantum computing, post cloud computing and cryptography in general to see how it affects our daily lives.
I think that's all we have for today.
Thank you everyone to listening to this episode of Tech & Savvy on cryptography.
You can find us on social media on Twitter and Instagram, and you can also contact us through our website technsavvy.com. Well, thanks again. We're looking forward to seeing you in Episode 2.
Your intro and outro song is gone by 414.