Generating Eight-Character Passwords

Date: 03/08/2002 at 12:00:01
From: Lohkee
Subject: Generating Eight-Character Passwords

Suppose, for example, we have a rule that states that all passwords 
must be eight characters in length and contain at least one character 
from each of the following four sets: uppercase alpha (26), lowercase 
alpha (26), numeric (10), and punctuation or other special characters 
(33).  

Assuming an eight-character password, an analysis of this rule would 
yield the following: 

   Without the rule, a user's password can be from one to eight 
characters in length, and may use any one of ninety-five characters in 
each position. The total number of possible passwords is 

  95^1 + 95^2 + 95^3 + ... + 95^7 + 95^8 = 6,704,780,954,517,120

   With the rule in place, the user's password must be eight 
characters in length and include at least one character from each of 
the four sets.  The number of possible passwords, assuming an eight-
character password for side-by-side comparison, is now only  (     ) 
or   X.  Put another way, how many passwords become impossible because 
of this rule?

Date: 03/08/2002 at 14:19:53
From: Doctor Ian
Subject: Re: Generating Eight-Character Passwords

Hi Lohkee, 

Let's start with all the possible 8-character passwords.  There are 95^8 different of those.  

Now, eliminate all the illegal passwords, i.e., those where

  [1] there is not at least one uppercase character
    
      (There are (95-26)^8, or 69^8 of these.)
  
  [2] there is not at least one lowercase character

      (There are (95-26)^8, or 69^8 of these.)

  [3] there is not at least one digit

      (There are (95-10)^8, or 85^8 of these.)

  [4] there is not at least one special character

      (There are (95-33)^8, or 62^8 of these.)

This leaves

  95^8 - (69^8 + 69^8 + 85^8 + 62^8)
  
passwords.  But alas, but we've counted some illegal passwords more 
than once!  For example, 'aaaaaaaa' falls into categories 1, 3, and 4.  

In fact, if we let [a,b,c] mean 'the number of passwords that fall
into categories a, b, and c simultaneously', then what we want is

  95^8 - [1] - [2] - [3] - [4]
       + [1,2] + [1,3] + [1,4] + [2,3] + [2,4] + [3,4]
       - [1,2,3] - [1,2,4] - [1,3,4] - [2,3,4]
       
This is an application of the inclusion-exclusion principle:

  Inclusion-Exclusion Principle
  http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html
  
Thinking about 'aaaaaaaa', we would 

  subtract it three times (as part of [1], [3], and [4]), 
  then add it back three times (as part of [1,3], [1,4], and [3,4]),   
  then subtract it again once (as part of [1,3,4])  

Which is to say, we'd end up subtracting it one time, which is what we want. 

So let's see what those terms come out to be:

  [1]        =   (95-26)^8      =  69^8
  [2]        =   (95-26)^8      =  69^8
  [3]        =   (95-10)^8      =  85^8
  [4]        =   (95-33)^8      =  62^8
  [1,2]      =   (95-26-26)^8   =  43^8
  [1,3]      =   (95-26-10)^8   =  59^8
  [1,4]      =   (95-26-33)^8   =  36^8
  [2,3]      =   (95-26-10)^8   =  59^8
  [2,4]      =   (95-26-33)^8   =  36^8
  [3,4]      =   (95-10-33)^8   =  52^8
  [1,2,3]                       =  33^8            
  [1,2,4]                       =  10^8
  [1,3,4]                       =  26^8
  [2,3,4]                       =  26^8

When we add (and subtract) it all up, we get

  95^8 - 69^8 - 69^8 - 85^8 - 62^8 
       + 43^8 + 59^8 + 36^8 + 59^8 + 36^8 + 52^8 
       - 33^8 - 10^8 - 26^8 - 26^8
       
  = 3,025,989,069,143,040    

I hope this helps.  Please write back if you'd like to talk about this 
more.

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/