Chapter 1. Math and Security

Unfortunately, it is necessary for you to learn some math in the network security course. If you had a look at the course notes, you know what I mean. Security has borrowed many tools from mathematics (see the list below for some examples) and in some sense, many theories in security can be seen as the natural progressions of mathematics. This is particularly true of cryptography.

Mathematics also allows people to formally define and rigorously prove security. This is another point why mathematics is so important in security. For example, if you designed a new cipher, how can you convince me that your cipher is secure?

Here is an example how to mathematically construct and cipher and how to define and prove security using formal math language.

In 1917, Gilbert Vernam invented a cipher for use on telex machines. The idea is quite simple. At the sender side, each transmitted 5-bit Baudot code was mixed with a random 5-bit code on a paper tape (see the graph below). At the receiver side, a copy of the tape used in encryption is used to decrypt the ciphertext. The mathematical operation used in encryption and decryption is XOR (exclusive OR). The key has the same length as the message and must be used only once.

In his paper, Vernam claimed : If the key used with this type of cipher is made very long, so that it never repeats and if any portion of this key is never used for more than one message, the operation of "breaking" the cipher becomes very much more difficult. If, now, instead of using English words or sentences, we employ a key composed of letters selected absolutely at random, a cipher system is produced which is absolutely unbreakable. This claim, however had been left unproved until 25 years later Claude Shannon introduced the concept of perfect secrecy and demonstrated that the Vernam cipher archives this level of security.

So what is perfect secrecy? A cipher is perfectly secret if for every message m and every ciphertext c we have:

Pr [ M = m | C = c ] = Pr [ M = m ]

How to read this equation? M is a random variable representing all possible plaintexts and C is a random varaible representing all possible ciphertexts. Pr [ M = m ] is called the a priori probability. It is the estimated probability of the plaintext being a particular message m before seeing the ciphertext. And Pr [ M = m | C = c ] is called the a posteriori probability, which is the estimated probability of the plaintext being a particular message m after knowing that the ciphertext is c. The intuition behind this definition is that if the ciphertext contains some information which can help you to recover the plaintext, then after knowing the ciphertext, you will have a better chance of determining the plaintext than when you have nothing. On the other hand, if the probability is unchanged, then the ciphertext you've got contains no useful information about the plaintext. And since the ciphertext contains no useful information about the plaintext, the cipher is secure.

Is the Vernam cipher perfectly secret? Before giving the proof, let us have a look at a simple case so you will have an intuitive conviction. Consider now you have only one bit to encrypt. So the plaintext M can be either 0 or 1. Let the probability of M=0 be p, then the probability of M=1 is 1-p. Since the plaintext is only one bit, in Vernam cipher, you generate a one-bit key randomly. The relation ship between the plaintexts, keys, ciphertext and the probabilities can be summarised in the following table:

 K=0 (0.5)K=1 (0.5)
M=0 (p)C=0 (p1 = 0.5p)C=1 (p2 = 0.5p)
M=1 (1-p)C=1 (p3 = 0.5(1-p))C=0 (p4 = 0.5(1-p))

If the ciphertext you've got is 0, then the plaintext can be 0 in the case that the key is 0, or the plaintext can be 1 in the case that the key is 1. Similarly, if the ciphertext you've got is 1, then the plaintext can be 0 in the case the key is 1, or the plaintext can be 1 in the case that the key is 0. Then the following four probabilities can be calculated:

So in one-bit case, the Vernam cipher indeed satisfies the definition of perfect secrecy. The general proof for arbitrary length Vernam cipher follows the same intuition. If you are interested, you can find it here.

This page was translated into Estonian by Weronika Pawlak at