[plug] [semi-OT] Public/private keys?

[Craig Ringer]

> Yes, that's true. However, asymmetric encryption algorithms are selected
> to be such that trying to compute this inverse function would take
> billions or gazajillions of times longer than the other way around.
> As a very basic example, modern CPUs are very good at multiplying
> numbers together, but are very poor at division.

Its not so much that they're bad at division, they're bad at 
FACTORIZATION of large numbers. Its not just computers, either - the 
whole idea is that factorization is fundamentally harder than 
multiplication.

> You could employ an encryption algorithm that multiplies two numbers
> together, and to crack that encryption would require you to then divide
> the result to get the original numbers, which would take far longer.

Which is why one simple form of crypto involves taking your data, 
multiplying it by a damnn big prime number, and sending it to the 
recipient. They send it back multiplied by /another/ prime number, and 
then you divide by yours and send it back to them. Its inefficient but 
neither needs know the other's "key" and its a bastard to crack.

Also, in your message you write that:

 >I understand that encrypting a document with the
 >private key can only be decrypted by the matching
 >public key, and vice versa.

which is not quite accurate. One can encrypt a document using someone's 
public key, and it can then only be decrypted using the associated 
private key. It doesn't work in the opposite direction at all (if it did 
it wouldn't be crypto really). Sorry, might just be misunderstanding the 
  wording but best be sure.

Craig Ringer