Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5763
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-03 02:33 +0200 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <ms84g3$urv$1@speranza.aioe.org> (permalink) |
| References | (10 earlier) <ms7va6$vtj$1@news.albasani.net> <0a1fua58g3o3sbe715rv0ugvvkkdd06lvr@4ax.com> <ms80vk$2ls$1@news.albasani.net> <sq2fuahnogne19tirojcpghp4vb1nb9k1k@4ax.com> <ms83g0$2tp$1@news.albasani.net> |
On 03.09.2015 02:16, Mok-Kong Shen wrote:
> 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.
No, stop this and read mathbook and definition of entropy;-)
One bit is either x1=0 or x2=1. If AES is good, probability of both
are equal. So P(x1) = P(x2) = 0.5.
Entropy oh this one bit is H = \sum_i P(x_i)*log2(1/P(x_i)) =
0.5*log2(2)+0.5*log2(2) = 1
One bit.
It can't be more.
It can be less, if propability od that bit equal 1 is not 1/2,
but this is against the assumption about AES.
The entropy of one bit taken from sequence of n bits (n is arbitrary),
generated by decent hash function, from 128bit random sequence,
is 1bit.
Never more. Significantly less only if hash function is broken.
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