Cryptography Reference
In-Depth Information
But the probability isn't quite so simple. There's the possibility that both cards are of the suit, none are, or
just the first or the second one is. Rather than try to add up the probabilities of each of these events occurring,
we can take the probability that neither card is of the desired suit, and reverse it (by subtracting it from 1). In
this case, we have 9 cards that we are avoiding out of 47, and therefore 47 - 9 = 38 cards that are desired. We
then have to try our luck again, and attempt to get none of those 9 out of the 46 left, so we have 37 to choose
from. Since these happen in succession, we multiply
This is the probability that we fail in our endeavor to get the flush. Therefore, the probability that we get it is
the above subtracted from 1, which is about 0.3497, or 34.97%.
We won't venture further into poker probabilities here (although there is some more investigation in the ex-
ercises), but cryptanalysis is much like poker in some regards. In cryptanalysis, we often are trying to get a key,
which can be like trying to figure out the other person's hand, or trying to figure out how to win the game.
Nearly every technique in cryptanalysis is probabilistic and statistical: It works, statistically, some of the time,
and the trick is figuring out how much of that time it does work, and adjusting the algorithms appropriately.
2.1.3 The Birthday Paradox
The
birthday paradox
is an important concept in cryptanalysis. This “paradox” shows that the probabilities
aren't always what they first seem.
The traditional telling of the paradox is to ask someone, “How likely is it that two people have the same
birthday?” Here, we are interested in the probability of a
collision
occurring, where two events have the same
result. Intheory,the correct answer is not too difficult to figure out —1/365 ≈ 0.274%(not including leap years,
or taking into account any other factors that will skew this number in real life). The two events are
independent
— the first person's birthday doesn't influence the birthday of the second person. Assuming uniform distribu-
tion of birthdays, then the first person's birthday will be a random day. This means that we can just assume that
the first person's birthday is fixed: It won't be changing. We take the second person's birthday as being random
as well. The probability that it is going to happen to coincide with the first person's birthday is the same prob-
ability that it would happen to be any other day as well, since they are all equally probable: 1/365.
But what happens if you ask the question, “What is the probability that at least two people out of three have
the same birthday?” This is where things start to get a bit messier. If we are just concerned with collisions in
general (not caring which particular pair of people shares a birthday, as long as one pair does), then we now
have three different pairs to consider: 1-2, 2-3, and 1-3. Any of these pairs might share a birthday.
What is now the probability that a collision occurs in these three pairs? We might also naively answer, “Just
add the probabilities of one collision together three times!” This does seem logical at first, but this does not
scale well. We have to start considering cases such as if there were, say, 400 people. This would mean =
79,800 different pairs, and therefore a 79,800 × (1/365) = 218.63% probability, which is ludicrous. Hence, this
is definitely not the right way.
This is because, once you add a third person, you aren't just adding one more day to check; you are adding
two possible days, since the third person could match the first or the second. Therefore, adding a second day
significantly increases the probability that a collision occurs. However, eventually this will slow down to the
point where adding an additional person is unlikely to greatly affect the probability. For example, if you have a
group of 363 people and another group of 364 people, there is nearly no difference in the two groups' possibility
of having a repeat birthday.
Search WWH ::
Custom Search