Generating Eight-Character PasswordsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/