Strazdas said:
see, the problem with this is that its going to have plenty of backdoors. after all, you need to send the decryption key with the message or else the recipient would not be able to read it.
Er, no. The whole idea of public-key encryption is that the keys required for encrypting and decrypting a message are different. Granted, most of the public-key cryptosystems currently in use are vulnerable to being cracked via Shor's quantum factoring algorithm, but as far as I know nobody (except maybe the NSA, always except maybe the NSA) has actually built a quantum computer powerful enough to make Shor's algorithm useful. I acknowledge---quantum computers are coming, and sooner than we want them to---but they are not here yet.
However, there do exist public-key cryptosystems that are [em]not[/em] vulnerable to quantum factoring.[footnote]Look up "lattice-based cryptography".[/footnote] They're just slower and cause huge message blowup, so people don't use them because RSA works just fine for now. RSA is fairly easy to explain, in fact. Here I go. (By the way, I'm trying not to use too many scary mathematical words, so this explanation is still fairly hand-wavy.)
Let p and q be two large primes, say each having about 1000 decimal digits. Define the number n to be the product p*q, and let e be some integer that is more than 2 and less than n and that does not have p or q as a factor. In practice, people either set e=3 or e=65537, for reasons of computational efficiency; let us then accept e=65537. While we are defining values, let k = \eulerphi
= (p - 1)*(q - 1).
Now, let m be an integer at least 2 and less than 0.99n[footnote]The actual requirement is that m is coprime to n and that m < k, but p and q are to be kept secret, so just use a fudge factor here and trust that messages m that are multiples of p or q are extremely rare.[/footnote] The value m will represent the message that is to be encrypted. The encryption c of m is the value c = m^e (mod n).
The reason RSA is useful is that it is very difficult to find inverse e-th powers of arbitrary numbers modulo n, when n is explicitly a composite number. However, if one knows the values p and q, one can calculate the value d such that d*e=1 (modulo k) by using the facts that finding inverses modulo prime numbers like p and q is quite straightforward and that calculating in the system of integers modulo k has a direct and invertible relation[footnote]the Chinese Remainder Theorem[/footnote] to calculating simultaneously in the paired systems of integers modulo p and modulo q.
Once you have that d, you can forget p and q if you want to and just keep d itself as your private key. When you want to decrypt some encrypted text c into a plaintext t, it's simple: t=c^d (mod n). Here we note that decryption is far slower than encryption in RSA; most asymmetric cryptosystems have a similar property.
tl;dr -- if you generate a key pair (PUB, PRI) using your favourite program, and you go to the trouble to keep the value
PRI secret, then anyone who encodes a message with the value PUB will be able to trust that only you will ever be able to read that message.
Where Shor's algorithm defeats RSA is by factoring n into p and q in polynomial (soft quantum cubic, in fact) time in the size of n. Absent that, though, nobody has found usable ways of factoring big numbers like n, or of defeating RSA in any other way.
It was noted in a more recent post that
Whoracle said:
Yes, RC4 is broken. (snip) Yes, AES1 sucks, AES2 is highly dubious.
RC4 and AES are [em]symmetric[/em] cryptosystems---i.e., the keys for encryption and decryption are exactly the same, unlike in the RSA cryptosystem. RC4 is "broken"; it's possible to read messages encrypted with RC4 without knowing the key for the encryption. AES is not ... theoretically; indeed, AES is an excellent algorithm, in theory. The problem with AES is that it is vulnerable to "side-channel attacks": if you can measure with great precision how much time a computer requires to perform every step in the encryption of a message, then you can figure out what key it is using.
Shor's algorithm is useful against some, but not very many, of the symmetric cryptosystems currently in use. AES is not vulnerable to it, for example. Lots of other symmetric cryptosystems have the side-channel vulnerability, but not all of them, and people are trying to find ones that don't have it. Also, since the vulnerability is a known one, you can write your AES program so that it doesn't expose how long it takes to do each part of its job; generally, however, that means making it about a hundred (!) times slower to run. Finally, dedicated AES chip manufacturers are also aware of this vulnerability, so they make their circuits take constant time irrespective of the keys in use.
In that both the sender and the receiver of a message encoded using a symmetric cryptosystem must know the same key, and thus must have communicated that key between them at some point, it is only that symmetric cryptosystems like AES are hugely faster to calculate than RSA is. (And RSA is fast, amongst asymmetric algorithms. Quantum-factoring-resistant public-key cryptosystems are really, really slow indeed.) Thus, what really happens when Alice sends a message M to Bob in a hybrid system like GnuPG is the following:
1. Alice chooses a completely new random key K for use in the symmetric cryptosystem S. She computes C = S(K, M).
2. Alice encrypts K using Bob's public key E in the asymmetric system A. She computes R = A(E, K).
3. Alice sends *both* values C and R to Bob.
4. Bob uses his private key D in the asymmetric system to recover K from R.
5. Finally, Bob uses K in the symmetric system to recover M from C.
Note in particular that Alice and Bob never actually communicate the raw value K. If the size of a message M is much bigger than the size of a key K, then this scheme works out computationally and practically.
So---the hackers and the spies out there won't reasonably be able to crack our encryption until they build quantum computers. What they will be able to do is beat the security on our operating systems so they can tunnel in and read our messages before we encrypt them. Alternately, they will steal our keys because we don't keep the private keys sufficiently secure. (Key management is a whole 'nother problem, and a [em]harder[/em] one.) The cryptographic primitives themselves are still valid, though, and they're getting stronger, not weaker.
Edit: changed one (admittedly essential) letter in line 5 of the explanation of hybrid cryptosystems
