Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5827
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-07 15:57 +0200 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <msk54j$ak4$1@speranza.aioe.org> (permalink) |
| References | (9 earlier) <msclg4$1uo$1@news.albasani.net> <9unjuap4cjrt83f7pc6sqh3kf4ut3niv2k@4ax.com> <mscsmk$f59$1@news.albasani.net> <279qua9otkos9f14b3en1q58536hk6n7hb@4ax.com> <msjv2h$u33$1@news.albasani.net> |
On 07.09.2015 14:14, Mok-Kong Shen wrote:
> 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.
Be carefully with '1.0 bits of entropy per bit'.
Someone may understand that this is equivalent to "every bit
of keystream has 1.0 bit of entropy".
Like results of this function
long long unsigned int not_so_much_entropy()
{
unsigned long long int r = 0; //or =73495634398ll
if (rand()%2) r=~r;
return r;
}
;-)
> 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.)
Does diehard return any results named 'entropy'?
How do you define entropy for a sequence?
Entropy is about a set of possible messages (or just ouptputs
from a function). A probability distribution of messages and
how probable message is (if I get a rare message, it contain
more information).
We can take a long sequence, divide it into k-bit segments
and compute entropy as the segments were independent messages,
this approach is useful for example in compression (it is very
close to Huffman coding), but this have nothing to do with entropy
in this sequence. It just measure if the segments are evenly
distributed.
It looks like you know that, but it is no harm to repeat:
Of course, this is all about 'conditional probability'
and knowledge. If you give me just a long sequence of
pseudorandom numbers, for me it can even have more entropy
than you have used in seed. But I _may_ know more.
bartekltg
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