Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Entropy in Cryptography?
3.
Importance of Entropy in Cryptography
4.
Calculating Entropy
5.
Properties of Entropy
5.1.
Jensen’s inequality
5.2.
Theorem-1
5.3.
Theorem-2
6.
Conditional Entropy
7.
Sources of Entropy in Computing
8.
Frequently Asked Questions
8.1.
What is low entropy in cryptography?
8.2.
Does encryption change entropy?
8.3.
Why is Minimum entropy significant in cryptography?
8.4.
What does entropy mean in security?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Entropy in Cryptography

Author Yukti Kumari
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We all are familiar with Cryptography. With increasing cyber attacks, there has been an increase in cyber security measures as well to protect sensitive information. 

One such field is cryptography which deals with providing confidential communication between trusted parties, and in most cases, the secret key 🔑  is employed for this purpose.

Now, after encrypting the system, we want to ensure whether a cryptanalyst can attack the system or not 🔏. That's where Entropy comes to the rescue.

Entropy in Cryptography

In this article, we will learn about entropy in cryptography, its importance, properties, how to calculate entropy, and sources of entropy in computing in the real world. 

Let's get started 🔰

What is Entropy in Cryptography?

Shannon introduced the idea of entropy in 1948, which is defined as the measure of information or uncertainty. We compute entropy as a function of a probability distribution.

But how do we use entropy in cryptography? 🤔

We use entropy to produce several random numbers, which in turn helps to create security keys for protecting sensitive information. Now, the security value of the key depends on the quality of random number generation.
 

What do we mean by high entropy?

High entropy means that the data is totally random, and you can't find any meaningful patterns. 

On the other hand, low entropy implies there is a possibility to predict forthcoming generated values.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Importance of Entropy in Cryptography

You can measure the quality of cryptographic functions by finding the entropy of their outputs. We chose the algorithm with high entropy for encryption and hash functions.

Moreover, entropy is crucial for generating random inputs, like security keys, nonces, and initialization vectors, for cryptographic algorithms. Since these values should be purely random, i.e., non-predictable and completely secret, we need to have high entropy sources of data.

Calculating Entropy

Let's first understand entropy by an example. 

Suppose you have a discrete random variable X, which denotes the toss of a coin. We know that there are only two possible outcomes, heads, and tails. 

So, Probability[heads] = Probability[tails] = ½.

Now, what is the entropy of a coin toss?

The entropy or the information of the coin toss is 1 bit. Why? As we can encode the two outcomes, heads and tails, by using 1 bit, say, 1 for heads and 0 for tails.

Similarly, if you have n coin tosses, then the entropy will be n bits, one bit for each coin toss. You can encode the n coin tosses by a binary string of length n, where the i’th character represents the result of the i’th toss. 

Basically, the entropy of a random variable X following a specific probability distribution is nothing but the number of bits by which we can encode it. 

More formally, we have - 

An outcome occurring with probability p might be encoded by a bitstring of length: ceil(log2p).

Moving towards a more formal definition of entropy, we have - 

Suppose X is a discrete random variable that takes on values from a finite set X. Then, the entropy H(X) of the random variable X is defined to be the quantity

Formulae of H(X)

Where Pr[x] is the probability of x.

Some of the interesting points about H(X) are

  • A particular case, for which |X| = n and Pr[x] = 1/n for all x∈X, H(X) is equal to logn(base 2). 
  • H(X) >= 0 for any random variable X.
  • H(X) = 0 if and only if Pr[x0] = 1 for some x0 ∈ X and Pr[x] = 0 for all x ≠ x0.
     

How to Compute the Entropy of a cryptosystem?

Suppose the random variables associated with the key, plaintext, and ciphertext are K, P, and C, respectively. 

Then we can find the entropies for each of them individually as H(K), H(P), and H(C). 

Properties of Entropy

In this section, we will see some of the fundamental results related to entropy, along with their proofs. 

Before moving further, let's introduce a theorem, “Jensen’s inequality,” which is a prerequisite for the properties we discuss.

Jensen’s inequality

Suppose f is a continuous strictly concave function on the interval I. Suppose further that 

Formulae

and ai > 0, 1 ≤ i ≤ n. Then

Formulae

where xi ∈ I, 1 ≤ i ≤ n. Additionally, equality occurs if and only if x1 = · · · = xn.

Theorem-1

Suppose X is a random variable having a probability distribution that takes on the values p1, p2, . . . , pn, where pi > 0, 1 ≤ i ≤ n. Then H(X) ≤ log2 n, with equality, if and only if pi = 1/n, 1 ≤ i ≤ n.

Let's see the proof of this theorem below.

Applying Jensen’s inequality, we get: 

Formulae

 

We can see that equality occurs if and only if pi = 1/n, 1 ≤ i ≤ n

Theorem-2

H(X, Y) ≤ H(X) + H(Y), with equality if and only if X and Y are independent random variables.

Let's see the proof of this theorem below. 

We compute H(X) + H(Y) as follows:

Formulae

Here, 

  • pi = Pr[X = xi ], 1 ≤ i ≤ m 
  • qj = Pr[Y = yj ], 1 ≤ j ≤ n 
  • rij = Pr[X = xi , Y = yj ], 1 ≤ i ≤ m, 1 ≤ j ≤ n, where Pr[X, Y] is joint probability distribution

Also, Formula and Formula.

 

Similarly, we compute H(X, Y) as

Formula

 

Now, we combine the above two equations as

Formulae
 

You can observe that the equality, i.e., H(X, Y) = H(X) + H(Y), occurs when there is a constant

c such that piqj/rij = c for all i, j.

It follows that c=1 according to 

Formulae

So, equality occurs if and only if rij = piqj orPr[X = xi , Y = yj ] = Pr[X = xi ]Pr[Y = yj ].

This means that X and Y are independent, hence, proved.

Conditional Entropy

The conditional entropy of two random variables, X and Y, H(X|Y), is defined as the average amount of information about X that Y. does not reveal.
 

We calculate the weighted average of the entropies H(X|y) over all possible values y of Y to find the value of H(X|Y).

 

H(X|y), i.e., the conditional probability distribution of X for a fixed value y of Y is given as

Formulae

So, we compute H(X|Y) as

Formulae
 

The properties associated with conditional entropy are as follows:

  • H(X, Y) = H(Y) + H(X|Y)
  • H(X|Y) ≤ H(X), with equality if and only if X and Y are independent.

Sources of Entropy in Computing

Computers can generate random numbers, but did you know that those numbers are not truly random in nature!! 

Instead, they are pseudorandom.  

So, to overcome this shortcoming, some of the sources to derive entropy are as follows:

✅ Audio and Video data

✅ The timing of the interrupts from storage devices like hard-drive, etc.

✅ Mouse movements

✅ Timings of keyboard inputs

✅ Timing of network packets

✅ Circuit Voltage

✅ Thermal Readings

Frequently Asked Questions

What is low entropy in cryptography?

Low entropy data provides the ability or possibility to predict forthcoming generated values.

Does encryption change entropy?

Both compression and encryption schemes increase the entropy of plaintext because there are not as many patterns present as in natural language.

Why is Minimum entropy significant in cryptography?

The min-entropy is a widely used metric to quantify the randomness of generated random numbers in cryptographic applications; it measures the difficulty of guessing the most likely output.

What does entropy mean in security?

A measure of the amount of uncertainty an attacker faces to determine the value of a secret.

Conclusion

In this article, we learned about entropy in cryptography, the importance of entropy, how to calculate entropy, and its properties. Finally, we also saw some of the sources of entropy used in the real world. 

We hope this blog has helped you enhance your knowledge of Entropy in Cryptography.

Check out these fantastic blogs on Cryptanalysis - 

🎯 What is Linear Cryptanalysis?

🎯 Substitution-Permutation Networks (SPN) in Cryptography

🎯 Difference Between Differential and Linear Cryptanalysis

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!!

Previous article
Perfect Secrecy in Cryptography
Next article
What are Spurious Keys and Unicity Distance?
Live masterclass