2
$\begingroup$

Suppose you're given a task to find the number of configurations for a password with the following stipulations;

1) there must be at least 8 characters (and let's assume a limit of 16 characters)

2) there must be at least 1 upper case character and at least 1 lower case

3) there must be at least 1 digit

4) there must be at least 1 special character (e.g., ., -, _, !, @, *, %)

With 26 letters both lower case and upper case (a-z), 10 digits (0-9), and 33 special characters, it seems we have a total combination of $95^8$ (of course, this is too simple because we don't want to neglect or re-use any of the above stipulations).

In the end, how many configurations may exist in an orderless, ≥8-character password such as this? Can you demonstrate how this is solved using summation notation?

$\endgroup$
  • 1
    $\begingroup$ If there is no limit to the number of characters there is an infinite number of passwords. Append aA! to any number $10000$ or above and you have a legal password. $\endgroup$ – Ross Millikan Sep 5 '18 at 4:30
  • $\begingroup$ Right, in that case, then let's assume a limit of 16 characters since I imagine that's as far as most people will ever ago. $\endgroup$ – user581844 Sep 5 '18 at 4:42
  • 1
    $\begingroup$ The usual approach is to compute the number of passwords without the restrictions, like your $95^8$ then subtract the ones that violate each restriction. You need inclusion-exclusion because you subtract the ones that violate more than one restriction more than once. $\endgroup$ – Ross Millikan Sep 5 '18 at 4:55
  • $\begingroup$ @user581844: Where did this magic upper limit of $16$ come from? It isn't in the problem. $\endgroup$ – David G. Stork Sep 5 '18 at 4:57
  • $\begingroup$ @DavidG.Stork Well, I could use a limit of say, 100, which is the limit for a Gmail account password. Some websites have other limits that may be lower or even higher. Because the limit is going to be arbitrary, and because we cannot have an infinite amount, it's best to just use a limit that is reasonable in the real world. $\endgroup$ – user581844 Sep 5 '18 at 5:02
2
$\begingroup$

Using the principle of inclusion exclusion, you can write it as a sum of $15$ exponential terms, where the exponent ranges from $8$ to $16$. If you like, this can be written without a summation using the finite geometric series formula.

\begin{align}\sum_{n=8}^{16}\begin{cases}95^n\\ -(95-26)^n-(95-26)^n-(95-10)^n-(95-33)^n \\+(95-52)^n+2(95-36)^n+2(95-59)^n+(95-43)^n \\-26^n-26^n-10^n-33^n\end{cases} \end{align}

$\endgroup$
1
$\begingroup$

The number of passwords of length 8 to 16 with those restrictions is $36430117984090740313099435877280 \approx 10^{31.56}$.

(Assuming my code is right :)

nLower = 26
nUpper = 26
nDigits = 10
nSpecial = 33

nTypes = (nLower, nUpper, nDigits, nSpecial)
minOfType = (1, 1, 1, 1)

def count(length, minRequired, nAvailable) :
  if sum(minRequired) > length:
    return 0
  if length == 0 :
    return 1

  s = 0L
  for i,n in enumerate(nAvailable):
    m = list(minRequired)
    m[i] = max(m[i]-1, 0)
    s += n * count(length-1, tuple(m), nAvailable)
  return s

print sum([count(k, minOfType, nTypes) for k in range(8, 17)])
$\endgroup$

Your Answer

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