Can the NSA break 100000 bit RSA assuming they have O(n^6) or O(n^12) factoring algorithm?
Georgi Guninski
guninski at guninski.com
Mon Sep 7 01:41:46 PDT 2015
In 2010 I generated two RSA keys (and certs) of size above 100000
bits:
[Full-disclosure] nonsense fun: 100 000 bit rsa key
http://archives.neohapsis.com/archives/fulldisclosure/2010-08/0384.html
The keys/certs:
http://archives.neohapsis.com/archives/fulldisclosure/2010-08/att-0384/gir.tar.gz
(the certs might have expired but this doesn't matter).
The private keys are included too.
According to my mail they were generated in
"about 30 hours on 1 core" and I used state of the art
primality checking "pfgw".
n is the size of the modulus in bits.
Assume the much loved NSA has factoring algorithms of
complexity O(n^6) or O(n^12) running on classical computers.
Can the NSA break n=100000 without using owning/torture?
Some computations suggest NO, especially for the second:
sage: k=100000
sage: RR(k^6).log(2)
99.6578428466209
sage: RR(k^12).log(2)
199.315685693242
Comments about quantum computer that can break them
are welcome too.
More information about the cypherpunks
mailing list