We have a one time pad where:

  1. We have 8 bits. probability that a bit=0 is p.

  2. The key is common for all 8 bits. It can have a value of 0 or 1 with equal probability.

  3. After applying the XOR operation we take the encrypted result that has n zeros and 8-n ones.

What I am asked to do is calculate the probability that the key used is 0.

Until now I am thinking like this:

There are 2 events:

EventA. We have k zeros in the original 8 bits

EventB. We have k zeros in the encrypted data.

P(A) can be calculated from the binomial distribution P(B) = 2P(A) I am searching the probability P(key=0|P(B)).

Is my thinking correct until now? How can i procede from there?

  • $\begingroup$ Welcome to CryptoSE! :), Just to clarify, your message is 8 bits long but your key is only 1 bit? and you use that one bit to xor with the 8 bits of the message and then get 8 bits ciphertext? If that's the case then consider that the key is sampled uniformly at random and independently of the message. $\endgroup$ – Marc Ilunga Mar 7 '19 at 12:30
  • $\begingroup$ Hello! Yes exactly that was the case. Key is 0 or 1 for the whole block of 8-bit text to cipher! $\endgroup$ – baskon1 Mar 7 '19 at 16:31

Assume the message is an $n$-bit string with each bit drawn independently with $P(0) = p$.

Let $A$ be the event that the key bit is $0$.

Let $B$ be the event that there are $k$ zeroes in the ciphertext.

Then $P(A) = \frac{1}{2}$ and $P(B) = \frac{1}{2}{{n}\choose{k}}\left(p^k(1-p)^{n-k} + p^{n-k}(1-p)^{k}\right)$, since with equal probability we had $k$ zeroes or $n-k$ zeros in the message.

$P(B | A) = {{n}\choose{k}}p^k(1-p)^{n-k}$ since this occurs exactly when the message originally had $k$ zeros

Then $P(A | B) = \frac{P(A)P(B | A)}{P(B)} = \frac{p^k(1-p)^{n-k}}{p^k(1-p)^{n-k} + p^{n-k}(1-p)^k}$

  • $\begingroup$ Thanks Tjaden Hess! What I cant understand is how P(B) was calculated. Why 1/2 in the front? $\endgroup$ – baskon1 Mar 8 '19 at 7:30
  • $\begingroup$ It may make more sense if you distribute it out. You can also think of it as averaging over the two possibilities of the key bit. $\endgroup$ – Tjaden Hess Mar 8 '19 at 13:43

Your Answer

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

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