If I can assume that the output of a block cipher like AES is a PRandom distribution, can I assume that Benford's law will hold if I partition that output into integer data?
2
-
2$\begingroup$ From what I read on Wikipedia it only applies to natural data and encrypted data is not "natural" but uniformly random. $\endgroup$– SEJPMMar 10, 2017 at 13:38
-
$\begingroup$ I saw that as well, but I guess I wasn't exactly sure what "natural" number distributions meant $\endgroup$– DerekMar 10, 2017 at 13:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No, Benford's law does not hold.
As a simple example, assume a block size of $8$ bits, so the values are uniformly distributed in the half-open interval $[0, 256)$. Benford's law predicts that the probability of a leading digit occurring is strictly decreasing for increasing digits. However, it's easy to see that values leading with any digit $d \geq 3$ is equally likely.
For $d=3$, the only choices are $x \in [30, 39]$ and $x = 3$, while for $d=4$ the choices are $x \in [40, 49]$ and $x = 4$, and so on for every $d \geq 3$. All of these have exactly $10 + 1 = 11$ choices that occur with equal probability. This contradicts Benford's law's prediction that the probability is strictly decreasing.
We do have a higher chance of $d=1$ and $d=2$, but this is strictly because of the choice of our base. If we chose a base $b$ such that $b^k = 256$ for some integer $k$, then every leading digit is equally likely.
$\begingroup$
$\endgroup$
From Wikipedia:
For example, in sets which obey the law, the number 1 appears as the most significant digit about 30% of the time, while 9 appears as the most significant digit less than 5% of the time.
Clearly, such a distribution cannot be pseudorandom.
