Hi, folks. On this video, I want to spend some time with you on Cryptographic Algorithm Design. Now, you might think you'd have to be a complete mathematical genius or total gearhead, to come up with a good crypto-algorithm. That's kind of right, but I want to decode a little bit for you, just to show that there is a method to the madness. And if you wanted to make up a crypto-algorithm, you might be able to. There's two strategies that are used frequently for creating crypto-algorithms. The first is called Substitution. That's where I'm doing a replacement of one thing with another. The dumb examples are replace one letter with another letter, not the greatest substitution cipher but it gives you the idea. But I can also do it non-linearly, like it doesn't have to be one letter, another letter. It could be weird sort of substitutions; like my two daughters and my wife have this language that they use when there are children around. It's a way of talking and gobbledygook so that the kids can't understand. If you want to take kids out for ice cream, you know, you never say, "Hey, let's go for ice cream," because then the kids hear that and it's not good. So they have this language that they use where they pre-pend the letter A and B in front of every vowel and they say it like my name is Ed, so I'd be Abed. We're on a video right now so it would be Vabidabeyabo. Follow? So they'd say, Abed, vabedabe. It sounds like ababababa. That's what it sounds like to me. It's an example of a non-linear substitution cipher that my girls use to talk around kids and the kids don't get it. Now, you have to be able to decode it, right? Keep in mind that when you're building a cipher, you can't just map everything to the letter A. That's a great way of hiding information but you can get back. You have to have a way of doing the inverse function. You're going to do a function that will be able to do the inverse back. So substitution, linear or nonlinear, preferably nonlinear, tend to be in almost every cipher. A second example, second strategy is called Transposition. And that's where you create a matrix arrangement, a representation of information. Think of it as rows and columns. And you do linear algebra, arithmetic-type transformations on the matrix remembering what you did, right? You got to get back. Think about a matrix like this, you can traverse it this way, you can traverse it this way, all kinds of crazy garblings. And if you've ever taken a course in linear algebra, which, by the way, is the first graduate course I ever taught as I was doing my phD. I have these fond memories, or maybe they're nightmares, of linear algebra, because it's not easy. But if you combine substitution with transposition, matrix manipulation, keep track of that, you can see how you could come up with some kind of fun jumblings of plain text. You could write programs pretty easily to do that. Now, you'd say, "But Ed, I may not do it very well." Let me give you the two requirements that have to be true, if your cipher, your algorithm is any darn good. The first is it has to be complicated, right? And in mathematics, we call that computationally hard. I know that doesn't sound like a very technical term, but if you've studied the theory of NP-Completeness, or if you've studied recursive functions, things like that; then you know that there's a class of problems, a very special class of problems called the NP-Complete problems, where we're pretty convinced as mathematicians, we can't prove it, but we're pretty convinced that the only way you can solve it is to try every possible case. And the classic example of this is you take two prime numbers and you multiply them together. Two big primes, multiply them together, then I give it to you and I say, "Hey, friend, is this the product of two primes? What do you think?" The only way that we know, as mathematicians, to answer that problem today is to divide by two, divide by three, divide by five, divide by seven and so on. Now, if somebody breaks that, that'll be equivalent in my mind to Newton's insights about gravity. That would just be incredible if somebody can figure out a shortcut to that particular problem, because a lot of other problems were transposed from that one and become basically the same problem. And a lot of cryptography hinges on that and, in particular, multiplying two primes and making it extremely difficult for you to find one. You're going to see later when we look at public key cryptography, we're going to multiply two primes and one of the primes is going to be a key. If I gave you the key, boom, you're done. If I don't give you the key, you don't know, essentially, how to decode that piece of numbers. That's the first requirement. The second is that the domain size, the number of things that are being encrypted has to be gigantic because if it's not, as we saw in a much earlier video where we went through and I had you crypto-analyze the Caesar cypher, by writing a program that just created or duplicated the histogram that comes from the frequency distribution of the English language. If you have a small domain size, if you write a program, I just decrypt everything. You could have a really complex cipher but if I can do all possibilities, then it's not very good. So think about it, combine the two things; gigantic domain size. Think the number of possibilities equal the amount of grains of sand that exists on the earth. That kind of a number that big, combine with a problem that can only be solved by trying everything, you've got some pretty good cryptography then, right? Because you got to try them all and I try one case for every grain of sand on Earth? Good luck on that. That's the kind of stakes that we have in mind when we're talking about cryptography. Now, to test you understand, got a little quiz here. And as you would guess, it's D. It's all of those, they're all of those, they're not very technical terms, jumbling things around. But you should keep that in mind. A lot of you probably have spent some time looking at cryptography, maybe in school or something. It always seems like this really hard mathematical thing but keep in mind, it's just secret writing. It's just jumbling things and you can try it, it's actually kind of fun. So we'll see you in the next video.
