Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5764
| 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:42 +0200 |
| Organization | albasani.net |
| Message-ID | <ms850q$51n$1@news.albasani.net> (permalink) |
| References | (11 earlier) <0a1fua58g3o3sbe715rv0ugvvkkdd06lvr@4ax.com> <ms80vk$2ls$1@news.albasani.net> <sq2fuahnogne19tirojcpghp4vb1nb9k1k@4ax.com> <ms83g0$2tp$1@news.albasani.net> <ms84g3$urv$1@speranza.aioe.org> |
Am 03.09.2015 um 02:33 schrieb bartekltg:
> 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.
Have I ever said of bits having entropy greater than 1.0 per bit?
That in practice, even with very good devices, one get's less
than 1.0 entropy per bit is understandable and well known. But that
doesn't affect my paradox logically which takes some idealizations
for discussion purposes. Is that ok?
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