Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/