[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. A vector of 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. So, you have to create a password, but the restriction I'm saying, the two restrictions I'm giving is that, the length of the password has to be 10 characters. Every character has to be either 0 or 1. The question now is this harder, and how hard it is for me to break, compared to the previous one where it is of length one, and you have two possible values that you can have in that, in that position. So now, for this, I can either use, for this first character I can either use 0 or 1. For the second one I can use either 0 or 1. For the third, it's either 0 or 1 and so on. 0 or 1. So, examples of such passwords is 0 0. This is a possible password. Another one is. Or, a more interesting one. Right, and so on. The question is, how many such passwords, exist, right? So, in the previous case again, the 2 was of length 1, we had 2 possibilities; so there were only 2 possible words. So now how many possible passwords I have here? So this is where counting comes in to the picture. I say that there are 2 possible ways I can create a, a value here, either 0 or 1. The same thing here, either 0 or 1, so I have 2 times 2, also 2 times 2 all the way to 2, 10 times. So this value is 2 to 10th, okay. And 2 to the 10th is special in computer science. We know that this value is 1,024, okay. So, we can create 1,024 distinct passwords. If I allow the password, if I allow the password to be of length 10 and in every position, I can use either 0 or 1. Now notice that. 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. All zero's. It's part of this, but it wouldn't fit my specifications if I say it has to have a letter in it, so this. If I am saying that the password is of length 8, you can use a through z and 0 through 9. You have to have at least one letter. And at least one digit, okay, or one number. So now, it's not this, it's smaller than this, because again, this includes ones that don't satisfy this condition, where I don't like these two, okay. So now what, how do I get the number? Again, we just have to do counting a bit more accurately. 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.
