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.