• Researches in quantum computing seem to progress only extremely slowly

    From Mok-Kong Shen@21:1/5 to All on Tue Sep 1 13:09:25 2015
    XPost: comp.programming

    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum
    computers and one could consequently concentrate one's efforts in
    attempting to improve the practical security of these schemes, e.g.
    in authentication of the public keys and in prevention of eventually
    possible backdoors being implanted in the software or hardware involved.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Mok-Kong Shen on Tue Sep 1 14:23:06 2015
    XPost: comp.programming

    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum

    Phew! Your python-PRNG-based security schemes is safe!

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Tue Sep 1 20:00:50 2015
    XPost: comp.programming

    Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum

    Phew! Your python-PRNG-based security schemes is safe!

    In another thread I asked you to provide a reference to support your
    claim there but you still kept silence on that!

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Chris M. Thomasson@21:1/5 to All on Tue Sep 1 13:23:02 2015
    XPost: comp.programming

    "Mok-Kong Shen" wrote in message news:ms4114$nal$2@news.albasani.net...


    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    AFAICT, the following project has some promise:

    http://www.dwavesys.com

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robert Wessel@21:1/5 to mok-kong.shen@t-online.de on Wed Sep 2 02:22:54 2015
    XPost: comp.programming

    On Tue, 1 Sep 2015 13:09:25 +0200, Mok-Kong Shen
    <mok-kong.shen@t-online.de> wrote:


    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum >computers and one could consequently concentrate one's efforts in
    attempting to improve the practical security of these schemes, e.g.
    in authentication of the public keys and in prevention of eventually
    possible backdoors being implanted in the software or hardware involved.


    Even if significant progress in quantum computing does occur, a number
    of public key algorithms, for example the lattice-based schemes, are
    known not to be vulnerable to quantum computing (or at least not any
    more than to conventional computing).

    As for private key algorithms, most of those will not be hit worse
    than halving their effective key length by quantum algorithms, so
    AES-256 should be fine (although it would be no stronger than AES-128
    is now).

    IOW, should quantum computing actually become practical, cryptographic implementations will need some updates, but it will hardly be the end
    of the world. Especially since we'll likely have considerable advance
    notice as quantum machines start to grow large enough to be
    meaningful.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Mok-Kong Shen on Tue Sep 1 18:43:13 2015
    XPost: comp.programming

    ["Followup-To:" header set to comp.programming.]
    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum

    Phew! Your python-PRNG-based security schemes is safe!

    In another thread I asked you to provide a reference to support your
    claim there but you still kept silence on that!

    The reference is that the entire sequence coming out of a PRNG only contains as much information as its seed. For instance, a 32 bit seed means that the
    entire sequence contains at most 32 bits of information. (This is true even if the PRNG is a good one with a big state vector, and a long period.)
    The seed is effectively a selector which chooses one of 2**32 different sequences.

    If you generate, say, a 1024 bit key with a PRNG that is seeded with, say, 64 bits, then it's effectively a 64 bit key. Given a known plaintext and ciphertext pair, we only have to search a 64 bit space to recover the key.
    The encryption algorithm might be RSA-1024, but it's not really because
    of the weak seeding; it is a misleading lie and "security through obscurity"--- you hope that the scheme is secure because the attacker doesn't know
    that a particular weekly-seeded PRNG was used.

    Do you also require a reference for the claim that water is wet?

    Moreover, a PRNG may have other problems with it even if the state space is large enough and the seed has enough entropy for the given crypto use.


    About stream ciphers; yes they are lot like PRNG's where the encryption key
    is a seed. The seed has an appropriate size to achieve a given security
    level, and no misleading claims are made about the space from which it
    is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
    that uses a 32 bit seed, we have the same problem: the cipher is effectively
    32 bit (but the users are duped into believing that it's the 256
    bit real thing).

    No, key entropy does not dilute with the increasing length of an encrypted message. Suppose we have a very good symmetric cipher against which there is no known attack other than brute force. Suppose the attacker knows all of our plaintext. It does not help the attacker to have a large quantity of known plaintext. In fact using more plaintext/ciphertext pairs only slows down the brute force search. For each key which is tried, it is enough to try a single known ciphertext/plaintex pair.

    Encryption does not work by spreading key entropy across a message.
    The entropy in a key is important, however, for obvious reasons:
    more entropy means a larger key space.

    If an encryption algoirthm requires keys with a certain amount of entropy,
    and is given less entropy, it is incompetently implemented. Its security
    is weakened.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From William Unruh@21:1/5 to Mok-Kong Shen on Wed Sep 2 16:24:09 2015
    On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    [For completeness I send a copy nonetheless to this group]


    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

    No. It is known to be very insecure. You might get 10-20 bits of randomness that way but not more.

    an "exact" standpoint (I mean in the sense of proofs of pure math),
    but there is in "practical" crypto in general IMHO no way to take that
    exact standpoint and yet have useful things done. Does e.g. AES have
    an exact proof of its security? There is none, at least to my humble knowledge.

    Rot 13 cannot be proven to be secure, AES 256 cannot be proven to be
    secure. Therefor Rot13 is as strong as AES 256. Can you see something
    wrong with that logic?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Wed Sep 2 10:56:27 2015
    [For completeness I send a copy nonetheless to this group]

    Am 01.09.2015 um 20:43 schrieb Kaz Kylheku:
    ["Followup-To:" header set to comp.programming.]
    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
    On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/

    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    This means that there is in the foreseeable future no danger of the
    currently used asymmetric encryption schemes being broken by quantum

    Phew! Your python-PRNG-based security schemes is safe!

    In another thread I asked you to provide a reference to support your
    claim there but you still kept silence on that!

    The reference is that the entire sequence coming out of a PRNG only
    contains as
    much information as its seed. For instance, a 32 bit seed means that the entire sequence contains at most 32 bits of information. (This is
    true even if
    the PRNG is a good one with a big state vector, and a long period.)
    The seed is effectively a selector which chooses one of 2**32 different sequences.

    If you generate, say, a 1024 bit key with a PRNG that is seeded with,
    say, 64
    bits, then it's effectively a 64 bit key. Given a known plaintext and ciphertext pair, we only have to search a 64 bit space to recover the
    key.
    The encryption algorithm might be RSA-1024, but it's not really because
    of the weak seeding; it is a misleading lie and "security through
    obscurity"---
    you hope that the scheme is secure because the attacker doesn't know
    that a particular weekly-seeded PRNG was used.

    Do you also require a reference for the claim that water is wet?

    Moreover, a PRNG may have other problems with it even if the state
    space is
    large enough and the seed has enough entropy for the given crypto use.


    About stream ciphers; yes they are lot like PRNG's where the
    encryption key
    is a seed. The seed has an appropriate size to achieve a given security level, and no misleading claims are made about the space from which it
    is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
    that uses a 32 bit seed, we have the same problem: the cipher is
    effectively
    32 bit (but the users are duped into believing that it's the 256
    bit real thing).

    No, key entropy does not dilute with the increasing length of an
    encrypted
    message. Suppose we have a very good symmetric cipher against which
    there is
    no known attack other than brute force. Suppose the attacker knows
    all of our
    plaintext. It does not help the attacker to have a large quantity of
    known
    plaintext. In fact using more plaintext/ciphertext pairs only slows
    down the
    brute force search. For each key which is tried, it is enough to try
    a single
    known ciphertext/plaintex pair.

    Encryption does not work by spreading key entropy across a message.
    The entropy in a key is important, however, for obvious reasons:
    more entropy means a larger key space.

    If an encryption algoirthm requires keys with a certain amount of
    entropy,
    and is given less entropy, it is incompetently implemented. Its security
    is weakened.

    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),
    but there is in "practical" crypto in general IMHO no way to take that
    exact standpoint and yet have useful things done. Does e.g. AES have
    an exact proof of its security? There is none, at least to my humble
    knowledge.

    To repeat a few points of mine in another thread: (1) if a CSPRNG were
    required in the implementation of Maurer's algorithm (detailed in HAC),
    the authors of HAC would have explicitly mentioned it according to the
    common style of writing in such contexts, (2) the algorithm given in
    HAC of implementing a CSPRNG via RSA would barely have had any
    practical sense (since one has a "need" of a CSPRNG "only" in
    situations where one doesn't yet have one).

    BTW, I like to mention (though this is certainly not any argument of
    mine here) that a copy of my code was sent to the authors of HAC
    since, if I don't err, it is the first publically available
    implementation of Maurer's algrorithm in any popular programming
    language.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Wed Sep 2 11:04:51 2015
    XPost: comp.programming

    Am 01.09.2015 um 22:23 schrieb Chris M. Thomasson:
    "Mok-Kong Shen" wrote in message news:ms4114$nal$2@news.albasani.net...


    http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/


    The article doesn't seem to be much more optimistic than reports on
    other well-known currently running big projects of physics, e.g.
    nuclear fusion.

    AFAICT, the following project has some promise:

    http://www.dwavesys.com

    Google has a machine from D-Wave. The mention of it in the given
    link isn't very clear (positive? negative?) in my understanding.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Thu Sep 3 05:58:09 2015
    Am 02.09.2015 um 18:24 schrieb William Unruh:
    On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

    [For completeness I send a copy nonetheless to this group]


    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

    No. It is known to be very insecure. You might get 10-20 bits of randomness that way but not more.

    I have in comment lines in my code already indicated how one could use
    Python's random.SystemRandom() instead of the normal random module.
    I am now preparing an update that actually uses random.SystemRandom().

    an "exact" standpoint (I mean in the sense of proofs of pure math),
    but there is in "practical" crypto in general IMHO no way to take that
    exact standpoint and yet have useful things done. Does e.g. AES have
    an exact proof of its security? There is none, at least to my humble
    knowledge.

    Rot 13 cannot be proven to be secure, AES 256 cannot be proven to be
    secure. Therefor Rot13 is as strong as AES 256. Can you see something
    wrong with that logic?

    I am conscious that I could never exclude the possibility of having
    security problems in my codes (seeing that even professional code
    writers could make errors) and therefore I always ask for critiques
    and comments.

    I think it is interesting to report here that, after Kylheku has
    set follow-ups to comp.programming, there were a few persons who
    discussed there with me. The last post I wrote to Kylheku was
    asking him to clearly resolve a paradox of mine (concerning AES in
    CTR), which seems to indicate in my view some posssible problems
    with security arguments based on entropy in general. I hope that he
    would reply to that soon. Another person, Wessel, agreed with my
    calculation of entropy in the paradox but asked about my intention
    in that. I explained and it seems that he has no more questions.
    A third person, bartekltg, wrote (especially in his more recent
    posts) arguments that IMHO are quite strange. Since he continued
    to claim that my calculation in the paradox is wrong, I asked him
    in a last post to similarly refute Wessel and I'll delay further
    discussions with him before seeing his post to Wessel. (He nonetheless
    wrote a last post to me, which I didn't answer.)

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Fri Sep 4 18:34:38 2015
    Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
    [snip]
    I have in comment lines in my code already indicated how one could use Python's random.SystemRandom() instead of the normal random module.
    I am now preparing an update that actually uses random.SystemRandom().

    The update, PROVABLEPRIME Version 1.2, has just been released.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From William Unruh@21:1/5 to Mok-Kong Shen on Fri Sep 4 18:32:26 2015
    On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
    [snip]
    I have in comment lines in my code already indicated how one could use
    Python's random.SystemRandom() instead of the normal random module.
    I am now preparing an update that actually uses random.SystemRandom().

    The update, PROVABLEPRIME Version 1.2, has just been released.

    The advantages of a provable prime are overhyped. The probability of not finding a prime if you use a probablistic approach are extremely small,
    and algorithm for proving primality AFAIK is very slow. Already
    generating primes is slow enough that people do not want to do it.
    And, AFAIK if you use a non-prime in RSA you will not get the right
    answers when you try to decrypt. So you will soon discover that you do
    not have a real prime. Ie, speed is probably more important that
    provability in this case.
    So what is the speed of your implimentation vs the speed of
    probabilistic approaches?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Sat Sep 5 20:50:05 2015
    Am 04.09.2015 um 20:32 schrieb William Unruh:
    On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
    [snip]
    I have in comment lines in my code already indicated how one could use
    Python's random.SystemRandom() instead of the normal random module.
    I am now preparing an update that actually uses random.SystemRandom().

    The update, PROVABLEPRIME Version 1.2, has just been released.

    The advantages of a provable prime are overhyped. The probability of not finding a prime if you use a probablistic approach are extremely small,
    and algorithm for proving primality AFAIK is very slow. Already
    generating primes is slow enough that people do not want to do it.
    And, AFAIK if you use a non-prime in RSA you will not get the right
    answers when you try to decrypt. So you will soon discover that you do
    not have a real prime. Ie, speed is probably more important that
    provability in this case.
    So what is the speed of your implimentation vs the speed of
    probabilistic approaches?

    As I noted in Epilogue of the software, the time for generation
    of RSA keys with moduli of the order of even 8000 bits (current
    practice 2000) is well acceptable for my targeted users.

    On the other hand, I am not blindly ignoring the efficiency issue.
    Having better efficiency is anyway a desirable property to be
    strived at for any software. Please however kindly be patient at
    the moment. I am writing code to perform an extensive comparison
    of the cpu-times of generation of provable primes vs generation
    with the probabilistic method. But I need yet some time to collect
    sufficient results, analyze them, eventually learn something
    useful from them and provide some good arguments for the pros and
    cons of employing the two approaches. You'll hear from me in due
    course of time.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Mon Sep 28 11:30:22 2015
    Am 04.09.2015 um 20:32 schrieb William Unruh:
    On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
    Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
    [snip]
    I have in comment lines in my code already indicated how one could use
    Python's random.SystemRandom() instead of the normal random module.
    I am now preparing an update that actually uses random.SystemRandom().

    The update, PROVABLEPRIME Version 1.2, has just been released.

    The advantages of a provable prime are overhyped. The probability of not finding a prime if you use a probablistic approach are extremely small,
    and algorithm for proving primality AFAIK is very slow. Already
    generating primes is slow enough that people do not want to do it.
    And, AFAIK if you use a non-prime in RSA you will not get the right
    answers when you try to decrypt. So you will soon discover that you do
    not have a real prime. Ie, speed is probably more important that
    provability in this case.
    So what is the speed of your implimentation vs the speed of
    probabilistic approaches?

    I have done a comparison. With my Python codes the mean values of
    runtime obtained are as follows, where nb is the bit size of the primes generated, tprov is the time with Maurer's algorithm and tprob is that
    with Miller-Rabin test (with prior sieving with trial divisions,
    different sizes of the table of small primes employed were tried and
    the least runtime values listed).

    nb=1000 nb=1500 nb=2000

    tprov: 0.493 sec 1.739 sec 4.648 sec

    tprob:

    t=1 0.324 sec 1.228 sec 3.462 sec
    t=2 0.340 sec 1.282 sec 3.567 sec
    t=5 0.357 sec 1.297 sec 3.534 sec
    t=10 0.394 sec 1.436 sec 3.926 sec
    t=20 0.450 sec 1.594 sec 4.191 sec
    t=30 0.517 sec 1.801 sec 4.670 sec
    t=40 0.570 sec 1.945 sec 5.035 sec

    It can be seen that my implementation of Maurer's algorithm starts to
    have a runtime shorter than with the Miller-Rabin test at t=30 and is
    superior for higher values of t. Even for t values less then 30, the differences are only moderate and certainly not extreme.

    Thus with additional consideration of the benefit of obtaining primes
    that are definitely prime, the results obtained support in my view the
    general use of Maurer's algorithm for generation of random primes of
    the said sizes in case my coding is employed.

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mok-Kong Shen@21:1/5 to All on Thu Oct 8 18:28:27 2015
    Am 28.09.2015 um 11:30 schrieb Mok-Kong Shen:
    [snop]
    I have done a comparison. With my Python codes the mean values of
    runtime obtained are as follows ..........

    The code for the comparison is in Post #31 of the thread http://s13.zetaboards.com/Crypto/topic/7234475/1/

    M. K. Shen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)