Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5752
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-03 01:21 +0200 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <ms80a0$nte$1@speranza.aioe.org> (permalink) |
| References | (8 earlier) <ms7ro4$qcm$1@news.albasani.net> <ms7tk8$is0$1@speranza.aioe.org> <ms7u7i$u75$1@news.albasani.net> <ms7uma$l1f$1@speranza.aioe.org> <ms7vnf$rd$1@news.albasani.net> |
On 03.09.2015 01:11, Mok-Kong Shen wrote:
> Am 03.09.2015 um 00:54 schrieb bartekltg:
>> On 03.09.2015 00:46, Mok-Kong Shen wrote:
>>> Am 03.09.2015 um 00:35 schrieb bartekltg:
>>>> On 03.09.2015 00:03, Mok-Kong Shen 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.
>>>>
>>>> OK, this will be far from formal math...
>>>>
>>>> Do you assume the text is known? If the entropy is only entropy
>>>> of the coding sequence, you do.
>>>> In the first 128 bits there is 128bit of enthropy.
>>>> In the second 128 bits there is 128bit of enthropy.
>>>> In the first 256 bits - 128 bits of enthropy.
>>>>
>>>> The entropy of whole sequence (X,Y)
>>>> H(X,Y) = H(X) + H(Y|X) (=H(y) + H(X|Y))
>>>> is equal to entropy of the first part plus
>>>> _conditional_ entropy od Y under the assumption X is known.
>>>> And because you use the same sequence to code the second half,
>>>> there is no new information. H(X|Y) = 0.
>>>
>>> Sorry, I can't follow your contional entropy argument.
>>
>> https://en.wikipedia.org/wiki/Conditional_entropy
>>
>>> You wrote "... assumption X is known".
>>
>> This is a standard formula from propability theory.
>> for two random variable X and Y, Y|X is a a distribution
>> of Y if X is fixed.
>>
>>> But one can simply consider
>>> that one has got n output bits from AES before doing anything
>>> else. What is "known" at that time?
>>
>> I look at the first 128 bits of the code. Because I know
>> original text, I can decode the sequance.
>> If I look at the second 128 bits, I do not get any
>> new information.
>>
>>> If none, what's the average
>>> entropy per bit?
>>
>> It looks like average entropy is very consuming,
>> because bits in your example are not independent.
>>
>> If you look at any 128bit chunk you get the whole 128bit
>> of information.
>> REad the second post about a candy.
>
> Sorry, I prefer not to be involved in discussing a different scenario
> and like to know why the simply calculation of mine, which concerns
> only input bits and output bits of AES alone (without involving
> any subsequent operations done with the output bits) is anywhere
> logically wrong.
This is exactly the answer to you question about 'mean entropy'.
You did not understand the direct answer because you do not
know math about entropy. This is why I also wrote the second
post about simplified problem, but with the same question
and answer.
If I have a candy in one hand I do not have a half of bits
of enthropy in each hand. I have one bit in left and one
bit in right. But both bits are corelated, so if you
known one, you also known the second - second hand
have zero entropy, because ("under the assuption the
first hand in known") you known where the candy is.
"Mean entropy" as you proposed ("128/n") have no sense,
because probability doesn't work that way.
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