I am having a set of random numbers and I want to calculate entropy of them. I searched many entropy calculation formula, but I didn't get it. Can you elaborate a little bit?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Many formulae? Is there more than one? $\endgroup$– Paul UszakSep 4, 2017 at 10:38
-
1$\begingroup$ Can you elaborate on what exactly you do not understand please? $\endgroup$– duskSep 4, 2017 at 11:27
-
$\begingroup$ If your numbers were auto correlated, that would be interesting. Are they? $\endgroup$– Paul UszakSep 4, 2017 at 13:38
-
$\begingroup$ @Paul Uszak: you are right, there is not more that one applicable formula; there's none, for the reason in the second sentence in that answer. $\endgroup$– fgrieu ♦Sep 4, 2017 at 14:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
In a cryptographic sense this is not really possible. The entropy of the numbers is determined by the way they have been chosen. From only a list of numbers, say $(1, 2, 3, 4)$, we cannot just determine the entropy.
But if we instead say that we choose four numbers uniformly from 1 to 10, we can calculate the entropy. Recall the definition of (Shannon) entropy:
$$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$
Here $X$ is the state (e.g. $(1, 2, 3, 4)$). The $x_i$ values are the possible states, e.g. $\{(1, 1, 1, 1), (1, 1, 1, 2), \ldots, (10, 10, 10, 10)\}$. $P(x_i)$ is the probability that the random number $X = x_i$. When the probability distribution is uniform, then the probabilities are all equal to $\frac{1}{n}$.
Notice that this is a calculation not over the state itself, but over the probability distribution of all the possible states. In other words: The entropy is determined not on what the numbers are, but how they are chosen.
[More information on how entropy is actually calculated.]
It is possible to estimate (not calculate) the entropy of a series of data, but this is more relevant in the field of data processing. This is not relevant in cryptography.
-
$\begingroup$ And what is x exactly if the source isn't a CSPRNG? $\endgroup$ Sep 4, 2017 at 11:35
-
$\begingroup$ I expanded the answer to elaborate $x$ and the other variables. Not sure if it is really clear. What do you think? $\endgroup$– duskSep 4, 2017 at 11:45
-
1$\begingroup$ Usually in cryptography we are concerned with min-entropy, $-\max_i \log_2 P(x_i)$, not Shannon entropy, since it better reflects a smart adversary's chance at breaking a system, rather than a random uninformed adversary's chance at breaking it. I also like to emphasize the interpretation that a probability distribution formalizes either a physical process or an adversary's state of knowledge. $\endgroup$ Sep 4, 2017 at 14:54