0
$\begingroup$

Supposed we have a password policy with the following requirements:

  • Can only contain lower letter, upper letter or digits (a-zA-Z0-9)
  • Must have 8-chars
  • Must start with a lower letter (a-z)
  • Must have at least one number (0-9)
  • Must have at least one lower letter (a-z)
  • Must have at least one upper letter (A-Z)

How do i calculate the number of all possible combinations?

$\endgroup$
  • $\begingroup$ How many passwords with $8$ characters are there that start with a lowercase letter? How many of those are invalid due to the other 3 constraints? $\endgroup$ – vrugtehagel Mar 24 '17 at 16:54
  • $\begingroup$ Must have exactly eight characters? $\endgroup$ – David G. Stork Mar 24 '17 at 17:17
  • $\begingroup$ @DavidG.Stork: I'm assuming yes; otherwise, there are an arbitrarily large number of valid passwords. $\endgroup$ – Brian Tung Mar 24 '17 at 17:22
  • $\begingroup$ @DavidG.Stork, yes. exactly 8 characters $\endgroup$ – SomeU Mar 24 '17 at 17:59
1
$\begingroup$

The condition that the first letter be lower case automatically satisfies the later condition that there be at least one lower case letter present, so we may ignore that condition in the rest of our calculations.

We ask the sub-question: how many $7$-character passwords with at least one uppercase letter and at least one number are there? We approach by inclusion-exclusion.

Let $A$ be the set of 7-character passwords which contain at least one uppercase letter and $B$ the set of 7-character passwords which contain at least one number. Let $S$, our universal set, be the set of 7-character passwords regardless of either of those two conditions. We are searching then for the value of $|A\cap B|$.

By De'Morgan's $|A\cap B|=|S\setminus (A^c\cup B^c)|$ which by inclusion-exclusion is $|S|-|A^c|-|B^c|+|A^c\cap B^c|$

We have $|S|=(10+26+26)^7=62^7$

We have $|A^c|=(10+26+0)^7=36^7$

We have $|B^c|=(0+26+26)^7=52^7$

We have $|A^c\cap B^c|=(0+26+0)^7=26^7$

We have the total number of $7$-character passwords with at least one uppercase letter and at least one number are $62^7-36^7-52^7+26^7$

Finally, since any 8-character passwords satisfying your conditions can be uniquely described as a lower case letter followed by a 7-character password with at least one uppercase and at least one number, we bring our final total for the original problem to:

$26\cdot (62^7-36^7-52^7+26^7)=63003474293760$

$\endgroup$
1
$\begingroup$

We use the Inclusion-Exclusion Principle.

Since the first position must be occupied by a lower case letter, we are guaranteed to have at least one lower case letter.

Since there are $26$ lower case letters, $26$ upper case letters and $10$ digits, if there were no further restrictions, we could fill the remaining positions in $(26 + 26 + 10)^7 = 62^7$ ways, giving us $26 \cdot 62^7$ passwords. However, we must exclude those passwords with no digits, no upper case letters, or both.

The number of passwords with no digits is $26 \cdot (62 - 10)^7 = 26 \cdot 52^7$.

The number of passwords with no upper case letters is $26 \cdot (62 - 26)^7 = 26 \cdot 36^7$.

The number of passwords with neither an upper case letter nor a digit is $26 \cdot (62 - 26 - 10)^7 = 26 \cdot 26^7$.

Notice that if we subtract the number of passwords with no upper case letters and the number of passwords with no digits from $26 \cdot 62^7$, we will have subtracted those passwords with neither an upper case letter nor a digit twice, once when we subtracted the number of passwords with no upper case letters and once when we subtracted the number of passwords with no digits. Since we only want to subtract these numbers once, we must add them back. Hence, by the Inclusion-Exclusion Principle, the number of permissible passwords is $$26 \cdot 62^7 - 26 \cdot 52^7 - 26 \cdot 36^7 + 26 \cdot 26^7 = 63,003,474,293,760$$

$\endgroup$
  • $\begingroup$ @JMoravitz Thank you. Clearly, you did a better job proofreading than I did. $\endgroup$ – N. F. Taussig Mar 24 '17 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.