# Entropy of the key

Suppose a $1000$-bit key used in the one-time pad is not randomly and uniformly generated.

1. Suppose that the values of the first $5$ bits are $0$, and the other $995$ bits are randomly generated and uniformly distributed (each bit with value $0$ and $1$ with probability $0.5$), what is the entropy of the key?
2. Suppose that each bit of the key is randomly generated but with value $0$ with probability $0.54$. What is the entropy of the key?

I have no idea how to start the two questions above. For part 1, I use the entropy formula $$-\sum_{x \in X}{P(x) \log_2 P(x)}$$ but I don't know what should I let $X$ be. Can anyone guide me?

EDIT: Proof of Additivity of Shannon Entropy

Aim: If $X$ and $Y$ are independent random variables, then $H(X,Y) = H(X)+H(Y)$

Proof: Since $X$ and $Y$ are independent random variables, we have $$P(X=x)=\sum_{y \in Y}{P(X=x,Y=y)}$$ $$P(Y=y)=\sum_{x \in X}{P(X=x,Y=y)}$$

Question: Do the equations above require the independence of $X$ and $Y$? If they are not independent, are the equations still true?

-
It's not a one-time pad if the key is not randomly and uniformly generated. –  CodesInChaos Sep 3 '14 at 9:33

Since bits are independently generated, the entropy of the key is the sum over the entropy of the individual bits. The following calculations use the chance $P(x)$ of a zero or one bit.

1. The first 5 bits are constant and thus have 0 entropy.

The others are unbiased and have 1 bit of entropy each. $P(0)=P(1)=0.5$.

$-2\cdot(0.5 \cdot \log_2(0.5))= -log_2(0.5) = -log_2(2^{-1}) = 1$

for a total of 995 bits of entropy.

2. For each bit, use the formula with $P(0)=0.54$ and $P(1)=0.46$

$-\sum_{x \in X}{P(x)\cdot \log_2(P(x))} = -(0.54 \cdot \log_2(0.54) + 0.46 \cdot \log_2(0.46)) \approx 0.9954$

for a total of 995.4 bits of entropy.

-
For part $(1)$, if I want to use the formula, what should be my $P(x)$? –  Idonknow Sep 3 '14 at 9:40
For the first 5 bits it's $P(0)=1$ and $P(1)=0$, for the other 995 bits it's $P(0)=0.5$ and $P(1)=0.5$. –  CodesInChaos Sep 3 '14 at 9:42
Actually for part$(b)$, I am required to prove that entropy of the key is the sum of the entropy of individual key. –  Idonknow Sep 3 '14 at 9:46
For part $(b)$, shouldn't we need to multiple $0.9954$ with $1000$ since the length of the key is $1000$? –  Idonknow Sep 3 '14 at 9:53
1) Just search for a proof for additivity of Shannon entropy. This is such a basic property that you should find plenty. 2) 0.9954 is the entropy per bit. The entropy of the whole is obviously 1000 times that value. –  CodesInChaos Sep 3 '14 at 10:05