Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5826
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-07 14:14 +0200 |
| Organization | albasani.net |
| Message-ID | <msjv2h$u33$1@news.albasani.net> (permalink) |
| References | (8 earlier) <fjqgua5aqj4v41bgr73ou57kftm5scnp7v@4ax.com> <msclg4$1uo$1@news.albasani.net> <9unjuap4cjrt83f7pc6sqh3kf4ut3niv2k@4ax.com> <mscsmk$f59$1@news.albasani.net> <279qua9otkos9f14b3en1q58536hk6n7hb@4ax.com> |
Am 07.09.2015 um 07:50 schrieb Robert Wessel:
> On Fri, 4 Sep 2015 21:50:52 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 04.09.2015 um 20:42 schrieb Robert Wessel:
>>> On Fri, 4 Sep 2015 19:47:57 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 03.09.2015 um 17:49 schrieb Robert Wessel:
>>>>> On Thu, 3 Sep 2015 16:51:00 +0200, Mok-Kong Shen
>>>> [snip]
>>>>>> Thank you for your kind efforts to help me understand the paradoxical
>>>>>> phenomenon. Excuse me however for my slow learning capability and allow
>>>>>> me to ask a question so that I could be sure of having correctly
>>>>>> captured what you wrote. Is a good "apparent randomness" (e.g. one with
>>>>>> a score near 1.00 from diehard) sufficient for a bit sequence of n
>>>>>> bits to securely encrypt a plaintext bit sequence of n bits with xor?
>>>>>> (A simple yes/no is sufficient for the question. I might under
>>>>>> circumstances have a 2nd question depending on that.)
>>>>>
>>>>>
>>>>> No. Diehard will return a 1.00 (or near that) for the output from a
>>>>> good (non-CS) PRNG (like Mersenne Twister). Using MT will not be
>>>>> secure.
>>>>>
>>>>> OTOH, diehard should show (near) 1.00 on any CSPRNG (say AES in CTR
>>>>> mode). So a (near) 1.00 entropy rating from diehard is a necessary
>>>>> condition, but not a sufficient one. IOW, if your (hoped for)
>>>>> CSPRNG's output does not get a ~1.00 from diehard, it's probably not
>>>>> CS (or a very good PRNG, either).
>>>>
>>>> I understand that a score of diehard of 1.0 shows only that each
>>>> bit has 1 bit of "apparent entropy". But isn't it that for a very
>>>> secure keystream for stream encryption each bit should have (nearly)
>>>> 1 bit of "true" entropy? In fact, you wrote earlier "The entire
>>>> output of a AES-128 stream (assuming a good key), will contain
>>>> 2**128 bits of entropy." However this means that one feeds AES
>>>> with 128 bits of "true" entropy and out comes from it 2**128 bits
>>>> of "true" entropy. Could that be true? I mean AES would then be a
>>>> very wonderful magic device of creation of true entropy. (I haven't
>>>> yet seen any literature that contains claims in that direction.)
>>>
>>>
>>>
>>> Sorry, I added a "2**" to that inappropriately. "The entire output of
>>> a AES-128 stream (assuming a good key), will contain _128_ bits of
>>> entropy." Probably lost it editing the rest of that paragraph ("that
>>> means the "key" stream will only be one of 2**128 possible streams,").
>>>
>>> "Very secure" is an interesting term. In the case of OTP, yes, you
>>> need 1.0 bits of "real" entropy per key bit. And that's certainly
>>> "very secure".
>>>
>>> OTOH, AES-128 is such that it appears* that you cannot recover the
>>> key, or other parts of a message, if you know some of the plaintext,
>>> with less than 2**128 work, and since that's an implausible amount of
>>> work, that also seems "very secure", despite the entire keystream
>>> having been seeded with only 128 bits of entropy.
>>>
>>> But not any generated sequence seeded with 128 bits of entropy is
>>> secure. A 128 bit LFSR seeded with 128 bit of entropy is decidedly
>>> *not* secure, since it's actually fairly easy** to run in reverse to
>>> generate what the internal state is.
>>>
>>> Given 16 bytes of plaintext, I *know* an algorithm to recover the
>>> key*** and the remainder of a message that's been encrypted with a 128
>>> bit key (any cipher), it just won't finish in a useful amount of time.
>>> What's special about AES (and other good ciphers), is that they appear
>>> to *require* that amount of work, and don't allow any shortcuts (as
>>> does, for example, an LFSR).
>>>
>>>
>>> *The lack of an actual proof of security is disheartening, of course.
>>>
>>> **FSVO "easy", but there are plenty of easy to find descriptions of
>>> the process if you're interested.
>>>
>>> ***Actually simple brute force will generate on average about two
>>> possible keys if you only know 128 bits of plaintext (with 128 bit
>>> keys). So in practice you'd want a few extra bits of plaintext.
>>> Almost always all of the "wrong" keys will decrypt to gibberish (which
>>> is just another way of saying we have a few extra bits of plaintext).
>>
>> I suppose that, according to what you wrote in the last posts about
>> "apparent entropy", we could in future drop any issues involving it,
>> since we are concerned here with security or more exactly secure
>> encryption. That is, entropy will henceforth mean "true" entropy.
>>
>> Now, assuming we can agree that AES-128 can't generate any
>> "additional" entropy, the situation is: If the output CTR-mode bit
>> sequence is of length n, the estimated entropy of each bit is <= 128/n,
>>from which it follows that for sufficiently large n the entropy per
>> bit would be neligible. The question is how the thus generated bit
>> sequence could nontheless be secure when considered in terms of entropy
>> (i.e. relative to "perfect security", which according to Shannon
>> requires 1 bit of entropy per bit of keystream).
>
>
> Why do you think that good security requires anything close to 1.0
> bits of entropy per bit of keystream? *Perfect* security does require
> 1.0 bits, but that gives no hint at all to what amount of entropy
> pre-keystream-bit would be necessary for "good enough" security. And
> as it turns out, we're pretty sure there's no actual minimum, at least
> on a per bit basis.
Oh, this is certainly a so-called common sense reasoning of mine.
If for perfect security one needs 1 bit of entropy, then one could
IMHO think of for some not too bad security a requirement of r bit of
entropy, where r might be, say, 0.9, 0.5, but one would not think
of values like 0.001 in this connection. For otherwise entropy would
have a very very strange unit of measurement for it to be a suitable
concept in practice at all. (As an an analogy, even one knows that
diehard doesn't give a measure of true entopy, diehard would totally
lose its value as a measure of (pseudo-)randomness, if a score of 0.9
from it doesn't mean at least something not too bad, though not the
best, relative to 1.0.)
M. K. Shen
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 13:09 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 14:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 20:00 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 18:43 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 10:48 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 13:00 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 22:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:31 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:58 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-03 00:32 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:18 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:29 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:25 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:53 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:16 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:17 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:30 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:36 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:19 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 22:51 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 16:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-03 10:49 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 19:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-04 13:42 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 21:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 23:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 01:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 00:50 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-07 14:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-07 15:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 12:19 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-08 23:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-09 02:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 00:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 17:11 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 02:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 20:15 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:35 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:11 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:21 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:01 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:08 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-03 07:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:14 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-02 23:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-01 13:23 -0700
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 11:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:22 -0500
csiph-web