Can the NSA break 100000 bit RSA assuming they have O(n^6) or O(n^12) factoring algorithm?

Georgi Guninski guninski@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