Consider the following five events:

  1. Correctly guessing a random 128-bit AES key on the first try

  2. Winning a lottery with 1 million contestants

  3. Winning a lottery with 1 million contestants 5 times in a row.

  4. Winning a lottery with 1 million contestants 6 times in a row

  5. Winning a lottery with 1 million contestants 7 times in a row

What is the order of these events from most likely to least likely?

  • $\begingroup$ Possible outcomes (do not know correct english term), least likely to most likely: (5) $=(10^6)^7 = 10^{42}$, (1)$=2^{128} \approx 10^{38}$, (4)$=(10^6)^6 = 10^{36}$, (3), (2) $\endgroup$ – Fleeep Nov 22 '15 at 8:16
  • $\begingroup$ thanks. but would you solve it for (2) & (3)? $\endgroup$ – farnaz Nov 22 '15 at 10:49
  • $\begingroup$ @farnaz: Hint for solving this basic and excellent exercise: Express odds of events 1..5 as a power of two. For events 2..5, use that a million is a thousand thousands, and a thousand is $10^3=1000$, which is only few percents from $1024=2^{10}$. You should be able to find the answer without even pencil and paper, much less a calculator. $\endgroup$ – fgrieu Nov 22 '15 at 12:24
  • 1
    $\begingroup$ @fgrieu You've got a point. I don't think either method strains our brains to capacity though :) $\endgroup$ – Maarten Bodewes Nov 22 '15 at 13:24
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is about counting, with only a superficial application to cryptography. $\endgroup$ – Gilles 'SO- stop being evil' Nov 22 '15 at 19:37

To randomly guess a single key from a 128-bit key space has a chance of 1 divided by the number of elements or $\frac{1} {2^{128}}$ where $2^{128}$ is the number of keys possible.

To get ballpark figures to convert between base 2 exponents and base 10 exponents you can use the following trick:

Because $2^{10} = 1024 \approx 10^3$ you can easily count the number of decimal digits, then divide by 3 and multiply with 10. To go from the number of bits to the number of decimal digits multiply by 3 and divide by 10.

If you want to be more precise: you can divide or multiply with the constant value $\log_2(10) = \frac1{\log_{10}(2)} = \ln(10) / \ln(2) = 3.321928094\ldots$

(easy to remember in your pocket calculator or phone).

So as an AES key is 128 bits you can easily see that it represents about $10^{\frac {128 * 3} {10}} = 10^{38.4}$ possible values. The bigger the possible value the less likely it is to guess (or brute force) one.

To get to the possibility of winning the lottery you have to calculate $\frac1n$ where $n$ is the number of contestants. To calculate the chance of winning it x times in a row you have to calculate $(\frac1n)^{x}$ which is equal to $\frac1{n^x}$.

As you can see that one million is $10^6$ you can then see that winning it 5 times in a row would be identical to pick one value out of $10^{6^5} = 10^{30}$ values. So you have a significantly better chance of winning the lottery 5 times: $\frac1{10^{30}}$ than picking a random 128 bit AES key: $\approx \frac1{10^{38.4}}$


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