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
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/