1
$\begingroup$

I have been super stuck on this problem for a while and thought I turn to some expert help. My problem question:

A password has length $8$ with a mix of $1$ uppercase letter (from $A$..$Z$), $5$ lowercase letters (from $a$...$z$) and $2$ digits (from $0$...$9$). Bob is trying to guess the password and does not know in which order these characters occur in the password.

Suppose that all characters in the password are different and Bob discovers the position of the lowercase letters and one of them is $'w'$(without knowing which one). Bob then writes a program that repeatedly chooses one of the possible passwords uniformly at random, and tries it.

The program tries $6000$ trials per second. What is the expected value of the number of minutes until Bob guesses the password?

I have an inkling that this is related to Bernoulli trials and/or geometric distribution but I don't know where and how to start. Please help.

$\endgroup$
1
$\begingroup$

We first need to determine the range of possible passwords. The lowercase letters are in known positions and the w can be put in any one of those $5$ positions. There are then (since all characters are different) $25×24×23×22$ ways to assign the remaining lowercase letters.

For the uppercase letters and digits there are

  • $3$ positions where the uppercase letter can be placed
  • $26$ possibilities for the uppercase letter
  • $10×9$ ways to assign the digits

Multiplying the numbers together gives $10,656,360,000$ possible passwords. Bob's random search program would, per guess, hit the correct password with probability $\frac1{10,656,360,000}$, and the number of guesses required is a geometric distribution with this tiny number as success probability. Therefore, the expected number of trials to success is the reciprocal of this tiny number, i.e. $10,656,360,000$ (this is a property of the geometric distribution).

Dividing the large number by $6000$ tries/second and then by $60$ seconds/minute shows that Bob requires $29601$ minutes on average to guess the password. This is around $20.5$ days, but remember that modern GPUs can be marshalled to crack passwords of this length nearly instantaneously.

$\endgroup$
  • $\begingroup$ Since w has already been discovered but the position is not known, wouldn't this remove one letter from the alphabet as the remaining 4 lowercase letters and the uppercase can't be w? My initial understanding was 25 x 24 x 23 x 22 x 21 x 10 x 9. $\endgroup$ – Moonshine45 May 26 at 15:02
  • $\begingroup$ @Moonshine45 I interpret $W$ as different from $w$. $\endgroup$ – Parcly Taxel May 26 at 15:17

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.