Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I understand that the entropy is the number of bits that can encode a set of messages. However, I don't understand what the min-entropy is and how it is related to entropy.
Let's describe a simple password case: if a password is 100 random bits, is the min-entropy also 100?
There is min-entropy, Shannon entropy, and max entropy. (Plus a few more definitions, but let's only focus on these.) All of these measures are greatest, for a given number of outcomes, when each outcome occurs with equal probability. (In such case all three are equal.)
$$\text{min-entropy} \leq \text{Shannon entropy} \leq \text{max-entropy}$$
Min-entropy describes the unpredictability of an outcome determined solely by the probability of the most likely result. This is a conservative measure. It's good for describing passwords and other non-uniform distributions of secrets.
$$\text{min-entropy} = -\log_2{(p_{\text{max}})}$$
Say you have an algorithm which produces 8 digit numeric password. If the number 00000000 occurs 50% of the time, and the remaining $10^8 - 1$ passwords occur with equal probability, then the Shannon entropy would be about $14.3$ bits, but the min-entropy is precisely $1$, which is $-\log_2{(0.5)}$.
Min-entropy can be associated with the best chance of success in predicting a person's password in one guess.
Shannon entropy is defined to equal $$\sum_{i=0}^n{-p_i\log_2(p_i)}$$ for a probability distribution $p$ with $n$ possible outcomes. Shannon entropy describes the average unpredictability of the outcomes of a system.
It also measures how much information is in a system (on average). Shannon entropy is the smallest possible average file size for a compression algorithm designed specifically with the distribution $p$ in mind.
Max-entropy is defined solely on the number of possible outcomes. It is equal to $-\log_2(n)$. It's not particularly useful in cryptography or passwords. It's a measure of the number of bits you would need to have to designate one bit pattern for every possible outcome.
The three quantities are always the same for a uniform distribution. This is because $p_i = p_\text{max} = \frac{1}{n}$.
$$-\log_2(p_\text{max}) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$
$$\sum_{i=0}^n{-p_i\log_2(p_i)} = n(\frac{1}{n} \log_2 (\frac{1}{n})) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$
This is why passwords picked from a uniform distribution (using a secure RNG) are said to be stronger than human generated passwords. Humans are biased in which password they choose. (Their password distribution is non-uniform.)
