How does asymmetric encryption work?

I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.

How does it encrypt something with one key and decipher it with another key?

-
It would be useful if you comment on the existing answers where these are not yet good enough for you, and/or what more you are searching with your bounty. (Or if you already selected a winner.) –  Paŭlo Ebermann Aug 26 '11 at 11:41

Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure.

One possible design for a public key encryption system is that of a trapdoor permutation. A trapdoor permutation is a mathematical function which is a permutation of some space, such that computing the function in one way is easy, but the reverse is hard, unless you know some information on how the trapdoor permutation was built. Encryption is applying the function on a message, decryption is about using the trapdoor to reverse the function.

For RSA, a well-known asymmetric encryption algorithm, consider a rather big (say 300 digits or more) integer n. n is composite: it is the product of two big prime integers p and q. There are more such composite integers than there are particles in the observable universe, so there is no problem in generating such an integer. n is called the modulus because we will compute things "modulo n". It turns out that:

• it is easy to compute cubes modulo n (given m, compute m3 mod n);
• if p and q were chosen appropriately (I skip the details), raising to the cube is a permutation modulo n (no two integers modulo n will have the same cube, so any integer between 0 and n-1 has a unique cube root modulo n);
• computing the cube root of an integer modulo n is extremely hard
• ... unless you know p and q, in which case it becomes computationally easy;
• recovering p and q from n (that's factorization) is extremely hard.

So the public key is n, the trapdoor permutation is raising to the power 3, and the reverse is computing a cube root; knowledge of p and q is the private key. The private key can remain "private" even if the public key is public, because recomputing the private key from the public key is a hard problem.

There is a bit more to RSA than the description above (in particular, RSA does not necessarily uses the power 3), but the gist of the idea is there: a function which is one-way for everybody, except for the one who selected the function in the first place, with a hidden internal structure which he can use to reverse the function.

SSL (now known as TLS) is a more complex beast which usually uses some asymmetric encryption during the initial stages of the connection, so that client and server end up having a "shared secret" (a commonly known sequence of bits); the shared secret is then used to apply conventional encryption and decryption to the rest of the data ("conventional" meaning: same key to encrypt and decrypt).

-
"computing the cube root of a random integer modulo n is extremely hard" would be more correct. Computing the cube root of 0, 1, 8, n-27, or interestingly the product modulo n of numbers for which we already know the plaintext, is easy. –  fgrieu Aug 26 '11 at 15:13
I would be careful to avoid saying that factorization is "extremely hard" but instead say that "no one knows how to do it efficiently." (And the truly correct statement is that "no one in the public community knows how to do it efficiently.") –  Fixee Aug 27 '11 at 6:00

A lot of answers have said "a mathematical structure" which is absolutely right, but I still see there might be a question: how on earth can one exist? I'll try and fill that gap at a simpler level.

So a simple caeser-shift cipher might look like this: $x+7$. In our really simplistic, dangerous example, the "key" here is $7$. If I have some encrypted text, I know that by subtracting $7$, I get back to $x$. Therefore, this is a really simple example of a symmetric cipher, because what I do one way also allows me to undo it.

As you might have noticed, most domains in cryptography are finite - for example, there are only 26 letters in the alphabet. At some point you need to "wrap around". Mathematics provides us with a technique to do this called modulo arithmetic. Essentially, under a modulus, you can think "if I divide this by the modulus, the number I have is the remainder". some examples:

• $4 = 4 \mod 7$

• $8 = 1 \mod 7$ (8/7 = 1 remainder 1)

• $4+7 = 4 \mod 7$ (11/7 = 1 remainder 4)

• $-3 = 4 \mod 7$ (not so hard... what happens when you add 7 to -3?)

As you can see, arithmetic holds under modulo. Undergraduate mathematics courses rigorously establish these truths and if you're interested, read up on Number and Group theory. The next step is to understand that multiplication also holds:

• $2*4 = 1 \mod 7$ (2*4 = 8, as above)
• $5*3 = 1 \mod 7$ (5*3 = 15, 15/7 = 2 remainder 1)

and so on. Multiplication in mathematics often throws up some problems when it comes to inverses - for example, how do I go from 1 back to 5? I can multiply by 5. How do I go back to 2 from 1? Multiply by 2. These examples are not quite right in terms of what I wanted to show, so here are some more:

• $6*3 = 4 \mod 7$ (6*3=18. 18/7 = 2 remainder 4)
• $4*5 = 6 \mod 7$ (4*5=20. 20/7 = 2 remainder 6).

With these examples, I've shown that you can go from 6 to 4 and back to 6 using multiplication, but by multiplying by different things.

This is one, very simple way to create such a mathematical structure. The genius of RSA is choosing the numbers involved in such a way that one can easily determine how to get to an encrypted value, but not back again. I've explained it fully in another answer; however, in essence, it is simply a more complicated version of what we've done here. The clever part is understanding those structures and which choices of numbers make good/bad keys and which work/do not.

But you're telling me multiplication is hard to undo: what about division?

Firstly, it really depends on circumstances. Under some circumstances, like the trivial example I present above, finding an inverse or even using division is easy. It's important to think about what division means. In a rational (any number you can write as a fraction) field, multiplicative inverses exist in the form $p * (1/p)$ (as well as $p*q = 1$).

However, when considering RSA, note that encryption is $t\times t\times \ldots = t^e = c \mod n$ for some public key $e$. So to compute the inverse, we'd need to compute $c \times (1/t) \times (1/t) \times \ldots = c \times (1/t)^e \mod n$. The reason for this is that each multiplication of $t$ needs to be undone by an inverse $(1/t)$ but it should be clear that if we only have the ciphertext $c$, we don't know $t$ to compute $1/t$.

So our next possible route is to compute $c^{1/e}$ as $t^{e*1/e} = t$. This is equivalent to computing the eth-square root of $c$ (for example, $x^{1/2} = \sqrt{x}$) which is hard to do when under a modulus of the size that RSA requires you use - under certain circumstances. Under others, it's known as the "cube root" attack: see this presentation and this one.

Other public key crypto systems use similar observations - for example, Diffie-Hellman relies on this property: $$a^x = b \mod n$$ Under certain cases of n (for example $(\mathbb{Z}_p, \times )$ i.e. when n is prime and we are interested only in multiplication and therefore a is greater or equal to 1) this is hard to reverse. This forms the basis of a number of other public cryptosystems.

-
great answer. The problems I had when I was learning public-private key encrypt was not thinking about the basic math under it. –  woliveirajr Aug 26 '11 at 12:50
For the Caesar-cipher you could say that modular subtraction is a decryption algorithm (with the same key as the encryption) or you could say that using the "private" key $+19$ with the encryption algo modular addition undoes the encryption with the "public" key $+7$. The problem being of course that anyone can deduce the private key from the public key. But otherwise it looks already a little bit like asymmetric encryption. –  j.p. Aug 27 '11 at 19:45
@Jug True. For very simple examples this falls down fairly easily; however, the nth-root under a modulus becomes more difficult. Multiplication as a whole often has situations where division is a much more difficult concept (matrices, for example). Obviously it doesn't make a great cryptosystem, but it is a place to start to look for possible trapdoor functions compared to addition, which is usually quite simple to reverse. –  Ninefingers Aug 27 '11 at 20:17
One can repeat what I wrote for modular addition/subtraction quite similar for modular multiplication/division (maybe one should exclude 0 as plain/cipher). Here finding the "private key" is already a little bit more difficult: one has to use Euclid's algorithm. It still doesn't have a trapdoor, but you do if you go to the next more complicated operation: modular exponentiation with its inverse taking modular roots. It can be solved efficiently only if one knows the factorization of the modulus. As finding and multiplying primes is easy, but factoring isn't, one gets a good trapdoor. –  j.p. Aug 28 '11 at 17:38
Your answer already points in the direction I write about in my comment. But in my opinion it is not (yet?) as well written as it could be. Least I like the 3 lines starting with "However, when...". Multiplying with (1/t)*...*(1/t) and then the step to taking roots is in my opinion not quite logical (in the sense why should one multiply and then try suddenly the root). But I think that your answer has great potential. –  j.p. Aug 28 '11 at 17:46

At a basic level, the client (i.e. your browser) and the server negotiate a key exchange algorithm to derive a random session key and then they use that private key to encrypt traffic with a symmetric algorithm.

There's a lot of detail to the process and I wrote about this extensively on my blog: The First Few Milliseconds of an HTTPS Connection

-
Could you try to summarize the article here, in case your site goes off-line? (If that's possible, of course) –  Arsen7 Aug 3 '11 at 11:16
I added a small synopsis, but without pictures and captures like I have on my blog –  Jeff Moser Aug 3 '11 at 11:27

The simplest way to explain it is that the two keys have a special mathematical relationship that allows one (the secret or private key) to undo what the other (the public key) does.

All asymmetric encryption schemes require some operation that cannot be easily reversed unless you have some secret piece of knowledge. With that piece of knowledge, the operation can be reversed.

One common encryption scheme uses the following relationships:

Given very large numbers m and n, pick a number p, compute:
s = p m modulo n
Now try to reverse that operation and get p from s, m and n. Given p, m, and n, calculating s is easy, but given m, n, and s, calculating p is very hard.

Given two very large prime numbers, m and n, compute:
k = m x n
Now try to reverse that operation and get m and n from k. Multiplication is simple. Factoring very large near primes is very hard.

-
2^{243112609} is a very large number near a prime (it's one more than a prime). And I can factor it in my head. –  Fixee Aug 27 '11 at 6:03
By "near prime", I mean a number with very few factors. –  David Schwartz Aug 27 '11 at 10:39
Ah, like a semiprime then (en.wikipedia.org/wiki/Semiprime). These are not always hard to factor (perfect squares being the obvious example) but usually are, yes. –  Fixee Aug 27 '11 at 16:54
Agreed regarding your specific constant, but perfect squares are easy to factor and there an infinite set of them. The fact that semiprime n=pq is vulnerable for certain values of p and q has led to the recommendation that p and q be "strong primes" in some RSA standards. (en.wikipedia.org/wiki/Strong_prime). –  Fixee Aug 28 '11 at 5:07
@David Schwartz, your use of the phrase "near prime" is sloppy, ambiguous, and confusing. I think that's causing all sorts of problems, so I suggest you change it to something more precise: factoring a product of two large primes is very hard. –  D.W. Sep 1 '11 at 20:41
show 2 more comments

The "How" is already explained well by others, but as far I can see, nobody wrote about "What does asymmetric encryption do?".

It does not, as many think, magically allow two parties Alice and Bob to communicate securely over a public channel.

Instead, it converts an authentic channel from Alice to Bob into a secret channel from Bob to Alice (given a public channel in both directions).

It can also be use to turn a public channel into a (bi or uni-directional) authenticated channel, a secret channel, or a secret and authenticated channel.

-