3
$\begingroup$

Assume we are trying to crack a password. There are $2^{88}$ possibilities.

I have a machine that can test $2^{40}$ passwords per second.

What is the expected time to find the password if I use exhaustive search.

My answer was $2^{88}$ / $2^{40}$ = $2^{48}$ seconds

However, the correct answer is $2^{47}$ seconds, could someone explain to me why is that?

$\endgroup$
5
$\begingroup$

If you check all possibilities, you need $2^{88} / 2^{40} = 2^{48}$ seconds. But actually you needn't check all possibilities because you finish searching when you find the answer.

The time will be approximately normally distributed. And the normal distribution is symmetric around the mean. So the expected time is $2^{48} / 2 = 2^{47}$ seconds.

$\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.