[Cryptography] NSA and cryptanalysis

[Ray Dillinger]

On 08/30/2013 08:10 PM, Aaron Zauner wrote:

> I read that WP report too. IMHO this can only be related to RSA (factorization, side-channel attacks).

I have been hearing rumors lately that factoring may not in fact be as hard
as we have heretofore supposed.  Algorithmic advances keep eating into RSA
keys, as fast as hardware advances do.  A breakthrough allowing most RSA keys
to be factored could be just one or two more jumps of algorithmic leverage
away (from academics; possibly not from the NSA).  It could also be the case
that special-purpose ASICs that accelerate the process substantially may
have been designed and built.

We know about Shor's algorithm for factoring in NlogN time.  It requires a
quantum computer to run though.  We have heard rumors of quantum computers
being built, and I recall a group of academics who actually built one nearly
eight years ago.

That seems to be the sort of thing that would attract attention from a lot
of three-letter agencies, and efforts to scale it up would be intensely
supported with all the resources and brainpower that such an organization
could bring to bear.  How far have they come in eight years?  It is both
interesting and peculiar that so little news of quantum computing has been
published since.



				Bear