assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason it tends to output 1 in probability of 70% and 0 in probability of 30%.

does it make the one time encryption not perfect mathmatically?

my assumption that yes, because $p(P=p | C=c) = p(P=p)$ is not always true here. for an edge case, if most of the bits are 0 then after xoring, the encrypted bit is equivalent to the decrypted bit in most of the bytes. if the message is in english for instance, it's just fixing spelling errors.

but my problem is not intuition, but mathmatics: how can i show that $p(P=p | C=c) = p(P=p)$ is not always true and that in the given case the cryptosystem is not perfect?

this is what i've done so far:

the probability of generating 0 is 0.3. this is the first event, A.

the probability that there are k zeroes in a string consists of n characters: $0.5\left(\binom{n}{k}\right)\left(0.3^k\left(1-0.3\right)^{n-k}\:+0.3^{n-k}\left(1-0.3\right)^k\right)$, meaning since we can choose from {0,1}, then it's 0.5 * choosing k characters from a message with length n knowing there can be n-k or k zeroes in the message cipher, this is event B.

so the probability of having k zeroes if there the bit is zero: $P\left(B\left|A\right|\right)=\left(\binom{n}{k}\right)\left(0.3^k\cdot \left(1-0.3\right)^{n-k}\right)$

now since $P(A|B)=\frac{P(A)P(B|A)}{P(B)}$, meaning that if we opted for perfect security, it would have meant that $p(P=p | C=c) = p(P=p)$, but it can not be the case since $\frac{P(B|A)}{P(B)} \neq 1$

so the ciphersystem as applied here is not perfectly secure as shown.

  • $\begingroup$ This flaw would, without a doubt, be a security flaw, though probably a very mild one. It would still be beyond modern hardware for messages (keys) of more than about 20 characters to be broken as far as I am aware. $\endgroup$ – Legorooj Nov 21 '19 at 11:12
  • 1
    $\begingroup$ Don't forget that only schoolboy OTP systems are "perfectly secure". Hardware and environmental imbalances and the entire basis of the Left Over Hash lema mean that all TRNG output is biased in the way you are asking about. It's just the their biases ($\epsilon$) are/should be $ \le 2^{-64}$ which is "more perfect" than your $\epsilon = 0.2$. $\endgroup$ – Paul Uszak Nov 21 '19 at 11:42
  • $\begingroup$ thank you very much for your well appreciated comments. could you please check if the math i did there is also correct? by the way i am reading and learning about lemma you mentioned and it's quite interesting $\endgroup$ – alberto123 Nov 21 '19 at 12:17
  • $\begingroup$ Note that if the 0's and 1's are still well distributed you can XOR two digits together like $c = a \oplus \neg b$ to get a reasonably unbiased output stream. However, with such a large bias I would certainly question the quality of the random stream; possibly it would only suffice as an (additional) seed to a good PRNG. $\endgroup$ – Maarten Bodewes Nov 21 '19 at 17:59

Your Answer

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

Browse other questions tagged or ask your own question.