4
$\begingroup$

This is part of an assignment and I'm not sure what conclusion I'm supposed to draw from the result.

We were supposed to generate two 1024 bytes words, one using an algorithm that randomly generate 0 and 1 (50%/50%) and one using an algorithm with a "secret" probability distribution. I'll call them word 1 and word 2 from now.

We were supposed to calculate the empirical entropy of each word bit per bit first, and then byte per byte.

I got the following results :

word 1 (bit per bit): 1.00

word 1 (byte per byte): 7.79

word 2 (bit per bit): 0.95

word 2 (byte per byte): 0.81

We where then supposed to generate a random 1024 bytes mask and apply it on each word, giving us word 1m and word 2m. The results are this time:

word 1m (bit per bit): 1.00

word 1m (byte per byte): 7.81

word 2m (bit per bit): 1.00

word 2m (byte per byte): 7.81

I'm not sure what those results mean! Of course I noticed the fact that the byte per byte empirical entropy of word 2 is low, which probably means that some specific bytes are appearing more often than other, but I don't know what happen for word 2m

Not sure I made myself very clear, don't hesitate to ask for clarifications. Thanks !

$\endgroup$
  • $\begingroup$ This is part of an assignment and I'm not sure what conclusion I'm supposed to draw from the result. Is this assignment over by now (it's not 100% clear to me)? Because this is meant to train you in thinking about problems and probably also evaluating your learning perfomance and thus our help can be considered "cheating" if it isn't over. $\endgroup$ – SEJPM Sep 19 '16 at 18:52
  • $\begingroup$ I appreciate and understand your concern, but I tried to solve the problem myself. My interpretation was that a random mask applied to any signal give a random signal, similar to word 1which is generated with a 50/50 probability for 0 and 1. If you're not comfortable with giving me the direct answer, a simple confirmation or invalidation of that fact would already be a great help! (the assignment isn't over) $\endgroup$ – user39469 Sep 19 '16 at 19:15
  • $\begingroup$ Define "apply it [the mask] on each word" mathematically. $\endgroup$ – kodlu Sep 19 '16 at 22:41
  • $\begingroup$ word1 m = word1 && mask, with && being the AND operator. $\endgroup$ – user39469 Sep 19 '16 at 23:06
  • $\begingroup$ What do you mean by "compute the entropy"? That really does not make any sense. AFAIK entropy is a property of a random variable, not a concrete outcome. $\endgroup$ – Guut Boy Sep 20 '16 at 10:29
4
$\begingroup$

A uniform random source has maximum entropy: 1 bit per bit. It's fully unpredictable.

There's no way to measure the entropy of a source since you can only get a partial, finite view of it. If you see no pattern in the first $n$ bits, that doesn't prove that the source doesn't repeat every $n$ bits. Conversely, an ideal random source can return $n$ identical bits, it's just very unlikely (probability $2^{-n}$). So when you estimate the entropy of a uniform random source by sampling it, you can expect to get an entropy measure of about 1 bit per bit, whereas a non-random source usually has less (but only if your entropy estimation manages to catch the non-randomness).

You're getting 1 bit/bit and 7.79 ≈ 8 bit/byte (clearly not 7.79 byte/byte: it's a number between 0 and 1) as the entropy estimate for source 1 which is supposed to be uniformly random. This is within expected bounds.

You're getting 0.95 bit/bit and 0.81 bit/byte for source 2. This indicates that source 2 has pretty much equal numbers of 0's and 1's, but there's a very strong correlation between successive bits since grouping bytes together gives a low entropy estimate.

When you apply a uniformly random mask, the resulting combination becomes itself random. This is because every bit has a .5 chance of being flipped, so each 0 bit in the source has equal chances of being 0 or 1 in the combination, and each 1 bit in the source also has equal chances of being 0 or 1 in the combination. The entropy estimates that you get for source 1 with the random mask and for source 2 with the random mask are close to 1 bit/bit as expected.

Note that the mask is a xor, not an and. A bitwise and with a uniform random source would merely reduce the entropy by forcing about half the bits to 0.

This observation that an unpredictable mask xored with an arbitrary source results in an unpredictable combination is the basis of stream ciphers.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks a lot! I think a big part of my confusion was due to the fact that I thought that the mask was an and. $\endgroup$ – user39469 Sep 20 '16 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy