0:00

[Music]

Â So, counting is a very important concept in

Â computer science and it's a very powerful tool,

Â because for example, it allows us to count

Â the number of steps that an algorithm would take.

Â And it will allow us to reason about the running time of that algorithm.

Â So that we see the, whether that algorithm is worth implementing, for example.

Â Or how the running time will grow, as the input size grows.

Â But a very, a very powerful application of counting, is also

Â in, in certain, area, that is related to security, computer security.

Â So, for example, one of things that we all deal

Â with or we all use is the notion of passwords.

Â Right?

Â So, we have the, passwords for our credit cards.

Â We have passwords for our computers.

Â Passwords for our bank accounts and so on.

Â And the question is, when you go create a password.

Â Different systems are going to have different requirements on the password.

Â The length of the password, the certain number of characters,

Â that you can use in the password and so on.

Â Now why do, why do we need to have all these requirements?

Â And the answer is, that, has to do with counting and the number

Â of possible passwords that you can have, given these kind of restrictions.

Â So, let me illustrate that by, looking at an extreme

Â case where we say, I say that you have to

Â create your password, the length of the password is one

Â character, and that character can be either 0 or 1.

Â So what are the possible passwords in that case that we can create?

Â There are two possible passwords there, either 0 or 1.

Â And now you can imagine, the security of such a system, right.

Â Because for me, now to, to figure out your password, I can try 0 first.

Â If it works, fine, I am done.

Â If it doesn't work, I do a second attempt.

Â And I will get your password.

Â So, as you can see, this is not a very

Â good system, because there are two possible passwords out there,

Â and if I want to figure out your password, all

Â I need to do is just try these two possibilities.

Â And the other thing is, given that these are the only two passwords we can have.

Â And if we assign these passwords randomly, uniformly to users, we would expect 50%

Â of the users to have this password, and 50% of the users to have this password.

Â So it's going to be very easy for me to

Â break these passwords, and find your password very quickly.

Â Now what happens if, I don't enrich the set of characters you're allowed to use.

Â I still force you to use either 0 or 1 for characters, but

Â now I say, that the length of your password has to be ten characters.

Â So, now, your password, when the system ask

Â you to create a password, you're going to have.

Â 5:03

The space of possible passwords here is much

Â larger now, but this is still not that good.

Â First of all i can go through 1024 numbers very quickly, if i

Â want to try each one of them i can go through them very quickly.

Â Computers are so fast that this will take fractions

Â of a second to try each one of them.

Â And compare it against the password file.

Â The second thing is that, this is going to allow,

Â 1024 distinct passwords, which means, since the number of users in

Â most cases is greater than this, many users will have

Â to use the same password, which is not a good system.

Â All right?

Â So, we are seeing that using the concept

Â of counting, we can tell about the strength.

Â One aspect of the strength of the password, and about the, the space

Â of all possible passwords, so that we can avoid figuring out the password easily.

Â So this, of course.

Â Tells us, using counting.

Â This tells us, that you should not be using password of length ten.

Â And every position is either 0 or 1.

Â It's not good, we can easily find it.

Â Of course, it's not good to use it of length one, and two possibilities.

Â So, the question is in general how many, what,

Â what happens in general for systems, about creating passwords?

Â So, for example, many of the systems that,

Â or websites where you go create a password, it

Â says, you can use any of the English alphabet letters, all the way from a to z.

Â [BLANK_AUDIO]

Â And suppose it is case insensitive, so capital letters, small letters,

Â they are all the same, so I'm just going to consider small letters.

Â And says you can also use, the digits from 0 to 9, okay.

Â So, the size of this set there are 26

Â possible letters and here we have 10 possible letters.

Â So now we're say and suppose i say that, the length of the password has to be 8

Â characters, so now my password, is this vector or list,

Â from 1 to 8.

Â Every value here can be either a or b or c or z or 0, 1, all the way to 9, okay.

Â So, there are 36 possible values, that they could have put here.

Â Now, a same thing here, a, b, c.

Â 36 possible values.

Â The same thing here, 36 possible values.

Â So now what is the possible number of passwords, if the, given these

Â two constraints, that the length is 8 and the number of characters I can use is 36?

Â Now, we have 36 times 36 times 36 times 36 all the way to here.

Â So we have 36 possibilities for the first position.

Â 36 for the second, for the third, for the fourth, for the fifth,

Â for the sixth, seventh and eighth, which is 36 to the 8th.

Â Now, this is a different story, now right,

Â because this is not similar to 1,024, this is a very large number, right.

Â So, even with fast computers, this is not a number that we can,

Â we can go through, all these possibilities

Â very quickly, and find the password, right.

Â This is number one, and number two is that this number is very large, that we are not

Â going to run into this issue, where we have two

Â users choosing the, the same password with very high probability.

Â Now, keep in mind that when we allow the users to choose a random

Â password, there's still always a chance that

Â two users will choose exactly the same password.

Â We cannot stop that.

Â In theory, all users could have chosen the same password.

Â But the thing, when this, the, the

Â number of possible passwords gets larger and larger,

Â the probability of choosing the same password

Â by more than one user starts decreasing, okay.

Â So, this, the counting, allows us to get to do this kind of reasoning.

Â And know why certain constraints on passwords are bad.

Â Why certain constraints are good.

Â Of course, as you can see, from here.

Â I have, I showed before, the, the passwords of length ten.

Â And you can use either 0 or 1.

Â We went from 2 to the 10th.

Â Now, if you use all the English alphabet letters and the

Â digits from 0 to 9, we go to 36 to the 8th.

Â As you can tell, this is bigger than this in two ways,

Â because of, we can get this number to be bigger in two ways.

Â One is, make the possible values that you can use for every entry.

Â Make that set larger and larger, and the second thing is, if you make

Â your password longer, it will even make

Â the space of possible passwords even larger.

Â For example, if I still allow only these letters, but I make

Â the password of length 10, now we go to 36 to the 10th.

Â If I make the password of length 50, then we go to 36 to the 50.

Â And this is, of course, is much bigger than this, this is bigger than this.

Â Okay, so we can always make it longer and we can always enrich this set, okay.

Â So this is how counting allow us, to do this kind of reasoning so that we know.

Â How to design specifications of a password.

Â The last thing I want to say is that, sometimes you see that the system says you

Â have to use a, a letter and you have to use a digit between zero and nine.

Â so it's not anything, it has to be either,

Â it has to contain either and at least one digit.

Â So what does that mean?

Â How does that change our scenario?

Â So suppose we are still working with the

Â password of length 8, and this kind of possibilities.

Â This would be the number of possible

Â passwords, that can have letters or digits.

Â But notice that I'm not putting a constraint here that it

Â has to have letter and a it has to have a digit.

Â Because one of these 36 to the 8.

Â Is for example, a, all a's.

Â All right?

Â But this wouldn't fit my specifications if I say it has to have a digit in it.

Â The same thing.

Â 12:27

So, we can start by saying that 36 to the 8th, is the number,

Â of all passwords of length 8 and that can have any of these letters, okay.

Â Or digits.

Â But out of that, I need to exclude ones that are all letters.

Â So, how many possible passwords, are only letters.

Â There are 26 letters, okay, so there are 26 letters,

Â so 26 times 26 times 26 times 26 and so on.

Â So, I need to subtract all the possible passwords that are only letters.

Â So, these are the possible strings.

Â Or vectors of length 8, where I'm using only letters, okay.

Â So, this will exclude something like this, but also at the same

Â time I need to exclude the ones that are only numbers, okay.

Â And there are, for, that, there are 10 to the 8th that are only digits, okay.

Â So now, this will give me.

Â The number of passwords that every of length 8, every letter is either

Â a letter, every position is either a letter from a to z or a digit from 0 to 9.

Â But I'm going to exclude ones that don't have any digits 0 to 9.

Â I'm going to exclude all ones than don't have any letter a to z.

Â Now, notice that, this is definitely smaller than 36 to the 8th, right?

Â Because it's 36 to the 8th minus very large numbers here, right?

Â So, why would we put this constraint, if it reduces the number of possibilities?

Â Because, I don't, put this constraint, I go back to 36 to the 8th.

Â If I put this constraint, I have reduced the number of passwords significantly.

Â This doesn't have to do much with counting, it has

Â actually to do with something about the predictability of the password.

Â So if I do, if I say for example you can create the password.

Â With only letters, you are allowed to create it with only letters.

Â Remember that, we human beings, don't generate random, really random passwords.

Â I would never create a password for myself that has the form of 1XY2RS2U, right.

Â because this is very hard for me to remember.

Â If you ask me to generate a password, I might use my name as a password, right.

Â So, usually it is predictable that humans are going to use their

Â names, their dog's names, their favorite course number or something like that.

Â So, if i'm not forced to use numbers

Â and special characters like underscore, like star, like

Â equal sign and so on, we might be

Â that, passwords we'll generate might be more predictable, okay.

Â So, the counting tells me something about

Â how big the space of possible passwords are.

Â Then, these kind of constraints that are, or

Â restrictions that we add, are not really about increasing

Â the size of the space in fact, they

Â shrink the size of the space of possible passwords.

Â But they, take away from predictability of these passwords.

Â