How does public key encryption work exactly?

Factual Questions
1

Perhaps someone could demonstrate how public key encryption works using small numbers?

Say the public key is 35, meaning the “private” key would be the numbers 5 and 7? Now how can you encode something using the public key ‘35’ in a way such that you can’t decrypt it using that same number, but can decrypt it using the set of numbers 5 and 7?

Or on the other hand, if there’s something about this post that indicates I’ve completely misunderstood public key cryptography, please explain that as well/instead. My understanding is that it works by having a “public” key which is a very large number, which has only two very large prime factors, said prime factors being the “private” key.

I did a search here and didn’t find a straightforward explanation as to how this works.

-FrL-

2

This is not with simple numbers, but it is easily understood (to me at least…)

Public-key encryption for dummies.

3

Thanks for the link.

I still want to know the nuts and bolts of this though–how is it that you encrypt a message using some key in such a way that you can’t decrypt the message using that same key, but can decrypt it using some other key?

Also, I’m not sure the link is talking about the same thing I am asking about, though it’s clearly related. The link talks about some trusted “certification authority” being necessary, whereas I thought there were ways to send coded messages which count as “public key encryption” methods in which no “trusted” go-between would be needed–in other words, in which A’s knowing B’s public key and B having a private key related mathematically to that public key were all that was needed for A to send B a coded message.

Maybe I am wrong to think that is possible, though, and the link describes public key encryption more accurately than I have described it. If that is the case, I am still interested in knowing just how it works… like, in terms of math and stuff…

-FrL-

4

What you are looking for is RSA. There are probably other public-key systems, but I am not familiar with them.

5

I used to understand the math easily… man I’m getting rusty.

6

There is a small-number example in the wiki article bitwise linked to. There’s a very good RSA description and small-number example in Schneier’s “Applied Cryptography” (which is a good place to look for any crypto explanation). In the Second Edition, the RSA example is in section 19.3.

There are several other good public-key algorithms, but RSA almost certainly has the widest use. ElGamal was fairly popular when RSA was encumbered by patent.