In DES and AES (and any symmetric key cryptosystem) there is only one secret: the key.
The same key can be used to encrypt as well as decrypt messages.
The encryption process and decryption process are either similar or identical.
But there are some shortcomings...
If Alice and Bob share exactly they same key, then you can't use that key to uniquely identify Alice or Bob.
There's no way to tell whether it was Alice or Bob that sent a given message.
It the message is a financial payment you can't tell who paid whom, or whether the whole thing was forged.
There is a simple idea that solves all of these problems:
Have two keys, one for encryption and one for decryption.
There is no reason to keep the encryption key secret (so we call it the public key).
However the decryption key must be kept secret (it is the private key).
A metaphor...
The mail slot: Your house may have a mail slot: anyone can send a message to you, but only you can unlock the door and read the messages.
How does the public key idea solve the problems we mentioned?
Alice and Bob want to exchange a key for AES.
Alice generates the key $k$ using a TRNG.
She encrypts the key using Bob's encryption key : $c = E_{{Bob}_{pub}}(k)$.
She then sends Bob $c$, which he decrypts using his private key: $k = D_{{Bob}_{priv}}(c)$
(This is how HTTPS works)
Why do they even need AES? Because it's much much faster than the public key algorithm.
We no longer need a key for each pair of people.
We now only need two keys per person: a public key and a private key.
For $n=10000$ users there are $20000$ keys (not 49995000 keys).
As a bonus, there is no reason to keep the public key secret. You can put it in your public profile.
(Being sure that you have Bob's public key and not Eve's is still a problem though.)
Each user has a unique private key. Knowledge of the private key is proof of who you are.
You can even prove you know the key without revealing it:
Just "decrypt" some challenge statement $c$:
$s = D_{{Bob}_{priv}}(c)$.
Then anyone can "encrypt" $s$ using the public key and see that the result is $c$:
$c \stackrel{?}{=} E_{{Bob}_{pub}}(s)$
Something very similar to this happens when you spend bitcoin.
Ralph Merkle had the idea for Pub Key when he was an undergraduate at UC Berkeley in 1974.
His idea was rejected by his professor.
He then wrote the idea up as a paper and submitted it to a journal.
It was rejected as a crazy idea.
Eventually in 1975 two established cryptographers had similar ideas: Diffie and Hellman.
They published a famous paper called "New Directions in Cryptography" which became a classic work.
They solved the key exchange problem (we still use their solution).
Here is a deeper history:
http://cr.yp.to/bib/1988/diffie.pdf
Secret branches of the US and British government claimed later to have known about pub key methods.
But it is doubtful that they grasped the implications.
A function $f(x)$ is a one-way function if:
We can't prove these exist (it depends on $P\neq NP$).
But they probably do and there are a few known candidates.
Given large primes $p$ and $q$, computing $N=pq$ is easy.
But going from $N$ back to the factors $p$ and $q$ is hard.
There is no known polynomial time algorithm for factoring.
(But there is a fast quantum algorithm)
Given a big prime $p$, let $0 < x < p$. Assume $p$ and $x$ are public.
Let $d$ be a big number which is kept private.
Then computing $x^d \mod p$ is easy.
But recovering $d$ from $x^d \mod p$ and $x$ is hard.
(We want to take the discrete logarithm of $x^d$ base $x$.)
In symmetric key cryptography the key is a random number, secretly generated.
In public key cryptography, the decryption key is the solution to a simple mathematical equation that everyone can see.
Whereas in symmetric key you might need to try every key to break a cipher, in public key you only need to solve the equation.
Solving the equation might be easier than trying every key (and often is).
For that reason public keys tend to be much longer than private keys.
According to the NSA
"A sufficiently large quantum computer, if built, would be capable of undermining all widely-deployed public key algorithms used for key establishment and digital signatures.
... It is generally accepted that quantum computing techniques are much less effective against symmetric algorithms than against current widely used public key algorithms.
While public key cryptography requires changes in the fundamental design to protect against a potential future quantum computer, symmetric key algorithms are believed to be secure provided a sufficiently large key size is used. ...
In the longer term, NSA looks to NIST to identify a broadly accepted, standardized suite of commercial public key algorithms that are not vulnerable to quantum attacks. "