search

libtom / tomsfastmath

TomsFastMath is a fast public domain, open source, large integer arithmetic library written in portable ISO C.
http://www.libtom.net
Other
209 stars 66 forks source link

REQUEST: Support > 2048-bit sizes #37

Closed VA1DER closed 3 days ago

VA1DER commented 3 days ago

RSA is receiving renewed attention since key sizes on the order of what most SSH implementations support (16384-bit) actually appears to be a viable post-quantum solution.

While qubit counts for Shore's algorithm are only on the scale of 2n, the quantum gate count required for factoring is O(n^2 * log(n)) for the Fourier transform, and O(n^3) for the overall complexity. This can be reduced somewhat by certain optimizations, but likely no more than a factor of 2. This leaves the quantum gate count requirement for factoring a 16384-bit number in the billions. This is likely as far away from us now as VLSI was from the transistor.

In short, while Shore's offers a theoretical way to factor RSA, in practical terms even when quantum computers are common, it will still be as far out of reach of quantum computers as factoring the same number is out of reach of a current classical supercomputer.

Please, therefore, support proper bit-sizes so downstream users can take advantage of RSA key sizes that protect against quantum attacks.

sjaeckel commented 3 days ago

TFM has support for MPI operations > 2048bits if you compile it like that.

10 tracks the progress on having arbitrary MPI sizes and therefore I'm closing this issue.

sjaeckel commented 3 days ago

I forgot to mention, if it wasn't clear: we welcome new contributors if you want to add something to the code base.

E.g. if you want to make tfm arbitrary sized or port some of tfm's improvements over to ltm, you're very welcome to do so.

Please feel free to open a PR with your contribution or an issue or discussion if you have questions before starting an implementation. If you don't want to communicate in public, you can find an E-Mail address on our homepage.