[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Can the NSA break 100000 bit RSA assuming they have O(n^6) or O(n^12) factoring algorithm?
- To: [email protected]
- Subject: Can the NSA break 100000 bit RSA assuming they have O(n^6) or O(n^12) factoring algorithm?
- From: [email protected] (Georgi Guninski)
- Date: Mon, 7 Sep 2015 11:41:46 +0300
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.