Placeholder Image

字幕表 動画を再生する

  • [MUSIC PLAYING]

  • SPEAKER 1: Cryptography.

  • What is it, and why is it important?

  • We're going to answer those two questions in exactly that order.

  • Let's start with what cryptography is.

  • It's the art and science of obscuring, and ideally protecting, information.

  • Now it's an art and a science because there's math involved with it.

  • It's pretty straightforward to manipulate characters in some way

  • by adding some constant number to them or to change them

  • in some systematic manner.

  • But it's an art, because doing so in a way to defend against potential attacks

  • is not as easy as it might first appear.

  • There's a lot of guesswork and calculation

  • that needs to go into play to find a really strong cipher.

  • Cryptography gives us the opportunity to have

  • a basic level of security against an adversary who might

  • do bad things with the information.

  • We usually contrast, in cipher information,

  • with information that is presented in the clear, which

  • is to say there's no protection surrounding it at all.

  • And it's generally considered better to protect information using cryptography

  • than to have information just freely available out there.

  • Now a cipher, we're going to start by talking about cryptography

  • sort of through history.

  • We'll lead up to more modern forms of cryptography,

  • which are derived from more ancient forms of cryptography.

  • But a cipher is one of the most fundamental forms of cryptography.

  • And ciphers are algorithms.

  • And recall that an algorithm is just a step-by-step set of instructions

  • that we use to complete a task.

  • And in case, the task is to obscure or encipher information.

  • And ciphers can also be used in reverse to unobscure, or decipher,

  • that same information that was previously encoded or enciphered.

  • Now there are many different ciphers out there

  • that have varying levels of security potential.

  • Some of the more ancient ciphers that we're going to start with

  • should be [INAUDIBLE] be considered to have no security potential at all

  • considering how easy they are to crack.

  • But again, this leads into the more modern approach to cryptography,

  • which is much more secure than some of these basic ones.

  • And now let's start by imagining that we have possession of this device.

  • Now if you're looking at this device and it seems somewhat familiar to you,

  • it may be because you've recently seen the movie A Christmas Story,

  • where Ralphie, the character there, obtains

  • one of these, which is a little orphan Annie's secret society decoder pin.

  • And this decoder pin has a set of numbers going sequentially one

  • through 26 around the inner edge, and a set

  • of letters, which is not presented in any particular order,

  • around the outer edge.

  • And what would happen is the radio announcer would provide,

  • set your pins to some combination.

  • So line up one number with one letter.

  • And then it would read off some secret message

  • that, ostensibly, only individuals who possessed this pin,

  • or many of the duplicate versions of this pin that were distributed

  • to children around the country, could then decipher

  • by taking the numbers that were given over the radio

  • and transforming them back into letters so that it makes sense.

  • So if you can, if you zoom in on this image,

  • it might be a little difficult to see, but you

  • can see that the 3 corresponds to the letter L, and the 4 corresponds to an M

  • based on this particular setting of this decoder pin.

  • So this is one potential, what we would call a substitution cipher,

  • where we're changing, we're substituting a letter in this case for a number,

  • and that number will henceforth represent that letter

  • for the rest of this message.

  • But what is the problem with this cipher?

  • Or more generally, when we think about issues in computer science

  • where we have adversaries who are trying to penetrate some system,

  • or break a code, or break in, or hack into anything,

  • hack your password, we sometimes frame this in terms of asking the question,

  • what is the attack vector?

  • Where is the vulnerability that is potentially

  • part of this particular cipher?

  • And in this case, it's that anybody who has access to this pin

  • is able to break any cipher that is made with this pin.

  • And again, this pin was distributed pretty extensively in 1930s and 40s

  • to children who listened to this very popular radio program.

  • So these pins were in the hands of many people.

  • And anybody who had access to the pin would

  • be able to understand the message.

  • And so that is, how we might frame this attack vector,

  • is the key, in this case, the pin, which we will call a key for this purpose,

  • is just very prevalent.

  • It's pretty well known how to use this key and manipulate this key.

  • A lot of people have access to that key.

  • But that's just one example of a substitution cipher.

  • We have many different examples of substitution ciphers that we could use.

  • Let's just take another very simple, straightforward one,

  • which is imagine we have all of the letters of the alphabet

  • and we're just going to assign the ordinal position of that letter

  • as its cipher value.

  • So with the secret society pin, there was this sort of random element

  • to it, right?

  • The letters were being skipped.

  • There wasn't a rhyme or reason to them, although the numbers were sequential.

  • Here let's just line up both.

  • Let's use sequential letters and map them to their sequential numbers.

  • So A becomes 1, B becomes 2, and so on.

  • Both of these things are increasing linearly.

  • Now you may recall that as computer scientists,

  • we ordinarily start counting from zero rather than counting from one.

  • I'm counting from one here because this mapping of A to 1 and Z to 26

  • is much more familiar to us intuitively as humans,

  • and I want to keep us grounded in this discussion of cryptography right now.

  • But ordinarily, you might actually instead see this as 0 to 25, 0 being A,

  • through Z being 25 as opposed to 1 through 26.

  • But this cipher would work exactly the same

  • and has roughly the same security potential

  • as Annie's secret society cipher does.

  • And we can actually make this a little bit better because we are consistently

  • increasing the letters, A through Z, and consistently increasing

  • the numbers, 1 through 26.

  • We could also, instead of just doing this direct mapping,

  • we could rotate around.

  • We could start the 1 somewhere else as opposed to being A.

  • And now instead of having just one cipher where A maps to 1, B maps to 2,

  • we have a variety of different ciphers, depending

  • on where we decide we want to have our starting point.

  • So for example, we might instead add two to every number.

  • So instead of going from 1 to 26, we go from 3 to 28.

  • Now think about it.

  • If you're trying to break this cipher and you see patterns

  • like this with all these numbers in them, what might jump out at you?

  • Well, if you're used to seeing ciphers that are 1 through 26, for example,

  • something where you don't see any 1s or 2s

  • and suddenly you're seeing 27s and 28s potentially in the message that might

  • be long enough to have, in this case, Ys or Zs in it

  • might seem to you that this is slightly off.

  • Like this cipher must be shifted in some way.

  • Instead of being this straightforward line,

  • there's some modification that's been made to it.

  • That's kind of a tip off if you're trying to defend

  • against somebody figuring that out.

  • And so instead of going 27, 28 at the end,

  • we might instead wrap around the alphabet.

  • Once we have exhausted the 26 possible values that we started with,

  • the 26 letters of the alphabet, we might instead, once we have X is 26,

  • say, well, instead of Y being 27, Y is 1 and Z is 2.

  • And this is not a massive improvement on the security of this cipher.

  • Like I said, it's still quite fragile and quite easy to break.

  • But it doesn't give quite as much of a clue to a potential adversary

  • as to how to crack it, how to decipher the message.

  • And this can be done for any different value

  • to obtain any number of different ciphers.

  • Instead of going forward by two positions,

  • we could add 20 to every letter's value, again,

  • wrapping around the alphabet when we exhaust,

  • when we get to 26, instead of having 27, 28, we would just reset at 1

  • and continue on.

  • But we can also add 26 to it.

  • But that doesn't look very different than what we had before.

  • And that's where this cipher's vulnerability comes into play.

  • There's only 26 possible ways to rotate the alphabet

  • while keeping the order of the letters preserved, right?

  • Unless we start skipping A, D, G, and then,

  • you know, rearranging the other letters in some other way.

  • If we want to keep everything straightforward in a line,

  • again, wrapping around 26 when necessary, there's

  • only 26 ways to do it.

  • That is to say that shifting the alphabet forward by 26

  • is exactly the same as shifting the alphabet forward by 0.

  • And so that's our limitation.

  • We have a very small number of, again, this word keys that can

  • be used to decipher using this cipher.

  • Now this is an example of something called a rotational cipher,

  • and it's actually a rather famous rotational cipher

  • known as the Caesar Cipher.

  • It's attributed to Julius Caesar and was apparently used

  • more than two millennia ago for him to encode messages to his troops

  • on the line.

  • And at the time, this was revolutionary.

  • And generally what you're going to find with cryptography

  • is there's just this pattern of breaking the mold and doing something new

  • and trying to stay one step ahead.

  • And oftentimes, other people will then catch up.

  • And this cipher, which was once, you know,

  • lauded as being a wonderful cipher, is no longer as strong

  • as it once was thought to be.

  • And so we keep having to advance and improve and get ahead

  • of it for whatever kind of adversary that is, whether that's

  • a potential enemy on the battle line, as might have been the case with Julius

  • Caesar, or whether that's a hacker who's trying to break into your system

  • as might be the case today.

  • And fortunately, again, we're not using Caesar Cipher today

  • to uncipher any of our information.

  • We're using much more modern techniques.

  • But these modern techniques evolved from seeing

  • codes being created, ciphers being created and broken,

  • and then having to be created anew to try

  • and defend against new vulnerabilities that have been exposed.

  • So like I said previously, very easy to decipher or to crack the Caesar Cipher,

  • but at the time, very, very difficult.

  • The limitation, again, limited number of keys.

  • There's only 26 ways to rotate the alphabet for it to make sense.

  • In the English alphabet, of course.

  • If you're using a different alphabet, you're

  • number of keys might be different if you're

  • using the same rotational approach.

  • But the fundamental limitation is you are

  • confined by how many letters are in your alphabet

  • that you're using to encipher information.

  • So let's take things one step further.

  • What is an improvement that we might be able to make to Caesar?

  • That would lead us to this idea potentially of the Vigenere Cipher.

  • So Caesar had this limitation of there's one key

  • and there's only 26 possible values for that key.

  • What Vigenere Cipher does is it, instead of using a single key,

  • uses multiple keys.

  • Instead of picking a number to shift by, we're

  • instead going to define a keyword.

  • And we're going to use the letters of that keyword in sequence as we

  • go to change what our key is at any given

  • time, such that our enciphered message, instead of being enciphered using one

  • key, might use three keys or five keys or 10 keys,

  • depending on the length of the keyword that we use,

  • if that keyword is three or five or 10 letters long.

  • So this keyword becomes the interesting twist

  • that made Caesar much more challenging for an adversary

  • to crack by using different keys.

  • Now let's walk through an example of how the Vigenere Cipher works

  • because I think it makes more sense to see this visually rather than just

  • discussing it verbally.

  • So what we want to do here is encrypt the message HELLO

  • using the keyword LAW.

  • So here our message HELLO is what also might be called plain text.

  • It is in the clear.

  • It is not enciphered.

  • It is not hidden against any adversary.

  • And our key is LAW.

  • All right, so let's take a look at how we might do this.

  • So it oftentimes helps, especially when trying to encipher or decipher

  • using the Vigenere Cipher, to consider all

  • of the inputs that go into determining the final outputted character.

  • So we're going to take a look at plain text,

  • and we're going to convert it, just like we did

  • with Caesar, to its ordinal position.

  • We're going to see<