0
$\begingroup$

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?

$\endgroup$
2
  • $\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$ Mar 7, 2019 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, 2019 at 16:31

1 Answer 1

1
$\begingroup$

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}$

$\endgroup$
2
  • $\begingroup$ Thanks Tjaden Hess! What I cant understand is how P(B) was calculated. Why 1/2 in the front? $\endgroup$
    – baskon1
    Mar 8, 2019 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$ Mar 8, 2019 at 13:43

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.