Skip to content

Probability

Table of contents

Open Table of contents

What it is

Probability is a very useful and important topic to study in the context of Cryptography as it’s closely related to randomness, which is the underpinning of most cryptographic constructions.

With the help of probability we can calculate the likelihood of an event happening / not happening and therefore estimate the security guarantees an algorithm based on randomness provides (e.g. a key generation algorithm).

Ranges of probabilities

The result of a probability calculation is a value between 00 and 11 that expresses the likelihood of an event occurring. The higher the value, the more likely it is that the event happens.

A value 00 expresses that “the event never happens”, whereas a value of 11 indicates that “the event always happens”.

This implies that a 50% chance of an event taking place can be expressed through the value 0.50.5.

Probability in Cryptography

In Cryptography, we’re often interested in the likelihood of an attacker breaking a construction.

This probability pp can be expressed via a calculation where the number of successful events is divided by the total number of possible events.

p=successfultotalp = \frac{successful}{total}

If we want to calculate the likelihood of an event not happening, we need to subtract the probability pp that the event happens from 11.

1p=1successfultotal1 - p = 1 - \frac{successful}{total}

As an example, let’s assume that we have a symmetric cipher that uses a 256-bit key for encryption. We know that the cipher itself doesn’t expose any design flaws that can be exploited to recover a plaintext given its corresponding ciphertext.

The only attack we can deploy is a brute-force key search in which we simply try every possible key and see if the key allows us to decrypt the ciphertext.

How likely is it that we’ll be successful using such an attack?

We know that there’s exactly 11 key that was used and we also know that there are 22562^{256} possible keys we need to try. Using the formula from above we can calculate the success probability of such an attack as follows.

p=successfultotalp=12256p=0.0000000000...p0\begin{aligned} p &= \frac{successful}{total} \\ p &= \frac{1}{2^{256}} \\ p &= 0.0000000000... \\ p &\approx 0 \end{aligned}

This shows that it’s highly unlikely that the key we’ve chosen at random is the correct one. Conversely we can also calculate the likelihood that the randomly chosen key is the wrong one.

1p=1successfultotal1p=1122561p=1.0000000000...1p1\begin{aligned} 1 - p &= 1 - \frac{successful}{total} \\ 1 - p &= 1 - \frac{1}{2^{256}} \\ 1 - p &= 1.0000000000... \\ 1 - p &\approx 1 \end{aligned}

As we can see, it’s very likely that the key we picked randomly is the wrong one.

Additional Resources