True Random Number Generator
in [Cryptography]
|
From: unruh on 8 Feb 2010 20:37 On 2010-02-08, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > Mok-Kong Shen wrote: > [snip] > >> ....................... The essence of the >> point, I suppose, is that it can be a valuable research enquiry to find >> efficient and good entropy combiners such that, by inputing a plaintext >> and a sufficiently random key stream, one could achieve a resulting >> entropy of 1 - epsilon per bit, ................. > > Just an observation: If one uses a good block cipher like AES to > encrypt, it is common that a single key is used to process a fairly > long plaintext stream. But the key has at most 128 bits of entropy. > Isn't it a miracle that the resulting ciphertext stream (a result > of combination) has very high entropy? Or is it rather the case that > the ciphertext stream doesn't possess much higher entropy per bit > "after all" in comparison with the plaintext stream (the enhancement > of entropy per bit being at most 128 divided by the (commonly > relatively large) total number of bits being processed) and thus the > achieved security, on which one "believes", were actually an illusion > (cf. optical illusions)? Of course it is. We know the attack. Try every one of the 2^128 keys and see which one works. That is the 128 bits of entropy. the problem is that "try all 2^128 keys" is really really tedious. Ie, this indicates that if done properly, 128 bits of entropy is sufficient to hide any text you wish, for all practical purposes. (at least for now). 128 bits of entropy is really a lot of different states. > > M. K. Shen >
From: Mok-Kong Shen on 9 Feb 2010 01:58 unruh wrote: >> Just an observation: If one uses a good block cipher like AES to >> encrypt, it is common that a single key is used to process a fairly >> long plaintext stream. But the key has at most 128 bits of entropy. >> Isn't it a miracle that the resulting ciphertext stream (a result >> of combination) has very high entropy? Or is it rather the case that >> the ciphertext stream doesn't possess much higher entropy per bit >> "after all" in comparison with the plaintext stream (the enhancement >> of entropy per bit being at most 128 divided by the (commonly >> relatively large) total number of bits being processed) and thus the >> achieved security, on which one "believes", were actually an illusion >> (cf. optical illusions)? > > Of course it is. We know the attack. Try every one of the 2^128 keys and > see which one works. That is the 128 bits of entropy. the problem is > that "try all 2^128 keys" is really really tedious. Ie, this indicates > that if done properly, 128 bits of entropy is sufficient to hide any > text you wish, for all practical purposes. (at least for now). 128 bits > of entropy is really a lot of different states. My point is this: If one considers the input natural language text has, say, 1 bit of entropy per character (this is the lowest figure of estimate I have seen of all textbooks), then the ciphertext from encryption using AES has not much more than 1.0001 bit of entropy per character. I am not sure that people are commonly conscious of that. M. K. Shen
From: WTShaw on 9 Feb 2010 02:23 On Feb 9, 12:58 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > unruh wrote: > >> Just an observation: If one uses a good block cipher like AES to > >> encrypt, it is common that a single key is used to process a fairly > >> long plaintext stream. But the key has at most 128 bits of entropy. > >> Isn't it a miracle that the resulting ciphertext stream (a result > >> of combination) has very high entropy? Or is it rather the case that > >> the ciphertext stream doesn't possess much higher entropy per bit > >> "after all" in comparison with the plaintext stream (the enhancement > >> of entropy per bit being at most 128 divided by the (commonly > >> relatively large) total number of bits being processed) and thus the > >> achieved security, on which one "believes", were actually an illusion > >> (cf. optical illusions)? > > > Of course it is. We know the attack. Try every one of the 2^128 keys and > > see which one works. That is the 128 bits of entropy. the problem is > > that "try all 2^128 keys" is really really tedious. Ie, this indicates > > that if done properly, 128 bits of entropy is sufficient to hide any > > text you wish, for all practical purposes. (at least for now). 128 bits > > of entropy is really a lot of different states. > > My point is this: If one considers the input natural language text has, > say, 1 bit of entropy per character (this is the lowest figure of > estimate I have seen of all textbooks), then the ciphertext from > encryption using AES has not much more than 1.0001 bit of entropy per > character. I am not sure that people are commonly conscious of that. > > M. K. Shen Remember that with higher bases, entropy may not be easily described in bits, and might have more useful bang for the buck. Too difficult subjects are avoided because they are that, not that they are not worth knowing, or are even superior to the usual gruel.
From: Mok-Kong Shen on 9 Feb 2010 09:10 WTShaw wrote: > Remember that with higher bases, entropy may not be easily described > in bits, and might have more useful bang for the buck. Too difficult > subjects are avoided because they are that, not that they are not > worth knowing, or are even superior to the usual gruel. In textbook sources, English charaters (hence base 26) are said to have entropy somewhere between 1.0 and 1.5 bit pro chaaracter (See Stinson). As layman I don't know the details of how these figures got evaluated. Certainly that's not a trivial task, maybe indeed very very difficult, as you said. But that has nonetheless been done! M. K. Shen
From: Spinner on 9 Feb 2010 12:24
Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: <snip> (Note BTW that the theoretical OTP with >an entropy of 1.0 per bit is practically not obtainable, or at least >not "knowable" to have been achieved in practice.) The essence of the >point, I suppose, is that it can be a valuable research enquiry to find >efficient and good entropy combiners such that, by inputing a plaintext >and a sufficiently random key stream, one could achieve a resulting >entropy of 1 - epsilon per bit, and that would be entirely satisfactory >for the practical applications. > >M. K. Shen Silly statement. The fact that a totally provably random OTP has never been created is going to be a helluva suprise to a lot of people who have been using them for many manyt years. Not to mentioni there are websites where you can go get a list of quantum-generated (radioactive decay) random numbers. Secondly : My OTP follows a x b 9 Please use only once for text <= pad length. Note only good for encrypting two letters, but thats not the problem of the pad, now is it? -- 2+2!=5 even for extremely large values of 2 |