Re: Unbreakable code using XOR for one time pad?
- From: Bryan Hussein Olson <fakeaddress@xxxxxxxxxxx>
- Date: Tue, 11 Nov 2008 00:45:16 -0800
Gordon Burditt wrote:
You are right, if the key is truly random, never reused, and keptsecret, the one-time pad provides perfect secrecy otherwise very simple
attack can render it useless.
You may readhttp://en.wikipedia.org/wiki/One-time_pad.Why does the key need to be random?
But, it is not very convenient to use in practice.
Why not set up a key that decodes the text in some
different meaning so the attacker thinks he found
the solution, but was totally wrong?
Using a random key means that all possible plaintext messages of
the same length are equally likely. There's a key for not just
*one* incorrect decoding, there's a key for *all possible* incorrect
decodings of the same length.
Bravo! The O.P.'s question here is, in my estimation, the single most frequently asked question here on sci.crypt. Today there are more know-nothings posting on s.c. than ever before, but that detraction is more than offset by increase in participants who take cryptology seriously, and respond with real answers. Bravo!
I have one nit to pick: it's not that all ciphertexts are equally likely; it's that thier probabilities do not change when given the OTP ciphertext. Perfect secrecy means that the ciphertext and plaintext are independent, in the mathematical, statistical, probabilistic sense.
If there's any structure to the key, then that can be used to decide
that some of the incorrect decodings are wrong because the corresponding
key is unlikely or impossible.
Sure. "One time pad" is a technical term, a 'term of art'. It implies, by definition, that the key-stream is truely random -- all possible key-streams are equally likely. That, along with some trivial mechanics and some subtle issues such as length (which Gordon Burditt nailed), implies perfect secrecy.
For more, check out the foundation paper: Shannon, Claude; "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28(4), page 656–715, 1949. When I was young in cryptology, looking up that paper was a significant effort. Today it's a few minutes of Googling; no excuses.