4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ It's not a one-time pad if the key is not randomly and uniformly generated. $\endgroup$ Commented Sep 3, 2014 at 9:33

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ For part $(1)$, if I want to use the formula, what should be my $P(x)$? $\endgroup$
    – Idonknow
    Commented Sep 3, 2014 at 9:40
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 3, 2014 at 9:42
  • $\begingroup$ Actually for part$(b)$, I am required to prove that entropy of the key is the sum of the entropy of individual key. $\endgroup$
    – Idonknow
    Commented Sep 3, 2014 at 9:46
  • $\begingroup$ For part $(b)$, shouldn't we need to multiple $0.9954$ with $1000$ since the length of the key is $1000$? $\endgroup$
    – Idonknow
    Commented Sep 3, 2014 at 9:53
  • $\begingroup$ 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. $\endgroup$ Commented Sep 3, 2014 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.