Unbreakable code using XOR for one time pad?
in [Cryptography]
|
Prev: Cipher challenge
Next: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
From: Bill B on 11 Nov 2008 01:36 Encoding data using the XOR function against a "one time pad" of the same or longer length of the file seems to yield an unbreakable cypher message since there is more than one solution using different keys. For example, the message "The quick brown fox" can be encoded by XORing each character against a key of say "abcdefghijklmnopqrstuvwxyz" producing a cyphertext message of decimal characters '"53,10,6,68,20,19,14,11,2,74,9,30,2,25,1,80,23,29,11" Decoding this message using the original key produces the original message of "The quick brown fox" However, if the cyphertext is XORed against a different set of decimal key characters of say; "97,98,99,100,120,114,116,114,34,56,108,122,34,125,110,55,55,61,43, 116,117,118,119,120,121,122" the output will be: "The lazy red dog" So, it appears that using a one time pad (single use of key) will yield an unbreakable code, since there are many solutions to the problem. In other words, using the appropriate key will produce whatever results are desired and the original message can never be found without knowing the correct key. Have I missed something? -Bill
From: Jyoti Sharma on 11 Nov 2008 01:50 On Tue, 11 Nov 2008 12:06:20 +0530, Bill B <wrongaddress(a)att.net> wrote: > Encoding data using the XOR function against a "one time pad" of the > same or longer length of the file seems to yield an unbreakable cypher > message since there is more than one solution using different keys. > You are right, if the key is truly random, never reused, and kept secret, the one-time pad provides perfect secrecy otherwise very simple attack can render it useless. You may read http://en.wikipedia.org/wiki/One-time_pad. But, it is not very convenient to use in practice. regards, Jyoti
From: Bill B on 11 Nov 2008 02:05 On Nov 10, 10:50 pm, "Jyoti Sharma" <jyoti.mic...(a)gmail.com> wrote: > On Tue, 11 Nov 2008 12:06:20 +0530, Bill B <wrongaddr...(a)att.net> wrote: > > Encoding data using the XOR function against a "one time pad" of the > > same or longer length of the file seems to yield an unbreakable cypher > > message since there is more than one solution using different keys. > > You are right, if the key is truly random, never reused, and kept secret, 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. > > But, it is not very convenient to use in practice. > > regards, > Jyoti Why does the key need to be random? 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? -Bill
From: Gordon Burditt on 11 Nov 2008 02:40 >> You are right, if the key is truly random, never reused, and kept >secret, 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. >> >> But, it is not very convenient to use in practice. >> >> regards, >> Jyoti > >Why does the key need to be random? >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. 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.
From: mockturtle on 11 Nov 2008 03:09
Bill B ha scritto: > On Nov 10, 10:50 pm, "Jyoti Sharma" <jyoti.mic...(a)gmail.com> wrote: > > On Tue, 11 Nov 2008 12:06:20 +0530, Bill B <wrongaddr...(a)att.net> wrote: > > > Encoding data using the XOR function against a "one time pad" of the > > > same or longer length of the file seems to yield an unbreakable cypher > > > message since there is more than one solution using different keys. > > > > You are right, if the key is truly random, never reused, and kept secret, 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. > > > > But, it is not very convenient to use in practice. > > > > regards, > > Jyoti > > Why does the key need to be random? I remember (I am going by memory, but if you want I can search in my notes and be more precise) that with quite reasonable assumptions (e.g., the encryption function E(C, K) [C=clear text, K=key] is invertible if you fix K), if H(K) is the entropy of your key, you can "destroy" _at_most_ H(K) bits of the clear text. What does "destroy H(K) bits" means? It means that _on_average_ a powerful adversary which is able to check all the possible keys in a reasonable amount of time will end up with 2^H(K) "reasonable" messages. The proof is just some computation with information theory tools. Note that in order to have the maximum efficiency, your message should be "uniformly distributed" too. I admit that the exposition above is a little bit (to be kind) sloppy. If you want, I can try to search for some notes of mine I wrote some times ago. > 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? > > -Bill |