Re: [gentoo-user] Public key cryptography... (Used to be: Something about SOPA and PIPA)

[Chris Walters]

On 1/19/2012 06:00 PM, Neil Bothwick wrote:
> On Fri, 20 Jan 2012 00:42:16 +0200, Alan McKinnon wrote:
>
>> There's no known way to decrypt a mail like that without the single
>> private key needed (this works exactly like https traffic to your
>> bank). I feel very confident saying "no known way" as cracking that
>> puzzle has been the Holy Grail of maths prizes for 40 years and no-one
>> has announced success. Seeing as mathematicians are a vain lot, and the
>> one that accomplishes this feat with be showered with honour and glory
>> for all time (making Einstein look like a child), it's a safe
>> assumption that it hasn't been done yet.
>
> Unless he works for GCHQ/NSA or any other government's security services.
>
> Remember, RSA was invented several years before R, S and A did so, by a
> mathematician working at GCHQ (the UK's communication monitoring
> department).

Possible, but not too likely*.  RSA keys are based on two very large prime
numbers and their composite.  The two primes are hundreds of digits in length,
and are used to generate the cipher (public) key, and the decipher (secret)
key.  After which their composite is found and the two primes are discarded.

This type of public key cryptography is based on the difficulty of factoring
very large composites with only two very large prime factors, and is based in
number theory.  It can be done, but it usually takes years using distributed
computer networks.  It is possible that the NSA has found a magic formula to do
such factoring, but I find it more likely that the US Navy or the CIA would do
so first.  Remember, the NSA exists to monitor communications for "suspicious"
activity and this is what most of their supercomputers are used for (sifting
many emails, web page interactions, telephone conversations, and the like).

While I am sure the NSA has its share of cryptologists, and cryptographers, I
would hazard to say that the Navy has more, and so probably does the CIA/MI5
(or is it MI6 now?).

*DISCLAIMER: With any public key cryptosystem, there is a risk that you will be
using keys that have already been cracked.  If so, anyone who knows the crack
could decrypt your messages.

Chris