2
$\begingroup$

Sorry for yet another password/combinatorics problem but I haven't seen this one answered yet. Let's say I must pick a $12$-character password that has $2$ uppercase, $2$ lowercase, $2$ digits, and $2$ special characters (assume $33$ possibilities for special characters).

So, I've worked it out as follows. Let's assume we place the $8$ required characters at the beginning of the password. We have $8!$ different possible places to put them ($40320$). After that, to distinguish between the characters, we need to multiply as follows: $$8! \newcommand{\xt}{\times} \xt 26 \xt 26 \xt 26 \xt 26 \xt 10 \xt 10 \xt 33 \xt 33 = 2.00 \xt 10^{15}$$. Now, to account for the remaining $4$ characters (and all other possible password combinations), we want to multiply $(2.00 \xt 10^{15}) \xt (95^4) = 1.63 \xt 10^{23}. Is my thinking at all correct with this?

$\endgroup$
  • 2
    $\begingroup$ You are assuming that the eight special characters are all in the first eight positions. How do account $aaaaAAbb11çç$? $\endgroup$ – Jack D'Aurizio Aug 15 '14 at 0:13
1
$\begingroup$

This looks like you have to use inclusion-exclusion and it will still be a mess. You have a total alphabet of $26+26+10+33=95$ characters. To get the ones that have at least two lower case, you can subtract the ones that have no lower case $(95-26)^{12}$ and the ones that have only one $12\cdot 26 \cdot 69^{11}$ Now subtract the ones that have no upper case, but you have subtracted the ones that have neither upper nor lower case twice, so add them back in.

$\endgroup$
0
$\begingroup$

Another way to think about it is that for any placement of uppercase, lowercase, digit , and special characters for that particular placement there are 49764686400 combinations since $$(26^{4})(10^2)(33^{2})=49764686400$$ Now to find how many combinations there are of placement of each category (uppercase, lowercase, digit, and special characters) we can use the multinomial coefficient $$12 \choose 2,2,2,2$$ So the required characters we have ${12 \choose 2,2,2,2}(26^{4})(10^2)(33^{2})=1.489\times10^{18}$ Now for the remaining ones we have that for any placement of characters we have there are $(95^{4})=81450625$. Thus finally we have the number of possible passwords is $${12 \choose 2,2,2,2}(26^{4})(10^2)(33^{2})(95^4)=1.489\times10^{18}(81450625)=1.2134\times 10^{26}$$

$\endgroup$
  • $\begingroup$ I think it is a bit more delicate. What if you choose two special characters in the remaining four positions? You accounted such possibility twice. $\endgroup$ – Jack D'Aurizio Aug 15 '14 at 0:16
  • $\begingroup$ oh you are completely right. $\endgroup$ – Kamster Aug 15 '14 at 2:34
0
$\begingroup$

There is a simple way to get a pretty accurate answer. That way is Monte Carlo simulation. I did a simulation on this problem and arrived at an answer of 1.23e+23 ways, which is about 22.8 percent of the number of passwords that would be possible without any restrictions.

To get the number of ways you can express a decimal number with 12 digits, you raise 10 to the power 12. Since we are given 95 symbols, we raise 95 to the power 12. So, with no restrictions, we have 95^12 ~= 5.4e+23. This sets an upper bound. One of the above answers is larger than the upper bound, so it must be incorrect. It seems reasonable to expect that the correct answer should not be radically lower than 5.4e+23, since we have 12 digits and a legal password is only required to have a minimum of two of each type of symbol, and there are only 4 types of symbols.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.