RSA in theory (was: Re: NSA, PGP and RSA)

[Robert J. Hansen]

> How could anyone honestly answer that question, if the suspected
> weakness has never been found?  We don't know that it exists, and if
> it does exist we don't know its nature.

There are some hints the theoretical underpinnings of RSA aren't quite
what we've always believed them to be.  These hints don't point at a
weakness -- just some weirdness that we don't fully understand.  My
reading of the tea leaves says this weirdness will not result in a
serious attack, but I don't recommend people stake much money on my
hunches.  :)

The security of RSA is predicated on three major conjectures:

1.  P != NP
2.  Integer factorization is really hard
3.  Breaking RSA is equivalent to integer factorization

#1 is strongly believed to be true (but so far there's no proof).  #2 is
strongly believed to be true (and there are good lines of math to
suggest it's so).  #3 is ... now believed to be *false*, [1] which opens
all kinds of doors for cryptographers to study.

Don't panic.  Some top-drawer cryppies are looking at this closely and
so far they keep on using phrases like "Our results do not expose any
weakness in the RSA system" when talking about their findings.  This is
a fascinating area of ongoing research, *not* any indication of weakness
in the overall system.

But yeah, we've got some tantalizing hints that the theoretical
underpinnings of RSA aren't quite what we've always believed them to be.
 It's a fascinating time to be alive!



[1] http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20141002/a386e12c/attachment.sig>