As the title suggests, I am curious to know why you can't work backwards using a message, public key and encrypted message to work out how to decrypt the message!
I don't understand how a message can be encrypted using a key and then how you cannot work backwards to "undo" the encryption?
There are one-way functions in computer science (not mathematically proven, but you will be rich and famous if you prove otherwise). These functions are easy to solve one way but hard to reverse e.g. it is easy for you to compute 569 * 757 * 911 = 392397763 in a minute or two on a piece of paper. On the other if I gave you 392397763 and asked you to find the prime factors, you would have a very hard time. Now if these numbers are really big, even the fastest computer in the world will not be able to reverse the factorization in reasonable time.
In public-key cryptography these one-way functions are used in clever ways to allow somebody to use the public key to encrypt something, but making it very hard to decrypt the resulting message. You should read the Wiki article RSA cryptosystem.
Your question is a little like this (with apologies to Tom Stoppard): "why can I stir the jam into my rice pudding, but not stir it out again?"
Some mathematical operations are as easy to do backwards as forwards. For instance you can add 100 to a number as easily as subtracting 100. However, some are more difficult to reverse. For instance, if I take x and find g(x) = a(x^5)+b(x^4)+c(x^3)+d(x^2)+ex+f, I have to do merely simple multiplies and adds. But to get back from g(x) to x is difficult (in an algebraic manner) as there is no general algebraic solution to a quintic equation. It's not immediately obvious why that should be the case (as opposed to a quadratic equation), but it is. For a more appropriate example, if I told you that 34129 and 105319 were both prime (which they are) you would be able to quickly work out that their product was 3594432151. However, if I asked you to find the two prime factors of 3594432151, you'd probably find that rather harder.
Public key cryptography takes a pair of keys. In general, the private key provides the parameters a difficult to reverse algorithm going in one direction (e.g. plain text to cypher text), and the public key provides parameters for a difficult to reverse algorithm going in the other.
So, the reason you can't work backwards is simply because the algorithm is designed to make this hard.
Juggling is easy: you just throw the balls at the right time, so that you have a free hand when they fall. With one ball or two balls, this is trivial. With three, it is easy enough. With more balls, it (surprisingly) becomes harder. Even substantially harder.
In all generality, "reversing" encryption done using an n-bit key is like juggling with 2n balls. With a 2048-bit key this is like 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 balls. Or so.
(Of course, since public key algorithms use a lot of mathematical structure, smart minds have leveraged maths to reduce that number of balls to 162259276829213363391578010288128, which is considerably lower, but still way beyond the aggregate power of all existing computers on Earth.)
Max, the best tool ever created for thinking about cryptography is the Rubik's cube. If you presume a world where solving them is an unsolved problem, there are direct analogs for DiffieHellmanKeyExchange, RSA signing, RSA encryption, etc. You can play tricks with writing down moves and performing them on cubes and exchanging them; and the group theory equations are the same for the crypto and the rubiks cubes.
But the key thing to keep in mind, which I think is what must bother you: You are correct. It is "possible" to invert all of these operations. Technically, we have f(x) and f_inverse(x), where f(x) runs in polynomial time (ie: you can encrypt large numbers quickly), while f_inverse(x, s) runs in exponential time (ie: even medium numbers are infeasible) - unless you have the right secret s to plugin to f_inverse. Such function pairs are called trapdoors. The common trapdoors are number theory problems such as prime factorization and discrete logarithms.
What you need to do is read up on Public-Key Cryptography. The short answer is it is based on an algorithm that allows one key to encrypt and the other key to do the decryption, which is why you cannot work backwards.
That is a simplified explanation of what is happening, if you want to get to the heart of the issue you can look at sources such as the following, but be warned it quickly steps off the cliff into some mathematics that may or may not be easy for you to follow: http://nrich.maths.org/2200
In this public-key encryption (or assymetrical encription), to encrypt something, you do the following:
Take your message to be transmited (as a number) : let's say it's 5.
Calculate 3 ^ 5 (3 raised to the "secret") = 243
Calculate the modulus of it, divided by another number: let's say 143. So, 243 / 143 = 100.
There you go. Your encrypted secret is 100.
To find the secret, without the private key, you just need to find a number that when divided by 143 leaves 100 as result, and then find the cubic radix of it.
Generally you can't work backwards—in the obvious way—because you don't have enough information.
RSA depends on the difficulty of factoring large numbers. You generate your RSA modulus n by multiplying two large primes, p and q. Multiplying p by q is easy. You can also reverse the operation by computing q = n / p (or p = n / q). What you can't easily do is throw away both p and q, then compute them from n. That's a different problem, not a reversal of some process you've already used.
Similarly, RSA encryption of a message m using encryption key e involves computing (m ^ e) mod n. You could theoretically invert m ^ e using logs, but without the modulo operation, this number would be too big to work with. In any case, the modulo operation discards part of the number, so again you don't have all the information you would need to work backwards in a trivial way.
