Prove complexity bound without reduction? The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization in terms of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?
As mentioned on Wikipedia, there is no known proof that breaking RSA is at least as difficult as prime factorization -- and there are reasons to believe it might not be.  In other words, we don't currently expect any such proof to exist.  See the reference listed in Wikipedia.