Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
For part $(1)$, if I want to use the formula, what should be my $P(x)$? –  Idonknow Sep 3 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 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 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 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 at 10:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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