On 1/2/25 22:59, Robert J. Hansen wrote:
Do I understand correctly that, while the complexity of
conventional factoring scales with a logarithm of RSA key length,
Shor's algorithm has a space requirement that scales linearly, but
the engineering challenges implied by that linear growth scale
exponentially?
The keyspace equivalency is made under the assumption the attacker is
using the generalized number field sieve. It's unsurprising for work
factors to be different for different algorithmic approaches. Your
conclusion is sound but please be careful not to draw inferences about
one approach from the behavior of the other.
Yes, but you seem to be missing my intended point: each additional RSA
key bit far less than doubles the work to factor the key on a
conventional computer, but nonetheless always add 5 additional qubits to
the requirements for Shor's algorithm.
"Only 5 more qubits" may not sound like much, but the difficulty of
adding those compounds for each additional qubit.
In theory, with long-enough (perhaps too long for practical use) RSA
keys, conventional factoring would be /easier/ than Shor's algorithm.
Is there such a "turnover" point?
One of the rationales for limiting GnuPG RSA keys to 4096 bits is those
diminishing returns against GNFS factoring, but raising that limit may
be appropriate to enable greater quantum resistance. (Lack of
interoperability for longer RSA keys might be another good reason to
keep the 4096-bit limit.)
Are those figures including error correction or /before/ error
correction?
Before.
So those figures are low by factor of ...? (Somehow I suspect that
quantum error correction is considerably less efficient than
Reed-Solomon...)
[...]
Do the mathematical complexities that prevent conventional
computing from making short work of 256-bit ECC keys also affect
Shor's algorithm?
My understanding is "no".
So a quantum computer able to solve RSA-256/384/512 can also solve
EC-RSA-256/384/512 with the same difficulty?
If not, that would mean that RSA is actually /stronger/ against
future threats and TLS should be moving back to RSA and Diffie-
Hellman posthaste.
The US government's belief is that RSA-3072 will be sufficient for
protection of Top Secret/SCI data for the next twenty-five years.
[...]
And what about the various elliptic curve cryptosystems?
-- Jacob
_______________________________________________
Gnupg-users mailing list
Gnupg-users@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gnupg-users
