Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5759
| 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-03 02:16 +0200 |
| Organization | albasani.net |
| Message-ID | <ms83g0$2tp$1@news.albasani.net> (permalink) |
| References | (9 earlier) <nrueuap090o6cds3elqata8fsbos63j1md@4ax.com> <ms7va6$vtj$1@news.albasani.net> <0a1fua58g3o3sbe715rv0ugvvkkdd06lvr@4ax.com> <ms80vk$2ls$1@news.albasani.net> <sq2fuahnogne19tirojcpghp4vb1nb9k1k@4ax.com> |
Am 03.09.2015 um 01:53 schrieb Robert Wessel:
> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>
>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>>
>>>>>>>> Am 02.09.2015 um 23:52 schrieb Robert Wessel:
>>>>>>>>> On Wed, 2 Sep 2015 22:50:52 +0200, Mok-Kong Shen
>>>>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>>>>
>>>>>>>>>> Am 02.09.2015 um 15:00 schrieb Kaz Kylheku:
>>>>>>>>>>> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>>>>>>>>>>> In my code PROVABLEPRIME
>>>>>>>>>>>> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) there is no seed
>>>>>>>>>>>> to be input by the user at all. When the Python session starts, the
>>>>>>>>>>>> system employs the current time to seed its built-in PRNG. So each
>>>>>>>>>>>> time one uses the code to e.g. generate RSA keys, one gets a different
>>>>>>>>>>>> pair by chance. Certainly one could question the security of that from
>>>>>>>>>>>> an "exact" standpoint (I mean in the sense of proofs of pure math),
>>>>>>>>>>>
>>>>>>>>>>> The "exact standpoint" here is quite obvious and it is that a sample of the
>>>>>>>>>>> current time (even if it includes micro or nanoseconds from a high resolution timer,
>>>>>>>>>>> and not only the "seconds sine epoch" or whatever) simply has too few bits of
>>>>>>>>>>> entropy to generate good RSA keys.
>>>>>>>>>>
>>>>>>>>>> I must admit that I yet have doubt on such application of the entropy
>>>>>>>>>> argument (i.e. without regard to how an amount of entropy is actually
>>>>>>>>>> being employed in the processing) due to a paradox that I put up
>>>>>>>>>> and described in a recent another thread: AES-128 in counter mode has
>>>>>>>>>> an input of max 128 bits of entropy but its ouput is commonly used to
>>>>>>>>>> e.g. xor n plaintext bits with n >> 128. The average entropy that is
>>>>>>>>>> contained in one ciphertext bit thus can't be greater than 128/n,
>>>>>>>>>> which is negligible for even moderately large n. Does that imply that
>>>>>>>>>> AES in CTR mode is totally broken?
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> No, it simply means that you don't need to do more than about 2**128
>>>>>>>>> work to break it with a known plaintext attack of sufficient size
>>>>>>>>> (where "sufficient" may be as little as 16 bytes). But that's not
>>>>>>>>> broken, since that's what we were assuming anyway. Sure, it's not a
>>>>>>>>> OTP, but it was never meant to be.
>>>>>>>>
>>>>>>>> I don't yet understand. One expands a sequence of 128 bits somehow
>>>>>>>> to a sequence of n bits with n >> 128. If the input 128 bits have
>>>>>>>> a total "entropy" of 128, then it can certainly also be asked how
>>>>>>>> much entropy the output n bits have in total and hence the average
>>>>>>>> value of entropy of each output bit.
>>>>>>>
>>>>>>>
>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>> matter how long it might be.
>>>>>>
>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>
>>>>>
>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>> of entropy per output bit.
>>>>>
>>>>> That's not really at question, or very interesting. If I take a
>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>> have an eighth of an ounce of milk in each container.
>>>>>
>>>>> I have perhaps missed some part of this discussion.
>>>>>
>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>>> future outputs from existing ones without excessive work. For example
>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>> some output from it, you can work it backwards to determine what that
>>>>> initial seed (or at least the initial state derived from that seed)
>>>>> was.
>>>>
>>>> The paradox I had also posted previously elsewhere and is thus not
>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>> can't be resolved, then I would say that employing entropy to treat
>>>> the security of crypto schemes seems to have some fundamental logical
>>>> problems in general.
>>>
>>>
>>> Well, your paradox posted previous elsewhere is not immediately
>>> visible to me, so I can't really comment on it.
>>
>> That's the same in content as I described in this thread. (I only
>> mentioned its history, in order to explain that it is not specifically
>> thought of for this thread.) So you don't have to look at what I posted
>> elsewhere and need only to treat what I posted in this thread.
>
>
> Sorry, after rereading all of your posts in this thread, I can't see
> what you're going on about.
>
> What are you trying to do?
You have agreed on my argument that (assuming the quality of output from
AES is uniformly good) the entropy of each output bit is 128/n.
Now, for stream encryption with xor, one needs a good so-called
key-stream. The ideal case is a sequence of bits of full entropy,
i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad
case is a sequence of bits having very low value of entropy. Now, if
n is even moderately large, say 10000, the output bits in CTR mode
will have entropy of 1/10000. Obviously no one would seriously
consider doing any stream encryption with a key-stream having such
a low value of entropy per bit. However, AES in CTR is generally
deemed to be secure in practice. Thus the paradox indicates in my
view that employing the concept entropy to discuss security has some
fundamental problems in general that anyway yet need clarifications.
Have I explained my thoughts clear enough now?
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